Hispanopedia Wiki
Articulo de referencia

¡Vamos, matemáticas!

El juego de Go es uno de los más populares del mundo. Gracias a sus reglas elegantes y sencillas, ha sido durante mucho tiempo fuente de inspiración para la investigación matemá...

Hispanopedia WikiContenido en espanolLectura gratuita

El juego de Go es uno de los más populares del mundo. Gracias a sus reglas elegantes y sencillas, ha sido durante mucho tiempo fuente de inspiración para la investigación matemática . Shen Kuo , un erudito chino del siglo XI, estimó en sus Ensayos sobre la Piscina de los Sueños que el número de posiciones posibles en el tablero ronda las 10¹⁷² . En años más recientes, la investigación del juego realizada por John H. Conway condujo al desarrollo de los números surrealistas y contribuyó al desarrollo de la teoría combinatoria de juegos (siendo los infinitesimales de Go [ 1 ] 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 crucialmente de las reglas ko .

El Go está "casi" en PSPACE , ya que en el juego normal los movimientos no son reversibles, y solo a través de la captura existe la posibilidad de los patrones repetitivos necesarios para una mayor complejidad.

Sin ko

Sin ko, Go es PSPACE-difícil . [ 2 ] Esto se demuestra reduciendo la Fórmula Booleana Cuantificada Verdadera , 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 de Go.

Regla japonesa ko

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

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

Regla de Superko

La regla superko (también llamada regla superko posicional) prohíbe repetir cualquier posición del tablero que ya se haya dado. Esta es la regla ko que se utiliza en la mayoría de los reglamentos chinos y estadounidenses.

Es un problema abierto determinar la clase de complejidad del Go bajo la regla superko. Aunque el Go con la regla ko japonesa 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-difícil, ya que la prueba en [ 2 ] de la PSPACE-dificultad de Go no se basa en la regla ko, o en la ausencia 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, «ninguna posición anterior puede recrearse», a ciertos juegos de dos jugadores que son EXPTIME-completos, 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 puede ser exponencialmente largo.

Como resultado, las variantes superko (no se permiten movimientos que repitan una posición anterior del tablero) del ajedrez y las damas generalizadas son EXPSPACE-completas, ya que el ajedrez [ 5 ] y las damas [ 6 ] generalizadas son EXPTIME-completas. Sin embargo, este resultado no se aplica al Go. [ 4 ]

Complejidad de ciertas configuraciones de Go

Un final de partida de Go comienza cuando el tablero se divide en áreas aisladas de las demás por piedras vivas, de modo que cada área tiene un árbol de juego canónico de tamaño polinomial. En el lenguaje de la teoría de juegos combinatoria , esto ocurre cuando una partida 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 subjuegos de Go pequeños (con árboles de juego canónicos de tamaño polinomial). Cabe señalar que el artículo no demuestra que los finales de Go pertenezcan a PSPACE, por lo que podrían no ser PSPACE-completos.

Determinar qué bando gana una carrera de captura de escaleras es PSPACE-completo, ya sea que se aplique la regla japonesa ko o la regla superko. [ 8 ] Esto se demuestra simulando QBF, conocido por ser PSPACE-completo, con escaleras que rebotan por el tablero como haces de luz.

Dado que cada casilla del tablero puede estar vacía, ser negra o blanca, hay un total de 3n² posibles posiciones en un tablero cuadrado de longitud n ; sin embargo, no todas son válidas. Tromp y Farnebäck derivaron una fórmula recursiva para las posiciones válidas.L(metro,norte){\displaystyle L(m,n)}de un tablero rectangular de longitud m y n . [ 9 ] El número exacto deL(19,19){\displaystyle L(19,19)}se obtuvo en 2016. [ 10 ] También encuentran una fórmula asintóticaL≈ABmetro+nortedometronorte{\displaystyle L\approx AB^{m+n}C^{mn}}, dóndeA≈0,8506399258457145{\displaystyle A\approx 0.8506399258457145},B≈0,96553505933837387{\displaystyle B\approx 0.96553505933837387}ydo≈2.975734192043357249381{\displaystyle C\approx 2.975734192043357249381}Se estima que el universo observable contiene alrededor de 10⁸⁰ átomos, una cantidad mucho menor que el número de posiciones legales posibles en un tablero de tamaño regular (m=n=19). A medida que el tablero se agranda, disminuye el porcentaje de posiciones legales.

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 aproximadamente 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 , incluyendo 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 10 10 108 , mayor que 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! ≈1,4 × 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 o1,0 × 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. Si bien la mayoría de las partidas duran menos de 400 o incluso 200 movimientos, son posibles muchas más.

El número total de partidas posibles puede estimarse a partir del tamaño del tablero de varias maneras, algunas más rigurosas que otras. La más sencilla, una permutación del tamaño del tablero, ( N ) L , no incluye capturas ni posiciones ilegales. Si tomamos N como el tamaño del tablero (19 × 19 = 361) y L como la partida más larga, N L constituye un límite superior. En el artículo de Tromp y 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 aproximadamente 31 millones de segundos en un año, se necesitarían aproximadamente 2 + 1/4 años , jugando 16 horas al día a razón de un movimiento por segundo, para jugar 47 millones de movimientos.

Véase también

Notas

  1. ↑ "Go Infinitesimals at Sensei's Library" . senseis.xmp.net . Consultado el 10 de febrero de 2022 .
  2. 1 2 Lichtenstein, David; Sipser, Michael (abril de 1980). "Go es difícil en el espacio polinomial" (PDF) . Journal of the ACM . 27 (2): 393– 401. doi : 10.1145/322186.322201 . S2CID 29498352 . 
  3. 1 2 Robson, John (1983). "La complejidad del Go". Actas del 9º Congreso Mundial de Informática de la IFIP sobre Procesamiento de la Información : 413–417 .
  4. 1 2 3 Robson, J (1984). "Juegos combinatorios con problemas de decisión completos en espacio exponencial". Fundamentos matemáticos de la informática 1984. Notas de clase en informática. Vol. 176. págs. 498–506 . doi : 10.1007/BFb0030333 . ISBN   978-3-540-13372-8.{{cite book}}: |journal=ignorado ( ayuda )
  5. ↑ Aviezri Fraenkel y D. Lichtenstein (1981). "El cálculo de una estrategia perfecta para el ajedrez n × n requiere un tiempo exponencial en n" . J. Comb. Theory A. 31 ( 2): 199–214 . doi : 10.1016/0097-3165(81)90016-9 .
  6. ↑ JM Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing . 13 (2): 252– 267. doi : 10.1137/0213018 .
  7. ↑ Wolfe, David (2002). Nowakowski, Richard J. (ed.). "Los finales de Go son PSPACE-difíciles" (PDF) . More Games of No Chance, Mathematical Sciences Research Institute Publications 42 : 125–136 . Archivado del original (PDF) el 10 de agosto de 2017. Recuperado el 9 de julio de 2016 .
  8. ↑ Crâşmaru, Marcel; Tromp, John (2000). "Ladders Are PSPACE-Complete". Computers and Games . Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 241–249 . CiteSeerX 10.1.1.24.4665 . doi : 10.1007/3-540-45579-5_16 . ISBN    978-3-540-43080-3.
  9. 1 2 Tromp, J ; Farnebäck, G (2007), "Combinatoria del Go", Computers and Games , Lecture Notes in Computer Science, vol. 4630, Springer, Berlín, Heidelberg, pp. 84– 99, doi : 10.1007/978-3-540-75538-8_8 , ISBN   978-3-540-75537-1
  10. ↑ https://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
  11. ↑ "Combinatoria del Go" (PDF) . github.io . Consultado el 17 de junio de 2023 .
  12. ↑ Allis 1994
  13. 1 2 3 4 Walraet, M; Tromp, J (2016), "Un googolplex de juegos de Go", Computers and Games , Lecture Notes in Computer Science, vol. 10068, Springer, Berlín, Heidelberg, pp. 191–201 , doi : 10.1007/978-3-319-50935-8_18 , ISBN   978-3-319-50934-1
  14. ↑ "Inicio - Asociación Americana de Go" . www.usgo.org . Consultado el 17 de junio de 2023 .
  15. ↑ Tromp 1999
  16. ↑ "Estadísticas sobre la duración de una partida de go" .

Referencias

  • AGA. "Diez razones principales para jugar al Go" .
  • Allis, Victor (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) . Tesis doctoral, Universidad de Limburgo, Maastricht, Países Bajos. ISBN 978-90-900748-8-7.
  • Hearn, Robert A. (2006). "Juegos, rompecabezas y computación" (PDF) .[Tesis doctoral, 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 juegos de 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 del Go" .
  • Go y Matemáticas
  • Número de resultados posibles de un juego - artículo en la Biblioteca de Sensei