Combinatorial games are an interesting class of games where two players take turns to make a move. In these games, both players have perfect information about the state of the game and there is no element of chance. In ‘normal play’, the winner is declared when the other player is unable to move.

Even games that don’t exactly match these conditions can be analysed using techniques from combinatorial game theory, including chess and Go, and the pen-and-paper game Dots and Boxes.

The simplest way of thinking of these games is as a set of moves for the player Left, and a set of moves for the player Right. When a player chooses an option from their set, this new position can be considered another game. This gives us a tree-like structure: