Shuffle a deck, split it between two players, and play War, and the game can feel like it will never end. Sometimes it really doesn't. In the simplest version of the game, with one card of each rank, 312,707,435,743,775 of the 355,687,428,096,000 ways to deal 17 cards lead to a game that never ends: about 88 percent of them. This study counts the endless deals exactly for every deck of up to 17 cards, shows that some deck sizes can never loop at all, works out how long the loops last, and answers a question from 2010 about what kinds of endless game exist.
The game
There are n cards, numbered 1 to n, dealt alternately to two players, player 1 first. On each turn both players turn over their top card. The higher card wins, and the winner puts the winning card and then the losing card at the bottom of their own pile. A player who runs out of cards loses. All the cards are different, so there are no ties and no "battles". This is the version of War studied by Michael Spivey in a 2010 paper in the journal Integers.
Once the cards are dealt, nobody makes a decision. The deal decides everything: the game either ends, or it reaches a position it has seen before, and from then on it repeats forever.
The smallest endless game
Five cards are enough. Deal the deck 2, 5, 4, 1, 3: player 1 gets 2, 4 and 3, and player 2 gets 5 and 1, top card first. 5 beats 2, so player 2 puts the 5 and then the 2 under their pile. Then 4 beats 1, 5 beats 3, 4 beats 2, 5 beats 1 and 4 beats 3, and after those six turns both piles are exactly as they started. The game loops forever. Of the 120 ways to deal five cards, 30 end up in a six-turn loop like this one; the other 90 end.
How many deals never end
Write a(n) for the number of the n! ways to deal n cards whose game never ends. Before this study, the only published value was a(10) = 395,940, from Spivey, together with the zeros for decks of up to 4 cards and, from searches by Jean-Paul Delahaye and Philippe Mathieu, the zeros for 6, 8 and 12 cards. Spivey's third question asked for exactly this number, as a probability. We computed every value up to 17 cards, each one with at least two programs written independently of each other.
| Cards (n) | Deals that never end, a(n) | Share of all deals | Longest game that ends (turns) |
|---|---|---|---|
| 1 | 0 | 0% | 0 |
| 2 | 0 | 0% | 1 |
| 3 | 0 | 0% | 3 |
| 4 | 0 | 0% | 6 |
| 5 | 30 | 25.00% | 8 |
| 6 | 0 | 0% | 15 |
| 7 | 2,304 | 45.71% | 15 |
| 8 | 0 | 0% | 26 |
| 9 | 218,680 | 60.26% | 28 |
| 10 | 395,940 | 10.91% | 49 |
| 11 | 28,223,770 | 70.71% | 41 |
| 12 | 0 | 0% | 74 |
| 13 | 4,880,546,113 | 78.38% | 57 |
| 14 | 3,790,165,176 | 4.35% | 461 |
| 15 | 1,095,264,882,758 | 83.76% | 80 |
| 16 | 0 | 0% | not computed |
| 17 | 312,707,435,743,775 | 87.92% | 100 |
The odd and even decks behave differently. For an odd number of cards, from 5 on, the share of endless deals climbs steadily: 25.0 percent at 5 cards, then 45.7, 60.3, 70.7, 78.4 and 83.8 percent, and 87.9 percent at 17. For an even number of cards, up to 16, it is small or zero: 10.9 percent at 10 cards and 4.35 percent at 14. The largest value, a(17), meant playing every one of the 17! deals. Two separate GPU programs, using two different tests for detecting a loop, each played all of them, and they agree to the last digit.
Deck sizes that can never loop
Spivey proved that for every number of cards except possibly 2k and 3×2k (1, 2, 3, 4, 6, 8, 12, 16, 24, 32, and so on), some deal never ends. His second question asked whether those exceptional sizes have any loops at all. For every one of them up to 16 cards, the answer is no: every deal ends, and no position of the game, reachable from a deal or not, lies on a loop.
The search that shows this rests on one observation. The highest card never loses, so it never changes hands, and in a game that never ends it keeps coming back to the top of its owner's pile. Every loop therefore passes through a position with the highest card on top, and since swapping the players turns a loop into a loop, it is enough to check the positions where player 1 holds it. For 16 cards that is 19,615,115,520,000 positions, and none of them loops. Whether any larger deck of these sizes can loop is still open.
How long a loop lasts
For an odd number of cards the loops have a rigid structure, and their length can be written down exactly. Every loop repeats after lcm(n + 1, 2a, 2b) turns, where a and b are positive whole numbers with a + b = (n − 1)/2, and every such length occurs. For 13 cards the possible lengths are 42, 56 and 70, and nothing else.
The same structure makes it possible to count the loops without playing a single game. A position on a loop is a way of filling a fixed pattern of slots with the cards, and the number of loops follows from counting the orderings those slots allow. Counting a loop and the same loop with the players swapped as one, this gives 653,644,195,200 different loops for 19 cards, from the formula alone.
A new kind of endless game
Every loop Spivey constructed has the same rhythm: the two players take turns winning runs of the same length, a power of 2. His first question asked whether War has loops of any other kind. It does. The smallest deck with one has 14 cards. Of the 26,640 different loops of 14 cards, 720 are of the new kind, all of them 96 turns long, and 61,184,620 deals end in one of them.
Explicit families give loops of the new kind, reached from ordinary deals, for every deck of n = m×2v cards where m is at least 7 and one less than a multiple of 4, and v is at least 1: 14, 22, 28, 30, 38, 44 and 46 cards, and on from there. Spivey sorted the cards of a loop into categories by which cards beat them, and some of these loops have arbitrarily many categories. We conjecture that no other deck size has loops of the new kind.
The other way to collect cards
If the winner puts the losing card under their pile first and the winning card second, the counts change, but the zeros still follow a clean pattern. Up to 16 cards, the only deck sizes with no endless deal are the powers of 2: 1, 2, 4, 8 and 16. For 16 cards, no position loops at all. Spivey noted that for this rule a version of his construction gives loops for every deck size that is not a power of 2.
What entered the public record
The study adds two new sequences to the OEIS: A400411, the number of deals of n cards for which War never ends (now through 17 cards), and A400868, the same count when the losing card goes under first. The full paper, with every proof, is on Zenodo, and every program and the saved output of the runs behind every number are public, so each number on this page can be checked.
Questions
Can a game of War go on forever?
Yes. With one card of each rank and a fixed rule for collecting cards, some deals reach a position they have seen before and then repeat forever. The smallest deck where this happens has 5 cards: 30 of its 120 deals never end.
How likely is it that a game of War never ends?
It depends on the number of cards. For an odd number, from 5 on, the share of endless deals has grown with every deck up to 17: 25.0 percent at 5 cards and 87.9 percent at 17. For an even number of cards, up to 16, it is small or zero: 10.9 percent at 10 cards, 4.35 percent at 14, and none at all for 2, 4, 6, 8, 12 and 16 cards.
Can a real 52-card game of War last forever?
Nobody knows. In the real game, ties trigger battles, and whether every 52-card game has to end is still open. Delahaye and Mathieu built endless games for a 32-card deck under one rule for collecting cards, and their computer searches found none for 52 cards. This study works with the version that has no ties, where the answer for small decks is now known exactly.
What is OEIS A400411?
It is the sequence of the number of deals of n cards, numbered 1 to n, for which War never ends: 0, 0, 0, 0, 30, 0, 2304, 0, 218680, 395940, and so on, up to a(17) = 312707435743775. A400868 is the same count when the losing card goes under the winner's pile first.
Abstract
From the paper
In the card game War with one card of each rank, cards 1, …, n, the higher card wins each turn, and the winning card and then the losing card go under the winner's pile. Some deals never end. Let a(n) be the number of the n! deals of cards 1, …, n that never end. We compute a(n) exactly for n ≤ 17, each value with at least two independent programs. Before this, a(10) and the zeros for n ≤ 4 were known from Spivey, and the zeros at n = 6, 8, 12 from searches of all deals by Delahaye and Mathieu. The zeros fall exactly at n = 1, 2, 3, 4, 6, 8, 12, 16, the numbers of the form 2k or 3·2k. Spivey (2010) proved that every other n has endless games, and his Question 2 asks whether these n have any cycles at all. For each of these n up to 16, an exhaustive search of the positions in which one player holds the highest card on top finds no position of any kind on a cycle. For odd n we prove that every cycle has length lcm(n + 1, 2a, 2b) for some a, b ≥ 1 with a + b = (n − 1)/2. Cycles can also be counted without any search, as linear extensions of explicit partial orders. This gives all cycles for odd n, with a closed form when (n + 1)/2 is prime, and for every n the cycles of the type Spivey constructs. The length of every cycle of that type is divisible by n + 2v, where 2v is the largest power of 2 dividing n. Spivey's Question 1 asks whether War has cycles of other types than those constructed in the proof of his Theorem 3. It does. The smallest deck with one has 14 cards, and explicit families give such cycles, reached from ordinary deals, for every n = m·2v with m ≡ 3 (mod 4), m ≥ 7 and v ≥ 1. Some of them have arbitrarily many categories in the sense of Spivey's original definition. The values a(n)/n! answer Spivey's Question 3 for n ≤ 17. The sequence is A400411 in the OEIS, and the code and data are public.