Analyzing a modified version of the card-game “War”

Question

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 still has cards is declared the winner.

As the game has been described so far, neither skill nor luck is involved in determining the outcome. Since there are a finite number of permutations of 52 cards, there are a finite number of ways in which the decks may be initially dealt, and it follows that (since the only state information in the game is the current state of both players' decks) the outcome of each game configuration can be decided a priori. Certainly, it is possibly to win the game of War, and by the same token, to lose it. We also leave open the possibility that a game of War might result in a Tie or in an infinite loop; for the completely deterministic version described above, such may or may not be the case.

Several variations of the game which attempt to make it more interesting (and no, not all involve making it into a drinking game). One way which I have thought of to make the game more interesting is to allow players to declare automatic "trumps" at certain rounds. At each round, either player (or both players) may declare "trump". If one player declares "trump", that player wins the round regardless of the cards being played. If both players declare "trump", then the round is treated as a tie, and play continues accordingly.

One can imagine a variety of rules limiting players' ability to trump (unlimited trumping would always result in a Tie game, as players would trump every turn). I propose two versions (just off the top of my head; more interesting versions along these lines are probably possible) of War based on this idea but using different trump limiting mechanisms:

1. Frequency-War: Players may only trump if they have not trumped in the previous $k$ rounds.
2. Revenge-War: Players may only trump if they have not won a round in the previous $k$ rounds.

Now for the questions, which apply to each of the versions described above:

1. Is there a strategy such that, for some set of possible initial game configurations, the player using it always wins (strongly winning strategy)? If so, what is this strategy? If not, why not?
2. Is there a strategy such that, for some set of possible initial game configurations, the player using it can always win or force a tie (winning strategy)? If so, what is this strategy? If not, why not?
3. Are their initial game configurations such that there is no winning strategy (i.e., a player using any fixed strategy $S$ can always be defeated by a player using fixed strategy $S'$)? If so, what are they, and explain?

To be clear, I am thinking of a "strategy" as a fixed algorithm which determines at what rounds the player using the strategy should trump. For instance, the algorithm "trump whenever you can" is a strategy, and an algorithm (a heuristic algorithm). Another way of what I'm asking is this:

Are there any good (or provably optimal) heuristics for playing these games?

References to analyses of such games are appreciated (I am unaware of any analysis of this version of War, or of essentially equivalent games). Results for any $k$ are interesting and appreciated (note that, in both cases, $k=0$ leads to unlimited trumping, which I have already discussed).

Answer 1

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.