# Positional game > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Positional_game > Markdown URL: https://mediated.wiki/source/Positional_game.md > Source: https://en.wikipedia.org/wiki/Positional_game > Source revision: 1287531313 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Type of two player combinatorial game}} {{distinguish|text=[position or positional play in poker](/source/Position_(poker))}} A '''positional game{{cite book|title=Combinatorial Games: Tic-Tac-Toe Theory|title-link=Combinatorial Games: Tic-Tac-Toe Theory|last1=Beck|first1=József|date=2008|publisher=Cambridge University Press|isbn=978-0-521-46100-9|location=Cambridge|authorlink1=József Beck}}{{Cite Positional Games 2014}}''' in [game theory](/source/game_theory) is a kind of a [combinatorial game](/source/combinatorial_game) for two players. It is described by: *X{{snd}}a [finite set](/source/finite_set) of elements. Often ''X'' is called the ''board'' and its elements are called ''positions''. *\mathcal{F}{{snd}}a [family of subsets](/source/family_of_sets) of 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 X are taken while no player wins, the game is considered a draw. The classic example of a positional game is [tic-tac-toe](/source/tic-tac-toe). In it, X contains the 9 squares of the game-board, \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](/source/Hex_(board_game)) and the [Shannon switching game](/source/Shannon_switching_game). For every positional game there are exactly three options: either the first player has a [winning strategy](/source/winning_strategy), or the second player has a winning strategy, or both players have strategies to enforce a draw.''''''{{Rp|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](/source/perfect_information); therefore, in theory it is possible to create the full [game tree](/source/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. == Alternative terminology == Often, the input to a positional game is considered a [hypergraph](/source/hypergraph). In this case: * The elements of X are called ''vertices'' (or ''points''), and denoted by ''V''; * The elements of \mathcal{F} are called ''edges'' (or ''hyperedges''), and denoted by ''E'' or ''H''. ==Variants== There are many variants of positional games, differing in their rules and their winning criteria. === Different winning criteria === ;[Strong positional game](/source/Strong_positional_game) (also called Maker-Maker game): The first player to claim all of the elements of a winning set wins. If the game ends with all elements of the board claimed, but no player has claimed all elements of a winning set, it is a draw. An example is classic [tic-tac-toe](/source/tic-tac-toe). ;[Maker-Breaker game](/source/maker-breaker_game): The two players are called Maker and Breaker. Maker wins by claiming all elements of a winning set. If the game ends with all elements of the board claimed, and Maker has not yet won, then Breaker wins. Draws are not possible. An example is the [Shannon switching game](/source/Shannon_switching_game). ;[Avoider-Enforcer game](/source/Avoider-Enforcer_game): The players are called Avoider and Enforcer. Enforcer wins if Avoider ever claims all of the elements of a winning set. If the game ends with all elements of the board claimed, and Avoider has not claimed a winning set, then Avoider wins. As in maker-breaker games, a draw is not possible. An example is [Sim](/source/Sim_(pencil_game)). ;[Discrepancy game](/source/Discrepancy_game): The players are called Balancer and Unbalancer. Balancer wins if he ensures that in all winning sets, each player has roughly half of the vertices. Otherwise Unbalancer wins. ;[Scoring game](/source/Scoring_game): Comparing at the end the winning sets obtained by the players, whoever has the winning set with the highest score wins, where the score of each winning set is given in the instance. An example is the [Largest Connected Subgraph Game](/source/Largest_Connected_Subgraph_Game), where the positions are the vertices of a graph, the winning sets are connected subgraphs and the winner is the one who obtains the largest connected subgraph. === Different game rules === ;[Waiter-Client game](/source/Waiter-Client_game) (also called Picker-Chooser game): The players are called Waiter and Client. In each turn, Waiter picks two positions and shows them to Client, who can choose one of them. ;[Biased positional game](/source/Biased_positional_game): Each positional game has a ''biased'' variant, in which the first player can take ''p'' elements at a time and the second player can take ''q'' elements at a time (in the unbiased variant, ''p''=''q''=1). == Specific games == The following table lists some specific positional games that were widely studied in the literature. {| class="wikitable" |+ !Name !Positions !Winning sets |- |Multi-dimensional '''[tic-tac-toe](/source/tic-tac-toe)''' |All squares in a multi-dimensional box |All straight lines |- |'''[Shannon switching game](/source/Shannon_switching_game)''' |All edges of a graph |All paths from ''s'' to ''t'' |- |['''Sim'''](/source/Sim_(pencil_game)) |All edges between 6 vertices. |All triangles [losing sets]. |- |'''[Clique game](/source/Clique_game)''' (aka '''Ramsey game''') |All edges of a [complete graph](/source/complete_graph) of size ''n'' |All cliques of size ''k'' |- |'''[Connectivity game](/source/Connectivity_game)''' |All edges of a [complete graph](/source/complete_graph) |All [spanning tree](/source/spanning_tree)s |- |'''[Hamiltonicity game](/source/Hamiltonicity_game)''' |All edges of a [complete graph](/source/complete_graph) |All [Hamiltonian path](/source/Hamiltonian_path)s |- |[Non-planarity game](/source/Non-planarity_game) |All edges of a [complete graph](/source/complete_graph) |All non-planar sub-graphs |- |'''[Arithmetic progression game](/source/Arithmetic_progression_game)''' |The numbers {1,...,n} |All [arithmetic progression](/source/arithmetic_progression)s of size ''k'' |} ==See also== *[Topological game](/source/Topological_game), a generalization of a positional game to [infinite set](/source/infinite_set)s *[Banach–Mazur game](/source/Banach%E2%80%93Mazur_game), a game played on a [topological space](/source/topological_space) by choosing among certain subsets, with winning conditions resembling those of a maker-breaker game ==References== {{Reflist}} * --- Adapted from the Wikipedia article [Positional game](https://en.wikipedia.org/wiki/Positional_game) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Positional_game?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.