Strong positional game
A strong positional game (also called Maker-Maker game) is a kind of positional game.[1]: 9–12 Like most positional games, it is described by its set of positions () and its family of winning-sets (- a family of subsets of ). 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 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: 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.[1]: 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. 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 and , 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.[2]
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 . 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.[3][4]
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:
- contains all edges of the complete graph on {1,...,N};
- contains all cliques of size n.
According to 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.[1]: 10
Multi-dimensional tic-tac-toe
Consider the game of tic-tac-toe played in a d-dimensional cube of length n. By the Hales–Jewett 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.[1]: 11–12
References
- ^ a b c d Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
- ^ Kruczek, Klay; Eric Sundberg (2010). "Potential-based strategies for tic-tac-toe on the integer latticed with numerous directions". The Electronic Journal of Combinatorics. 17: R5.
- ^ Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.
- ^ Christian Vogt (2025-07-14). Towards Understanding the Extra Set Paradox (Report).
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.