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?
Best Answer
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