Positional game

A positional game is a kind of a combinatorial game for two players. It is described by: A positional game is a kind of a combinatorial game for two players. It is described by: During the game, players alternately claim previously-unclaimed positions, until one of the players wins. If all positions in X {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, X {displaystyle X} contains the 9 squares of the game-board, F {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.: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. Often, the input to a positional game is considered a hypergraph. In this case: