Gomoku is the game where Black and White take turns placing stones of their own color, and the winner is the player who first gets five of their own stones in a row. Black moves first.
In Gomoku on an infinite big board, I made the following claim:
If Black can win on a $15\times 15$ board, he can certainly win on an infinite board, since he can pretend to be playing on a $15\times 15$ board, and if White plays outside the imaginary boundary, so much the better for Black.
I am no longer happy with this argument. Here is a counterargument:
Suppose Black pretends to be playing on a $15\times 15$ board, making all his moves inside the imaginary boundary of a $15\times 15$ region. If White has the opportunity to make any five moves outside the imaginary boundary before Black wins inside the boundary, White will win first. Thus if White can find a strategy $S$ for the $15\times 15$ board that delays Black's win long enough for her to pass five times, then she can win on the infinite board by playing $S$ against Black, and using her pass moves to play outside the imaginary boundary.
My idea is that Black's winning strategy might take a long time to execute, say 103 moves, and perhaps pass moves by White only allow Black to speed up his win by a moderate amount; say by passing at the correct times, White can still force Black to take 37 moves to win. Then despite Black's winning strategy for the $15\times 15$ board, White can win on the infinite board if Black does not defend outside the $15\times15$ region.
One of the two arguments must fail. Right now, I think it's the first one that fails. My questions are:
-
Is there some reason that I've overlooked that the notional winning strategy $S$ for White can't exist?
-
If there isn't, does such a strategy exist?
-
Is there any way in general to convert winning strategies on smaller boards to winning strategies on a larger boards?
Best Answer
In József Beck's book Combinatorial Games: Tic-Tac-Toe Theory, he states the following open problems ("unrestricted $5$-in a row" is Gomoku on an infinite board):
There are some relevant counterexamples in the more general setting of "positional games". The following information is from pp. 78-84 of József Beck's book.
A positional game is defined by a hypergraph $(V,E)$ where $V$ is the vertex set (or board) and $E$ is the set of (hyper-)edges (or winning sets), a collection of nonempty finite subsets of $E$. Two players take turns picking (previously unpicked) vertices; the game is won by the first player to succeed in picking all the vertices of a winning set.
The following example, attributed to Fred Galvin, illustrates what Beck calls "the Induced Extra Set Paradox". The board is $V=\{1,2,3,4,5,6,7\}$; the winning sets are $\{1,2,3\},\{1,3,4\},\{1,4,5\},\{1,2,5\},\{4,5,6\},\{4,5,7\},\{6,7\}$. This game is a draw, but it becomes a first-player win if the board is restricted to the subset $\{1,2,3,4\}$ with winning sets $\{1,2,3\},\{1,3,4\},\{1,4,5\},\{1,2,5\}$.
In Galvin's example the hypergraph is non-uniform, meaning that the winning sets are not all the same size. Here is a slightly larger example of the same phenomenon, attributed to Sujith Vijay, where the winning sets are all triples: the board is $V=\{1,2,3,4,5,6,7,8,9\}$, the winning sets are $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,5,6\},\{3,5,7\},\{2,4,8\},\{2,6,9\}$. This game is a draw, but the restriction to the board $\{1,2,3,4,5,6,7\}$ is a first-player win.
Beck states the following open problems concerning generalized Tic-Tac-Toe, analogous to your question 3: