8

In the card game War you deal a standard 52 card deck between two players. The players than flip cards with the higher card winning. In the case of ties (wars), each player plays N additional cards an the player with the highest Nth card wins all the cards (subsequent ties follow the same rules). The game can last a very long time and seems to never last a short time.

What is the expected number of "turns" until the game is completed?

I learned to play war with N equal to 3 (i.e., a total of 10 cards are played in a war: the original tie, 3 face down, and a final comparison card).

For completeness assume the game is over if a player has less than 5 cards and gets into a war (i.e., does not have a final card to flip).

Assume that upon playing your last card from your hand, you shuffle the winning cards into a random order and resume.

Assume the cards are in random order to start.

6
  • According to the Wikipedia article you linked, both players play two addition cards, not four. The winner then takes all four (2*2) cards.
    – Phil
    Dec 3 '18 at 16:34
  • Also, it would depend on how the captured cards are returned to the winner's deck. If they are just placed in bottom of the deck, then that might affect the answer to the question. Furthermore, if the 52 cards are divided perfectly into two identical piles, I would assume that the game ends in a tie? Would that count as the game being completed?
    – Phil
    Dec 3 '18 at 16:37
  • @Phil you are correct, not how I grew up playing and not how my son learned from friends, but okay. Will update.
    – StrongBad
    Dec 3 '18 at 16:37
  • @Phil does the edit cover everything?
    – StrongBad
    Dec 3 '18 at 16:42
  • 2
    This might be a better question for the math forum, as they tend to be better at complicated probability questions. Dec 3 '18 at 20:31
11

War is actually not a game but an Automata, as players don't have any options.

Wimpy Programmer already made this simulation, he found that when shuffling the winning cards, the mean number of turns is 262, the mode is 84, and the max (on a sample of 100,000 trials) is 2,702 turns. He also found that without shuffles of the winning cards, the game might be endless.

He used N=2 while you play with N=3, higher N shortens the game, however I don't think that it will make a big difference.

turns of war untill someone wins (thousand)

2
  • There must be a bug in this simulation, since it finds that 1 in 8 games lasts beyond 5,000 turns, possibly infinite. This has never been the case for me in reality, and I play without shuffling the cards I replace.
    – Noumenon
    Jul 28 '19 at 14:55
  • 1
    It might be a bug in the simulation (the code is in the link) however, i can think of other explanations: maybe you play with N !=2, maybe when playing in reality there is some unintended shuffling.
    – Cohensius
    Jul 29 '19 at 6:00
4

As a math problem, this is a case of a random walk ("walking" N cards at a step from your opponent's deck to your deck, where N is usually one, but can be 4 or 7 or whatever depending on ties.) It is often framed as the "gamblers ruin" problem. Ignoring the issue of ties and treating each throw of cards as an independent trial, the average number of turns is 26*26 = 676 turns.

Factoring in ties would reduce it quite a bit based on N -- allowing for bigger steps occasionally. The average number of turns when the step size is 5 (i.e., every turn is a war that is resolved on its first tiebreak) is equivalent to playing with 6 cards each (26/5, rounded up). And 6*6 = 36 turns.

So then it's just a matter of figuring out the probability of big steps. Ties can be expected about 3/51 of the time (when you play a card, there are 3 cards that can tie it out of the 51 other cards). 48/51 = step size 1, 3/51 * 46/49 = step size 5, 3/51 * 3/49 * 44/47 = step size 9, and so on. This makes an average step size of about 1.25. A game played with all steps equal to 1.25 would be expected to last about 21*21 = 441 turns (26/1.25 = 21 cards each equiv). And then reduce that some more to factor in the chance for sudden death when one of the ties occurs when a player is low on cards. (Sorry I don't have the details on how to do that exactly.)

EDIT: I should also emphasize that this approach assumes the trials are independent trials. That's basically the difference between dice and cards. Each throw of a die is independent. But each draw is not -- it depends on what else has been drawn / what else remains. And in the case of War, winning a trial in general improves your odds on the Kth following draw (when you draw that card again). It's a very mild (IMO) runaway leader effect (mitigated by also receiving the losing card, but I still think the net is a gain). And it will multiply the advantage, if any, bestowed to one player over the other in the initial deal. That is, any slight deviation toward the higher-numbered cards in the initial deal will be amplified each successive trip through the deck.

Further reading:

Simple Random Walk: http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf

First Passage of a One-Dimensional Random Walker https://www.math.ucdavis.edu/~tracy/courses/math135A/UsefullCourseMaterial/firstPassage.pdf

2

Well, from that same link you shared, on the summary table on the right reads:

Playing time 10–40 min.

Which directly says the average duration of a game.

Now, turns on this game, as per my experience, are quite fast. They can last a few seconds (reveal cards, someone wins, cards are taken, end of turn), or in case of a tie some extra few seconds.

So, assuming a turn lasts in average 10 seconds, we can transform that average duration from time units to turns. Best case (10 mins) it will take 60 turns to complete, worst case (40 mins) it will take 240 turns.

3
  • 1
    Perhaps the OP can clarify, but I interpreted the question as asking about probability and statistics; what is the average expected number of turns given the factors we know.
    – GendoIkari
    Dec 3 '18 at 20:38
  • 1
    @GendoIkari yes that is what I meant. It seems like a more accurate answer than starting with an estimated time and trying to infer turns.
    – StrongBad
    Dec 3 '18 at 21:11
  • 1
    @GendoIkari Although my approach was not so rigorous, it is probabilistic. We have the average duration of these games. We also can obtain an average turn duration, based on the dynamics involved (which are quite few, drawing cards, showing it, someone wins, or tie) and from domain knowledge (having played the game several times myself)... but yes, this could be more rigorous. Perhaps making a small program simulating the game will yield a better estimate :)
    – DarkCygnus
    Dec 3 '18 at 21:21
-2

Just a quick answer here, war actually is a game, because how players pick up the cards, affects the outcome. You can choose to pick up the cards in different orders after each round. But it is very difficult to play strategically.

As for the question at hand, I built my own simulation, and for 5 trials, with shuffling, I got:

58, 144, 354, 428, 189

This comes to an average of 234 rounds. Obviously, you can do more trials, to get a more accurate number, but it's definitely a long game to play!

My source code is

<html>
<head>
<script>



window.addEventListener("load", () => goto(WAR));

    


// player decks and discards
let D1, D2, TABLE, ROUND;

function rank(x){
  let r = (x%13) + 1;
  if(r == 1) r = 14;
  return r;
}
function card(x){
  let r = rank(x);
  let suit = Math.floor(x/13);
  if(r > 10){
    r = ["Jack", "Queen", "King", "Ace"][r - 11]; }
  suit = ["Clubs", "Spades", "Hearts", "Diamonds"][suit];
  return `${r} of ${suit}`;
}
function deck(){
  return [...Array(52).keys()];
}
function shuffle(d){
  if(!d) d=deck();
  for(let i=0; i<d.length; ++i){
    let j = i + Math.floor((d.length-i) * Math.random());
    [d[i], d[j]] = [d[j], d[i]];
  }
  return d;
}

function draw(d,n,result){
  if(!d) d=deck();
  if(!n) n = 1;
  if(!result) result = [];
  n = Math.min(n, d.length);
  for(let i=0; i<n; ++i){
    result.push(d.shift()); }
  return result;
}

function ShowCounts(next){
  return next;
} 
    

function WAR(){
  D1 = shuffle();
  D2 = draw(D1, 26);
  console.log(D1, D2);
  TABLE = [];
  ROUND = 1;
  disp(`Welcome to War`);
  return WAIT;
}
function WAIT(){
  let handlers = [];
  more(`Press [Enter] or click anywhere to continue.`);
  wait(handlers, document.body, 'mousedown', null, FIGHT);
  wait(handlers, document.body, 'keydown', (e)=>(e.keyCode == 13), FIGHT);
  return null;
}
function FIGHT(){
  disp(`Fight! (Round ${ROUND++})`);
  more(`Player 1: ${D1.length} cards.`);
  more(`Player 2: ${D2.length} cards.`);
  more();
  if(D1.length == 0 || D2.length == 0) return END;
  let a = D1.shift();
  let b = D2.shift();
  TABLE.push(a);
  TABLE.push(b);
  more(`${card(a)} vs ${card(b)}.`);
  let x = rank(a);
  let y = rank(b);
  if(x == y){
    return TIE; }
  let winner = (x > y)? D1 : D2;
  more(`Player ${x>y? 1 : 2} wins ${TABLE.length} cards.`);
  draw(shuffle(TABLE), TABLE.length, winner);
  more();
  return WAIT;
}
function TIE(){
  more("Round is tied.");
  more("Each player draws 3 more facedown cards.");
  draw(D1, 3, TABLE);
  draw(D2, 3, TABLE);
  if(D1.length == 0 || D2.length == 0){
    return END; }
  return sleep(0.0, FIGHT);
}
function END(){
  if(D1.length > D2.length){
    disp("Player 1 Wins!"); }
  else{
    disp("Player 2 Wins!"); }
  more(`After ${ROUND} rounds.`);
  return RESTART;
}

function RESTART(){
  return sleep(2.5, ()=>{
    more("Restarting ...");
    sleep(2.5, WAR)})
}

function goto(target){ // targets return the next function to run.
  while(target){
    target = target(); }
}


function wait(handlers, target, name, test, after){
  if(!handlers) handlers = [];
  let handler = function(evt){
    if(test && !test(evt)) return;
    for(let tuple of handlers){
      let [other_target, other_name, other_handler] = tuple;
      other_target.removeEventListener(other_name, other_handler);
    }
    goto(after);
  }
  handlers.push([target, name, handler]);
  target.addEventListener(name, handler);
  return null;
}

function sleep(n, after){
    setTimeout(()=>goto(after), n*1000);
    return null;
}

function disp(x){
  if(x == undefined) x = "";
  document.getElementById("disptext").innerHTML = x;
}
function more(x){
  if(x == undefined) x = "";
  document.getElementById("disptext").innerHTML += "\n" + x;
}
  
function randint(n){
  return Math.floor(Math.random() * n);
}

function Download(){
  var zip = new JSZip();

  // Generate a directory within the Zip file structure
  var guessgame = zip.folder("war");

  guessgame.file("index.html", document.documentElement.outerHTML);

  // Generate the zip file asynchronously
  zip.generateAsync({type:"blob"}).then(function(content){
      // Force down of the Zip file
      saveAs(content, "wargame.zip");
  });
}

</script>
<style>
 *{ font-size: 108%; font-family: monospace; }
 #editor{ height: 70%; width: 100%; overflow-x: scroll; }
</style>
</head>
<body>
  <p><pre id="disptext"></pre></p>
  <!--<input id='textinput' type='text'></input>
  <input id='okaybutton' type='button' value="ok"></input>-->
  <!-- <p style="position: fixed; bottom: 0px; right:8px; text-align: right;"> -->
  <p>
    <!-- <h3> Source Code </h3> -->
    <!--<button onclick="editor.innerHTML = document.documentElement.outerHTML; editor.style.display='block'"> View </button>-->
    <!--<button onclick="Download();"> Download Game</button>-->
  </p>
  <p>
    <textarea id='editor' wrap='off' style="display:none;" readonly="true"></textarea>
  </p>

</body>
</html>
3
  • 2
    The effect of how you pick up cards is extremely minimal when shuffling is added into the game, it's only significant when cards are placed in the order they are picked up onto the bottom of the current deck.\
    – Andrew
    Feb 25 at 19:48
  • From what I remember when playing war the cards always got shuffled when your play deck ran out.
    – Joe W
    Feb 26 at 19:55
  • If you have a running code, please run it 10K times to produce an accurate average. 5 samples are almost worthless.
    – Cohensius
    Feb 27 at 18:33

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.