Loading AI tools
Type of two player combinatorial game From Wikipedia, the free encyclopedia
A positional game[1][2] 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 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, contains the 9 squares of the game-board, 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.
Often, the input to a positional game is considered a hypergraph. In this case:
There are many variants of positional games, differing in their rules and their winning criteria.
The following table lists some specific positional games that were widely studied in the literature.
Name | Positions | Winning sets |
---|---|---|
Multi-dimensional tic-tac-toe | All squares in a multi-dimensional box | All straight lines |
Shannon switching game | All edges of a graph | All paths from s to t |
Sim | All edges between 6 vertices. | All triangles [losing sets]. |
Clique game (aka Ramsey game) | All edges of a complete graph of size n | All cliques of size k |
Connectivity game | All edges of a complete graph | All spanning trees |
Hamiltonicity game | All edges of a complete graph | All Hamiltonian paths |
Non-planarity game | All edges of a complete graph | All non-planar sub-graphs |
Arithmetic progression game | The numbers {1,...,n} | All arithmetic progressions of size k |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.