Go y matemáticas

El juego de go es uno de los juegos más populares del mundo. Como resultado de sus reglas elegantes y simples, el juego ha sido durante mucho tiempo una inspiración para la investigación matemática. Shen Kuo, un erudito chino en el siglo XI, estimó que el número de posibles posiciones en la junta es de alrededor de 10¹⁷² en Dream Pool Essays. En años más recientes, la investigación del juego por John H. Conway llevó a la invención de los números surreales y contribuyó al desarrollo de la teoría de juegos combinatorios (con Go Infinitesimals^[1]​ siendo un ejemplo específico de su uso en go).

Complejidad computacional

El go generalizado se juega en tableros de n × n, y la complejidad computacional de determinar el ganador en una posición dada del go generalizado depende de manera crucial de las reglas del ko.

El go es "casi" en PSPACE, ya que en el juego normal, los movimientos no son reversibles, y es solo a través de la captura que existe la posibilidad de que se repitan los patrones necesarios para una complejidad más difícil.

Sin ko

Sin ko, el go es PSPACE-difícil.^[2]​ Esto se demuestra reduciendo la fórmula booleana cuantificada verdadera, que se sabe que es PSPACE-completa, a la geografía generalizada, a la geografía generalizada plana, a la geografía generalizada plana con grado máximo 3, finalmente a las posiciones del go.

El go con superko no se sabe que esté en PSPACE. Aunque los juegos reales nunca parecen durar más de ${\displaystyle n^{2}}$ movimientos, en general no se sabe si hay un límite polinómico en la longitud de los juegos de go. Si lo hubiera, el go sería PSPACE-completo. Tal como está actualmente, podría ser PSPACE-completo, EXPTIME-completo o incluso EXPSPACE-completo.

Regla japonesa del ko

Las reglas japonesas del ko establecen que solo el ko básico, es decir, un movimiento que revierte el tablero a la situación anterior, está prohibido. Se permiten situaciones repetitivas más largas, lo que potencialmente permite que un juego se repita para siempre, como el triple ko, donde hay tres kos al mismo tiempo, lo que permite un ciclo de 12 movimientos.

Con las reglas de ko japonesas, Go es EXPTIME-completo.^[3]​

Regla del superko

La regla de superko (también llamada regla de superko posicional) establece que está prohibida la repetición de cualquier posición en el tablero que haya ocurrido previamente. Esta es la regla ko utilizada en la mayoría de los conjuntos de reglas chinos y estadounidenses.

Es un problema abierto cuál es la clase de complejidad del go bajo la regla del superko. Aunque el go con la regla japonesa del ko es EXPTIME-completo, tanto el límite inferior como el superior de la prueba de completitud EXPTIME de Robson^[3]​ se rompen cuando se agrega la regla del superko.

Se sabe que es al menos PSPACE-hard, ya que la prueba^[2]​ de la dureza PSPACE del go no se basa en la regla del ko ni en la falta de la regla del ko. También se sabe que el go está en EXPSPACE.^[4]​

Robson^[4]​ demostró que si se agrega la regla superko, es decir, “nunca se podrá recrear ninguna posición anterior”, a ciertos juegos de dos jugadores que son EXPTIME-completo, entonces los nuevos juegos serían EXPSPACE-completos. Intuitivamente, esto se debe a que se requiere una cantidad exponencial de espacio incluso para determinar los movimientos legales desde una posición, porque el historial del juego que conduce a una posición podría ser exponencialmente largo.

Como resultado, las variantes superko (movimientos que repiten una posición anterior en el tablero no están permitidas) del ajedrez generalizado y las damas son EXPSPACE-completo, ya que el ajedrez generalizado^[5]​ y las damas^[6]​ son EXPTIME-completo. Sin embargo, este resultado no se aplica al go.^[4]​

Complejidad de ciertas configuraciones del go

Un final de go comienza cuando el tablero se divide en áreas que están aisladas de todas las demás áreas locales por piedras vivas, de modo que cada área local tiene un árbol de juego canónico de tamaño polinomial. En el lenguaje de la teoría de juegos combinatorios, sucede cuando un juego de go se descompone en una suma de subjuegos con árboles de juego canónicos de tamaño polinomial.

Con esa definición, los finales de go son PSPACE-difíciles.^[7]​

Esto se demuestra al convertir el problema de la fórmula booleana cuantificada, que es PSPACE completo, en una suma de pequeños subjuegos de go (con árboles de juego canónicos de tamaño polinomial). Téngase en cuenta que el documento no prueba que los finales de go estén en PSPACE, por lo que es posible que no estén completos en PSPACE.

Determinar qué lado gana una carrera de captura de escalera es PSPACE-completo, ya sea que la regla japonesa de ko o la regla superko esté en su lugar.^[8]​ Esto se demuestra mediante la simulación de QBF, conocido por ser PSPACE-completo, con escaleras que rebotan alrededor de la tabla como rayos de luz.

Posiciones legales

Dado que cada ubicación en el tablero puede estar vacía, negra o blanca, hay un total de 3ⁿ² posibles posiciones de tablero en un tablero cuadrado con longitud n ; sin embargo, no todos son legales. John Tromp y Farnebäck derivaron una fórmula recursiva para posiciones legales ${\displaystyle L(m,n)}$ de un tablero de tamaño m y n.^[9]​ El número exacto de ${\displaystyle L(19,19)}$ se obtuvo en 2016.^[10]​ También encuentran una fórmula asintótica ${\displaystyle L\approx AB^{m n}C^{mn}}$, donde ${\displaystyle A\approx 0.8506399258457145}$, ${\displaystyle B\approx 0.96553505933837387}$ y ${\displaystyle C\approx 2.975734192043357249381}$. Se ha estimado que el universo observable contiene alrededor de 10⁸⁰ átomos, mucho menos que el número de posibles posiciones legales para el tablero de tamaño regular (m=n=19). A medida que el tablero se hace más grande, el porcentaje de posiciones legales disminuye.

Complejidad del árbol del juego

El científico informático Victor Allis señala que los juegos típicos entre expertos duran alrededor de 150 movimientos, con un promedio de alrededor de 250 elecciones por movimiento, lo que sugiere una complejidad de árbol de juego de 10³⁶⁰.^[13]​ Para el número de juegos teóricamente posibles , incluidos los juegos imposibles de jugar en la práctica, Tromp y Farnebäck dan límites inferior y superior de 10^{10^48} y 10^{10^171} respectivamente.^[9]​ Walraet y Tromp mejoraron el límite inferior a Googolplex.^[14]​ El número más comúnmente citado para el número de juegos posibles, 10^{700 [15]}​ se deriva de una simple permutación de 361 movimientos o 361! = 10⁷⁶⁸. Otra derivación común es suponer N intersecciones y L juego más largo para N^L juegos totales. Por ejemplo, 400 jugadas, como se ve en algunas partidas profesionales, serían una de cada 361⁴⁰⁰ o 1×10¹⁰²³ partidas posibles.

El número total de juegos posibles es una función tanto del tamaño del tablero como del número de jugadas jugadas. Si bien la mayoría de los juegos duran menos de 400 o incluso 200 movimientos, muchos más son posibles.

El número total de partidas posibles se puede estimar a partir del tamaño del tablero de varias formas, algunas más rigurosas que otras. El más simple, una permutación del tamaño del tablero, (N)_L, no incluye capturas y posiciones ilegales. Tomando N como el tamaño del tablero (19×19=361) y L como el juego más largo, N^L forma un límite superior. Un límite más preciso se presenta en el artículo de Tromp/Farnebäck.

10⁷⁰⁰ es una sobreestimación del número de juegos posibles que se pueden jugar en 200 movimientos y una subestimación del número de juegos que se pueden jugar en 361 movimientos. Dado que hay alrededor de 31 millones de segundos en un año, se necesitarían aproximadamente 2¹⁄₄ años, jugando 16 horas al día a un movimiento por segundo, para jugar 47 millones de movimientos.

Véase también

• Complejidad en los juegos
• Número de Shannon

Notas

Referencias

• AGA. «Top Ten Reasons to Play Go». 
• Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7. 
• Hearn, Robert A. (2006). «Games, Puzzles, and Computation».  [Ph.D. Thesis, MIT.]
• Johnson, George (29 de julio de 1997). «To Test a Powerful Computer, Play an Ancient Game». New York Times. 
• Papadimitriou, Christos (1994), Computational Complexity, Addison Wesley.
• Tromp, John (1999). «Number of 2×2 games with positional superko». 
• Tromp, John (2016). «Number of legal Go positions (up to 19×19)». 
• Tromp, John; Farnebäck, Gunnar (2007). «Combinatorics of Go». 

Enlaces externos

• Go and Mathematics
• Number of possible outcomes of a game - artículo en Sensei's Library