# When can we quit a game of War?

Consider the game of War. (The rules are below.) It would be nice to be able to end the game early. Suppose, for example, one player has 50 of the 52 cards. It is very likely that he's going to win. Without knowing what's in his hand, can we say how likely it is that he's going to win? More generally, what is the likelihood of a win for a player once he has $n$ of the 52 cards?

I'm looking for a formula. However, I ran a simulation, and will share the results in case it helps someone find a formula (and for general interest). I used war.pl (from version 1.45 of the Games::Cards Perl module) to play 1,000,000 games of war. For each ($i$th) game, I noted the greatest number $m_i$ of cards held by the loser at any time during the game. Then, for each integer $n\in[27,52]$, I found the number $w$ of games for which $m_i<n$. Those results are:

cards n   games w
27    117488
28    202416
29    280208
30    332080
31    396849
32    439204
33    502378
34    536453
35    594499
36    621622
37    675878
38    697617
39    747468
40    764932
41    811182
42    825481
43    867215
44    878880
45    917070
46    925920
47    959246
48    965522
49    987942
50    989722
51    999968
52   1000000


Rules of War:

1. You start with a standard 52-card deck, shuffled, and two players.
2. Distribute 26 cards to each player.
3. Start of a round: Each player displays his top card; the higher rank wins the round, and proceed to the "Disposition of a round" step. If there's a tie, proceed to the next step:
4. Each player displays four more cards off the top. Among the respective last cards displayed by each player, the higher rank wins the round, and proceed to the "Disposition of a round" step. If there's a tie, repeat this step.
5. If a player has run out of cards, his last card is always the one to compare to the other player's, no matter how many times the other player displays four more cards.
6. If both players have run out of cards and there's a tie, the game is over: it's a draw.
7. Disposition of a round: The winner of the round takes all the cards that have played this round and puts them at the bottom of his set of cards. Note the ambiguity in this last step — I haven't said what order the player should take them in. Indeed, in my experience playing War, there is no rule, and each player can do what he wants, including taking them in differing orders during different rounds. For the purposes of this question, I'd be happy with an answer that answers the question according to any rule of your choosing.

I don't know what rules war.pl uses (I didn't trace through its dependencies), and you should feel free to use those rules instead of my own.

 This is unlikely, but let's assume it anyway.

 I edited the script to not give up after any finite number of turns, but every game ended anyway. I also edited it so it would give me the information noted in the text above. (See the next footnote.) But I didn't change the rules it used for the game.

 In case anyone is wondering (or finds a bug), here's the script I used. To war.pl I added the line map {$size[$_] = $Hands[$_]->size if $size[$_] < $Hands[$_]->size} keys @Hands to the start of each turn and print $size[$other[$winner]] to sub win. Then in a separate script I collected the$m_i$s by for (1..1_000_000) {my$score = perl war.pl; $scores{$score}++;} and displayed the $w$s by $\=$/;for my $score (sort{$a<=>$b} keys %scores) {print (($score+1) . ' ' . ((sum0 map { ($_<=$score) * $scores{$_} } keys %scores) / sum0 values %scores))}.

 I made that rule up for the purposes of this question, so the game is well defined. I don't think it has ever actually come up in my years of playing War, and I don't know what I would do if it did. If you prefer to use a different rule in answering this question, by all means do so.

• related question: mathoverflow.net/questions/11503/… Apr 21 '16 at 16:30
• Based on extreme ignorance, and having read about it many years ago in Feller, this makes me think of the arcsine distribution: en.wikipedia.org/wiki/Arcsine_distribution Apr 22 '16 at 5:27
• The only way for both players to run out of cards is for them to start with the same number of cards and a "war" occurs (tied cards) repeatedly until both decks are empty. This means there must be a war at 1, 5, 9, 13, 17, 21, and 25 and then reveal their last two cards and tie on the 27th play. That's only a total of 8 ties in a row. That draw case, while rare in practice, is actually a relatively frequent possibility. Jun 7 '16 at 6:47
• Do I understand correctly that you're interested not in the probability for a player uniformly randomly dealt $n$ cards to win, but in the conditional probability of a player uniformly randomly dealt $26$ cards to win given that at some point in the game she has $n$ cards? Jun 7 '16 at 7:06
• @joriki, well, I really want the conditional probability $f(n)$ of a player uniformly randomly dealt 26 cards to win, given that at some point in the game he has $n$ cards and his opponent did not previously have that many. (That way, we can stop the game when a player has $n$ cards, and can say we're $f(n)$ sure that that player will win.) Jun 9 '16 at 19:45

2. A lower bound of the winning probability having $$n$$ cards can thus be obtained computing the probability of having all 4 Aces in $$n$$ cards.
3. To have a better estimate, one could consider a Markov chain where the state is given by the couple $$(n,k)$$, where k is the number of Aces in a player's deck. For instance, one could manage to estimate what is the probability of eventually catching the fourth Ace, when having already three of them (and the complementary probability of losing one).