Chapter I
Combinatorial Games
1. Introduction
Combinatorial games are two-player games with no hidden information
and no chance elements. They include child’s play such as Tic-Tac-Toe
and Dots and Boxes; mathematical abstractions “played” on arbitrary
graphs or grids or posets; and some of the deepest and best-known board
games in the world, such as Go and Chess.
The mathematical theory of combinatorial games pursues several inter-
related objectives, including:
exact solutions to particular games, usually in the form of an algebraic
description of their outcomes;
an understanding of the general combinatorial structure of games; and
hardness results, suggesting that for certain games, or in certain situ-
ations, no concise solution exists.
In all of the games considered in this book, there will be just two players,
Left and Right, who play alternately and whose moves affect the position
in a manner defined by the rules of the game. Both players will have com-
plete knowledge of the game state at all times (“no hidden information”),
and the effect of each move will be entirely known before the move is made
(“no chance elements”). We’ll defer a formal definition until after we’ve
introduced some examples.
1
Previous Page Next Page