Introduction to Combinatorial Game Theory, Part 1

I feel the urge to write this post partially because I’m interested on this thing (even though I failed to understand much of the later part of Winning Ways Vol. 1), and partially because I feel bad to begin analysis of The Genius 3’s Monorail with “Sprague-Grundy theorem” without people understanding a thing. Also because I should try writing mathematical posts and stuff. I’m not particularly experienced on this either, so what I’m writing is to the best of my knowledge and might be faulty at points. Blame Wikipedia for not having a good CGT article.

…so let’s go.

In combinatorial game theory (CGT), we’re only interested in a relatively small set of games:

• The game must have a clearly defined positions. This rules out pretty much all physical games that cannot be translated into non-physical games, such as pretty much all sports. Note that Memory Maze (The Genius 3, Death Match 8-9) can be translated into a non-physical game easily; instead of using players as the pieces, they can use pawns instead.
• The game must be two players. With more than two players, you can have kingmaker scenarios and the like, which I don’t think fit in CGT; try the more general game theory to handle that. This rules out many board games like Monopoly and The Settlers of Catan.
• The game may not involve any element of luck, such as rolling dice or tossing coins, or using a face-down deck of cards. This rules out even more games, including poker.
• The game must have perfect information, and is played sequentially. So no Black and White (The Genius 2, Death Match 9, 11), and no Goofspiel either, despite me also enjoying them. Perhaps later post.

What does that leave? Well, plenty of them: chess, checkers, go, Arimaa, tic-tac-toe, Hackenbush, Nim, Abstrac…

First, a formal definition of game. What is a game?

Mathematicians define it recursively, and not in terms of games, but in terms of positions. A position is a set in the form , where is positions that can be reached in a single move by the first (Left) player, and is positions that can be reached in a single move by the second (Right) player. So, for example, for tic-tac-toe in the starting position, we have:

As long as you assume X plays first (and thus is Left) like me, you’re fine. And after X plays in the center, we have:

But wait, after X plays, why are there still moves for X, you ask? Good point! Mathematicians are weird like that. But no, there is a better reason that you’ll see later.

Thus after several moves into the game, we get:

And when O plays at the top, thus getting three in a row, we get:

Whoa, what kind of game is the last one? is also known as the zero game, where neither player has any move and thus loses. Usually (when playing, you know, “normal” tic-tac-toe), this will be X’s move, and since X has no move (the left part is empty), X loses.

In fact, tic-tac-toe is a hard thing to play with, since it has a weird winning condition for mathematicians. The arguably simplest winning condition is that “the player that has no move loses”. Tic-tac-toe, chess and go don’t follow this condition: in tic-tac-toe, you win by making three-in-a-row. In chess, there is stalemate, where although a player has no move, they get a draw instead. In go, you will never run out of moves for obvious reasons (the board will never be full; when the board is full, the last move must have captured some stones). Arimaa follows this condition, but adds extra rules (getting a rabbit to the eighth rank or capturing all your opponents’ rabbits also wins), so not exactly correct either. Only in checkers that this condition is fully respected: the player with no move loses. (If you get all pieces captured, you obviously have no move left.)

However, checkers still have draws, because the game can last forever (both players having kings that just move back and forth). Although this is okay, it complicates analysis of games. Not to mention that these games are interesting to play, and they are interesting exactly because they are hard; if they aren’t hard, they would have been solved by now and nobody would play them again. Thus, let’s add a few more conditions on what things combinatorial game theorists mean by a game:

• The game must eventually end.
• The game cannot have draws.

This leaves too little! And thus, several simpler games are born; Hackenbush and Nim are two of them. Let’s take a look on the first one.

In Hackenbush, there are several segments colored in bLue or Red (for Left and Right), connected to a special “ground”. One example starting position with six segments is below, but the position can be anything as it’s not intended to be a game for entertainment.

What are the rules of the game? Each turn, a player may remove one segment of their color (blue for Left and red for Right). All segments must be connected to the ground, probably through other segments; if they are not connected to the ground, they collapse and disappear. For example, this is the same position, along with the moves:

…wait, what happened in Red’s second move? You see, when you remove the middle red body, the top part is no longer connected to the ground and thus they fall, disappearing.

Hackenbush’s winning condition is very simple: the player with no moves loses. Thus when there is no blue segment and it’s Left’s turn, Left loses, and if there is no red segment and it’s Right’s turn, Right loses. If there are no segments, of course, whoever to move loses, and that’s our zero game.

Let’s turn our attention to a simpler game than above, but a little more complex than a zero game…

What is this, a single blue segment? True. If Left removes this, we are left with the zero game. Right cannot move here.

Incidentally, drawing things all the time sucks, and thus let’s develop a little notation. The zero game, where everything is dead, let’s call this game . Thus the game with a single blue segment above is . We call this game , as it’s one move advantage for Left; if Left needs to make a move (and thus gets closer to having no move left), they can use this safely. And of course, naturally means , as it’s two moves advantage for Left: the first move moves to , which gives one move advantage. Note that ; if you can have one move advantage, why would you waste it?

Of course, on the opposite direction, we have , and so on.

So why are these important? Why can’t we just say “Left wins”, “Right wins”, “second player wins”, and the like? This is because an important concept in CGT: addition of games. When adding games together, a player may move in either of the games, but not both.

What would the top one, , be? If we interpret them as numbers, they add up to , so maybe that’s a zero game?

Indeed, as we can check; . Since the won’t do anything else, we can ignore it (which also means for any game ). Thus we are left with . Here, whoever to move must give their opponent moves, which means they lose. First player loss is always .

What is the second one? Heck, what is a blue stick with a red stick on top of it? You can check that it is ; Left to move destroys all, while Right to move leaves a blue stick, . But what is its value?

This, as it turns out, is equal to . To verify this, we can try adding it to itself, as well as adding a red stick (); this should be , so loss for either player to move. Is it?

Yes, it is. With Left to move, they have pretty much no choice; they must take down one of the tall sticks. Right can then save themself by taking the top red segment (otherwise as Left moves next, that segment will fall down). The remaining game is exactly above. With Right to move, they should save one top segment for the same reason, but after this Left can knock down the remaining top segment, leaving again . (If Right moved on the lone red segment, the remaining game is , which cannot be good for Right; if Right is to move, Left still has moves, but if Left is to move, Right has no move.) Thus .

Confused? Yes, it’s pretty confusing, but that’s CGT.

Next part, playing with Nim and impartial games.