Does War have infinite expected length? - MathOverflow

Does War have infinite expected length?

2010-01-12T04:58:10Z

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?

Answer by Ben Linowitz for Does War have infinite expected length?

2010-01-12T05:11:57Z

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

Answer by Kevin O'Bryant for Does War have infinite expected length?

2010-07-09T13:16:11Z

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.

Answer by Junkie for Does War have infinite expected length?

2010-07-09T15:37:17Z

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.

Answer by Evgeny Lakshtanov for Does War have infinite expected length?

2010-09-03T22:32:19Z

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

Answer by Evgeny Lakshtanov for Does War have infinite expected length?

2010-09-04T09:44:12Z

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:

By our assumption (players do not have strategy and do not have fixed rules how to return cards) the game is a Markov chain.
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.

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.

Answer by Evgeny Lakshtanov for Does War have infinite expected length?

2010-09-04T12:46:51Z

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?

Answer by Mike Spivey for Does War have infinite expected length?

2010-10-01T17:22:45Z

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.

Answer by Chris for Does War have infinite expected length?

2010-11-08T20:34:37Z

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.

Answer by Gil Kalai for Does War have infinite expected length?

2011-04-21T07:30:39Z

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.)

Answer by tim for Does War have infinite expected length?

2012-12-01T21:21:46Z

While playing a game of war on my pc, after sometime with 7 war between us (I won 3, lost 4), i began to notice patterns in the cards. So, I got out a paper & pencil and started writing down played combinations. Each of us had 26 cards and after the second roung of writing it all down they started repeating. Every two rounds, the same. What are the odds of this?