combinatorial games

>> >> mathematics >> combinatorial games
misere games

nim sequence calculation

partisan subtraction

hackenbush notebook


Combinatorial Games

Winning Ways authors
Richard K Guy, John Horton Conway, and Elwyn Berlekamp
Now in a four volume second edition! Buy it at AK Peters

Combinatorial Game Theory describes two-player games of complete information with no chance moves. The bible of this topic is Berlekamp, Conway, and Guy's Winning Ways for your Mathematical Plays.

I've played around with this subject off and on over the years, ever since as a sixteen year-old in 1977 I found a copy of On Numbers and Games in the Calvin T Ryan library on the campus of Kearney State College, in Kearney, Nebraska.

You can drill down on some of things I've worked on using the links at the left.

Here's an excerpt of a review of David Wolfe and Elwyn Berlekamp's Mathematical Go: Chilling Gets the Last Point that Richard K Guy wrote for the October 1995 American Mathematical Society Bulletin:
Last July, at the Combinatorial Games Workshop in Berkeley, David Blackwell suggested that most of mathematics may be chaotic, and that it is only the small part where we recognize patterns that we actually call mathematics. Combinatorial game theory tends to foster such a view. Are games with complete information and no chance moves of little interest because there are pure winning strategies? On the contrary, when we come to analyze even the simplest of such games, we often run into regions of complete chaos. David Gale wrote in [4] that he had barely scratched the surface of combinatorial game theory, but
...the experience has left me with an overwhelming sense of awe at the unfathomable diversity of mathematics itself. The authors of [Winning Ways] have created a mathematical fairyland ... [some] people say all of mathematics is really one ... I wonder if this belief in ultimate unity may not be just wishful thinking ... My own hunch is that mathematics (perhaps Physics too) is not going to unify ... Combinatorial game theory is just one example of what unfettered mathematical imagination is capable of creating ... There will be many others ... Mathematics will continue to diversify in totally unpredictable ways ...
But now this fairyland turns out to be part of the real world. Go is the most significant of combinatorial games, whether you measure by popularity, playability, or resistance to computer attack. Yet Berlekamp, a mere 10-kyu (connotes "child") player, has been to Japan, set up endgame positions against 9-dan (connotes "adult") professional opponents and beaten them, not once but repeatedly, and then again from the same position with the colors reversed!
[Abbreviated] References:

[4] David Gale, Mathematical Entertainments, The Math. Intelligencer, 16, #2 (1994) 25--29.