Joe Ganley [http://ganley.org/]

Writing code since 1979

I have been a professional software engineer for over 10 years. I have written many kinds of software, but my particular strengths are interactive graphics applications, compilers and interpreters, and algorithms.

I also enjoy writing, woodworking, and home improvement. Also this. NVConsumer.

~~Bio~~ (under renovation)
Resumé

not from a security camera

News

- New weblogs here and here.

Wednesday, July 28, 2004

War

My daughter has discovered the card game War, which got me once again to thinking about it. Specifically, is there a simple statistical measure of the deal that can predict the victor? I could only find one analysis on the web, done by a Patrick Kellogg for a college statistics class. I took his analysis a little further, but reached largely the same conclusions. The two obvious potential predictors are the player with the most aces (which I considered the highest card), or the player with the highest total point value. However, I wrote a program to simulate a million trials, and it turns out that the first player to acquire more than two of the aces still only wins 64% of the time, and the player who is dealt the most points only wins 59% of the time. As Kellogg says, much of the game seems to turn on the exact way the cards are shuffled, and no obvious statistical measure seems to be able to predict victory (much like war itself, perhaps). I also discovered an interesting phenomenon: For certain ways of adding a won trick to the bottom of the player's deck, there are hands that result in an infinite loop. Consider, for example, this deal:


One: 23456789TJQK2A3456789TJQKA

Two: 32547698JTKQA2436587T9QJAK

If won cards are added to the bottom in the right order, then play does not change each player's hand at all, so the game never ends. Obviously, this deal is pathological, but in my simulations I did see a hand that oscillated in a complex pattern such that neither player ever had fewer than 25 cards, and that never appeared to end.

| permalink

Comments:

Hi, this is Patrick Kellogg. That war paper can be found on the web at (http://www.patrickkellogg.com/school/papers/war/index.htm). Thanks for checking it out.

The research I'm currently most fascinated with is evolutionary programming, which is a lot like genetic algorithms, but it's the actual *algorithm* that is modified each generation. I'm hoping I can have a computer find better statistical measures for "good" war hands than I could do myself. However, beyond buyng a bunch of books, I've been too busy writing other code lately.

I never did a similar statistical test for solitaire, and I really wanted to. I wanted to answer the question of how many games were "winnable", how to recognize winnable set-ups before playing, and whether an optimal strategy exists. Oh well, maybe in the future! Take care, and happy coding...

# posted by Anonymous : 10:53 AM

For many solitaire games, it is NP-complete (i.e. computationally intractable) to determine a priori whether the game is winnable. However, in most solitaire games (unlike War) there is a little bit of strategy involved -- places where you have choices what play to make next -- that combinatorially explodes the size of the solution space.

# posted by Joe : 12:56 PM

Features

The Long Now Foundation

Man-Bag Buying Guide

dealnews.com
Breaking news on the
latest technology prices

Copyright (c) 1988-2004 by Joseph L. Ganley. All rights reserved except where otherwise noted.