Combinatorial Games

This chapter hardly relates to any of the previous games. Rather, these turn-based, zero-sum combinatorial games align more closely with what most people would associate with games (the likes of Chess, Connect 4, etc.). They are a subset of sequential games, but too complicated to analyze with a sequential tree diagram.

Instead, consider Zermelo’s Theorem (the proof of which is beyond the scope of this website), which states that either the first player can guarantee a win, the second player can guarantee the win, or both players can guarantee a draw for games satisfying the following criteria:

• There are two players that take turns making moves.
• There are finitely many possible moves.
• Each player has perfect knowledge of the other player’s possible moves.
• There is no element of chance.
• The game must always terminate in a finite number of moves.

In the following games, we’ll try to analyze strategies for guaranteeing a win or loss. I apologize for dropping the plot, but hopefully the interesting information about to be presented will allow you to forgive me.