When I was a kid, one of my favorite card games was War. In retrospect, I don’t really understand why I got so much enjoyment out of it, given that there is absolutely no strategy to the game whatsoever. If you happened to miss this game during your childhood, the rules are simple:

The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the process is repeated until there is no tie.

A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck face-up and still have a chance to stay in the game.

As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.

The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.

It turns out that the answer is “about 277” (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.

The vital step to the game turns out to be re-integrating your captured cards back into your active deck. If this re-integration is entirely deterministic, the progress and outcome of the game is completely determined by the initial deal. However, as is mentioned on any page discussing War simulation, if the re-integration is deterministic, it can (and with surprising frequency does) lead to games of War which will never terminate.

There are essentially three major non-deterministic ways to re-integrate captured cards into the active deck:

1. Add the captured cards to the bottom of the active deck in random order
2. Add the captured cards to random positions in the active deck
3. Pool the captured cards in a “capture deck” until the active deck is empty, then shuffle the capture deck, and make it the new active deck.

When I used to play War, I played using method 3, and I’m not sure anyone actually uses method 2 (it would be very prone to bias and deliberate cheating in the hands of a human rather than a simulation), but it is interesting to think about. I’ll refer to 1 as Standard War, 2 as Continuous-Shuffle War, and 3 as Pooled-Capture War.

It turns out that, regardless of the re-integration method, a game of war can be accurately and completely modeled as a Markov chain. This isn’t actually all that surprising. A Markov chain is really just a technical name for a series of states where the next event depends probabilistically only on the previous state and no states prior to that. Since children’s games often intentionally minimize strategy and state memory, it turns out that several well-known and popular children’s games are in fact nothing more than brightly-colored Markov chains; for example, Candyland, Chutes and Ladders, and Hi-Ho Cherry-O. War stands out among these, though, because the state space for War is absolutely enormous.

The smallest state space belongs to Continuous-Shuffle War. In this game, a state can be uniquely identified by specifying which player has which cards. Order is irrelevant. Therefore, the number of possible states is where the brace notation in within the sum denotes a Stirling number of the second kind, with parameters the number of cards, and the number of players. This is just shorthand for asking “How many different ways can we divide items into non-empty groups?” The factor of is there because Stirling number does not take order into account, and in this game two states where the players’ decks are swapped around are not equivalent. The sum is necessary because Stirling numbers of the second kind only count divisions into non-empty groups, and so we have to account for a -player game devolving into a -player game when one player runs out of cards. The exists to take into account which players have run out of cards in a reduced game. The additional is for the number of finishing states in which one player has all the cards. How many states are there in this chain, then? For a typical game with a 52-card deck and 2 players, there are 4 503 599 627 370 496.

Next, there is Pooled-Capture War. Here, we still don’t have to concern ourselves with order, but each player essentially maintains two decks – the active deck and the capture deck. The reason we don’t concern ourselves with order is that the active deck is always essentially drawn from in random order, owing to the fact that the player plays repeatedly plays through an entire freshly-shuffled active deck, rather than adding cards to the active deck as he goes. In this case, there is really no difference between shuffling the capture deck when it becomes active, and drawing from the active deck at random. Therefore the number of states for Pooled-Capture War is almost the same as for four-player Continuous-Shuffle War, but not quite. The difference is that since each player has two decks, the number of finishing states increases from to , because when one player has all the cards, they can be divided between the active and capture decks in different ways. Therefore, the number of possible states in Pooled-Capture War is . For a typical game, this works out to 1 690 198 646 610 354 052 103 573 055 990 states.

Finally, for Standard War, a state can only be uniquely identified by specifying the active decks of both players, where order is this time relevant. This means that the total number of states is expressed as a sum of of all possible permutations of hands over the different quantities of cards each player might have. In other words,

(If anyone can think of a more compact way to write this, please let me know.) This formula essentially takes all choices of how to assign cards to players, and then sums the distinct permutations within each of these possibilities. This works out to right around 164 548 210 943 005 434 162 687 272 511 830 757 530 229 530 638 988 932 546 560 000 000 000 distinct states for a typical game.

In order to work out the answer to my initial question of the expected number of rounds in a game of War and other mathematical questions about War, the approach would be to compute a transition table where cell answers the question: Given that you are now in state , what is the probability that after the next turn you will be in state ? The difficulty of working out this table is easiest for Standard War, and hardest for Pooled-Capture War.

In Standard War, we know based on the state alone which cards will be played, and therefore exactly what the result of the upcoming turn will be. Probability only comes into play when deciding in what order the captured cards will be added to the winner’s deck. This probability is also simple; each integration order is equally likely, and so has probability where is the number of cards captured. The number of states that you can reach in any one turn is relatively small, and so the matrix for Standard War, while huge, is very sparse.

In Continuous-Shuffle War, we don’t know which cards will be played just by inspecting the state. This isn’t by itself that complicating since we can assume each player will draw from their cards with equal probability of drawing any given card. The complicating factor is that because “wars” can go on for an arbitrary number of draws, any given state can reach almost any other state in a single turn, albeit with very small probability for most of them. Still, since these probabilities are nonzero, the smaller matrix for Continuous-Shuffle War is very densely populated.

In Pooled-Capture War, we have all the problems of Continuous-Shuffle War, plus when computing the probabilities, one has to deal with the fact that the capture deck can become the active deck in the middle of a turn. This doesn’t make the matrix any more densely populated, but it does severely complicate the probability calculation algorithm.

Were we able to compute , we could answer my original question in this manner: In a Markov chain, the th power of , , gives the transition probabilities of ending up in particular states after turns. We then compose a begin row-vector where probabilities are distributed uniformly among the states which could correspond to an initial deal. Then, for each turn , we can compute and add up the probabilities of all final states to get , the probability that the game has ended by turn . The expected number of turns the game will last is then . We could also use vectors that specify a single particular initial deal to compute the probabilities that each player will win, given that initial deal.

However, my conclusion after thinking all of this through is that it probably isn’t worth it to try to write a program to compute these kinds of things. The time required to iterate through the states of any of these methods, let alone the space required for (which has size the square of the number of states, times the size of the datatype used to store the probability value), makes this endeavor completely intractable for all but pathetically small decks of cards (around 10 or so). I figure that while the simulation-discovered answer of 277 is somewhat less accurate than a probabilistically computed answer would be, it’s likely to be accurate enough for any future application of this information.

(Thanks to Wolfram Alpha for making possible the giant scary numbers in this post.)

Share this content on: