I.1: Introduction to “Simple Games”

In What is Combinatorial Game Theory?, combinatorial games were defined. However, it’s beyond impractical to talk about all combinatorial games at once, so we’ll add some more conditions to get to what I’ll call a “Simple game” (this is not a standard term). For clarity, a combinatorial game has a fixed starting “position”, and after each move it’s in another position (possibly the same as some previous position). A Simple game:

  1. is two-player.
  2. is “normal play”, meaning when someone has no legal moves, they lose. (If a player with no legal moves were to win instead, it would be “misère play”.)
  3. has no ties; the only way for the game to end is for someone to lose/win.
  4. is “non-loopy”, meaning the game definitely ends; it can’t go on forever.
  5. is “impartial”, meaning that for a given position all players would have the same available moves. (The opposite of “impartial” is “partizan”.)

Occasionally, we may also ask that the game is “short”, so that there are only finitely many positions reachable. With all of these conditions, we’ve seriously restricted our concept of game, so that almost every game you’ve heard of (unless you’ve heard of Nim or looked into CGT before) is not a simple game. One of the easiest simple games to explain is “Kayles”. The starting position has a bunch of bowling pins in fixed spots in a row (perhaps with gaps). The players take turns throwing balls at the pins. The players are perfect bowlers who can hit any one pin they want, or any pair of pins in adjacent spots. If there are no pins to hit on your turn, you have no moves, and you lose.

An example game (I’ll use “i” to denote a spot with a pin and “.” to denote a spot without one): There are three pins in a row (iii), and I go first. If I hit a pair of pins (e.g. to make it i..), my opponent would hit the remaining pin and I lose. If I hit one of the outer pins (e.g. to make it ii.), my opponent would probably hit both remaining pins and I’d lose. Therefore, I hit the middle pin (leaving i.i). Since the remaining two pins aren’t adjacent, my opponent will only hit one and then I’ll hit the other and win.

It’s a good exercise to try and figure out what perfect play is like when the game starts with n pins in a row (so no gaps). It’s basically impossible to figure out what perfect play is like in all setups (e.g. ii.i.iiii.iii.ii) without CGT, but with a theorem we’ll get to, it’s totally doable!

Even though common games are generally not Simple games, some common games are almost Simple games. For instance, Tic-Tac-Toe is traditionally partizan (there’s a player who gets to place X’s and a player who gets to place O’s), isn’t normal play (the ending condition has to do with getting three in a row), and has ties (in case no one gets a three in a row). All of this can be fixed:

If you add a toggle switch next to the board, with one side labeled “write an O next” and the other labeled “write an X next” and ask that people flip the switch after each move (and have it start in the O position at the beginning of the game), then the game becomes impartial. If you say that “if there’s a three-in-a-row of X’s and the switch is in the ‘O’ position (or vice versa), then no move is legal” and “ties go to first player” (so if the board is full and it’s your turn then you lose, as in normal play), then there are no more ties and the game is normal play.

In this way, Tic-Tac-Toe can be turned into a Simple game. Similar tricks can be done for many other common games like Chess and Go (you may have to impose special conditions so the game doesn’t go on forever) or misère games, but this sort of conversion doesn’t usually help you analyze these other games. In short, the theory of Simple games is different than the theory of other games.

In upcoming posts, we’ll talk about “winning strategies”, and the game of Nim, the most famous Simple game.


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.