Consider a standard, two-player, 52-card game of War. If I start with just the four aces, and you start with all 48 other cards, randomly shuffled, what are your chances of winning?
Solution
Rules for this game vary and are often incompletely specified. I will assume that cards played in a “war” are shuffled before being returned to the bottom of the deck of the player who wins them.
The Python code below does a ten-million-run Monte Carlo simulation of the game, and the percentages of victories for the all-aces player, assuming one, two, and three cards are played face-down in wars, respectively, are 80.9%, 71.7%, and 65.5%.
For the one-face-down-card version of the game, there is an interesting pattern in the frequencies of the possible game-lengths, where a game’s length is its number of rounds, and where a round is considered to conclude when a player wins cards.
Inspection reveals that the chart columns for odd game lengths form a curve well below the higher curve formed by the even ones. This means that even game-lengths are observed much more frequently (about five times as often) as odd game-lengths. A good puzzle is: why should that be? Give it a think, or read on for what I believe is the answer.
Why
Say that a game after R completed rounds is an “even state” if R plus the number of cards in the loser’s deck is even. All games start in an even state, and a game lasts an even number of rounds iff it ends in an even state. Non-war rounds preserve the evenness of the game-state, since R increases by 1 and the loser either gains or loses 1 card. And so do decided war-rounds, because R increases by 1 and the loser’s cards increase or decrease by an odd number. Therefore a game can only exit an even state by the loser having one too few cards to play a battle (and thus losing the game). About 1 in 6 games end in that way, and only these games last oddly many rounds.
Code
# Attempted solution of Riddler at https://fivethirtyeight.com/features/riddler-nation-goes-to-war/
from random import shuffle
# Play the next cards and break any ties. Return True if
# there are more cards to play.
def PlayContinues():
global MyDeck,YourDeck,GameResult,CardsDown,Rep
# The Pot is a list of all the cards at play in the round
Pot = []
while True:
MyCard = MyDeck.pop()
YourCard = YourDeck.pop()
Pot.extend([MyCard,YourCard])
shuffle(Pot)
if MyCard > YourCard:
MyDeck = Pot + MyDeck
if len(YourDeck) == 0:
# GameResult: 1 if win, 2 if I don't win, and
# 0 if game continues.
GameResult = 1
else:
GameResult = 0
break
elif YourCard > MyCard:
YourDeck = Pot + YourDeck
if len(MyDeck) == 0:
GameResult = 2
else:
GameResult = 0
break
else:
# A tie (war).
if len(MyDeck) < 1 + CardsDown:
# I don't have enough cards to play a tiebreak
if len(YourDeck) < 1 + CardsDown:
# And neither do you. Start the game from scratch.
Rep -= 1
GameResult = 2
break
elif len(YourDeck) < 1 + CardsDown:
GameResult = 1
break
else:
# Play the tie-break, by first laying down the face-down
# cards and then continuing the "while True" loop
for _ in range(CardsDown):
Pot.extend([MyDeck.pop(),YourDeck.pop()])
return (GameResult == 0)
# You have four of every number from 0 to 11, while I have just four 12s
# Global parameters
# Ten million reps take less than ten minutes when this
# is run with PyPy (much faster than stock Python).
Reps = 10000000
# How many cards go face-down in a tie-break?
CardsDown = 1
# Main loop
YourCards = [n/4 for n in range(48)]
# For normal, fair-deal War uncomment the next line.
#Deck = [n/4 for n in range(52)]
MyWins = 0
GamesWithNRounds = [0]*8000
LengthAccum = 0
for Rep in range(Reps):
MyDeck = [12]*4
shuffle(MyDeck)
YourDeck = list(YourCards)
shuffle(YourDeck)
# For normal, fair-deal War, comment the previous three
# and uncomment next three lines.
# shuffle(Deck)
# MyDeck = Deck[:26]
# YourDeck = Deck[26:]
Rounds = 1
while PlayContinues():
Rounds += 1
GamesWithNRounds[Rounds] += 1
LengthAccum += Rounds
if GameResult == 1:
MyWins += 1
print "WinRate, GameLength:", 1.0*MyWins/Reps, 1.0*LengthAccum/Reps
# Uncomment below for plottable list of frequencies of round lengths
#for i in range(1,4000):
# print 1.0*GamesWithNRounds[i]/Reps