El ajedrez tiene una respuesta, pero nadie la conoce

Teoría de juegos, parte 2 de 9

El 24 de noviembre, en Ginebra, Gukesh y Javokhir Sindarov jugarán la primera partida de su match por el título mundial. Los dos llevan meses preparándose con equipos de ayudantes y los programas de ajedrez más fuertes que existen. Y aun así, ninguno conoce la respuesta a la pregunta más sencilla sobre el ajedrez: ¿quién gana si ambos bandos juegan a la perfección?

Lo más curioso es otra cosa. Hace más de un siglo, los matemáticos mostraron que esa respuesta existe. Está tan fijada como el resultado de 2 + 2. Simplemente, nadie la ha visto nunca.

Lo que mostró Zermelo

En la primera parte de la serie resolvimos el juego de las cerillas razonando del final hacia el principio. En un artículo de 1913, el matemático alemán Ernst Zermelo —hoy más conocido por su trabajo en teoría de conjuntos— aplicó un razonamiento parecido al ajedrez.

El ajedrez es un juego de dos jugadores con información perfecta y sin ningún azar. El número de posiciones es finito y las reglas no permiten que una partida dure para siempre. En juegos así, es cierta exactamente una de estas tres afirmaciones:

1. Las blancas pueden forzar la victoria, se defiendan como se defiendan las negras.
2. Las negras pueden forzar la victoria, jueguen como jueguen las blancas.
3. Cada bando puede asegurarse al menos las tablas.

Esa es «la respuesta del ajedrez». Cuál de las tres es la verdadera, nadie lo sabe.

Una pequeña nota histórica. En realidad, Zermelo se planteó una pregunta más estrecha que la que suele atribuírsele: ¿puede quien tiene una posición ganadora forzar la victoria, y en cuántas jugadas? La formulación de las tres posibilidades y la inducción hacia atrás de forma explícita llegaron después, en trabajos de los matemáticos húngaros Dénes Kőnig (1927) y László Kalmár (1928). Los historiadores de la teoría de juegos Ulrich Schwalbe y Paul Walker desenredaron esta confusión en detalle. Así que el «teorema de Zermelo» es, en realidad, obra de varias personas, bautizada con el nombre de la primera.

Tres niveles de «resuelto»

Cuando se dice que un juego está «resuelto», se quiere decir una de tres cosas:

• resuelto de forma ultradébil: se sabe cómo termina la partida con juego perfecto, pero no cómo conseguirlo;
• resuelto de forma débil: se conoce el resultado y una estrategia que lo asegura desde la posición inicial;
• resuelto de forma fuerte: se conoce la jugada correcta en cualquier posición que pueda surgir.

El juego de las cerillas de la primera parte está resuelto de forma fuerte: tenemos una regla para cualquier número de cerillas. Así están algunos juegos reales:

Fíjate en cómo está formulado lo de las damas. El resultado vale para una variante concreta: las piezas normales solo avanzan, la dama se mueve una casilla en cualquier diagonal y capturar es obligatorio. No se aplica a otras variantes, como las damas internacionales en un tablero de 10×10 o aquellas en las que la dama recorre varias casillas de una vez.

Las damas: dieciocho años de cálculo

El equipo de Jonathan Schaeffer, de la Universidad de Alberta (Canadá), empezó el cálculo en 1989. En el momento de mayor actividad, en 1992, trabajaban en él más de 200 procesadores. Solo la base de datos de finales —todas las posiciones con diez piezas o menos— contiene unos 39 billones de posiciones. En total, las damas 8×8 tienen unas 5 × 10²⁰ posiciones posibles.

En septiembre de 2007, la revista Science publicó el resultado: con juego perfecto por ambas partes, las damas terminan en tablas. Lo curioso es que para la demostración no hizo falta revisar todas las posiciones. Bastó con mostrar que ningún bando puede apartarse de las líneas de tablas con provecho.

Por qué el ajedrez no se puede calcular igual

En 1950, Claude Shannon, fundador de la teoría de la información, estimó el número de posiciones posibles en el ajedrez en unas 10⁴³, y el de partidas posibles, en unas 10¹²⁰. Calculó que una máquina que revisara una variante por microsegundo necesitaría más de 10⁹⁰ años para elegir su primera jugada.

Una estimación más reciente de John Tromp es todavía mayor: unas 4,8 × 10⁴⁴ posiciones legales. En comparación, las damas tienen unas 5 × 10²⁰. Es decir, el ajedrez no es «el doble de difícil» que las damas: la diferencia es del orden de un billón de billones de veces.

Los matemáticos no dicen que resolver el ajedrez sea imposible. Como en las damas, para demostrar una victoria o unas tablas no haría falta examinar cada posición. Pero el propio Jonathan Schaeffer, que dirigió la demostración de las damas, ha dicho que haría falta un salto tecnológico, como la computación cuántica, antes de poder siquiera intentarlo con el ajedrez.

Donde la respuesta ya se conoce

Hay una parte del ajedrez en la que la respuesta se ha encontrado por completo: los finales. Los ordenadores han calculado todas las posiciones con hasta siete piezas en el tablero, reyes incluidos. Estas tablas —llamadas tablebases— conocen el resultado exacto de cada posición y el camino más corto para alcanzarlo. Algunas de esas victorias duran más de quinientas jugadas, y ninguna persona sabría explicar su lógica.

Veamos qué dicen las tablas sobre uno de los estudios más famosos de la historia del ajedrez. Y este tiene un protagonista español.

La posición de Saavedra

Blancas: rey b6, peón c6. Negras: rey a1, torre d5. Juegan las blancas.

FEN: 8/8/1KP5/3r4/8/8/8/k7 w - - 0 1

La historia empezó en 1895, en la columna de ajedrez del periódico Glasgow Weekly Citizen. Su responsable, Barbier, publicó una posición parecida a esta y creía que, con buen juego de las negras, eran tablas. La solución que hizo famoso el estudio la encontró un lector: Fernando Saavedra, un sacerdote español que vivía en Glasgow.

Lo que ve casi todo el mundo. El peón está a un paso de coronar. La torre negra da jaques y el rey blanco huye de ellos. El plan natural es escapar de los jaques y conseguir una dama:

1.c7 Td6+ 2.Rb5 Td5+ 3.Rb4 Td4+ 4.Rb3 Td3+ 5.Rc2 Td4!

Las negras ya no pueden dar jaque, pero juegan con astucia. Ahora 6.c8=D parece ganar sin más. Sin embargo, tras 6...Tc4+! 7.Dxc4 el rey negro no tiene ninguna jugada legal. Es ahogado: tablas. Tampoco pueden las blancas evitar la captura: tras cualquier retirada del rey, las negras toman la dama con ...Txc8 y de repente son ellas las que juegan a ganar.

Lo que se pasa por alto. 6.c8=T!! Una torre no ahoga, porque no controla la diagonal que necesita el rey negro. Las blancas amenazan un jaque desde a8, tras el cual nada salva a las negras. La defensa más tenaz es 6...Ta4 (solo 6...Td2+ resiste lo mismo), y entonces 7.Rb3! Ahora las blancas amenazan a la vez capturar la torre de a4 y dar mate con Tc1. Las negras no pueden parar ambas cosas.

Lo que añadieron las tablas. La tablebase confirma lo esencial: 1.c7 es la única primera jugada ganadora, y 6.c8=D es de verdad solo tablas. Pero también muestra algo que el análisis clásico no deja ver. En la sexta jugada no solo gana 6.c8=T: también ganan 6.Rb3 y 6.Rc3. El camino al mate es ahí unas tres veces más largo y mucho menos bonito. La subpromoción es la victoria más corta, pero no la única.

Qué significa esto para quien juega

Una tablebase no piensa en jugadas «bonitas» y «malas». Piensa en tres categorías: victoria, tablas y derrota. Cualquier jugada que mantenga la categoría es, en cierto sentido, correcta. 6.Rb3 es correcta. 6.c8=D es un error, aunque sea la jugada más natural del tablero: convierte una victoria en tablas.

De ahí sale un principio práctico. Antes de una jugada que parece evidente, conviene preguntarse no «¿es la mejor jugada?», sino «¿cambia el resultado?». Ahogado, jaque perpetuo, un peón perdido: así es como las posiciones ganadas se convierten en tablas.

Pero el principio tiene un límite. En el medio juego nadie sabe en qué categoría está la posición: no hay tablas para 32 piezas, ni las habrá en un futuro previsible. Ahí, jugadores y programas tienen que valorar la posición de forma aproximada y buscar la jugada que sea mejor frente a la respuesta más fuerte del rival. Esa idea —el minimax— es el tema de la próxima entrega de la serie.

Y el match de Ginebra es interesante justamente porque Gukesh y Sindarov no juegan a la perfección. Juegan a un juego cuya respuesta nadie conoce.

Ejercicio

1. En la posición tras 6.c8=T Ta4, encuentra la jugada ganadora de las blancas y explica por qué gana.
2. ¿Por qué, tras 6.c8=D Tc4+, las blancas están obligadas a capturar la torre aunque sea ahogado?
3. ¿En qué nivel de «resuelto» está piedra, papel o tijera, de la primera parte? ¿Se puede decir siquiera quién gana con juego perfecto?

Las respuestas, al final.

Preguntas para el debate

• Si mañana se anunciara que el ajedrez es tablas con juego perfecto, ¿cambiaría algo en tu forma de ver el juego?
• ¿Qué es más útil para aprender: conocer la jugada perfecta gracias a una tabla o entender por qué funciona una jugada, aunque existan otras más rápidas?
• Saavedra encontró una jugada que al autor del estudio se le había escapado. ¿Has visto alguna vez una solución que pasaron por alto personas con más experiencia?

Próximamente en la serie: «Minimax: cómo piensa un rival que te desea lo peor», sobre el teorema de von Neumann y cómo «piensan» los programas de ajedrez.

Respuestas. 1) 7.Rb3!: según la tablebase, la única jugada ganadora. Las blancas atacan la torre de a4 y a la vez amenazan mate con Tc1. 2) Tras cualquier retirada del rey, las negras toman la dama con ...Txc8 y se quedan con una torre contra el rey solo. 3) Las jugadas son simultáneas, así que no hay una única «jugada correcta». La estrategia perfecta es elegir cada opción al azar con probabilidad 1/3. Así, en promedio, nadie gana, juegue como juegue el rival. Estas estrategias mixtas tendrán su propio artículo en la serie.