Combinatorial Game Theory - Overview

Overview

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation {L|R}. is the set of game positions that the left player can move to, and is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.

Use Domineering as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on the second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as

Note that, in standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states.

The above game (an irrelevant open square at C3 has been omitted from the diagram) describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. The {|} in each player's move list (corresponding to the single leftover square after the move) is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, the player whose turn it is when the zero game comes up automatically loses.

The type of game in the diagram above also has a simple name; it is called the star game, which can also be abbreviated *. In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins.

An additional type of game, not found in Domineering, is a loopy game, in which a valid move of either left or right is a game which can then lead back to the first game. Checkers, for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called loopfree.