# Strong positional game

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Strong_positional_game
> Markdown URL: https://mediated.wiki/source/Strong_positional_game.md
> Source: https://en.wikipedia.org/wiki/Strong_positional_game
> Source revision: 1337527047
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Type of sequential game}}
A '''strong positional game''' (also called '''Maker-Maker game''') is a kind of [positional game](/source/positional_game).<ref name=":0">{{Cite Positional Games 2014}}</ref>{{Rp|9–12}} Like most positional games, it is described by its set of ''positions'' (<math>X</math>) and its family of ''winning-sets'' (<math>\mathcal{F}</math>- a  [family of subsets](/source/Family_of_sets) of <math>X</math>). It is played by two players, called First and Second, who alternately take previously untaken positions.

In a strong positional game, the winner is the first player who holds all the elements of a winning-set. If all positions are taken and no player wins, then it is a draw. Classic [Tic-tac-toe](/source/Tic-tac-toe) is an example of a strong positional game.

== First player advantage ==
In a strong positional game, Second cannot have a winning strategy. This can be proved by a [strategy-stealing argument](/source/strategy-stealing_argument): if Second had a winning strategy, then First could have stolen it and win too, but this is impossible since there is only one winner.<ref name=":0" />{{Rp|9}} Therefore, for every strong-positional game there are only two options: either First has a winning strategy, or Second has a drawing strategy.

An interesting corollary is that, if a certain game does not have draw positions, then First always has a winning strategy.

== Comparison to Maker-Breaker game ==
Every strong positional game has a variant that is a [Maker-Breaker game](/source/Maker-Breaker_game). In that variant, only the first player ("Maker") can win by holding a winning-set. The second player ("Breaker") can win only by preventing Maker from holding a winning-set.

For fixed <math>X</math> and <math>\mathcal{F}</math>, the strong-positional variant is strictly harder for the first player, since in it, he needs to both "attack" (try to get a winning-set) and "defend" (prevent the second player from getting one), while in the maker-breaker variant, the first player can focus only on "attack". Hence, ''every winning-strategy of First in a strong-positional game is also a winning-strategy of Maker in the corresponding maker-breaker game''.  The opposite is not true. For example, in the maker-breaker variant of Tic-Tac-Toe, Maker has a winning strategy, but in its strong-positional (classic) variant, Second has a drawing strategy.<ref name="kruczek2010">{{cite journal|last=Kruczek|first=Klay|author2=Eric Sundberg|year=2010|title=Potential-based strategies for tic-tac-toe on the integer latticed with numerous directions|journal=[The Electronic Journal of Combinatorics](/source/The_Electronic_Journal_of_Combinatorics)|volume=17|pages=R5}}</ref>

Similarly, the strong-positional variant is strictly easier for the second player: ''every winning strategy of Breaker in a maker-breaker game is also a drawing-strategy of Second in the corresponding strong-positional game'', but the opposite is not true.

=== The extra-set paradox ===
Suppose First has a winning strategy. Now, we add a new set to <math>\mathcal{F}</math>. Contrary to intuition, it is possible that this new set will now destroy the winning strategy and make the game a draw. Intuitively, the reason is that First might have to spend some moves to prevent Second from owning this extra set.'''<ref name="beck08">{{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|author-link1=József Beck}}</ref><ref>{{Cite report |author=Christian Vogt |date=2025-07-14 |title=Towards Understanding the Extra Set Paradox |url=https://www.researchgate.net/publication/393648037_Towards_Understanding_the_Extra_Set_Paradox}}</ref>'''

The extra-set paradox does not appear in Maker-Breaker games.

== Examples ==

=== The clique game ===
The '''clique game''' is an example of a strong positional game. It is parametrized by two integers, n and N. In it:

* <math>X</math> contains all edges of the [complete graph](/source/complete_graph) on {1,...,N};
* <math>\mathcal{F}</math> contains all [cliques](/source/Clique_(graph_theory)) of size n.

According to [Ramsey's theorem](/source/Ramsey's_theorem), there exists some number R(n,n) such that, for every N > R(n,n), in every two-coloring of the complete graph on {1,...,N}, one of the colors must contain a clique of size n.

Therefore, by the above corollary, when N > R(n,n), First always has a winning strategy.<ref name=":0" />{{Rp|10}}

=== Multi-dimensional tic-tac-toe ===
Consider the game of tic-tac-toe played in a ''d''-dimensional [cube](/source/cube) of length ''n''. By the [Hales–Jewett theorem](/source/Hales%E2%80%93Jewett_theorem), when ''d'' is large enough (as a function of ''n''), every 2-coloring of the cube-cells contains a monochromatic geometric line.

Therefore, by the above corollary, First always has a winning strategy.

== Open questions ==
Besides these existential results, there are few constructive results related to strong-positional games. For example, while it is known that the first player has a winning strategy in a sufficiently large clique game, no specific winning strategy is currently known.<ref name=":0" />{{Rp|11–12}}

== References ==
{{Reflist}}

Category:Positional games

---
Adapted from the Wikipedia article [Strong positional game](https://en.wikipedia.org/wiki/Strong_positional_game) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Strong_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.