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:
- Frequency-War: Players may only trump if they have not trumped in the previous $k$ rounds.
- 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:
- 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?
- 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?
- 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).