26
$\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$
9
  • 3
    $\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$ 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
0
$\begingroup$

According to the rules I used, when there is a tie, each player displays only 1 cards. If one of the two cards is higher than the other one, then the player that showed it wins all four cards (the two cards of the tie and the new two cards); if there is another tie, the players keep showing one card at a time, until there is no tie or one of the two players ends his deck.

It seems to me that with these rules I proposed, what really matters is the number of Aces (the highest card) in each deck. When a player has all 4 Aces in his deck, we can say that he will eventually win.

  1. A rule of thumb about when to end the game (which me and my friends actually used when we played this version of "War") is that when we become aware that one of the two players has all 4 Aces, then the game can be ended.

  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).

I hope these remarks are helpful.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.