19
$\begingroup$

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,[1] 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.[2] 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$.[3] 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.[4]
  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.


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

[2] 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.

[3] 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))}.

[4] 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.

$\endgroup$
  • 2
    $\begingroup$ related question: mathoverflow.net/questions/11503/… $\endgroup$ – Rus May Apr 21 '16 at 16:30
  • 1
    $\begingroup$ 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 $\endgroup$ – marty cohen Apr 22 '16 at 5:27
  • $\begingroup$ 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. $\endgroup$ – Axoren Jun 7 '16 at 6:47
  • $\begingroup$ 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? $\endgroup$ – joriki Jun 7 '16 at 7:06
  • 1
    $\begingroup$ @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.) $\endgroup$ – msh210 Jun 9 '16 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.