O.1: What is Combinatorial Game Theory?

Lots of people have played some sort of strategic game. Whether it’s Chess, Go/WeiQi/Baduk, Tic-Tac-Toe/Noughts and Crosses, or Dots and Boxes, it’s amenable to rigorous analysis and computerized play. Elwyn Berlekamp, a major force in the field of Combinatorial Game Theory (CGT, for short), has said:

As I use the term, “combinatorial game theory” differs from artificial intelligence in the same primary respect that mathematics differs from engineering: the emphasis is on conclusions which are provably correct rather than on conclusions which are plausible or good enough to be acceptable in some imprecise sense. The mathematicians’ main goal is understanding; the engineer’s main goal is a functioning system.

In short, mathematicians want to be able to understand games on a theoretical level, and when possible, to play them perfectly. CGT is the main tool they use to do that, and they’ve already had success with lots of games, perhaps most notably, late Go endgames.

The most basic thing that needs to be clarified is: What games are we talking about? As far as I know, with the possible exception of Blackwell games (which have simultaneous moves), CGT is considered to only deal with combinatorial games that at least satisfy the following condition:

Some finite number of players take turns (unlike the circular lake problem) and the game has “perfect information” meaning there is no randomness (like in a dice game or Poker), hidden information (like in Battleship or Poker), secret rules (like in Betrayal at House on the Hill), or simultaneous moves (like in the Prisoner’s Dilemma).

Now, some of you are saying “doesn’t Game Theory deal with the Prisoner’s Dilemma?” ; and you’d be right. Unfortunately, when people study Game Theory (related to Economics, and a big subject of John Nash’s work), they usually don’t focus on combinatorial games, so CGT is an essentially unrelated field.

Advertisements