El juego del Go analizado con computadora

El juego chino del Go se practica desde hace más de 2,500 años. Se juega en un tablero de 19×19 intersecciones y el objetivo del juego es rodear con las piedras propias un área más grande en el tablero que el rival. A pesar de que las reglas del Go son muy simples, sus estrategias son muy complejas y hay quien indica que es mucho más complicado que el propio ajedrez, aunque hay esfuerzos por hacer un programa de Go que juegue tan bien como los grandes maestros de este pasatiempo de mesa.

Evidentemente el juego de Go es susceptible de analizarse con la computadora. John Tromp decidió de entrada calcular el número de posiciones legales del mismo. Empieza indicando que hay 361 intersecciones en el tablero de 19×19 líneas. Solamente algunas de las 3^361 posiciones son legales. Tromp se dio pues a la tarea de hacer este cálculo y lo logró el 20 de enero de este 2016.

El total de posiciones legales es de:

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

o poniéndolo en una forma más compacta:

2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935

El problema es de cómputo finalmente y se trata de alguna manera al equivalente de factorizar este gigantesco número. El autor trabajó con dos posibles métodos: el General Number Field Sieve y el Método Elíptico de Curvas (ECM), los cuales aunque son de tiempo exponencial, pero al menos no lo son como el querer factorizar por la división repetitiva.

Tromp usó la implementación de EMC, cortesía de Darío Alejandro Alpern y pudo factorizar el número en cuestión en unas cuantas horas, dándole 8 factores primos:

5 *
401 *
4821637 *
964261621 *
2824211368611548437 *
2198466965002376001759613307922757 *
65948646836807567941440434317404197 *
54536540603346595211722061421378072820459376985314707345317470047

Es claro que probar individualmente las 3^361 posiciones para ver si son legales o no es tan absurdo como hacer la factorización a través de las divisiones repetitivas. Por ende, el autor se centró en buscar un algoritmo que resolviera sus problemas de manera más eficiente y halló que ya existe, desde el año 2000, un algoritmo, el cual se describe aquí. Éste reduce esencialmente el cómputo del número total de posiciones de Go a una matriz de 363 mil millones de filas y columnas. Así entonces, bastaba tener el equipo de cómputo adecuado para resolver el problema.

Tromp indica que tuvo acceso al poder computacional necesario el año pasado. Aún así tuvo que hacer uso del Teorema Chino de residuo, amén de otras manipulaciones matemáticas. Finalmente empezó a correr su programa de análisis el 6 de marzo del 2015 ejecutándose en servidores grandes, como el de la Escuela de Ciencias Naturales de Princeton, el Centro de Investigaciones en Comunicaciones IDA y la nube de HP Helion Cloud.

El trabajo se terminó el 26 de diciembre del 2015, generando una salida de unos 30 petabytes en disco.

El software lo ha puesto Tromp en el depósito GitHub. El programa, para calcular las posiciones legales dado el número de posibilidades requiere de unos 15 Terabytes de espacio, de 8 a 16 núcleos y 192 GB de RAM. Es claro que no cualquiera en su casa tiene este tipo de equipos. El programa en estas condiciones tarda unos dos meses en ejecutarse por completo.

Un logro francamente monumental, que habla de alguna manera de cómo se hace un análisis en matemáticas hoy en día, apoyado del poder de cómputo que se tiene actualmente.
Referencias: