Combinatorial Games

Combinatorial games are games that have the following properties:

• They have what is known as perfect information; in other words, chance is not involved and no player can hide information about the state of the game from other players.
• They are sequential; in other words, one player makes a move, after which another player makes a move, and so on.

The requirement that combinatorial games have perfect information excludes most situations found in everyday life, but combinatorial games include many well-known games such as chess, checkers, Tic-Tac-Toe, Go, Nim, Conway's Game of Life, Sprouts, as well as others that aren't well-known, such as Don't Make a Triangle. Combinatorial game theory is the theory of such games.

Consider any two-player combinatorial game. If you think about it for a while, it might occur to you that one of these three statements has to be true:

1. The first player has a winning strategy; in other words, there is a strategy (possibly very complex) that the first player can follow such that the first player can always win regardless of how the second player plays
2. The second player has a winning strategy
3. Neither player has a winning strategy, but each player has a strategy to guarantee a draw.

This result has been proven by Ernst Zermelo (who is better known for his work on set theory).

Naturally, knowing the winning strategy for a game can take the fun out of it. You probably remember how you quickly lost interest in Tic-tac-toe once you discovered that, with best play, the game is always a draw. However, for more complex games, knowing that a strategy exists to guarantee a draw or a win is often of little help for practical play. Checkers has been recently found to be a draw with best play, although the correct drawing strategy would be far too complicated to describe, so casual players can continue to enjoy the game. For more complicated games, such as chess, the number of possible ways of playing the game is so large that, for the time being, it is not possible to "solve" the game, even with the assistance of computers.

External links: Connect-Score, a pencil-and-paper combinatorial game.