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 $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^n² 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 $L(m,n)$ de un tablero de tamaño m y n.^[9] El número exacto de $L(19,19)$ se obtuvo en 2016.^[10] También encuentran una fórmula asintótica $L\approx AB^{m+n}C^{mn}$ , donde $A\approx 0.8506399258457145$ , $B\approx 0.96553505933837387$ y $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.

Tamaño del tablero n×n	3^n²	% legal	$L$ (posiciones legales)^[11]^[12]
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³⁸	23.44%	1.03919148791 × 10³⁸
13 × 13	4.30023359390 × 10⁸⁰	8.66%	3.72497923077 × 10⁷⁹
19 × 19	1.74089650659 × 10¹⁷²	1.20%	2.08168199382 × 10¹⁷⁰

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⁷⁰⁰ ^[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.

Tamaño	Intersecciones	N!	Longitud promedio de partida 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^[16]	386,356,909,593
3 × 3	9	3.6×10⁵	5	5.9×10⁴
4 × 4	16	2.1×10¹³	9	6.9×10¹⁰
5 × 5	25	1.6×10²⁵	15	9.3×10²⁰
9 × 9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13 × 13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19 × 19	361	1.0×10⁷⁶⁸	200	3×10⁵¹¹	10⁴⁸	10^10⁴⁸	10^10¹⁷¹
21 × 21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

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.

Partida más larga 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 abandonan 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¹²⁶		7.5×10¹²⁷
100	1.4×10²⁴⁹		5.6×10²⁵⁵
150	6.4×10³⁶⁷		4.2×10³⁸³
200	1.9×10⁴⁸¹		3.2×10⁵¹¹
250	8.2×10⁵⁸⁷		2.4×10⁶³⁹
300	2.8×10⁶⁸⁴		7.8×10⁷⁶⁶
350	3.6×10⁷⁶⁰		1.3×10⁸⁹⁵
361	1.4×10⁷⁶⁸		1.8×10⁹²³	Partida más largo con 181 piedras negras y 180 blancas.
411	n/a			Partida profesional más larga^[17]
500	n/a
1000	n/a
47 millones	n/a		10^10⁸	361³ jugadas
10⁴⁸	n/a	10^10⁴⁸	10^10¹⁷¹	Partida más larga

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

Notas

↑ «Go Infinitesimals at Sensei's Library». senseis.xmp.net. Consultado el 3 de abril de 2021.
↑ ^a ^b Lichtenstein, David; Sipser, Michael (1 de abril de 1980). «GO Is Polynomial-Space Hard». Journal of the ACM 27 (2): 393-401. ISSN 0004-5411. doi:10.1145/322186.322201. Consultado el 3 de abril de 2021.
↑ ^a ^b Robson, John (1983). «The complexity of Go». Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413-417.
↑ ^a ^b ^c Robson, J. M. (1984). «Combinatorial games with exponential space complete decision problems». En Chytil, M. P., ed. Mathematical Foundations of Computer Science 1984. Lecture Notes in Computer Science (en inglés) (Springer): 498-506. ISBN 978-3-540-38929-3. doi:10.1007/BFb0030333. Consultado el 3 de abril de 2021.
↑ «Computing a perfect strategy for n × n chess requires time exponential in n». Journal of Combinatorial Theory, Series A (en inglés) 31 (2): 199-214. 1 de septiembre de 1981. ISSN 0097-3165. doi:10.1016/0097-3165(81)90016-9. Consultado el 3 de abril de 2021.
↑ Robson, J. M. (1 de mayo de 1984). «N by N Checkers is Exptime Complete». SIAM Journal on Computing 13 (2): 252-267. ISSN 0097-5397. doi:10.1137/0213018. Consultado el 3 de abril de 2021.
↑ Wolfe, David (2002). «Go endgames are PSPACE-hard». En Nowakowski, Richard J., ed. More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125-136.
↑ Crâşmaru, Marcel; Tromp, John (2001). «Ladders Are PSPACE-Complete». En Marsland, Tony, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer): 241-249. ISBN 978-3-540-45579-0. doi:10.1007/3-540-45579-5_16. Consultado el 3 de abril de 2021.
↑ ^a ^b Tromp, John; Farnebäck, Gunnar (2007). «Combinatorics of Go». En van den Herik, H. Jaap, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer): 84-99. ISBN 978-3-540-75538-8. doi:10.1007/978-3-540-75538-8_8. Consultado el 3 de abril de 2021.
↑ 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
↑ «A094777 - OEIS». oeis.org. Consultado el 3 de abril de 2021.
↑ https://tromp.github.io/go/gostate.pdf
↑ Allis 1994
↑ Walraet, Matthieu; Tromp, John (2016). «A Googolplex of Go Games». En Plaat, Aske, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer International Publishing): 191-201. ISBN 978-3-319-50935-8. doi:10.1007/978-3-319-50935-8_18. Consultado el 3 de abril de 2021.
↑ AGA – top ten reason to play Go
↑ Tromp 1999
↑ «Statistics on the length of a go game». homepages.cwi.nl. Consultado el 3 de abril de 2021.

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

Datos: Q5574974

[1] «Go Infinitesimals at Sensei's Library». senseis.xmp.net. Consultado el 3 de abril de 2021.

[sipser1980-2] Lichtenstein, David; Sipser, Michael (1 de abril de 1980). «GO Is Polynomial-Space Hard». Journal of the ACM 27 (2): 393-401. ISSN 0004-5411. doi:10.1145/322186.322201. Consultado el 3 de abril de 2021.

[robson1983-3] Robson, John (1983). «The complexity of Go». Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413-417.

[robson1984-4] Robson, J. M. (1984). «Combinatorial games with exponential space complete decision problems». En Chytil, M. P., ed. Mathematical Foundations of Computer Science 1984. Lecture Notes in Computer Science (en inglés) (Springer): 498-506. ISBN 978-3-540-38929-3. doi:10.1007/BFb0030333. Consultado el 3 de abril de 2021.

[Fraenkel1981-5] «Computing a perfect strategy for n × n chess requires time exponential in n». Journal of Combinatorial Theory, Series A (en inglés) 31 (2): 199-214. 1 de septiembre de 1981. ISSN 0097-3165. doi:10.1016/0097-3165(81)90016-9. Consultado el 3 de abril de 2021.

[robson1984checkers-6] Robson, J. M. (1 de mayo de 1984). «N by N Checkers is Exptime Complete». SIAM Journal on Computing 13 (2): 252-267. ISSN 0097-5397. doi:10.1137/0213018. Consultado el 3 de abril de 2021.

[7] Wolfe, David (2002). «Go endgames are PSPACE-hard». En Nowakowski, Richard J., ed. More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125-136.

[8] Crâşmaru, Marcel; Tromp, John (2001). «Ladders Are PSPACE-Complete». En Marsland, Tony, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer): 241-249. ISBN 978-3-540-45579-0. doi:10.1007/3-540-45579-5_16. Consultado el 3 de abril de 2021.

[Tromp_and_Farnebäck_2007-9] Tromp, John; Farnebäck, Gunnar (2007). «Combinatorics of Go». En van den Herik, H. Jaap, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer): 84-99. ISBN 978-3-540-75538-8. doi:10.1007/978-3-540-75538-8_8. Consultado el 3 de abril de 2021.

[10] ttps://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] «A094777 - OEIS». oeis.org. Consultado el 3 de abril de 2021.

[12] ttps://tromp.github.io/go/gostate.pdf

[13] Allis 1994

[14] Walraet, Matthieu; Tromp, John (2016). «A Googolplex of Go Games». En Plaat, Aske, ed. Computers and Games. Lecture Notes in Computer Science (en inglés) (Springer International Publishing): 191-201. ISBN 978-3-319-50935-8. doi:10.1007/978-3-319-50935-8_18. Consultado el 3 de abril de 2021.

[top_ten-15] AGA – top ten reason to play Go

[16] Tromp 1999

[17] «Statistics on the length of a go game». homepages.cwi.nl. Consultado el 3 de abril de 2021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]