Four Aces Against The Deck

The Riddler Express for September 8, 2017 was a participatory War-deck design tournament with no derivable optimum, so it is omitted here. The Classic is below.

Riddler Classic

In a standard, two-player, $52$-card game of War, you start with just the four aces and your opponent starts with the other $48$ cards, randomly shuffled. What are your opponent’s chances of winning?

The Riddler, FiveThirtyEight, September 8, 2017(original post)

Solution

In War both players flip the top card of their deck; the higher rank wins both cards. If the two cards tie, a war ensues: each player puts one card face down and then one face up, and the higher of the two face-up cards wins all six. If a player cannot complete a war (fewer than two cards left), they lose. Won cards are gathered back to the bottom of the winner’s deck after the round. Aces are the highest rank.

Starting with all four aces looks like an unbeatable advantage, since no single card can beat an ace head-to-head. The trick is the war. Suppose your opponent flips a five and you flip one of your aces; you win the trade and take both cards. Later, when that five comes around in your deck, it can tie an opponent’s five and trigger a war. In the war you place one card face down, and if that card happens to be one of your aces it goes to the opponent if the face-up comparison goes against you. Lose enough aces this way and the opponent can take you out.

There is no clean closed form here. Once a war starts, the chance that you sacrifice an ace face-down depends on the current contents of your deck, which in turn depends on the entire history of the play. The Solution is the rigorous setup just given, and the headline number is the result of an honest Monte Carlo of the actual experiment, reported in the next section.

$$\boxed{\,\Pr(\text{opponent wins with the }48\text{ cards}) \approx 19\%.\,}$$

A few sanity checks. The opponent’s only hope is to convert wars into ace captures, so games tend to swing late and decisively rather than gradually. Once the opponent loses two aces in wars, they almost always finish the rout; once you lose two aces, you almost always do. The $19\%$ figure is moderately robust to the small rule variations that crop up in different copies of the game (one or two cards face-down, whether tied face-up cards trigger a further war, whether won cards are shuffled or kept in order); the simulation below uses the most common American rules, and other versions move the number by a percentage point or two.

The computation

Simulate the actual game. Each round flips two top cards; if they match, run a war by placing one face-down card from each side and then a face-up comparison, repeating wars on further ties. A player who cannot complete a war (fewer than two cards left) loses immediately. The pile of table cards goes to the bottom of the winner’s deck, shuffled.

1. Set up: you hold $4$ aces; the opponent holds $4$ each of ranks $2$ through king, shuffled.

2. Each round: pop the top card from each deck and compare. If unequal, the higher rank wins all cards on the table. If equal, recurse: each side places one face-down card and one face-up card; compare face-up cards, repeating if they tie.

3. If a side runs out of cards mid-war, the other side wins.

4. Otherwise the round resolves with all table cards shuffled and placed at the bottom of the winner’s deck.

5. Play until one deck is empty; record the winner.

6. Repeat over many trials and report the opponent’s winning frequency.

import random

def play_war(seed):
    rng = random.Random(seed)
    you = [14] * 4                               # four aces
    opp = []
    for r in range(2, 14):                       # ranks 2..K
        opp += [r] * 4
    rng.shuffle(opp)
    turns = 0
    while you and opp and turns < 20000:
        turns += 1
        table = []
        a, b = you.pop(0), opp.pop(0)
        table += [a, b]
        while a == b:
            if len(you) < 2: return "opp"
            if len(opp) < 2: return "you"
            ad, bd = you.pop(0), opp.pop(0)      # face-down
            a, b = you.pop(0), opp.pop(0)        # face-up
            table += [ad, bd, a, b]
        winner = "you" if a > b else "opp"
        rng.shuffle(table)
        (you if winner == "you" else opp).extend(table)
    if you and not opp: return "you"
    if opp and not you: return "opp"
    return "draw"

N = 200_000
opp_wins = sum(play_war(s) == "opp" for s in range(N))
print(round(opp_wins / N, 4))                    # ~0.191

The frequency clusters around $0.19$, in agreement with the boxed estimate.