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 del siglo XI, estimó en sus Dream Pool Essays que el número de posibles posiciones del tablero es de alrededor de 10 172 . En años más recientes, la investigación del juego por parte de John H. Conway condujo al desarrollo de los números surrealistas y contribuyó al desarrollo de la teoría de juegos combinatorios (siendo Go Infinitesimals [1] un ejemplo específico de su uso en Go).
El Go generalizado se juega en tableros n × n , y la complejidad computacional para determinar el ganador en una posición dada de Go generalizado depende fundamentalmente de las reglas ko .
Go está “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 mayor.
Sin ko, Go es PSPACE-hard . [2] Esto se demuestra reduciendo True Quantified Boolean Formula , que se sabe que es PSPACE-completa, a geografía generalizada , a geografía generalizada planar, a geografía generalizada planar con grado máximo 3 y, finalmente, a posiciones Go.
No se sabe si Go con superko está en PSPACE. Aunque las partidas reales parecen no durar nunca más que las jugadas, en general no se sabe si había un límite polinómico para la duración de las partidas de Go. Si lo hubiera, Go sería PSPACE-completo. Tal como está actualmente, podría ser PSPACE-completo, EXPTIME-completo o incluso EXPSPACE-completo.
Las reglas japonesas del ko establecen que solo está prohibido el ko básico, es decir, un movimiento que hace que el tablero vuelva a la situación en la que se encontraba un movimiento antes. Se permiten situaciones repetitivas más largas, lo que potencialmente permite que una partida se repita eternamente, como el triple ko, donde hay tres ko al mismo tiempo, lo que permite un ciclo de 12 movimientos.
Con las reglas ko japonesas, Go es EXPTIME -completo. [3]
La regla superko (también llamada regla superko posicional) establece que está prohibida la repetición de cualquier posición del tablero que haya ocurrido previamente. Esta es la regla ko que se utiliza en la mayoría de los conjuntos de reglas chinos y estadounidenses.
Es un problema abierto cuál es la clase de complejidad de Go bajo la regla superko. Aunque Go con la regla japonesa ko es EXPTIME-completo, tanto los límites inferior como superior de la prueba de completitud EXPTIME de Robson [3] se rompen cuando se agrega la regla superko.
Se sabe que es al menos PSPACE-hard, ya que la prueba en [2] de la PSPACE-hard de Go no se basa en la regla ko, o en la falta de la regla ko. También se sabe que Go está en EXPSPACE. [4]
Robson [4] demostró que si se añade la regla superko, es decir, “no se puede recrear nunca ninguna posición anterior”, a ciertas partidas de dos jugadores que son EXPTIME-completas, las nuevas partidas serían EXPSPACE-completas. 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 de la partida que conduce a una posición podría ser exponencialmente largo.
Como resultado, las variantes superko (movimientos que repiten una posición previa del tablero no están permitidos) del ajedrez generalizado y las damas son EXPSPACE-completos, ya que el ajedrez generalizado [5] y las damas [6] son EXPTIME-completos. Sin embargo, este resultado no se aplica al Go. [4]
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 , ocurre 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-hard. [7]
Esto se demuestra convirtiendo el problema de la fórmula booleana cuantificada , que es PSPACE-completo, en una suma de subjuegos de Go pequeños (con árboles de juego canónicos de tamaño polinomial). Tenga en cuenta que el artículo no demuestra que los finales de Go estén en PSPACE, por lo que podrían no ser PSPACE-completos.
Determinar qué lado gana una carrera de captura de escalera es PSPACE-completo, independientemente de si se aplica la regla del ko japonés o la regla del superko. [8] Esto se demuestra simulando QBF, conocido por ser PSPACE-completo, con escaleras que rebotan alrededor del tablero como rayos de luz.
Dado que cada ubicación en el tablero puede estar vacía, negra o blanca, hay un total de 3 n 2 posibles posiciones del tablero en un tablero cuadrado con longitud n ; sin embargo, no todas son legales. Tromp y Farnebäck derivaron una fórmula recursiva para las posiciones legales de un tablero rectangular con longitud m y n . [9] El número exacto de se obtuvo en 2016. [10] También encuentran una fórmula asintótica , donde , y . Se ha estimado que el universo observable contiene alrededor de 10 80 átomos, mucho menos que el número de posibles posiciones legales de un tablero de tamaño regular (m = n = 19). A medida que el tablero se hace más grande, el porcentaje de posiciones que son legales disminuye.
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 del árbol de juegos de 10 360 . [12] 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] El límite inferior fue mejorado a un googolplex por Walraet y Tromp. [13] El número más comúnmente citado para el número de juegos posibles, 10 700 [14] se deriva de una permutación simple de 361 movimientos o 361! = 10 768 . Otra derivación común es asumir N intersecciones y L juego más largo para N L juegos totales. Por ejemplo, 400 movimientos, como se ve en algunos juegos profesionales, serían uno de 361 400 o 1 × 10 1023 juegos posibles.
El número total de partidas posibles depende tanto del tamaño del tablero como del número de movimientos realizados. Aunque la mayoría de las partidas duran menos de 400 o incluso 200 movimientos, es posible realizar muchas más.
El número total de partidas posibles se puede estimar a partir del tamaño del tablero de varias maneras, algunas más rigurosas que otras. La 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 la partida más larga, N L forma un límite superior. En el artículo de Tromp/Farnebäck se presenta un límite más preciso.
Por lo tanto, 10 700 es una sobreestimación del número de partidas posibles que se pueden jugar en 200 movimientos y una subestimación del número de partidas 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+1 ⁄ 4 años, jugando 16 horas al día a un movimiento por segundo, para realizar 47 millones de movimientos.
{{cite book}}: |journal=ignorado ( ayuda )