Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.

The question is: Is the expected length of the game infinite?

The Rules. (from http://en.wikipedia.org/wiki/War_(card_game)) The deck is divided evenly among the two players, giving each a face-down stack. In unison, each player reveals the top card on his stack (a "battle"), and the player with the higher card takes both the cards played and moves them to the bottom of his stack. If the two cards played are of equal value, each player lays down three face-down cards and a fourth card face-up (a "war"), and the higher-valued card wins all of the cards on the table, which are then added to the bottom of the player's stack. In the case of another tie, the war 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 as his face-up card and still have a chance to stay in the game.

Let us assume that the cards are returned to the deck in a well-defined manner. For example, in the order that the cards are played, with the previous round's winner's cards going first (and a first player selected for the opening battle).

On the Wikipedia page, they tabulate the results of 1 million simulated random games, reporting an average length game of 248 battles. But this does not actually answer the question, because it could be that there is a devious initial arrangement of the cards leading to a periodic game lasting forever. Since there are only finitely many shuffles, this devious shuffle will contribute infinitely to the Expected Value. Thus, the question really amounts to:

Question. Is there a devious shuffle in War, which leads to an infinitely long game?

Of course, the game described above is merely a special case of the more general game that might be called Universal War, played with N players using a deck of cards representing elements of a finite partial pre-order. Any strictly dominating card wins the trick; otherwise, there is war amongst the players whose cards were not strictly dominated. Does any instance of Universal War have infinite expected length?

-
If I read this correctly: esorensen.com/2009/10/26/the-science-of-war the "rules" for ordering make a big difference. He had 10% loops with the "player 1 always before player 2" and 0% with "biggest card before smaller" –  Junkie Jul 9 '10 at 20:32
Irrelevant, but your son's name is bad-ass. –  drvitek Sep 3 '10 at 23:07
Bjørn, I appreciate your attention to editing, but I don't think that game-theory is the right tag here. Perhaps you want to use combinatorial-game-theory, which I view as synonymous with theory-of-games. For example, I have heard Berlekamp describe his subject as the theory-of-games specifically in contrast to game-theory. –  Joel David Hamkins Sep 29 '10 at 16:35

9 Answers

Yes, a game of War can continue endlessly. In particular, if the following hands are dealt and player 1's cards are always added before player 2's cards to the bottom of the winner's stack, then the resulting game of War will never end:

Player 1: 10S JS KD 6C 6D 2S 7S AC 3S 8D 5C 5D 8H AD KH 2D 4S 7C 3H 3D 10C 4D KC 4H 6H 7D

Player 2: 9H 4C QC 9S 10D QH 5H QS 10H 8C AH 8S JH QD JD 2C KS 9D 3C 5S 6S 7H 9C AS JC 2H

-
That's great! But could you explain why? Also, your re-loading rules are slightly different from the ones I had mentioned. Can your shuffle be modified to accomodate that? –  Joel David Hamkins Jan 12 '10 at 5:17
The proof that this deal leads to a periodic game of War is by simulation. It's the example given in the 'Simulations of War using MATLAB' page cited on the Wikipedia page you linked to. –  Ben Linowitz Jan 12 '10 at 5:52
I know I've played games of War with my 7-year-old that felt endless. –  Kevin O'Bryant Jan 12 '10 at 9:59
@Kevin: I recommend the Math War variant. Each person plays two cards, and then use the product (or sum) for batttle. It's great arithmetic practice, and it seems that the kids can go forever with it. –  Joel David Hamkins Jan 12 '10 at 14:52
This is a great example. A more subtle question, and something a friend asked me several years ago: what is the probability that a games goes on forever? –  Matthew Kahle Jul 9 '10 at 13:51

This article (of Evgeny Lakshtanov and Vera Roshchina) purports that the answer is "the expected length of a game of War is finite". There is some ambiguity, as Joel notes, in the rules on Wikipedia; in particular, "the player with the higher card takes both the cards played and moves them to the bottom of his stack" is not specific enough. Does the highest card get moved first, or the lowest, or is it random? The Lakshtanov & Roshchina article uses random replacement.

They don't indicate the expected length, just its finiteness.

-
Great ! –  Joel David Hamkins Jul 9 '10 at 13:30
Moving the played cards to the bottom of the winner's stack in random order makes it much harder to retain a stable cyclic formation, so this result seems not at all surprising, and minimally informative about the answer for any variant without the randomness. –  Hugo van der Sanden Sep 4 '10 at 9:12
On the other hand the randomness assumption is a statistical one, therefore the proof may be informative in cases of, sufficiently defined, pseudorandomness. –  dakota Sep 5 '10 at 6:33
@Hugo: you're assuming that a stable cyclic formation is the way to have an infinite game. Here's another game to try the reasoning on: Pick a random rational (somehow), and then add it to itself until you get an integer. Variation: Pick a random rational, and then add it to your running total until you get an integer. In the variation, the randomness makes it much easier to have an infinite game. –  Kevin O'Bryant Sep 5 '10 at 13:52

Dear Joel David, I will try to explain it, but I have to note that article is quite primitive, and is written in a readable English. Moreover there are many figures. But I will try: I will make a list of statements and then You can mention the number of the non clear one:

1. By our assumption (players do not have strategy and do not have fixed rules how to return cards) the game is a Markov chain.

2. Absorbing (final) state is a state where you stay forever :) For us it means the end of the game i.e. the state when one of players has got all cards.

3A. In finite Markov chain, assuming arbitrary initial state, you are absorbed with probability ONE If And Only If "for each vertex of the Markov chain graph there is a way to an absorbing state."

3B. So we have to prove that for the graph of our game of war, there no exists such initial state that players do not have any chance to reach the end.

1. To prove it we should consider first the simplification. Consider the game with cards {1,...,n} i.e. every value meets only once.

We call a vertex attaining if it has got terminal states as its descendants, and wandering otherwise. It is obvious that a descendant of a wandering vertex is again wandering, and an ancestor of attaining is again attaining. For an arbitrary oriented graph it is possible that an attaining vertex has got wandering vertices among its descendants. We show that for our graph G it is not so. For that, we need to understand some properties of the graph G.

LEMMA 1. A: Let state be such that one of the players has got only one card in his hand, then this state has got exactly one ancestor.

B: If both players have got at least two cards, then this state has got exactly two ancestors.

LEMMA 2. For the graph of the game it holds that a descendant of an attaining vertex is again an attaining vertex. (Page 5 of the article)

Lemma 3. The states in which one of the players has got only one card are attaining. (page 6)

Lemma 4. Every vertex has got an ancestor that corresponds to the state in which one of the players has got only one card.

Therefore, we have shown that each vertex has got an ancestor that corresponds to the state in which each player has got exactly one card. This state is attaining by Lemma 3. By Lemma 2 descendants of attaining vertices are again attaining, therefore, the initial state is again attaining, and we have proved

Theorem: Graph G does not have any wandering vertices.

Now how to apply it to the standard GAME: We use the following obvious fact: If a subgraph of an oriented graph does not have wandering vertices, then the original graph does not have any wandering vertices either.

Now the proof is similar.

I hope it is better to read the article, I am sorry. and I want to note once more time, that question of strategy is never been discussed.

[Added by J.O'Rourke:] The paper has appeared: "On Finiteness in the Card Game of War," Evgeny Lakshtanov and Vera Roshchina, The American Mathematical Monthly, Vol. 119, No. 4 (April 2012) (pp. 318-323). JSTOR link.

-
Thank you very much for your further explanation, which helps me very much. (By the way, one can edit an answer, rather than posting a new answer, by clicking on 'edit'.) –  Joel David Hamkins Sep 4 '10 at 13:41
Unfortunately 'Edit' appears after my own posts only... :( In case if you are really understand the result of our article, may I ask You to find another words to comment post by Hugo van der Sanden? I have read that he is a professional programmer i.e. usually for his profession if something looks evident it is evident and people who try to find the proof are do nothing.... –  Evgeny Lakshtanov Sep 4 '10 at 15:08
Evgeny, you'll be able to edit when you get 100 reputation, at least on community wiki. –  Elizabeth S. Q. Goodman Dec 1 '10 at 7:03

My paper "Cycles in War" addresses this question, too. I was interested in characterizing the kinds of cycles that can occur. In other words, what does the structure of a cycle in War actually look like? I simplified the problem by assuming that wars are not possible (i.e., the cards have a strict ranking from 1 to n, where n is the number of cards in the deck). Even in this simpler version I found it difficult to characterize all of the cycles. However, in the case that the winning card goes to the bottom of the winning player's deck before the losing card, I was able to find a way to construct a deal of an $n$-card deck that cycles, for any $n$ that is not a power of 2 or three times a power of 2.

For example, the following deal of a 52-card deck cycles.


26 46  1  7  8 27  9 28 29 47  2 10 11 30 12 31 32 48  3 13 14 33 15 34 35 49

16 36 17 37 38 50  4 18 19 39 20 40 41 51  5 21 22 42 23 43 44 52  6 24 25 45


It takes over 30,000 battles for the deck to return to this ordering. The mathematical argument for why this deal cycles is in the paper, which has been accepted for publication by the journal Integers but has not appeared in print yet. Among other things, the re-loading rules do make a difference, as other people have already noted here. Also, given that characterizing cycle structures when wars are not possible turns out to be difficult (or, at least, I found it so), one should expect that characterizing cycles in the standard version of the game in which wars are possible would be even more difficult.

Edit: The paper has now been published on the Integers web site, in the games section, as Vol. 10, Article G2, 2010, pp. 747-764.

-
I just saw your article, and came here to post a link. Your paper ends with some very nice questions; some might go well in this space. –  Kevin O'Bryant Mar 10 '11 at 19:31
@Kevin: Thanks. Maybe I will ask some of the more general of those questions on here someday. :) –  Mike Spivey Mar 11 '11 at 0:29

Sorry to make this an answer, but the formatting needs specification.

Here is a stupid 8-card version of your rules, top player going first.

AD KH KS AC
KD AH AS KC


If I read your rules correctly, after one round it looks like:

AD KD KC AC
KH AH AS KS


and so on. These seems to generalise to 8n cards.

-
+1. Thank you very much! This is a good idea. I guess it shows that if we use a standard 52 card deck with 4 additional wild cards, then we can do it according to my reloading rules. –  Joel David Hamkins Jul 9 '10 at 18:05
My woeful further attempts at this do seem to indicate that there really is a parity problem in passing the turn back if you try this with odd*4 cards. In that case I think you need to hit the "WAR" stage in searching for a periodic loop. (Isn't the whole point of the game to yell "WAR" and then maybe "1-2-3-BOOM!" when the cards match?). –  Junkie Jul 9 '10 at 18:37
I think you can modify this to work with 52 cards. If you just take the first 2 rounds of your shuffle, it repeats with 4 cards. But a deck has 13 sets of 4 cards, and your first two rounds uses only half of 2 sets. So let's have 12 pairs like your first two rounds, using half the cards from 3 to Ace. Now make 12 more pairs using 2 through King. This leaves two 2s and two Aces, to make one more pair of rounds. –  Joel David Hamkins Jul 9 '10 at 18:37
"If you just take the first 2 rounds of your shuffle, it repeats with 4 cards." False! In fact, that's whole problem. After these two round, the SECOND player is now "on turn", and then plays K, taken by A, and then player 1 also plays K, taken by A, and we reach the silly stalemate as both now have KA. –  Junkie Jul 9 '10 at 20:12
Darn! You're right. I suppose this plan works if we use the top-player-first order for reloading the cards, as in Ben's answer. But this is better, sincee we can see easily how it works. –  Joel David Hamkins Jul 9 '10 at 21:19

I've always played war where the captured cards go into a pile which are shuffled before played again. In this case a war game will rarely go on forever.

One flaw in the rules is this, and I just played it with my daughter. I had 6 cards left, the next play were 2 kings (doesn't really matter) so we layed our cards down and we both turn up 3's another war. Now I have 1 card left, so I turn that over an 8 and my daughter plays another 3 and turns her card over an 8! So now I have no cards left and the last cards were played with 3 wars in a row! ?? What's the probability of that happening - should go out and buy a lottery ticket ...

Anyways I think the rules would call for the player with cards to continue to play another 3 and turn over to try to beat the 8 but I'm not sure, there's no rules for that so ... what's supposed to happen. In the meantime the game is at a stalling point.

Interesting statistics on the game though. Although it's mostly random the statistics are merely only for interest only.

-
I see! You are saying that there is another kind of stall. For example, if you have all the red cards and I have all the black cards, and our cards are ordered the same way, then we will have War on the first hand all the way until our cards are used up and it is a tie, before anyone has won a hand! –  Joel David Hamkins Nov 9 '10 at 0:32

We really just have proved that "final state can be reached from every state." The proof is of Euler style i.e. it is not a constructive proof. So we know nothing about the length of the game. We know that it is finite assuming that the players regularly use both possible ways of returning cards to their hand.

Another question is if there exists a strategy?

Evgeny Lakshtanov

-
I assume that you are the Lakshtanov mentioned in Kevin's answer; so I thank you very much for answering here! But could you explain your remark a bit more? –  Joel David Hamkins Sep 4 '10 at 1:24

Many years ago Amir Dembo and I looked at the expected length of a simple variant of the game of war. You have n cards labelled 1,..,n and you divide them at random. In each round the higher card wins. In this version there are "battles" but no "wars" and the identity of the winner is determined in advance as the player having 'n'. We were able to estimate the expected length of this game as propotional to $n^2log n$ but not the precise constant. (Note that there are still some possible variants regarding what to do when you run out of your pack.)

-
On May 30 2011, "luckylak" asked (in an answer now deleted) for a reference to the article, and wants to know whether it was Monte-Carlo or rigorous analysis. –  S. Carnahan Nov 7 '12 at 7:25

I have not possibility to answer at the right place to this post by Hugo van der Sanden:

Moving the played cards to the bottom of the winner's stack in random order makes it much harder to retain a stable cyclic formation, so this result seems not at all surprising, and minimally informative about the answer for any variant without the randomness

As I already wrote it several times here, our result means that end of the game can be reached from any state. In other case randomness does not help you to finish the game. Is it clear?

-