Lo que esconde el verdadero ajedrez por ordenador.

 por Jose Fernando Blanco

Recapitulando

En la entrega anterior me planteé el objetivo de estudiar el fenómeno de AlphaZero desde un punto de vista ajedrecístico: es decir, hasta qué punto este programa ha cambiado, o podrá llegar a cambiar, el panorama actual del ajedrez por ordenador. ¿Y cuál es dicho panorama? Dicho de otro modo, ¿qué pueden hacer, y qué no pueden hacer, los módulos hoy en día?

Para responder a esta pregunta, nada mejor que empezar por el principio: ¿Qué han hecho los módulos en el pasado? Es decir, ¿cuál ha sido la historia del ajedrez por ordenador? Una historia corta (de apenas setenta años) pero apasionante, cuyos principales hitos iremos repasando. Antes de empezar, sin embargo, tengo que desviarme un poco del ajedrez para adentrarme en cierto campo de las matemáticas.

Un juego “sencillo”

En la primera mitad del siglo XX, y gracias sobre todo al trabajo del húngaro-estadounidense John (Janos) von Neumann, conoció su máximo desarrollo la llamada Teoría de Juegos. A pesar de su simpático nombre, esta rama de las matemáticas tiene aplicaciones en campos tan serios como la economía, la política o la guerra.

Más de un lector pensará que el ajedrez es uno de los juegos más complejos que esta teoría maneja; pero seguramente cambiará de opinión si ve la siguiente comparativa:

  Ajedrez Bolsa de valores
Número de participantes Dos Sin límite
Forma de juego Por turnos estrictos Sin turnos, cada participante puede jugar cuando quiera
Duración del juego Definida Indefinida
Ganancias y pérdidas La ganancia de un participante es igual a la pérdida del otro, es decir, no hay ganancias ni pérdidas netas Puede haber ganancias y pérdidas netas importantes
Tabla 1: El ajedrez, un juego relativamente sencillo.

La última fila de la tabla se entiende si pensamos que las ganancias y pérdidas se refieren al objetivo global de la partida, que es ganar o hacer tablas:

  • Al comienzo de la partida podemos decir que cada jugador tiene medio punto (ya que hay un punto en juego y está sin repartir).
  • Al final de la partida:
    • En caso de tablas, la situación no ha cambiado (nadie suma ni pierde puntos).
    • Si uno de los rivales gana la partida, suma medio punto, exactamente lo que resta su rival.

En ambos casos, la suma algebraica de lo que uno gana y lo que el otro pierde es cero. Esto y el número de contendientes son los factores que determinan la inclusión del ajedrez en la categoría de los llamados juegos de suma cero entre dos contendientes, una de las más sencillas de analizar, según la Teoría mencionada.

“Si preguntas a un matemático cuántas son dos y dos, contestará que la solución existe y es única, pero no te dirá cuál es”.

Así pues, tenemos a nuestro querido ajedrez metido en la categoría de los juegos facilones, en el mismo saco que las tres en raya o el boxeo, y por debajo de otros más sofisticados, como los chinos o el julepe (que, para empezar, admiten más de dos jugadores). Pero no nos lo tomemos a mal y veamos qué dicta la Teoría de Juegos en estos casos.

Pues bien, von Neumann demostró que a los juegos de esta categoría se les puede aplicar un algoritmo, llamado minimax, para determinar la mejor decisión de cada jugador en cualquier situación posible del juego. Ahora bien, si existe ese algoritmo y es aplicable al ajedrez, ¿cómo es que seguimos cometiendo error tras error en nuestras partidas (unos más que otros, claro)? ¿Por qué no aplicamos el algoritmo para calcular la mejor jugada posible en cada posición (empezando por la inicial) y gastamos nuestras neuronas en algo más provechoso, como la bolsa o el póker?

Aquí me viene a la cabeza lo que decía uno de mis profesores en la Universidad: “Si preguntas a un matemático cuántas son dos y dos, contestará que la solución existe y es única, pero no te dirá cuál es”. Eso es exactamente lo que sucede con el minimax y el ajedrez; aunque en este caso el matemático tendría una buena excusa, ya que la complejidad de nuestro sencillo juego hace que, en la práctica (al menos hasta ahora), haya sido imposible aplicarle el minimax hasta sus últimas consecuencias, incluso utilizando los ordenadores más potentes.

Pero entonces, ¿qué utilidad tiene el susodicho algoritmo para los ajedrecistas? Quizá para los jugadores no mucha, pero para los programadores de los módulos sí; tanto que, durante más de medio siglo, prácticamente no han utilizado otra cosa. Razón de sobra para que sepamos en detalle cómo funciona. A ello va dedicado el resto de este artículo y, aunque el lector va a encontrar poco ajedrez en lo que sigue, confío en que lo lea hasta el final, pues es esencial para entender futuras entregas de esta serie.

El minimax completo (pues hay versiones reducidas, como en las quinielas, y en sucesivas entregas hablaremos de ellas) consta de tres fases:

  1. Generar el árbol completo de decisiones del juego.
  2. Valorar los nodos inferiores del árbol (situaciones en las que el juego termina, de acuerdo con las reglas del mismo).
  3. Trasladar las valoraciones anteriores, en sucesivos pasos hacia atrás, a los nodos anteriores, hasta llegar a la posición de partida (en seguida veremos cómo)

Otro juego sencillo

Para ilustrar estos pasos de forma gráfica, he inventado un juego llamado doblatú que se disputa según estas reglas:

  • La partida se desarrolla entre dos jugadores.
  • El objetivo de cada jugador es ganar la mayor cantidad de dinero posible (o perder la menor posible).
  • Se juega por turnos. Al comienzo de la partida se decide (por sorteo o por otro método) el número total de turnos (mínimo tres) y el jugador que recibe el turno de salida.
  • En el primer turno, el jugador elegirá entre:
    • Recibir 1 € del rival.
    • Recibir 2 € del rival.
  • En los turnos siguientes, el jugador que tiene el turno elegirá entre:
    • Recibir lo mismo que entregó en el turno anterior.
    • Recibir el doble de lo que entregó en el turno anterior.

Para asimilar la nomenclatura a la del ajedrez, utilizaré algunos términos familiares de nuestro juego:

  • Al jugador que tiene el turno de salida lo llamaré el blanco y a su rival el negro.
  • A las decisiones tomadas por cada jugador en sus turnos las llamaré jugadas.
  • A las diferentes situaciones producidas tras cada jugada (balances de pérdidas y ganancias) las llamaré posiciones.

Para abreviar, al número total de turnos lo llamaré T. Por aclarar: si por ejemplo T = 5, el blanco tendrá tres turnos (los impares) y el negro dos (los pares). Es decir, que cuando T es par, los jugadores tienen el mismo número de turnos, pero cuando T es impar, el blanco tiene un turno más que el negro.

El doblatú puede parecer muy simple (y lo es), pero observemos que, en Teoría de Juegos, se encuadra en la misma categoría que el ajedrez. Por otro lado, algo de truco tiene, aunque sea poco, y por su misma sencillez nos permite aplicar el minimax hasta sus últimas consecuencias (siempre que elijamos un valor moderado de T), y así ilustrar algunas sutilezas del algoritmo.

  Artículo relacionado: Stockfish: configuración, descarga y secretos.

Dos programadores, dos estilos

Imaginemos dos programadores, Irene y Mario, a los que damos a conocer las reglas del doblatú y les pedimos que hagan cada uno un programa que decida las mejores jugadas de ambos bandos para cualquier valor de T.

Vemos que Mario se pone inmediatamente a teclear y en unos quince minutos tiene el programa listo. En cambio, Irene emplea primero unos cinco minutos en tomar notas en un papel y después, en menos de veinte segundos, ha terminado de codificar.

Tras unas cuantas pruebas, queda claro que los dos programas juegan perfectamente; pero el de Mario, cuanto más alto sea el valor de T, más tiempo tarda en procesarse, hasta el punto de resultar impráctico para valores de T por encima de mil. En cambio, el programa de Irene responde siempre al instante, incluso con valores de T superiores al millón.

Indagando un poco, averiguamos el motivo de esta diferencia de comportamiento: Mario ha aplicado el minimax completo, mientras que el programa de Irene se basa sencillamente en el valor, o más bien la paridad, de T: si T es impar, elige siempre la opción de mayor ganancia, y si es par, la de menor ganancia.

Estos dos enfoques tan diferentes de un mismo problema se entrelazan, como veremos, en la historia de los programas de ajedrez por ordenador. Si bien el enfoque de Irene (al que en adelante llamaremos enfoque inteligente) es más sencillo de implementar y ofrece mejores resultados, en muchos casos (y en particular en el ajedrez) no se puede aplicar de forma tan obvia como en el doblatú, y hay que optar por el enfoque de Mario (al que llamaremos enfoque mecánico).

  Artículo relacionado: Los 5 mejores módulos de análisis (descarga gratuita)

El árbol de la ciencia

Como lo que yo quiero es ilustrar el mecanismo del minimax, lógicamente, tendré que usar el enfoque mecánico y añadir a mi programa unas rutinas de generación de gráficos. Hecho esto, introduzco el valor de T = 4 y obtengo la siguiente figura, en la que están representadas las tres fases del minimax y algún elemento más que quiero comentar.

Figura 1: El minimax completo y alguna cosa más.

Paso a explicar los elementos del gráfico:

  • La fase 1 del minimax (desarrollo del árbol de variantes) está representada por los elementos en blanco y negro:
    • El árbol completo de posibles jugadas hasta el final del cuarto turno, con sus ramificaciones.
    • Los nodos (posiciones) en las que un bando u otro debe tomar una decisión. Cada nodo tiene un nombre según el turno: T1 se refiere al turno 1, T2 al turno 2, y así sucesivamente; las letras A, B, C… sirven solo para diferenciar nodos del mismo turno.
    • Las posibles decisiones (jugadas) del blanco en los turnos impares y del negro en los turnos pares. Estas jugadas se representan desde el punto de vista de lo que gana o pierde el blanco. Por ejemplo, +1 quiere decir que el blanco decide ganar un euro en su turno, y -4 quiere decir que el negro decide ganar cuatro en el suyo, y por tanto el blanco los pierde.
  • En la fase 2 se han valorado las posiciones de los nodos inferiores del árbol. Estas valoraciones están en azul. Cada nodo recibe la valoración resultante de sumar y restar las jugadas que han llevado a esa posición. Por ejemplo, las posiciones obtenidas tras cada una de las dos posibles jugadas del nodo T4C reciben estas valoraciones:
    • + 1 – 2 + 2 – 2 = – 1
    • + 1 – 2 + 2 – 4 = – 3

Estas valoraciones corresponden fielmente con lo que el blanco ha ganado o perdido al final de cada nodo. Es importante observar que solo hemos valorado los nodos inferiores, es decir, las posiciones finales. A estas valoraciones de los nodos finales, en azul en el árbol, las llamaré valoraciones reales (VR, para abreviar).

  • Por último, en la fase 3 del minimax las valoraciones de la fase anterior se trasladan hacia arriba en el árbol de variantes. A las valoraciones así trasladadas (en verde oscuro en la figura) las llamaré valoraciones heredadas (VH). El camino que siguen, árbol arriba, está marcado en verde claro. En cada caso, se traslada la valoración más favorable para el jugador que tiene el turno. Así, siguiendo con el ejemplo del nodo T4C:
    • Dado que el turno 4 es del negro, elegiremos la opción de la derecha (mayor ganancia del negro), y trasladaremos la valoración de esta opción (-3) al nivel inmediatamente superior. Haremos lo mismo con el resto de nodos del turno 4 hasta tener valoraciones en todos los nodos del turno 3, según muestra la figura 2.
    • Para subir valoraciones del nivel 3 al 2 haremos lo mismo pero, como el turno 3 corresponde al blanco, elegiremos las valoraciones más favorables a este jugador.
    • Del nivel 2 (turno del negro) al 1 volveremos a elegir las valoraciones más favorables al negro.
    • Por último, del nivel 1 subiremos a la posición de partida la valoración más favorable al blanco.

Las flechas marcan el camino que sigue la valoración (-3) que finalmente resulta elegida al aplicar los criterios mencionados. Este camino es la línea óptima de jugadas (el blanco gana 1 €, el negro gana 2 €, el blanco gana 2 €, el negro gana 4 €) que llevan a dicha valoración. A esta secuencia de jugadas la llamaré línea principal.

El lector habrá observado que queda por explicar qué significan las cantidades en rojo. Las he dejado expresamente fuera del árbol porque no son parte del minimax. Son las valoraciones de los nodos intermedios, es decir, la situación de la partida (cuánto está ganando o perdiendo el blanco) en cada momento del juego. Estas valoraciones, como ya se ha dicho, no son necesarias en el algoritmo, pues solo se usan las valoraciones de los nodos finales. A estas valoraciones intermedias, en rojo en el árbol, las llamaré valoraciones propias (VP) de cada posición.

El minimax solo garantiza un resultado correcto si se desarrolla el árbol de variantes hasta el final y se trasladan las valoraciones finales hacia arriba en la forma descrita.

Obsérvese que las valoraciones propias pueden ser muy diferentes a las heredadas; por ejemplo, en el nodo T3D la segunda posible jugada del blanco (+8, es decir, ganar 8 €) tiene una VP de +6 (el blanco ganaría 6 €) y una VH de -10 (el blanco perdería 10 €).

Ya es hora de extraer algunas conclusiones:

  • La valoración de la posición de partida del doblatú, para T = 4, es de -3; es decir, contra el mejor juego posible del negro, lo mejor a que puede aspirar el blanco es a perder solo 3 €.
  • Del mismo modo, el negro solo puede aspirar a ganar 3 € contra la mejor estrategia posible del blanco.
  • Cualquiera de los dos que se desvíe de la estrategia óptima en cada turno (marcada en verde) se arriesga a perder más (o ganar menos).

El minimax solo garantiza un resultado correcto si se desarrolla el árbol de variantes hasta el final y se trasladan las valoraciones finales hacia arriba en la forma descrita. Supongamos, por ejemplo, que Mario, agobiado por la lentitud de su programa para valores altos de T, hubiera querido ahorrar tiempo de proceso acortando en un nivel el algoritmo.

Eso quiere decir que las VP del nodo T3 serían, para el programa de Mario, VR. Como tales, se habrían propagado hacia los nodos superiores. Es fácil comprobar entonces que no solo el programa de Mario daría a la posición inicial una valoración errónea (+4), sino que elegiría una jugada inicial perjudicial para sus intereses (ganar 2, en lugar de la más modesta ganar 1, que a la larga consigue limitar sus pérdidas).

A los errores producidos por la aplicación incompleta del minimax se les llama errores por efecto horizonte y, como veremos, han atormentado durante décadas (y todavía lo hacen, aunque en menor medida) a los programadores de módulos de ajedrez.

¡Por fin, un poco de ajedrez!

Gracias por llegar hasta aquí. Es buen momento para recuperar el último diagrama de mi anterior entrega:

Juegan blancas. Recuerdo mi pregunta de entonces: ¿Cuál cree el lector que sería la valoración de esta posición?

Como dijo Marvin Guzmán (gracias por tu comentario), la valoración de esta posición es negras ganan, porque pueden dar mate (Cf2) en la próxima jugada, independientemente de lo que juegue el blanco. Nada que objetar a esta conclusión. Creo que Guzmán habrá pensado más o menos lo siguiente:

“La ventaja material del blanco es abrumadora, así que seguramente gana el blanco de cualquier manera… pero espera, ahora que caigo, el caballo negro está amenazando mate. Sin embargo, al ser el turno de las blancas, alguna jugada habrá que lo evite. Vamos a ver… pues parece que no hay ninguna. Revisemos todas las jugadas posibles otra vez… Definitivamente, no hay manera de evitar Cf2, por tanto la valoración de esta posición es negras ganan.”

Ahora voy a traducir estas cavilaciones a la jerga que he empleado en este artículo:

“La valoración propia (VP) de la posición inicial es muy favorable al blanco, pues tiene mucho más material. Además, el turno 1 le corresponde. Posiblemente casi cualquier jugada del blanco en el nodo T1 es ganadora. Ahora bien, si paso al nodo T2, en el que el turno es del negro, veo una posible jugada (Cf2) que da mate al rey blanco. En caso de mate, la partida termina, por tanto ese nodo es un nodo final y su valoración es una valoración real (VR). Esta VR se trasladaría a la posición inicial como valoración heredada (VH), salvo que existiera una jugada del blanco en T1 que evitara Cf2, o que evitara al menos que Cf2 diera mate. Como no existe tal jugada, la VH de la posición inicial es negras ganan”.

Y ahora añadiré algunas consideraciones que, si bien posiblemente no hayan pasado por la cabeza de Marvin, están implícitas en su razonamiento:

  • “Las VP de las posiciones después de las diferentes jugadas del blanco en T1 pueden ser incluso superiores a la VP de la posición inicial, pero no me sirven para nada ya que, como ninguna de ellas evita Cf2 mate, su VH va a ser siempre negras ganan.”
  • “El negro tiene otras jugadas posibles aparte de Cf2 (Re2, Cxe3, Ch6 etcétera) pero no me interesan porque Cf2 da una valoración de negras ganan, que es mejor para el negro en T2 que la que van a dar las otras.”

Volveremos a ver estas consideraciones, o similares, en posteriores entregas, cuando veamos las cuitas de los primeros programadores de módulos de ajedrez.

Resumiendo: a mi pregunta ¿cuál es la valoración de esta posición?, hay dos respuestas:

  • La valoración propia de esta posición es muy favorable al blanco.
  • La valoración heredada de esta posición es negras ganan.

Las dos respuestas son correctas, pero, como hemos visto, solo la segunda tiene utilidad práctica.

Con este ejemplo, muy sencillo y al mismo tiempo exagerado, quería ilustrar la diferencia entre las dos valoraciones (propia y heredada) y así explicar la misteriosa frase que dejé al final de la entrega anterior:

“No es cierto que la valoración que el módulo nos da corresponda a la posición que está valorando.”

Lo que quería decir es que el módulo no nos da la VP, sino la VH, es decir, la valoración de una posición posterior que, según sus cálculos, se alcanza siguiendo la línea principal (recordemos: la formada por las mejores jugadas posibles de cada bando en cada nodo). En el ejemplo que estamos viendo, de la posición inicial a esa otra posición posterior se llega fácilmente pero, en muchos casos, eso no es nada obvio.

Recordemos, por ejemplo, a mi amigo de la entrega anterior, que decía “Tenía la partida ganada, el módulo me daba +3”. Supongamos que mi amigo había entregado una pieza por ataque: la VP de su posición quizá fuera negativa por el material sacrificado. En cambio la VH que le daba el módulo era muy favorable, quizá porque había calculado que, ocho o diez jugadas más tarde, su rival tendría que devolver el material con intereses para evitar el mate.

Por tanto, es cierto (asumamos que los cálculos del módulo son correctos) que la posición de mi amigo era ganadora, pero solo se plasmaría en una victoria real si era capaz de encontrar la línea principal que había encontrado el módulo. Y eso no siempre es fácil, más bien en muchos casos es totalmente inviable incluso para un súper GM; no digamos ya para un aficionado.

Una posición para pensar

Como aperitivo de la próxima entrega, en la que prometo que entraremos de lleno en la historia del ajedrez por ordenador, propongo la siguiente posición, una de las más famosas de dicha historia.

Juegan las negras. Dos preguntas:

  • ¿Qué opciones tienen las negras en esta posición? Hay que encontrar al menos cinco, quizá más.
  • Si el lector tuviera negras en esta posición, ¿qué opción escogería?

Como siempre, cuidado con las cursivas y ¡hasta la próxima!

Deja un comentario

Your email address will not be published.