Por Rodrigo Díaz López
En un artículo anterior reflexionamos sobre la Inteligencia Artificial aplicada al mundo del ajedrez. Hoy nos centraremos en el nuevo actor que ha venido a revolucionar los mundos del ajedrez y del Machine Learning: AlphaZero.
Deep Blue, el pionero
Deep Blue, desarrollado por el gigante estadounidense IBM, fue el primer ordenador capaz de ganarle una partida al campeón del mundo de ajedrez. Fue, asimismo, el primer ordenador en derrotar al campeón del mundo de ajedrez en un torneo de partidas jugadas a un ritmo de juego normal.
Deep Blue logró tan excepcionales resultados gracias a la “fuerza bruta”. Era un superordenador de procesamiento paralelo masivo basado en el RS/6000 con 30 procesadores IBM Power2 de 120 MHz., con otros 480 coprocesadores VLSI diseñados específicamente para ejecutar operaciones relacionadas con el ajedrez. Su primera versión, empleada en el duelo contra Kaspárov de 1996, era capaz de calcular 100 millones de posiciones por segundo, y su segunda versión, empleada en la famosa revancha de 1997, era dos veces más rápida que la anterior.
El software de Deep Blue, además de tener acceso a extensas bases de datos de aperturas y tablas de finales, utilizaba el algoritmo minimax, y una técnica de poda alfa-beta, especialmente diseñado por un equipo de programadores y grandes maestros de ajedrez. Este algoritmo fue mejorado usando técnicas de machine learning. Se preparaba una primera versión del algoritmo y se le proponían una batería de cientos de miles de las mejores partidas de ajedrez de la historia, jugadas por humanos, de forma que Deep Blue podía aprender las técnicas utilizadas en ellas para poder aplicarlas en los enfrentamientos futuros. Pero este aprendizaje era supervisado por los desarrolladores. Cuando Deep Blue realizaba una jugada “errónea”, es decir un bug, se revisaba el código y se modificaba hasta que Deep Blue realizaba la jugada “correcta”. De este modo, el software se iba perfeccionando poco a poco.
No obstante, Deep Blue no estaba realmente diseñado para jugar al ajedrez, sino para jugar al ajedrez contra Gary Kaspárov. Deep Blue conocía todas las partidas jugadas por el campeón y los grandes maestros del ajedrez que lo entrenaron, entre los que se encontraba el español Miguel Illescas, consiguieron que su estilo de juego se opusiese perfectamente al estilo de juego agresivo de Kaspárov.
Por otra parte, en aquellos enfrentamientos contra Kaspárov hubo acusaciones de comportamiento poco ético por parte de IBM. Uno de los empleados de seguridad asignados a Kaspárov hablaba ruso y, presuntamente, espiaba las conversaciones con su entrenador para que el equipo de IBM pudiera obtener pistas sobre cómo preparar la siguiente partida. Además, aunque IBM no podía manipular el software de Deep Blue en medio de una partida, en ocasiones Deep Blue se “bloqueaba” y necesitaba reiniciarse lo que permitiría, presuntamente, realizar modificaciones en su software.
Nunca sabremos hasta donde podría haber llegado Deep Blue en un torneo convencional, contra otros humanos o contra otras máquinas. IBM nunca ha publicado el código de su algoritmo y desmanteló Deep Blue poco después del torneo de 1997, así que desde entonces no ha vuelto a jugar al ajedrez. Los dos racks que lo formaban se encuentran actualmente en el Museo Nacional de Historia Estadounidense y en el Museo Histórico de Ordenadores, ambos en Estados Unidos.
Stockfish, el sucesor
El que ha demostrado ser el mejor sucesor de Deep Blue es, sin lugar a duda, el motor de ajedrez de código abierto denominado Stockfish.
Stockfish fue desarrollado en 2008 por Tord Romstad, Joona Kiiski, Marco Costalba y Gary Linscott, con la colaboración de una comunidad de desarrolladores de código abierto. Está desarrollado en C++, el código se publica bajo la licencia GPL y está disponible para Windows, Linux, Mac, Android e iOS.
Stockfish puede usar hasta 512 hilos de CPU en sistemas multiprocesador, que le permiten examinar 70 millones de posiciones por segundo, e implementa una poda alfa-beta avanzada que se caracteriza por su gran profundidad de búsqueda. El software de Stockfish está en constante mejora. Cada uno de los cambios en el código, propuestos por la comunidad de desarrolladores, se acepta o rechaza en función de los resultados de jugar decenas de miles de partidas contra una versión "de referencia" más antigua del programa utilizando pruebas de razón de probabilidad secuencial. Las pruebas se verifican mediante la prueba de χ² y solo si los resultados son estadísticamente significativos se consideran fiables y se utilizan para revisar el código.
Todas estas características han llevado a Stockfish a ocupar varias veces el primer lugar en el campeonato mundial (no oficial) de ajedrez para ordenadores. Desde 2013 a 2019, de los 12 títulos que se han disputado, ha ganado 6 y ha quedado segundo en otras 5 ocasiones.
En definitiva, Stockfish es un motor de ajedrez, con un ELO superior al del campeón del mundo de ajedrez Magnus Carlsen, que puedes llevar en el bolsillo instalado en tu teléfono móvil.
Y en esto llegó… AlphaZero
En los últimos años, todos los módulos de ajedrez populares se habían basado en el algoritmo minimax, mejorado con una poda alfa-beta, habían usado una estructura de árbol para calcular las diferentes variantes y una compleja función de evaluación para asignar a la posición al final de una variante un valor como +1,5 (la ventaja de las blancas equivale a un peón y medio) o -9,0 (la ventaja de las negras equivale a una dama).
Sin embargo, en 2017 DeepMind (una compañía propiedad de Google) desarrolló AlphaZero para especializarse en aprender a jugar juegos de dos jugadores y movimientos alternos (como el ajedrez, el shogi o el go), basándose en técnicas de aprendizaje reforzado y aprendizaje profundo con redes neuronales.
El enfoque de AlphaZero con respecto del cálculo de variantes y la evaluación de posiciones es radicalmente distinto a lo que hacen otros módulos. AlphaZero usa el árbol de búsqueda Monte Carlo que evalúa una posición generando una serie de secuencias de movimientos (o “desarrollos”) aleatorios y, haciendo una media de los resultados finales que genera (victoria/tablas/derrota), modifica la función de evaluación cuando los movimientos aleatorios le llevan a posiciones “buenas”. Todo esto va generando desarrollos semi aleatorios, líneas que parecen apropiadas a su función de evaluación en mejora continua. Obviamente, estos desarrollos semi aleatorios pueden llevar a AlphaZero a cometer errores graves, pero le permiten mejorar en el futuro.
La mejora continua de la función de evaluación se consigue por medio de una red neuronal.
La posición actual sobre el tablero se introduce en la capa de entrada de la red, a continuación es procesada por la primera capa de neuronas, cada una de las cuales envía el resultado a las neuronas de la siguiente capa, y así sucesivamente hasta llegar a la capa de salida que obtiene el resultado final.
En AlphaZero este resultado tiene dos partes:
- Una evaluación de la posición de ajedrez que se le había planteado.
- Una evaluación de cada jugada legal en la posición.
En realidad, cada neurona es una unidad de procesamiento muy simple que acepta una serie de aportaciones, multiplica cada una por una cantidad de peso, suma las respuestas y luego aplica una función de activación que da un resultado, típicamente en el rango de 0 a 1. Es importante tener en cuenta que el resultado de una neurona puede depender de todas las neuronas que hay en la capa anterior, lo cual permite a la red captar muchas sutilezas.
La red neuronal de AlphaZero tiene 80 capas y cientos de miles de neuronas. Los pesos son muy importantes, porque entrenar a la red es una cuestión de dar valores a los pesos para que la red aprenda a “jugar bien” al ajedrez.
Como hemos visto en un artículo anterior, el gran problema del ajedrez son las variantes. Teniendo en cuenta todos los posibles movimientos, las posibles respuestas del adversario, nuestros posibles movimientos siguientes, etc. al cabo de solo 4 jugadas tendríamos unas 650.000.000.000 posiciones distintas que tendríamos que evaluar. Y esa cifra sigue creciendo exponencialmente. AlphaZero reduce el número de variantes considerando solo los movimientos que le recomienda su red neuronal, una media de tres posibles movimientos. De ese modo, una modesta cantidad de 80.000 posiciones evaluadas por segundo (como hemos visto, Stockfish examina 70 millones de posiciones por segundo) le permiten ver unos siete movimientos por delante en menos de un minuto.
En cuando al hardware, AlphaZero se ejecuta en un hardware especializado: las unidades de procesamiento por tensores (TPU) de Google. AlphaZero usa 5.000 TPUs de primera generación para generar partidas de juego autónomo, las cuales se usan para entrenar a la red, y 64 TPUs de segunda generación para realizar el entrenamiento como tal. No obstante, para jugar al ajedrez solo necesita 4 TPUs.
Por todo lo que hemos visto hasta el momento, se podría decir que AlphaZero es como un bebé recién nacido, está tremendamente equipado para aprender pero tiene muy pocos conocimientos. En el caso del ajedrez, a AlphaZero simplemente le enseñaron las leyes del ajedrez. No sabe nada de teoría de aperturas, ni tiene conocimientos estratégicos o tácticos. Por no conocer, ni siquiera conoce el valor relativo de las piezas de ajedrez. Su función de evaluación solo mide la probabilidad de victoria o derrota, entre -1 y 1. Es decir, le enseñaron a mover las piezas, que el objetivo del juego es dar jaque mate al rey contrario... y nada más.
En diciembre de 2017, con estos conocimientos tan exiguos, AlphaZero se puso a jugar al ajedrez consigo mismo. Los desarrolladores de DeepMind podrían haberle dado partidas de grandes maestros de las que aprender (aprendizaje supervisado). Sin embargo, esto habría dado como resultado que AlphaZero aprendería a jugar ajedrez como lo hacen los humanos, con sus mismos errores. Así que el equipo de DeepMind optó por usar un enfoque más ambicioso denominado aprendizaje de refuerzo. Al principio AlphaZero jugaba contra si mismo moviendo aleatoriamente las piezas pero si, eventualmente, uno de los dos bandos ganaba, sería debido a que las jugadas que había realizado debían ser mejores que las del bando que perdió, así que se reajustaban los pesos en la red neuronal. Tras un lote de ejecuciones (4.096 partidas) se consolidaba la mejor red neuronal obtenida hasta el momento, que se catalogaba como “Mejor jugador”, y en el siguiente lote se jugaba siempre contra este “Mejor jugador”. Si tras otro lote de ejecuciones el nuevo jugador había demostrado ser mejor que él, entonces ocupaba su puesto y vuelta a empezar. Esto es, AlphaZero aprende de sus propios errores y toma sus propias decisiones sin intervención humana.
Durante este período de aprendizaje, el progreso de AlphaZero se medía jugando partidas de un segundo por movimiento contra Stockfish. Cuando AlphaZero llevaba 300.000 iteraciones en los gigantescos servidores de Google (unas cuatro horas de entrenamiento) los desarrolladores comprobaron que ya tenía un nivel superior a Stockfish. No obstante, el entrenamiento de la red continuó hasta completar unas 700.000 iteraciones, proceso que duró 9 horas, y a continuación AlphaZero se enfrentó a Stockfish en una serie de 100 partidas, jugando la mitad con blancas y la mitad con negras. El resultado fue espectacular: +28 -0 =72. AlphaZero ganó 28 partidas, no perdió ninguna e hizo tablas en las otras 72.
Muchos consideraron que el encuentro no había sido justo porque no se utilizó la última versión disponible de Stockfish, no se le permitió utilizar su libro de aperturas y el hardware utilizado favorecía claramente a AlphaZero, así que a principios de 2018 se repitió el encuentro con un resultado muy similar. AlphaZero vapuleó a Stockfish en una nueva serie de 1.000 partidas, con un marcador de +155 -6 =839. AlphaZero ganó 155 partidas, sólo perdió 6 e hizo tablas en las otras 839.
Algunas de estas partidas han sido publicadas recientemente y muestran un estilo de juego revolucionario. Por ejemplo, como AlphaZero no conoce el concepto de “valor material de las piezas” realiza espectaculares sacrificios de peones o piezas en la apertura, solo porque maximizan sus posibilidades de ganar la partida a largo plazo.
Pero lo más sorprendente de AlphaZero no es que tras unas pocas horas de aprendizaje autodidacta haya sido capaz de aprender a jugar al ajedrez a un nivel sobrehumano. Lo más extraordinario es que el algoritmo de AlphaZero es idéntico para los juegos de ajedrez, shogi y go… y también ha logrado vencer a los mejores módulos informáticos de estos dos juegos, partiendo tan solo de las normas básicas de los mismos y unas pocas horas de entrenamiento. Esto supone un importante avance para la Inteligencia Artificial, y abre las puertas a crear en el futuro un sistema capaz de aprender cualquier juego… con las implicaciones que esto podría tener.
Como corolario comentaré que, debido al hardware tan especializado en el que corre, no es posible instalar AlphaZero en un dispositivo doméstico. No obstante, en 2018 se ha creado un motor de ajedrez de código abierto denominado Leela Chess Zero (Lc0), basado en el proyecto de AlphaZero. Lc0 ha ganado recientemente el campeonato mundial (no oficial) de ajedrez para ordenadores (TCEC 15), tras derrotar en la final precisamente a Stockfish, y dispone de una interfaz gráfica de usuario para Windows y para Linux.
La siguiente generación de motores de ajedrez basados en redes neuronales ya está aquí… y ha venido para quedarse.