LA REGLA DEL GO QUE CAMBIA LA RESPUESTA

Resolver un juego significa conocer su resultado cuando ambos bandos juegan a la perfección. En un tablero de go, ese resultado es un valor: el número de puntos por los que ganan las negras con juego perfecto; 28 en un tablero 4×7 significa que las negras se quedan con las 28 intersecciones. Las damas se resolvieron en 2007, igual que el Hex en tableros pequeños. Para el go existen demostraciones por ordenador para muchos tableros de hasta 30 intersecciones, sobre todo de un programa llamado MIGOS (2003 y 2009).

Pero hay una trampa. Esos resultados clásicos usan una regla simplificada para las posiciones repetidas: una regla de «ko» básica —un jugador no puede recapturar de inmediato una piedra suelta que acaba de capturar una de las suyas, lo que haría repetirse en bucle las dos mismas jugadas— más convenciones especiales, como que un pase levanta la prohibición de ko, que la partida se detiene en una posición repetida, etc. Estas convenciones se diseñaron para que el valor de una posición no dependiera de cómo se había llegado a ella.

La regla que de verdad se juega

Las reglas chinas tal como están escritas, y el go por ordenador, usan el superko posicional: ninguna jugada puede recrear ninguna posición de todo el tablero que ya se haya dado en la partida. Resolver con esta regla es mucho más difícil, porque la legalidad de una jugada depende ahora de toda la historia de la partida. Rompe tres herramientas que hacen viable la resolución:

reutilizar resultados de la misma posición alcanzada por otro camino: los dos caminos pueden prohibir jugadas distintas;
reconocer grupos seguros y territorio sin búsqueda, lo que supone que el dueño siempre puede capturar a los intrusos, y bajo el superko esa captura puede estar prohibida;
podar jugadas que nunca ayudan, como rellenar un ojo propio —una de las intersecciones vacías que un grupo necesita para seguir vivo—: bajo el superko, una jugada así puede volverse decisiva.

El coste era enorme: con una variante del superko, MIGOS necesitaba 1,1 horas para el tablero 4×4, frente a 3,3 segundos con el ko básico. La primera solución con superko del 5×5, en 2024, tardó 5,25 horas con seis procesos. Más allá del 5×5, ningún tablero con al menos dos filas se había resuelto con superko.

Un atajo que sigue siendo correcto

Sami Kharma y Florian Schintke, del Zuse Institute Berlin, crearon Sanko. Su núcleo es un sencillo teorema de transferencia de pruebas: una prueba almacenada de que un jugador gana sigue siendo válida en un camino nuevo salvo que ya haya aparecido una posición que el ganador tenga que crear. Solo importan las posiciones del ganador: si el perdedor ya no puede recrear una posición, simplemente pierde una opción. Comprobarlo lleva un tiempo proporcional a la longitud del camino, no al tamaño de la prueba. En el tablero 3×7, este atajo por sí solo reduce el trabajo de 664.000 millones de pasos a 112 millones.

También adaptaron el reconocimiento clásico de grupos seguros para que siga siendo correcto bajo el superko, y solo podaron las jugadas del bando cuya victoria intentaban demostrar, de modo que una búsqueda fallida se declara desconocida, nunca como victoria del otro bando.

Nuevos valores

5×5 en 15,7 minutos con seis hilos, unas 20 veces más rápido que antes, en parte gracias a un hardware mejor; con un solo hilo, el 4×4 se resuelve 58 veces más rápido. En una máquina de 192 hilos, el 5×5 tarda alrededor de minuto y medio.
Los primeros valores con superko de 23 tableros más; 11 de ellos nunca se habían resuelto con ninguna regla. El 3×10 vale 8 puntos para las negras: MIGOS solo había demostrado al menos 6, y dos meses de búsqueda no habían encontrado ninguna cota superior.
En los tableros de una fila, los valores del 1×9 al 1×15 repiten 0, 1, 2, 2, pero el 1×16 rompe el patrón: vale 1 en lugar de 2.

La sorpresa del 4×7

Con las reglas antiguas, el 4×7 es una victoria de tablero completo: las negras lo capturan todo, 28–0. Con superko vale 12. Los autores reprodujeron la línea óptima de 31 jugadas publicada para MIGOS: todas las jugadas son legales y las negras siguen quedándose con todo el tablero. Resolviendo la línea hacia atrás, encontraron la ruptura justo después de la jugada 25: en la posición posterior a la jugada 25, hecha por las negras, las blancas deberían jugar G2 (o C1) en lugar de A2.

Lo que sigue es un ko extraño. Las blancas capturan; la recaptura de las negras recrearía una posición anterior, algo prohibido. Cualquier otra jugada negra pone en peligro su propio grupo. Las negras tienen que pasar, las blancas pasan, y la partida termina con el grupo blanco vivo: lo que los autores de MIGOS ya habían llamado «vida a la luz de la luna» (moonshine life). Con las reglas antiguas, el pase levantaría la prohibición y las negras recapturarían y lo ganarían todo. Con superko, lo mejor que pueden lograr las negras en esta línea es una vida compartida (seki) que vale solo 3 puntos, así que el juego perfecto abandona antes la línea publicada, y lo máximo que las negras pueden asegurarse desde el tablero vacío es 12.

Ninguna de las dos búsquedas estaba equivocada. La diferencia procede de reglas que solo importan al final mismo de una partida. El consejo de los autores: los valores calculados con convenciones que vuelven inofensiva la repetición no deberían citarse como valores del go con superko sin comprobarlos.

Verificable por cualquiera

Cada valor se apoya en dos pruebas independientes, y el programa superó decenas de miles de verificaciones cruzadas sin ninguna discrepancia. A diferencia de las soluciones anteriores de tableros de go vacíos, el código fuente del programa y el comando exacto que hay detrás de cada resultado son públicos; la cadena de pruebas del 4×7 se reproduce en menos de veinte segundos. Las pruebas aún no son certificados que un tercero pueda verificar de forma independiente, y el 6×6 sigue fuera de alcance: según la extrapolación de los autores, unos 50 días en una de sus máquinas, o más.