The Science of War

war

I will never play this again.” — that seems to be my sentiment each time I play this stupid card game. And yet I repeatedly (usually in my most bored and desperate moments) fail to learn from my mistakes and convince someone to join me for some boredom-inducing card flipping.

My last victim was my brother. I convinced him to play a game of War as we were waiting for a flight out of New York (turns out airports are brimming with potential War victims..) Most of you already know what is coming next: During the next two and a half hours we miserably flipped cards and desperately clung to the false hope that the game would be ending in “just a few more hands”. After flipping our 1,000,000,005th cards, it started to become apparent that this game might never end.

The game did end up winning. And importantly (and the point of this whole post), it led my brother and me to develop an interesting train of thoughts:

1. This game requires no skill.

2. Someone could play War with his/her self.

3. “We’re essentially robots flipping cards..”

4. Someone could program a computer to do this for us.

5. #4 might be more fun than actually playing the game. <– Bingo.

Guess what I worked on during the flight home? Yes. I did. Allow me to introduce war.m. (You will need Matlab to run the code)

This program automatically generates a random deck of cards and deals out both hands for each game. It then plays each game just as two humans would. Trust me, this program is about as fun (not very) as real war without the hours of drudgery!

However, once I had the framework coded, I was able to save some statistics as it played through many thousands of games. This provided some insight into the game and (almost) made the entire thing worthwhile. For instance, I learned that being “human” actually has a profound effect on the game. I also learned that the average game between two humans will last 277 rounds and that the game can be theoretically unwinnable.

Most importantly, I learned that there is a “correct” way to play war which is systematic, repeatable, and relatively fast.

Results:
Note: It may be helpful to review the rules of war if you are completely unfamiliar with how this game is played.

In order for these results to make sense I need to explain some conventions.

Random factor:
As I created this simulator, I realized that there is an important difference between computers and humans: the “random factor”. This manifests itself in the way the players pick up the cards at the end of each round. There are two possible scenarios:

1.) Player 1’s card goes above Player 2’s card and to the bottom of the winners deck.
2.) Player 1’s card goes below Player 2’s card and to the bottom of the winners deck.

Since (most) human players don’t pay attention to this detail they likely pick up the cards without paying attention to their order.

I have three ways of dealing with this:

  • Simulate human behavior by randomly pick from the two scenarios with a 50% chance of choosing either option.
  • Use a very basic approach and always choose scenario 1.
  • Intelligently choose the order. If player one wins the round  choose scenario 1 and if player 2 wins the round  choose scenario 2.

Stuck games:
The results will show that certain games get “stuck”. This occurs when the game enters an endless loop and will never end. Take the following example:

Player 1’s hand: Ace Two King Three ~ High Low High Low
Player 2’s hand: Four Jack Three Ace ~ Low High Low High

After two rounds this game becomes:

Player 1’s hand: King Three Ace Four ~ High Low High Low
Player 2’s hand: Three Ace Two Jack ~ Low High Low High

This trend will continue for an infinite number of rounds — the game is stuck. Note that this is only possible under specific circumstances with the basic system.

With that out of the way, its time for some data!

Option 1: Randomly pick between scenario 1 and scenario 2 (human-like)

Typical game:

war-typical

Statistics (500,000 games):

Average Rounds: 276.9335
Std. Deviation: 223.9880
Average Victor: 1.4992
Average Wars: 16.3062
Stuck Percentage: 0
Longest Game: 3284

Option 2: Always choose scenario 1. (Basic computer)

Example of a “stuck” game which can occur under this scenario:

war_stuck

Statistics (500,000 games):

Average Rounds: 609.357
Average Victor: 1.5122
Average Wars: 21.6967
Stuck Percentage: 10.08
Longest Game: 9542

Option 3: Pick the scenario based on the round winner. (Intelligent approach).

Typical game:

war-smart

Statistics (500,000 games):

Average Rounds: 199.7003
Average Victor: 1.5052
Average Wars: 13.7014
Stuck Percentage: 0
Longest Game: 1963

Summary

The data shows there is, in fact,  a correct way to play War –  it is best to order the cards based on the winner of each individual round.Using option 3, the average game is only 200 rounds. And 96% of games are less than 550 rounds.

To put this  into perspective it is helpful to think of “rounds” in terms of time. Assume two players can complete a round in three seconds (trust me, this is conservative). This means than 550 rounds takes 1650 seconds or ~27 minutes. If you use this simple rule of thumb almost all of your games will be under half an hour!

If you don’t like the idea of making this game even more robotic,  randomly picking the order of the cards is an acceptable solution. Games will last a little bit longer (~277 rounds), but should still end in a reasonable amount of time.

The absolute worst way to play this card game is to fall into a rut in which the cards are always picked up in the same order. If this happens, you can expect games that last longer than 600 rounds on average! Even worse, 10% of games will never end if you maintain this behavior.

This entry was posted on Monday, October 26th, 2009 at 2:38 pm and is filed under Programming, Waste of Time. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

You must be logged in to post a comment.