rice_rice_baby

So a while ago I was looking at the Wiki page on the card game War. I noticed that the page included what might be called "original research" and a link to an article on the subject. I honestly don't think it was peer-reviewed. The research included the results of simulating 1,000,000 games of War. Eager to relearn what I'd forgotten about War, as well as having an interest in statistics, I decided to go ahead and write a basic card game simulator in MATLAB that was tailored to War. If nothing else, I wanted to confirm that author's findings.

For those too lazy to glance at the Wiki page, War is a simple card game wherein the object is to obtain all the cards in the deck. Each player (usually only two) is dealt half the deck. The game proceeds by having each player show the top card of their stack. The person whose card has a highest value (suits are ignored) wins those two cards, which are then put at the bottom of that person's stack of cards. If the players each show the same card, then you have a "war." Each player antes three cards, face down, then plays another card face up. If those cards are also the same, you repeat the process with three more cards. If not, then whoever has the higher-valued card gains all cards on the table.

Here's a basic set of plays in War (S=spades, H=hearts, D=diamonds, C=clubs):

  • P1: 2S
  • P2: 5D
  • Result: P2 wins and puts 2S, 5D on bottom of his deck

  • P1: 5H
  • P2: 5S
  • Result: WAR!
  • P1: 3 cards down, 9C up
  • P2: 3 cards down, 8S up
  • Result: P1 wins and puts 8S, 9C, 5S, 5H, and the 6 other cards on bottom of her deck.

What about aces? In War, the only way you can beat an ace is to win one in a war. In example 2 above, if the three cards P2 wagers during the war include an ace, then P1 gains an ace. Thus aces are pretty much awesome.

What else affects your victory? Hand strength. In a standard ace-high hand, we can assign numerical values as [2,3,4,5,6,7,8,9,10,J,Q,K,A]=[-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6]. Cards below 8 are more likely to be beaten than cards greater than 8, simply given the even distribution of cards. For 26 cards, the strength of an initial hands ranges from -84 to 84. The strength of P1 and P2's hands are negatives; if P1 has a strength of -60, P2 has a strength of 60.

MATLAB

Simulating a deck of cards is pretty easy in any language, all things considered, and it isn't any different in MATLAB. The catch is that MATLAB's object-oriented programming support is somewhat limited (in v2006a, at least). Basically, you create a folder called @whatever that you use to contain your class. Within that folder contains all the M-files you need for the class. In this case, there's a @deck, @hand, and @card folder for those three classes. Pretty simple stuff.

I took care to randomize the deck using what's called the "Fisher-Yates" shuffle. I programmed various other types of shuffles (riffle shuffle, overhand shuffle, Hindu shuffle, Truffle shuffle), but those are a little slower and not any more random (in fact, I'd guess they were actually decidedly less random).

I made a simple program to output the actual hands to the command window. This shows the number of cards in the two hands represented by '+' signs, separated by a few spaces. As hands are played, the number of cards in each stack varies. On the right side is the specific turn number as well as the cards played during the specific turn. During wars I write out "War!" For simulation purposes I supress the output.

WHAT IS OF INTEREST?

Good question! Well, basically I wanted to answer a few questions, mostly those brought up by the Wiki page and the associated "peer-reviewed" article.
  • 1) What is your exact win percentage in relation to the number of aces in your hand?
  • 2) How does hand strength relate to win percentage?
  • 3) What is the average initial strength when a player wins?
  • 4) Is there any correlation between expected number of turns and the initial strength of the hands?

SIDEBAR: ENDLESS WAR?

I found one peculiar thing I never knew. If the order of the cards added to the winner's stack never changes, you can very often get a game of endless war! For example, the following two initial hands will, if P1's card is always added before P2's card to the bottom of the winner's stack, yield an endless game (bottom of the stack to the top of the stack).

P1
10S JS KD 6C 6D 2S 7S AC 3S 8D 5C 5D 8H AD KH 2D 4S 7C 3H 3D 10C 4D KC 4H 6H 7D

P2
9H 4C QC 9S 10D QH 5H QS 10H 8C AH 8S JH QD JD 2C KS 9D 3C 5S 6S 7H 9C AS JC 2H

Obviously that throws a wrench in any simulation. It turns out that if the order the cards are added to the winner's stack is randomized, we never get any such endless wars. I didn't realize that before, though it makes perfect sense.

THE SIMULATION

I ran four simulations, the most significant being the most recent with 100,000 games played. Basically, I found a few results of note. Here are some of interesing statistics:

  • Number of games played: 100000
  • Time to compute (min): 1898.2 (MATLAB is slow!)
  • Time per game (s): 1.1389
  • Time per turn (s): 0.0041
  • P1 wins: 50138
  • P2 wins: 49862
  • Avg total wars per game: 16.29560
  • Avg single wars per game: 15.32988
  • Avg double wars per game: 0.91200
  • Avg triple wars per game: 0.05113
  • Avg quadruple wars per game: 0.00253
  • Avg quintuple wars per game: 0.00010
  • Avg sextuple wars per game: 0.00001
  • Max total wars in a game: 163
  • Min total wars in a game: 0
  • Max single wars in a game: 156
  • Max double wars in a game: 11
  • Max triple wars in a game: 3
  • Max quadruple wars in a game: 2
  • Max quintuple wars in a game: 1
  • Max sextuple wars in a game: 1
  • Max septuble wars in a game: 0
  • Turns between wars: 17.6959
  • Avg turns per game: 277.64963
  • Max turns in a game: 2995
  • Min turns in a game: 12
  • Avg number of cards greater than 8 in P1's initial winning decks: 12.2749412
  • Mean of P1's initial strength: -0.02722
  • Standard deviation of P1's initial strength: 13.5592189
  • Mean of P1's initial strength when P1 wins: 2.696417887
  • Standard deviation of P1's initial strength when P1 wins: 13.25665113

    Winning percentage as a function of number of aces:

  • P1 wins with 0 aces: 1194
  • P1 wins with 1 ace : 9082
  • P1 wins with 2 aces: 19394
  • P1 wins with 3 aces: 16119
  • P1 wins with 4 aces: 4349
  • P1 win percentage with 0 aces: 21.59%
  • P1 win percentage with 1 ace : 36.63%
  • P1 win percentage with 2 aces: 49.83%
  • P1 win percentage with 3 aces: 63.40%
  • P1 win percentage with 4 aces: 78.16%

I expected the win percentage with all four aces to be considerably higher, perhaps naively so.

In agreement with the article linked above, there's a fairly linear relationship between hand strength and victory percentage. Here are three graphs that are of increasing interest from worthless to semi-worthless.

This shows the distribution of initial hand strength for all 100,000 hands dealt to player 1. As expected given that we are dealing a random deck and thus the hand composition/strength is a random variable, it is Gaussian. The mean initial hand strength is -0.0272 with a standard deviation of 13.559.

This shows the distribution of initial hand strengh only for those hands that P1 won (which is slightly more than 50,000). This is still a Gaussian, but it is shifted to the right by +2.696. In other words, the average (and most common) initial hand strength when P1 wins is +2.595, which is basically like trading a 7 for a 10 (a net gain of 3). The standard deviation is 13.257. So there's basically a narrower range of initial hands strengths that yield a victory given the slight reduction in standard deviation.

This plots the win percentage as a function of P1's initial hand strength. There's an approximately linear relationship from -25 to +25, which is where there are more samples. At the ends of the hand strength spectrum the limited number of samples (some as small as 1/100,000) is a problem. This is a problem with the Gaussian distribution of hand strengths, and this noise is evident in the same plot presented in the linked article above.

I found that roughly the same equation fits my data:

p(S)=.0075*S+.5021

where S is the initial hand strength and p(S) is the probability of winning given the initial hand strength S.

So overall my results mesh with those noted earlier.

This shows the distribution of the number of turns;specifically this is a log-normal distribution.

Well, that's all well and good. The mode is 125 turns per game. The next chart shows the best-fit line.

The equation in the title is the log-normal equation that represents the best fit for this set of data. Hooray MATlAB curve-fitting toolbox.

This shows the mean number of turns as a function of P1's initial hand strength. Again this is normally distributed, implying that number of turns is an independent random variable. As expected, the number of turns peaks around a hand strength of 0. Thus, games where the hands are even last the longest. Well, that's to be expected.

This shows the mean number of turns when P1 wins, again as a function of P1's initial hand strength. This shifts to the same peak as above.

I'm not sure what I was expecting, but here is the result of my simulation that was run while I was stuffing my face full of Thanksgiving turkey.