Convirtiendo una estrategia ganadora de Gomoku de un tablero pequeño a una estrategia ganadora en un tablero más grande

Question

Gomoku es el juego en el que Negro y Blanco se turnan para colocar piedras de su propio color, y el ganador es el jugador que primero consigue cinco de sus propias piedras en fila. Negro juega primero.

En Gomoku on an infinite big board, hice la siguiente afirmación:

Si Negro puede ganar en un tablero de $15\times 15$, ciertamente puede ganar en un tablero infinito, ya que puede pretender estar jugando en un tablero de $15\times 15$, y si Blanco juega fuera del límite imaginario, tanto mejor para Negro.

No estoy contento con este argumento. Aquí hay un contraargumento:

Supongamos que Negro finge estar jugando en un tablero de $15\times 15$, haciendo todos sus movimientos dentro del límite imaginario de una región de $15\times 15$. Si Blanco tiene la oportunidad de hacer cinco movimientos fuera del límite imaginario antes de que Negro gane dentro del límite, Blanco ganará primero. Así que si Blanco puede encontrar una estrategia $S$ para el tablero de $15\times 15$ que retrase la victoria de Negro el tiempo suficiente para que ella pase cinco veces, entonces puede ganar en el tablero infinito jugando $S$ contra Negro, y usando sus movimientos de pasar para jugar fuera del límite imaginario.

Mi idea es que la estrategia ganadora de Negro podría tardar mucho tiempo en ejecutarse, digamos 103 movimientos, y tal vez los movimientos de pasar de Blanco solo permiten que Negro acelere su victoria en una cantidad moderada; digamos que al pasar en los momentos correctos, Blanco aún puede obligar a Negro a tomar 37 movimientos para ganar. Entonces a pesar de la estrategia ganadora de Negro para el tablero de $15\times 15$, Blanco puede ganar en el tablero infinito si Negro no defiende fuera de la región de $15\times 15.

Uno de los dos argumentos debe fallar. En este momento, creo que es el primero el que fracasa. Mis preguntas son:

1. ¿Hay alguna razón que he pasado por alto por la cual la estrategia ganadora teórica $S$ para Blanco no pueda existir?

2. Si no la hay, ¿existe tal estrategia?

3. ¿Hay alguna manera en general de convertir estrategias ganadoras en tableros más pequeños en estrategias ganadoras en tableros más grandes?

Answer 1

En el libro de József Beck Combinatorial Games: Tic-Tac-Toe Theory, se establecen los siguientes problemas abiertos ("5 en línea ilimitado" es Gomoku en un tablero infinito):

Problema Abierto 4.1. ¿Es cierto que 5 en línea ilimitado es una victoria para el primer jugador?

Problema Abierto 4.2. ¿Es cierto que n en línea ilimitado es un empate para cada n≥6?

Hay algunos contraejemplos relevantes en el contexto más general de "juegos posicionales". La siguiente información es de las páginas 78-84 del libro de József Beck.

Un juego posicional se define por un hipergrafo $(V,E)$ donde $V$ es el conjunto de vértices (o tablero) y $E$ es el conjunto de hiperarcos (o conjuntos ganadores), una colección de subconjuntos finitos no vacíos de $E$. Dos jugadores se turnan eligiendo (previamente no seleccionados) vértices; el juego lo gana el jugador que logre seleccionar todos los vértices de un conjunto ganador.

El siguiente ejemplo, atribuido a Fred Galvin, ilustra lo que Beck llama "la Paradoja del Conjunto Extra Inducido". El tablero es $V=\{1,2,3,4,5,6,7\}$; los conjuntos ganadores son $\{1,2,3\},\{1,3,4\},\{1,4,5\},\{1,2,5\},\{4,5,6\},\{4,5,7\},\{6,7\}$. Este juego es un empate, pero se convierte en una victoria para el primer jugador si el tablero se restringe al subconjunto $\{1,2,3,4\}$ con los conjuntos ganadores $\{1,2,3\},\{1,3,4\},\{1,4,5\},\{1,2,5\}$.

En el ejemplo de Galvin, el hipergrafo es no uniforme, lo que significa que los conjuntos ganadores no tienen todos el mismo tamaño. Aquí hay un ejemplo ligeramente más grande del mismo fenómeno, atribuido a Sujith Vijay, donde los conjuntos ganadores son todos triples: el tablero es $V=\{1,2,3,4,5,6,7,8,9\}$, los conjuntos ganadores son $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,5,6\},\{3,5,7\},\{2,4,8\},\{2,6,9\}$. Este juego es un empate, pero la restricción al tablero $\{1,2,3,4,5,6,7\}$ es una victoria para el primer jugador.

Beck establece los siguientes problemas abiertos relacionados con el Tic-Tac-Toe generalizado, análogos a tu pregunta 3:

Problema Abierto 5.2 ¿Es cierto que, si el juego $n^d$ de Tic-Tac-Toe es una victoria para el primer jugador, entonces el juego $n^D$, donde $D\gt d$, también es una victoria?

Problema Abierto 5.3. ¿Es cierto que, si el juego $n^d$ es un empate, entonces el juego $(n+1)^d$ también es un empate?

Answer 2

Sí, el argumento del robo de estrategia funciona en todos los tamaños de tablero para demostrar que blanco no puede ganar. Estoy de acuerdo en que es posible que negro deba jugar fuera de la original $15 \times 15$ para bloquear a blanco. Estás asumiendo que negro seleccionará al principio un área de $15 \times 15$ para jugar en que será una victoria, pero eso no es necesario. Si el tablero es de $19 \times 19$, se permite a negro jugar en cualquier lugar del tablero. No puedo ver una prueba fácil de que la victoria de negro en $15 \times 15$ demuestre que gana en todos los tableros más grandes. Podría ser que el flujo en el caso de $15 \times 15$ permita a blanco hacer amenazas en un tablero más grande que requiere más movimientos para que negro contraataque de los que blanco tomó para establecer. Eso permitiría que algunos tamaños de tablero mayores que $15 \times 15$ sean un empate, pero de ninguna manera blanco gana.