Strong positional game
Strong positional game
A strong positional game (also called Maker-Maker game) is a kind of positional-game. 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 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 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.
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.***'
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 on {1,...,N};
- <math>\mathcal{F}</math> 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.
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.