Analyzing a modified version of the card-game "War"

A simple game usually played by children, the game of War is played by two people using a standard deck of 52 playing cards. Initially, the deck is shuffled and all cards are dealt two the two players, so that each have 26 random cards in a random order. We will assume that players are allowed to examine (but not change) both decks, so that each player knows the cards and orders of cards in both decks. This is typically note done in practice, but would not change anything about how the game is played, and helps keep this version of the question completely deterministic.

Then, players reveal the top-most cards from their respective decks. The player who reveals the larger card (according to the usual order: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace) wins the round, placing first his card (the high card) at the bottom of his deck, and then his opponent's card (the low card) at the bottom of the deck (typically, the order of this isn't enforced, but to keep the first version of this question deterministic, such an ordering will be enforced).

In the event of a tie, each player reveals four additional cards from the top of their decks. If the fourth card shown by one player is higher than the fourth card shown by another player, the player with the higher fourth card wins all cards played during the tie-breaker, in which case the winner's cards are first placed at the bottom of the winner's deck (in first-in, first-out order; in other words, older cards are placed at the bottom first), followed by the loser's cards (in the same order).

In the event of subsequent ties, the process is repeated until a winner of the tie is determined. If one player runs out of cards and cannot continue breaking the tie, the player who still has cards is declared the winner. If both players run out cards to play at the same time the game is declared a tie.

Rounds are played until one player runs out of cards (i.e., has no more cards in his deck), at which point the player who st

If I understand correctly, all information about the game is available to both players. That is, the starting configuration and all of the possible moves are known by both players (mainly because both players can look at the cards of the other player). This makes game is a zero-sum game of perfect information. Thus there exists is a perfect strategy available to both players that would achieve the best outcome in each game for that player. This was proven in 1912 by the German mathematician Ernst Zermelo.

I do not know what the strategy is, but one could imagine building a big game tree for it and getting a computer to find the strategy for me using the min-max algorithm.

The tree for each game would have as root the hands of the two players. The branches in the tree corresponds to the moves of the players. In the simplest case, these consist of simply laying down the requisite cards. In the more advanced cases, the 'trump' move can be made. Internal nodes of the tree record what the current configuration of cards is along with any information about the state wrt 'trumps'. The leaves of the tree correspond to the end game positions, which will be labelled with, say, +1 for a win to Player 1, 0 for a tie, and -1 for a win to Player 2. Ignore looping games for now.

Now the min-max algorithm will work as follows (from Player 1's perspective). Assume that it looks at a node where Player 1 makes a move and that the nodes below are annotated with a +1, 0, or -1 (the payoff) along with the choices the player needs to make to get the given result. Player 1 simply selects the node with the largest payoff, records that payoff and the choice required to get that. For the node where Player 2 is making the move, the node with the minimum payoff is chosen, and the choice is recorded. This reflects that Player 2 is aiming for the lowest score to win. This is propagated to the of the tree. The choices recorded at each node correspond correspond to the best strategy a player can make. The final payoff determines who wins. This is ultimately a function in terms of the payoff, though the exact choice of moves may vary.

Potentially looping configurations can be incorporated into the game tree by simply adding loops that return to an already seen configuration (when computing from the top). For such nodes you take the greatest fixed point if it is a node where Player 1 plays and the least fixed point when Player 2 plays.

Note that if you had not made the assumption that both players could examine both decks, then this approach would not apply. The game would then involve chance and the selected strategy would be game specific.

Whether or not there is a strong or weak winning strategy for one of the players depends on the outcome of the min-max algorithm applied to all trees. But there sure are a lot of them .... Computing the tree for one is probably fairly easy, since there are not very many choices made through the game.

StackExchange Computer Science Q#248, answer score: 7