Nerd Wisdom

Combinatorial Game Theory (CGT) is a mathematical discipline that studies two-player, zero-sum games, where the players play sequentially, and there is perfect information and no chance. The aim of CGT is to build mathematical theories that will help players win such games! In practice, the ideas from CGT are of minimal help to the serious player in more complicated games like Chess or Go, but the theories are extremely helpful for simpler but still non-trivial games like Dots-and-Boxes.

The CGT bible is Winning Ways for Your Mathematical Plays, a four-volume set of books (for the 2nd edition from the early 2000’s; the first edition from 1982 was in two volumes), by the eminent mathematicians Elwyn Berlekamp, John Horton Conway, and Richard Guy.

The basic idea of CGT is to develop a calculus, which lets you assign a value to a position in the game. One normally considers games with the condition that a player who cannot move loses. If both players are without a move in a position (whoever moves loses), the position is assigned a value of 0. If the player on the right can make one move that transforms the position to one of value 0, and the player on the left cannot move at all, the position is assigned a value of 1 (if the roles are reversed, the position has value -1).

Now what happens if the player on the left has a move to a position of value 0, and the player on the right has a move to a position of value 1? What is the value of that position? It turns out to be worth 1/2, as can be seen by considering the position obtained by adding such two such positions together with a position of value -1, when one gets back to a position of value 0 where whoever moves loses (I’ll let you work out the details).

There are more different kinds of values than just fractions. Berlekamp, Conway, and Guy consider a multitude of different interesting games, which give rise to ever deeper mathematics, and game positions with strange values along with complex rules for combining those values.

The writing is informal, with constant punning, but the mathematics is serious. Still, one charm of the field is that there is no pre-requisite mathematical material needed to understand these books–bright high school students can launch right in.

After finishing “Winning Ways,” the ambitious student can move on to the two volumes “Games of No Chance” and “More Games of No Chance” (note that nearly all the papers in these books are available online), and then move onto the rest of the papers collected at David Eppstein‘s CGT page.

Also, take a look at Aaron Siegel‘s Combinatorial Game Suite software to help you do CGT computations.

There’s still much more to say, but I’ll leave that for other posts.

Tags: combinatorial game theory, dots-and-boxes, mathematical games, Mathematics

This entry was posted on August 29, 2007 at 1:29 am and is filed under Books, Chess, Entertainment, Game Theory, Games, Mathematics, Reviews, Science, Software. 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.