Determinación de la jugada ganadora en juegos de tablero

Determinar si un juego de mesa tiene una "jugada ganadora forzada" (o una jugada que fuerza el empate) pertenece, en matemáticas y ciencias de la computación, al ámbito de la Teoría de Juegos Combinatorios (Combinatorial Game Theory). Para determinar y encontrar una jugada ganadora forzada, generalmente es necesario examinar las propiedades del juego y aplicar los teoremas y algoritmos matemáticos correspondientes.

A continuación, se presentan las teorías y métodos comunes para determinar y demostrar si un juego de mesa tiene una jugada ganadora forzada:

1. Confirmar si el juego cumple las condiciones previas del "Teorema de Zermelo"

Antes de discutir una estrategia ganadora, primero hay que confirmar si este juego de mesa pertenece a la categoría de "juego finito, de dos jugadores, de suma cero y de información perfecta".

• Dos jugadores: Solo hay dos jugadores.
• Suma cero (o con resultado de victoria/derrota/empate): La victoria de uno implica la derrota del otro, no hay doble ganancia.
• Información perfecta: No hay información oculta (como cartas boca abajo en el póker), ambos jugadores pueden ver todo el estado del tablero.
• Determinista: No hay elementos aleatorios como lanzar dados.
• Finito: El juego termina en un número finito de movimientos, sin ciclos infinitos.

El Teorema de Zermelo (Zermelo's Theorem) establece: Para cualquier juego que cumpla las condiciones anteriores, si ambos jugadores adoptan la estrategia óptima, necesariamente hay un resultado definido:

1. El primer jugador gana;
2. El segundo jugador gana;
3. Ambos empatan (si las reglas lo permiten, como en el ajedrez o el tres en raya).

Es decir, siempre que se cumplan estas condiciones (como en el ajedrez, el go, el gomoku, el reversi, etc.), en teoría debe existir alguna jugada ganadora o que garantiza no perder (asegurar el empate). Ahora el punto clave es "cómo determinar cuál es" y "cómo encontrarla".

2. Búsqueda exhaustiva y deducción inversa (expansión del árbol de juego)

Para juegos con un espacio de estados pequeño, se pueden enumerar todas las situaciones posibles y generar un "árbol de juego".

• Método (inducción hacia atrás): Comenzar desde el estado final del juego (pérdida, victoria, empate) y retroceder hasta la posición inicial.
• Algoritmo (algoritmo Minimax): Asumir que ambos jugadores nunca cometen errores; el primer jugador siempre elige el movimiento más favorable para sí mismo (Max), y el segundo jugador siempre elige el movimiento que más perjudica al primero (Min).
• Aplicación:
  • Tres en raya (Tic-Tac-Toe): El espacio de estados es extremadamente pequeño, es fácil deducir que bajo el juego óptimo de ambos, el resultado es empate.
  • Cuatro en línea (Connect Four): Ya ha sido completamente resuelto por computadora, demostrando que el primer jugador gana.

3. Mecanismo de robo de estrategia (Strategy-Stealing Argument)

Este es un método de prueba de existencia muy ingenioso (por contradicción). Puede demostrar que el primer jugador gana, pero no dice cómo hacerlo específicamente.

• Lógica: Supongamos que el segundo jugador tiene una estrategia ganadora. Entonces, en el primer movimiento, el primer jugador hace un movimiento cualquiera, y luego "roba" la estrategia ganadora del segundo jugador, actuando como si fuera el segundo jugador. Si en este juego, tener un movimiento extra siempre es beneficioso y nunca perjudicial, entonces el primer jugador, siguiendo la estrategia ganadora del segundo, seguramente ganará. ¡Esto contradice la suposición de que "el segundo jugador gana"!
• Conclusión: En este tipo de juegos, dado que es imposible que el segundo jugador gane y no hay empate, entonces necesariamente el primer jugador gana.
• Aplicación:
  • Hex (Hex): Las reglas no permiten el empate, y colocar una ficha extra nunca es perjudicial, por lo que el matemático Nash utilizó este método para demostrar que Hex es una victoria para el primer jugador.
  • Gomoku sin restricciones (Gomoku): También se demostró que el primer jugador gana (más tarde, las computadoras encontraron jugadas ganadoras específicas, lo que llevó a la introducción de "restricciones" en el gomoku para equilibrar el juego).

4. Buscar simetría (Symmetry / Pairing Strategy)

Si el tablero tiene algún tipo de simetría y las reglas del juego lo permiten, un jugador puede obtener una estrategia ganadora "imitando" los movimientos del oponente.

• Ejemplo (juego de las monedas): En una mesa redonda, los jugadores colocan monedas planas por turno; quien no pueda colocar una, pierde. El primer jugador solo necesita colocar la primera moneda en el centro exacto de la mesa, y luego, sin importar dónde coloque el segundo jugador su moneda, el primero coloca la suya en la posición simétrica respecto al centro. Esta estrategia garantiza que el primer jugador gana.

5. Teorema de Sprague-Grundy (para juegos combinatorios imparciales)

Si el juego es "imparcial" (Impartial Game) — es decir, para la misma posición, los movimientos legales disponibles y las reglas son exactamente los mismos sin importar de quién sea el turno (por ejemplo, el juego de "recoger piedras" Nim) — entonces se puede usar el teorema SG.

• Método: Convertir cualquier posición compleja en un juego Nim equivalente (calculando el valor de la función SG / suma XOR).
• Conclusión: Si la Nim-Sum (o valor SG) de la posición inicial no es cero, el primer jugador gana; si es cero, el segundo jugador gana.

Resumen

• En teoría: Siempre que sea un juego finito, de dos jugadores, de información perfecta y sin suerte, debe existir una estrategia perfecta (ganar o empatar).
• Cómo encontrarla:
  1. Tablero muy pequeño: deducción manual hacia atrás.
  2. Modelo matemático (como el juego de las piedras): calcular el valor SG o buscar simetría.
  3. Propiedades especiales: usar "robo de estrategia" para demostrar que el primer jugador gana.
  4. Tablero enorme (como el go o el ajedrez): actualmente, humanos y IA solo pueden calcular una "solución óptima" que se acerca infinitamente a la victoria, pero en el sentido matemático riguroso, para estos juegos complejos, si es "el primer jugador gana" o "empate forzado", la capacidad de cómputo actual aún no puede realizar una enumeración exhaustiva de todo el juego, por lo que es una conclusión desconocida.

Al discutir la estrategia ganadora del gomoku, primero hay que aclarar una premisa absoluta: aquí se habla del gomoku tradicional "sin restricciones" (gomoku libre).

En el caso sin restricciones, el primer jugador (negras) tiene una estrategia ganadora. Esta es también la razón por la que las competiciones modernas y oficiales de gomoku (renju) deben introducir "restricciones para las negras" (como la restricción de tres-tres, cuatro-cuatro, y línea larga) y complejas reglas de apertura (como la regla Yamaguchi), cuyo objetivo es romper esta situación de victoria forzada para las negras y hacer que el juego sea más equilibrado.

A continuación, se presentan los detalles específicos de la estrategia ganadora del gomoku sin restricciones y el proceso de su descubrimiento:

I. ¿Cuál es la estrategia ganadora del gomoku?

La estrategia ganadora del gomoku no consiste en memorizar un "repertorio de aperturas" fijo y secuencial, porque las posiciones de defensa del oponente pueden ser miles. La estrategia ganadora es esencialmente un sistema táctico que utiliza la "iniciativa absoluta" para presionar continuamente al oponente, formando finalmente múltiples amenazas (que no se pueden defender simultáneamente).

Específicamente, la estrategia ganadora de las negras se basa en los siguientes puntos clave:

1. Elección de la apertura:
   En un tablero de 15×15, las negras juegan su primer movimiento en el tengen (centro). Si después de que las blancas defienden en el segundo movimiento, las negras eligen ciertas formaciones específicas en su tercer movimiento (como las aperturas "Flor de Luna" (Hana-getsu), "Ola de Luna" (Pu-getsu)), las negras pueden garantizar la victoria.
2. Táctica central: VCT y VCF
   • VCF (Victoria por Cuatro Continuos - Victory by Continuous Four): Cada movimiento de las negras es un "cuatro en línea" (las blancas deben defender apretadamente). En el proceso continuo de hacer cuatros en línea, las piezas negras se conectan imperceptiblemente, formando finalmente un golpe letal (como un cuatro-tres).
   • VCT (Victoria por Amenazas Continuas - Victory by Continuous Threats): Cada movimiento de las negras es un "tres vivo" o un "cuatro en línea", obligando a las blancas a solo poder bloquear pasivamente, sin poder contraatacar.
3. Crear puntos de cruce (preparar el mate):
   A través del ataque continuo mencionado, el objetivo final de las negras es crear en el tablero una situación de "doble tres", "doble cuatro" o "cuatro-tres". Dado que las blancas solo pueden defender un punto a la vez, ante múltiples amenazas, inevitablemente no podrán defender todas, y las negras ganarán.

II. ¿Cómo se descubrió y demostró esta estrategia ganadora?

1. Acumulación de experiencia e intuición (etapa humana temprana)

Durante cientos de años, los maestros del gomoku ya habían descubierto en la práctica que la ventaja del primer jugador era enorme. Los japoneses ya a finales del siglo XIX eran claramente conscientes de que, si no se limitaba, un jugador de negras de alto nivel era casi invencible. Por lo tanto, gradualmente evolucionaron las reglas del "renju" con restricciones. Pero en ese momento, la victoria forzada del primer jugador era solo un "consenso empírico", no una prueba rigurosa calculada.

2. Prueba matemática de existencia: Robo de estrategia (Strategy-Stealing)

Un matemático puede demostrar mediante un argumento lógico llamado "robo de estrategia" que el gomoku sin restricciones es una victoria forzada para el primer jugador.
La lógica es simple: Supongamos que el segundo jugador (blancas) tiene un método ganador. Entonces, las negras juegan su primer movimiento en cualquier lugar, y luego fingen ser las blancas (tratando esa primera pieza negra como si no existiera o fuera un movimiento extra) y adoptan el método ganador de las blancas. En el gomoku, tener una pieza propia extra en el tablero siempre es beneficioso y nunca perjudicial. Por lo tanto, las negras pueden ganar. Esto contradice nuestra suposición de que "el segundo jugador gana".
Por lo tanto, el gomoku sin restricciones o es un empate, o el primer jugador gana. Dado que es extremadamente difícil llenar el tablero de gomoku hasta el empate, la conclusión apunta a que el primer jugador gana. Pero esto es solo teoría, no proporciona movimientos específicos.

3. Resolución completa por computadora (1992, L. Victor Allis)

El verdadero "finalizador" de la estrategia ganadora del gomoku fue el científico informático holandés L. Victor Allis.

En 1992, mientras escribía su tesis doctoral, creó un programa de computadora llamado Victoria.

• Su método: El árbol de juego del gomoku es extremadamente grande; la búsqueda exhaustiva tradicional (como enumerar el tres en raya) era imposible en ese entonces. Allis incorporó ingeniosamente el conocimiento humano del gomoku (es decir, los algoritmos VCF, VCT y la búsqueda de dobles amenazas mencionados anteriormente) en el sistema, inventando un algoritmo basado en la "búsqueda por número de pruebas (Proof-number search)".
• Su resultado: El programa logró enumerar y calcular con éxito cada rama clave del gomoku sin restricciones en un tablero de 15×15, demostrando por primera vez en la historia humana, no solo que las negras ganan, sino que también calculó el camino ganador específico. También demostró que, incluso bajo reglas con restricciones de apertura específicas, ciertas aperturas siguen siendo ganadoras para las negras.

Resumen:
La victoria forzada del primer jugador en el gomoku fue un consenso empírico de los jugadores humanos durante milenios, y finalmente fue resuelta exhaustivamente en 1992 por un científico informático mediante un algoritmo diseñado específicamente. Por lo tanto, el gomoku sin restricciones se conoce en el campo de las ciencias de la computación como un "juego débilmente resuelto (Weakly Solved Game)" — es decir, siempre que las negras no cometan errores, sin importar cómo defiendan las blancas, las negras tienen una ruta de código que garantiza la victoria.

Antes de presentar qué otros juegos han sido resueltos, primero aclaremos los tres niveles de definición de "resuelto (Solved)" en ciencias de la computación, lo que ayudará a una mejor comprensión:

1. Ultradébilmente resuelto (Ultra-weakly solved): Solo se demuestra matemáticamente quién ganará (o si hay empate), pero no se conocen los movimientos específicos (como el "robo de estrategia" mencionado en la respuesta anterior).
2. Débilmente resuelto (Weakly solved): La computadora ha encontrado una ruta específica de victoria (o empate forzado) desde el estado inicial del juego. Siguiéndola, no se puede perder, pero si las piezas se colocan en una posición extraña de medio juego, la computadora podría no conocer la solución óptima.
3. Fuertemente resuelto (Strongly solved): Sin importar en qué posición legal de medio juego se encuentre el tablero, la computadora conoce la solución absolutamente óptima (como en el tres en raya).

A continuación, se presentan algunos juegos famosos que han sido débilmente resueltos (e incluso fuertemente resueltos), así como juegos que aún no han sido resueltos.

---

I. Juegos famosos que ya han sido "resueltos"

Además del gomoku sin restricciones, hay otros juegos de mesa famosos que han sido completamente descifrados por computadoras:

1. Cuatro en línea (Connect Four)

• Resultado de la resolución: Victoria del primer jugador (débilmente resuelto).
• Proceso de resolución: El mismo científico informático que resolvió el gomoku, L. Victor Allis, en 1988 (casi simultáneamente e independientemente con otro matemático, James Dow Allen) resolvió el Cuatro en línea. Siempre que el primer jugador coloque su primera ficha en la columna central y adopte una estrategia perfecta, el primer jugador gana. Si la coloca en las columnas adyacentes al centro, es empate; si la coloca en el borde, el segundo jugador gana.

2. Damas (Checkers / Draughts)

• Resultado de la resolución: Empate forzado bajo juego perfecto (débilmente resuelto).
• Proceso de resolución: Este fue un hito importante y sensacional. El profesor Jonathan Schaeffer de la Universidad de Alberta, Canadá, lideró un equipo que desarrolló el programa Chinook. Calcularon durante 18 años enteros (de 1989 a 2007), enumerando $5 \times 10^{20}$ (500 mil millones de millones) de posiciones de final, y finalmente en 2007 anunciaron en la revista Science que las Damas habían sido resueltas por completo. Si ambos jugadores no cometen errores, el resultado es necesariamente un empate.

3. Molino (Nine Men's Morris)

• Resultado de la resolución: Empate forzado bajo juego perfecto (fuertemente resuelto).
• Proceso de resolución: Este antiguo juego de mesa (que aparece en muchas películas clásicas occidentales) fue fuertemente resuelto en 1993 por Ralph Gasser. Demostró que, ya sea en la apertura o en cualquier posición de medio juego, si ambos jugadores no se equivocan, el resultado es inevitablemente un empate.

4. Reversi / Othello (Reversi / Othello) — ¡El avance más reciente!

• Resultado de la resolución: Empate forzado bajo juego perfecto (débilmente resuelto).
• Proceso de resolución: ¡Este es un avance muy reciente! En octubre de 2023, el investigador japonés Hiroki Takizawa, utilizando la potencia de cálculo de supercomputadoras modernas y algoritmos optimizados, tras varios días de cálculo, anunció oficialmente que el Reversi en tablero estándar de 8×8 había sido débilmente resuelto. La conclusión es: bajo estrategias perfectas de ambos jugadores, la puntuación final del juego es un empate directo.

---

II. Juegos que "no han sido resueltos" hasta hoy

Podrías preguntarte: ya que la IA es tan fuerte (como AlphaGo), ¿no deberían estar todos los juegos de mesa resueltos?
La respuesta es: no.

"La IA vence a los humanos" y "resolver matemáticamente un juego" son conceptos completamente diferentes. La IA vence a los humanos porque, mediante cálculos probabilísticos, puede encontrar jugadas excelentes con una tasa de victoria del 99%; mientras que "resolver" exige una enumeración exhaustiva del 100% y demostrar el resultado sin duda alguna.

Debido a que la "complejidad del espacio de estados" (número de estados posibles del tablero) y la "complejidad del árbol de juego" (número de todas las ramas posibles de movimientos) de los siguientes juegos son demasiado grandes, superando con creces la capacidad de cómputo total de todas las supercomputadoras existentes, e incluso de las de los próximos siglos.

1. Ajedrez (Chess)

• Por qué no ha sido resuelto: El ajedrez tiene aproximadamente $10^{43}$ estados legales, y el número de partidas posibles es de hasta $10^{120}$ (este número se conoce como el "Número de Shannon"). El número total de átomos en el universo observable es solo de aproximadamente $10^{80}$. Incluso si se convirtieran todos los átomos del universo en computadoras, no se podrían calcular todas las variaciones del ajedrez.
• Estado actual: Aunque Deep Blue y motores actuales como Stockfish aplastan a todos los maestros humanos, el ajedrez sigue siendo matemáticamente desconocido. No sabemos si una partida perfecta de ajedrez resulta en victoria de las blancas (primer jugador) o en empate (la mayoría de los expertos se inclinan por el empate).

2. Ajedrez chino (Xiangqi)

• Por qué no ha sido resuelto: El tablero del ajedrez chino es más grande y tiene más espacio de movimiento; su complejidad de espacio de estados es de aproximadamente $10^{48}$, varios órdenes de magnitud mayor que la del ajedrez occidental.
• Estado actual: Similar al ajedrez, los programas de ajedrez chino de primer nivel (como Wang Zhong Wang, Pi Ka Yu, etc.) no dan tregua a los humanos, pero en el sentido matemático riguroso, aún no ha sido resuelto.

3. Go (Go)

• Por qué no ha sido resuelto: El Go es el "rey de la complejidad" entre los juegos de tablero. En el tablero estándar de 19×19, la complejidad del espacio de estados alcanza la asombrosa cifra de $10^{170}$, y la complejidad del árbol de juego llega a $10^{360}$. Frente al Go, la complejidad del ajedrez es insignificante.
• Estado actual: Incluso el revolucionario AlphaGo y su sucesor AlphaZero no han "resuelto" el Go. Simplemente utilizan redes neuronales para establecer una "valoración intuitiva" extremadamente fuerte, sabiendo cómo jugar para maximizar las probabilidades de ganar en la mayoría de las posiciones. Pero si se le pidiera a AlphaGo que demostrara "si el Go es una victoria forzada para el primer jugador o un empate", no podría hacerlo.

Resumen

• Si la complejidad de un juego es inferior a $10^{20}$ (mil millones de millones), como las Damas, el Gomoku, el Reversi, los humanos pueden usar supercomputadoras para "resolverlo" hasta el final.
• Una vez que la complejidad supera $10^{40}$ (es decir, el Ajedrez, el Ajedrez chino, el Go), la resolución exhaustiva se vuelve físicamente imposible. Para estos juegos, solo podemos usar IA para acercarnos infinitamente a esa "verdad perfecta", pero quizás nunca podamos tocarla por completo.

¡Esta pregunta es muy aguda! El razonamiento que acabas de mencionar es completamente correcto: al expandir el tablero hasta el infinito, el número de situaciones se vuelve infinito, y es absolutamente imposible que una computadora "enumere" todos los movimientos.

Sin embargo, el gomoku sin restricciones en un tablero infinito sigue estando "resuelto" matemática y lógicamente, y la conclusión sigue siendo: el primer jugador (negras) gana.

Ya que no se puede enumerar, ¿cómo se resuelve? Aquí se utiliza una lógica de "reducción de dimensionalidad" muy simple pero también muy contundente:

1. Estrategia de "acotar el territorio" (prueba anidada)

En 1992, la computadora ya había demostrado exhaustivamente que, en un tablero limitado de 15×15, las negras tienen una ruta ganadora.

Entonces, en un tablero infinito, ¿cómo ganan las negras?
Muy simple: Las negras solo necesitan dibujar un cuadrado invisible de 15×15 en el centro del tablero infinito, y luego seguir exactamente el mismo método ganador del tablero de 15×15.

Mientras las blancas jueguen dentro de este cuadrado, las negras responden según el programa ganador conocido; si las blancas juegan a diez mil kilómetros de distancia, en el espacio infinito, las negras simplemente lo ignoran y forman cinco en línea dentro de su propia área de 15×15. Dado que el método ganador del gomoku es "presionar paso a paso" (hacer cuatros en línea y tres vivos continuos), las blancas no tienen tiempo libre para ir a molestar fuera; deben permanecer en el campo de batalla principal defendiendo.

2. Cuanto más grande es el tablero, más favorable es para el primer jugador

En el gomoku, el "borde del tablero" en realidad ayuda al bando perdedor (las blancas) a defender.
Cuando las negras atacan, su mayor miedo es que las piezas se queden "sin espacio" antes de completar las cinco.
Dado que las negras, en un espacio reducido de 15×15 donde es fácil quedarse sin espacio, pueden lograr una victoria del 100%; entonces, en un tablero infinito, las negras ya no tienen la preocupación de quedarse sin espacio, y ganar será aún más fácil.

Resumen:
El gomoku infinito no se resuelve mediante la capacidad de cómputo infinita de una computadora, sino mediante una anidación de lógica matemática humana. Siempre que se pueda ganar en un tablero de 15×15, en cualquier tablero de tamaño mayor que este (incluso infinito), el primer jugador seguramente podrá ganar.