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 172 en The 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 surrealistas 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 n × n tableros, 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 .
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, Go es PSPACE-hard . [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 Go.
Ir con superko no se sabe que esté en PSPACE. Aunque los juegos reales nunca parecen durar más demovimientos, en general no se sabe si hubo un polinomio límite en la duración de los juegos de Go. Si lo hubiera, Go sería PSPACE completo. Tal como está actualmente, podría ser PSPACE-complete, EXPTIME-complete o incluso EXPSPACE-complete.
Regla ko japonesa
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 de 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 de China y EE. UU.
Es un problema abierto cuál es la clase de complejidad de Go bajo la regla superko. Aunque la regla Go with Japanese ko es EXPTIME-complete, tanto el límite inferior como el superior de la prueba EXPTIME-completeness 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 dureza PSPACE de Go no se basa en la regla ko ni en la falta de la regla ko. También se sabe que Go está en EXPSPACE. [4]
Robson [4] demostró que si se agrega la regla superko, es decir, "ninguna posición anterior puede ser recreada", a ciertos juegos de dos jugadores que son EXPTIME-complete, entonces los nuevos juegos serían EXPSPACE-complete. 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-complete, ya que el ajedrez generalizado [5] y las damas [6] son EXPTIME-complete. Sin embargo, este resultado no se aplica a Go. [4]
Complejidad de ciertas configuraciones de 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 difíciles de PSPACE. [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). Tenga 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 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 n 2 posibles posiciones de tablero en un tablero cuadrado con longitud n ; sin embargo, no todos son legales. Tromp y Farnebäck derivaron una fórmula recursiva para posiciones legalesde una placa de rectángulo con longitud m y n . [9] El número exacto dese obtuvo en 2016. [10] También encuentran una fórmula asintótica, dónde , 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 tamaño de placa regular (m = n = 19). A medida que la junta se hace más grande, el porcentaje de puestos que son legales disminuye.
Tamaño de la placa n × n | 3 n 2 | Porcentaje legal | (cargos legales) ( A094777 ) [11] |
---|---|---|---|
1 × 1 | 3 | 33,33% | 1 |
2 × 2 | 81 | 70,37% | 57 |
3 × 3 | 19.683 | 64,40% | 12,675 |
4 × 4 | 43,046,721 | 56,49% | 24,318,165 |
5 × 5 | 847,288,609,443 | 48,90% | 414,295,148,741 |
9 × 9 | 4.43426488243 × 10 38 | 23,44% | 1.03919148791 × 10 38 |
13 × 13 | 4.30023359390 × 10 80 | 8,66% | 3.72497923077 × 10 79 |
19 × 19 | 1.74089650659 × 10 172 | 1,20% | 2.08168199382 × 10 170 |
Complejidad del árbol de 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 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] Walraet y Tromp mejoraron el límite inferior a Googolplex . [13] El número más comúnmente citado para el número de juegos posibles, 10 700 [14] se deriva de una simple permutación de 361 movimientos o 361! = 10 768 . Otra derivación común es suponer N intersecciones y L juego más largo para N L juegos totales. Por ejemplo, 400 se mueve, como se ve en algunos juegos profesionales, serían uno de cada 361 a 400 o 1 × 10 1023 juegos 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.
Tamaño del juego | Tamaño de tablero N (intersecciones) | ¡ N ! | Duración media del juego L | N L | Duración máxima del juego (número de movimientos) | Límite inferior de juegos | Límite superior de juegos |
---|---|---|---|---|---|---|---|
2 × 2 | 4 | 24 | 3 | 64 | 386,356,909,593 [15] | 386,356,909,593 | |
3 × 3 | 9 | 3,6 × 10 5 | 5 | 5,9 × 10 4 | |||
4 × 4 | dieciséis | 2,1 × 10 13 | 9 | 6,9 × 10 10 | |||
5 × 5 | 25 | 1,6 × 10 25 | 15 | 9,3 × 10 20 | |||
9 × 9 | 81 | 5,8 × 10 120 | 45 | 7,6 × 10 85 | |||
13 × 13 | 169 | 4,3 × 10 304 | 90 | 3,2 × 10 200 | |||
19 × 19 | 361 | 1,0 × 10 768 | 200 | 3 × 10 511 | 10 48 | 10 10 48 | 10 10 171 |
21 × 21 | 441 | 2,5 × 10 976 | 250 | 1,3 × 10 661 |
El número total de juegos 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.
Juego más largo L (19 × 19) | ( N ) L | Límite inferior de juegos | Límite superior de juegos | Notas |
---|---|---|---|---|
1 | 361 | 361 | 361 | Las blancas renuncian después del primer movimiento, 361 ignorando toda la simetría incluyendo y = x else (distancias desde la esquina) 10 × 10−10 = 90 90/2 = 45 +10 (sumando x = y puntos de simetría) = 55. |
2 | 722 | 721 | Las negras renuncian después del primer movimiento de las blancas, 721 ignorando toda la simetría, incluida y = x más 19 × 19−19 = 342 342/2 = 171 +19 = 190 - 1 = 189. | |
50 | 2,1 × 10 126 | 7,5 × 10 127 | ||
100 | 1,4 × 10 249 | 5,6 × 10 255 | ||
150 | 6,4 × 10 367 | 4,2 × 10 383 | ||
200 | 1,9 × 10 481 | 3,2 × 10 511 | ||
250 | 8,2 × 10 587 | 2,4 × 10 639 | ||
300 | 2,8 × 10 684 | 7,8 × 10 766 | ||
350 | 3,6 × 10 760 | 1,3 × 10 895 | ||
361 | 1,4 × 10 768 | 1,8 × 10 923 | Juego más largo con 181 piedras negras y 180 blancas. | |
411 | n / A | 1,3 × 10 1051 | Juego profesional más largo [16] | |
500 | n / A | 5,7 × 10 1278 | ||
1000 | n / A | 3,2 × 10 2557 | ||
47 millones | n / A | 10 10 8 | 361 3 movimientos | |
10 48 | n / A | 10 10 48 | 10 10 171 | Juego mas largo |
Por lo tanto, 10 700 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 alrededor de 2+1 ⁄ 4 años, jugando 16 horas al día a un movimiento por segundo, para jugar 47 millones de movimientos.
Ver también
- Complejidad del juego
- Número de Shannon (Ajedrez)
Notas
- ^ Ir Infinitesimals
- ↑ a b Lichtenstein, David; Sipser, Michael (abril de 1980). "Go Is Polynomial-Space Difícil" (PDF) . Revista de la ACM . 27 (2): 393–401. doi : 10.1145 / 322186.322201 .
- ^ a b Robson, John (1983). "La complejidad de Go". Actas del 9º Congreso Mundial de Computación de IFIP sobre procesamiento de información : 413–417.
- ^ a b c Robson, J (1984). Juegos combinatorios con problemas de decisión completos de espacio exponencial . Actas de los fundamentos matemáticos de la informática . Apuntes de conferencias en Ciencias de la Computación. 176 . págs. 498–506. doi : 10.1007 / BFb0030333 . ISBN 978-3-540-13372-8.
- ^ Aviezri Fraenkel y D. Lichtenstein (1981). "Calcular una estrategia perfecta para n × n ajedrez requiere tiempo exponencial en n" . J. Comb. Th. Una . 31 (31): 199–214. doi : 10.1016 / 0097-3165 (81) 90016-9 .
- ^ JM Robson (1984). "N by N checkers es Exptime completo". Revista SIAM de Computación . 13 (2): 252–267. doi : 10.1137 / 0213018 .
- ^ Wolfe, David (2002). Nowakowski, Richard J. (ed.). "Los finales de Go son difíciles de PSPACE" (PDF) . Más juegos sin azar, Instituto de Investigación de Ciencias Matemáticas Publicaciones 42 : 125–136.
- ^ Crâşmaru, Marcel; Tromp, John (2000). Las escaleras son PSPACE-Complete . Computadoras y juegos . Apuntes de conferencias en Ciencias de la Computación. 2063 . Saltador. págs. 241–249. CiteSeerX 10.1.1.24.4665 . doi : 10.1007 / 3-540-45579-5_16 . ISBN 978-3-540-43080-3.
- ^ a b Tromp, J ; Farnebäck, G (2007), Combinatoria de Go , Springer, Berlín, Heidelberg, doi : 10.1007 / 978-3-540-75538-8_8 , ISBN 978-3-540-75537-1
- ^ https://tromp.github.io/go/legal.html 20816819938197998469947863344862770286522453884530548425639456820927419612738015378 525648451698519643 90725991601562812854608988831442712971531931755736620397247064840935
- ^ https://tromp.github.io/go/gostate.pdf
- ^ Allis 1994
- ^ Walraet, M; Tromp, J (2016), A Googolplex of Go Games , Springer, Berlín, Heidelberg, doi : 10.1007 / 978-3-319-50935-8_18 , ISBN 978-3-319-50934-1
- ^ AGA - diez razones principales para jugar Go
- ^ Tromp 1999
- ^ https://homepages.cwi.nl/~aeb/go/misc/gostat.html
Referencias
- AGA. "Diez razones principales para jugar Go" .
- Allis, Victor (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) . Doctor. Tesis, Universidad de Limburg, Maastricht, Holanda. ISBN 978-90-900748-8-7.
- Hearn, Robert A. (2006). "Juegos, rompecabezas y computación" (PDF) .[Doctor. Tesis, MIT.]
- Johnson, George (29 de julio de 1997). "Para probar una computadora potente, juega un juego antiguo" . New York Times .
- Papadimitriou, Christos (1994), Complejidad computacional , Addison Wesley.
- Tromp, John (1999). "Número de partidas 2 × 2 con superko posicional" .
- Tromp, John (2016). "Número de posiciones legales de Go (hasta 19 × 19)" .
- Tromp, John ; Farnebäck, Gunnar (2007). "Combinatoria de Go" .
enlaces externos
- Go y Matemáticas
- Número de posibles resultados de un juego : artículo en la biblioteca de Sensei