Positional game

A positional game^[1][2] is a kind of a combinatorial game for two players. It is described by:

• ${\displaystyle X}$ – a finite set of elements. Often ${\displaystyle X}$ is called the board and its elements are called positions.
• ${\displaystyle {\mathcal {F}}}$ – a family of subsets of ${\displaystyle X}$. These subsets are usually called the winning sets.
• A criterion for winning the game.

During the game, players alternately claim previously-unclaimed positions, until one of the players wins. If all positions in ${\displaystyle X}$ are taken while no player wins, the game is considered a draw.

The classic example of a positional game is tic-tac-toe. In it, ${\displaystyle X}$ contains the 9 squares of the game-board, ${\displaystyle {\mathcal {F}}}$ contains the 8 lines that determine a victory (3 horizontal, 3 vertical and 2 diagonal), and the winning criterion is: the first player who holds an entire winning-set wins. Other examples of positional games are Hex and the Shannon switching game.

For every positional game there are exactly three options: either the first player has a winning strategy, or the second player has a winning strategy, or both players have strategies to enforce a draw.^[2]: 7 The main question of interest in the study of these games is which of these three options holds in any particular game.

A positional game is finite, deterministic and has perfect information; therefore, in theory it is possible to create the full game tree and determine which of these three options holds. In practice, however, the game-tree might be enormous. Therefore, positional games are usually analyzed via more sophisticated combinatorial techniques.