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 ( $X$ ) and its family of winning-sets ( ${\mathcal {F}}$ - a family of subsets of $X$ ). 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 to hold a winning-set.

For fixed $X$ and ${\mathcal {F}}$ , 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 ${\mathcal {F}}$ . 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]

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:

$X$ contains all edges of the complete graph on {1,...,N};
${\mathcal {F}}$ 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 an 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

Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.

[kruczek2010-2] 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.

[beck08-3] Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.