Shannon y el aprendizaje automático.
En la primera bitácora de esta serie vimos cómo la pregunta por la mejor partida de ajedrez lleva necesariamente a la pregunta por las características de la mejor ajedrecista. La primera respuesta posible a esta pregunta es, obviamente, que la mejor ajedrecista solo puede ser una mente humana, y como valedor de esa postura elegimos a Edgar Allan Poe. La segunda respuesta posible es que la mejor ajedrecista solo puede ser una Inteligencia Artificial.
Un poco más de un siglo después de que Poe publicara su artículo sobre el Jugador de Ajedrez de Maelzel, el matemático Claude Shannon escribe y publica un artículo sobre cómo programar un ordenador para que juegue al ajedrez [1]. El propio título ya sugiere que Shannon despliega su argumento contra Poe: donde el segundo afirmaba taxativamente que un autómata capaz de jugar al ajedrez era un invento sustantivamente distinto de una máquina de cálculo como la diseñada por Babbage, el primero demuestra que es posible escribir un programa para un ordenador convencional que sea capaz de jugar al ajedrez. De hecho, Shannon cita expresamente el artículo de Poe, y señala cómo este incurre en una falacia argumental cuando afirma que es igual de difícil diseñar un autómata que juegue al ajedrez y gane casi siempre o diseñar un autómata capaz de un juego perfecto [2].
Ahora bien, la lectura completa del artículo revela dos cosas: (1) que el motivo que tiene Shannon para escribir el artículo no es polemizar con Poe; y (2) que la reflexión de Poe es más aguda de lo que pudiera parecer.
Para Shannon, el problema de programar un ordenador para jugar al ajedrez es relevante porque el ajedrez comparte varias características con otros problemas computacionales de mayor trascendencia práctica, tales como: el diseño automático de filtros, ecualizadores y circuitos, el tratamiento automático de las conmutaciones telefónicas, la automatización de operaciones matemáticas simbólicas (no numéricas), automatización de la toma de decisiones estratégicas en escenarios simplificados, orquestación automática de melodías, automatización de deducciones lógicas…
El ajedrez comparte con todos estos problemas las siguientes características: (a) Los objetos de cálculo no son números. (b) El procedimiento automático que debe resolver el problema implica la aplicación de principios generales en iteraciones sujetas a ensayo y error, y no un proceso de cálculo inalterable. (c) Las soluciones no son binarias, correctas o incorrectas, sino que conforman un continuo de mayor a menor calidad.
Sin embargo, el ajedrez también tiene características particulares que hacen que se trate de un problema más simple que los otros: (a) El problema está claramente definido, pues están radicalmente acotadas las operaciones posibles (los movimientos de las piezas) y el objetivo que se debe alcanzar (jaque mate). (b) No constituye un problema tan simple como para ser trivial ni tan difícil como para que no tenga una solución satisfactoria. (c) A pesar de eso, el ajedrez se considera un juego que requiere “pensar”, y por tanto su automatización exitosa obliga, o bien a admitir que el pensamiento humano puede ser mecanizado, o bien a definir de forma más restrictiva qué significa pensar. Y (d) su estructura discreta es afín a la naturaleza digital del ordenador moderno. Frente a otros juegos, el ajedrez tiene dos peculiaridades relevantes: el azar no interviene, salvo para decidir al inicio quién juega con blancas y quién con negras; y que las dos personas que juegan tienen “información perfecta” en cada turno.
Para resolver el problema planteado, Shannon identifica los datos que definen una “posición” de ajedrez para cualquier momento de la partida, y determina que, cualquier posición, puede ser clasificada como: (a) una posición en la que ganan las blancas; (b) una posición en la que ganan las negras; o (c) una posición de tablas, en la que tanto las blancas como las negras pueden al menos llevar el juego a una situación de tablas. No existe un método para determinar a qué clase pertenece una posición; si lo hubiera, el ajedrez perdería su interés como juego, pues se sabría, en cualquier momento de la partida, cuál va a ser su desenlace [3].
Como se recordará, Poe en última instancia sugería que no es posible diseñar un autómata que juegue correctamente al ajedrez porque las condiciones del juego cambian a cada turno, dada la interacción con otra jugadora. Es decir, Poe sugería la naturaleza incalculable de una partida de ajedrez. El estudio de Shannon da, hasta cierto punto, la razón al escritor, ya que, aunque razona que el diseño de un autómata capaz de un juego perfecto es formalmente posible, es totalmente impráctico.
Si, por ejemplo, para cualquier posición, el autómata considerase todos los movimientos posibles, tanto propios como de la rival, y luego retrocediese de nuevo hasta la posición actual, este podría evaluar a que clase pertenece la posición. El cálculo de Shannon es que hay 10120 variaciones posibles a partir de la posición inicial, y que por tanto una máquina podría requerir, si su velocidad de procesamiento fuera 1 variación/microsegundo, 1090 años para calcular su primer movimiento. Para decidir los movimientos ulteriores ya no necesitaría realizar ningún cálculo adicional, suponiendo, claro está, que tuviese suficiente capacidad de almacenamiento (aunque esto ya es otra historia; o quizá no).
Si, en cambio, se elaborase un diccionario con todas las posiciones posibles para las piezas, y se asignase a cada posición un movimiento adecuado, calculado por el procedimiento anterior o propuesto por alguien que domine el ajedrez, tampoco se trataría de un diseño viable: a cada turno, el autómata debería buscar la posición correspondiente entre un listado de 1043 posiciones posibles.
Por lo tanto, como Shannon anticipaba al inicio de su artículo, diseñar una máquina capaz de una partida perfecta no es un problema computacional idéntico a diseñar una máquina que se desempeñe tan bien como una persona que domine el juego. Este es el problema cuya solución Shannon formaliza. Se trata de un diseño “altamente iterativo” que “no debería requerir mucha memoria”.
El programa que permite jugar al ajedrez se desglosa en una serie de subprogramas, que cumplen funciones específicas, 12 en total. Los subprogramas 0 a 7 permiten diseñar un autómata que juegue correctamente (es decir, siguiendo las reglas del juego) pero decida cada movimiento al azar.
El subprograma 8 aplica una función f(P) que realiza una evaluación aproximativa de la posición, de forma análoga a como lo hace una persona. Esta evaluación se fundamenta en principios formulados a partir de la generalización de la experiencia de juego: definición de los valores relativos de las piezas, la conveniencia de tener la máxima movilidad posible por el tablero, la inconveniencia de tener peones atrasados o aislados… [4]. Teniendo en cuenta esos parámetros, considera las piezas que puede mover, y sus consecuencias n turnos más allá del actual, y pondera cuál de ellas es más favorable. La complejidad de esta función depende del número de parámetros que sirven para evaluar cada posición, el número de turnos que se revisan (Shannon lo limita a tres turnos), y si se tiene en cuenta también lo que puede hacer el adversario. La premisa de la que parte la aplicación de la función es que cada jugadora busca, al mover una pieza en su turno, que la nueva posición suponga la máxima puntuación posible para él y la mínima puntuación posible para la jugadora rival.
Por último, el subprograma 9 selecciona, con arreglo al resultado de f(P), el movimiento que realiza la máquina. Pero este diseño presenta dos inconvenientes: por un lado, se trataría de un programa lento, que necesitaría aproximadamente 16 minutos para realizar cada movimiento; por otro, se trataría de un programa débil, que ante la misma posición realizaría siempre el mismo movimiento.
Shannon recurre de nuevo a la descripción de cómo opera mentalmente una persona cuando juega al ajedrez para proponer dos mejoras del programa: una persona no proyecta y evalúa el movimiento de todas las piezas n turnos, sino que examina el movimiento de unas pocas piezas y sus consecuencias un número mayor de turnos, tomando como puntos de referencia las posiciones estables (aquellas en las que ninguna de las dos jugadoras lleva claramente la iniciativa) y las posiciones de fuerza (aquellas en las que una de las dos jugadoras lleva claramente la iniciativa frente a la otra).
Shannon argumenta que se pueden añadir funciones adicionales al programa ya propuesto para mejorarlo sustancialmente:
Una función g(P) determina, con arreglo nuevamente a ciertos parámetros definidos, si la posición es estable o no. Por ejemplo, si g(P) fuera una variable binaria, su valor podría ser 1 si una pieza es atacada por otra de valor inferior, o por más piezas ofensivas que las defensivas disponibles, o si hay riesgo de jaque; su valor sería 0 en cualquier otro caso.
La otra función h(P, M) evalúa si vale la pena considerar el movimiento M en la posición P. Esta función debe asignar valores altos para los movimientos que llevan a posiciones de fuerza (jaques, capturas, o movimientos que las anteceden), valores medios para movimientos defensivos, y valores bajos para todos los demás. La función h(P, M) permite al programa evaluar si tiene sentido proyectar ese movimiento más turnos o no.
Una tercera mejora sería que, en los casos en los que dos o más movimientos tengan el mismo valor (o casi el mismo), el programa decida entre ellos de forma aleatoria.
Shannon plantea que, con estas modificaciones, un ordenador sería capaz de jugar al ajedrez de forma semejante a una persona que domine el juego, tanto en lo que respecta a la calidad de los movimientos elegidos como el tiempo en el que son llevados a cabo. En estas circunstancias, una máquina cuenta, frente a una persona, con ventajas notables: alta velocidad de cálculo, ausencia de errores, ausencia de pereza y ausencia de autopercepciones distorsionadas (derrotismo o exceso de confianza). Es formalmente posible que una jugadora humana aplique el mismo tipo de funciones que la máquina, y prevea con cierta fiabilidad cuál va a ser su siguiente movimiento, pero esa capacidad formal es inviable en la práctica, por el tiempo excesivo que requeriría una persona para realizar el cálculo y el riesgo de cometer errores.
La máquina carece, en cambio, de flexibilidad, imaginación, y capacidad inductiva y aprendizaje, pero Shannon llega a sugerir la posibilidad, aunque no la formaliza porque los métodos propuestos para ello “no parecen muy prácticos”, de diseñar un programa que aprenda a mejorar su juego, modificando los coeficientes de sus funciones de acuerdo con el resultado de partidas previas.
En todo caso, Shannon concluye que, si una máquina y un ser humano juegan al ajedrez y tienen el mismo margen de tiempo para elegir qué movimiento realizar, es muy posible que la máquina juegue mejor. Y esto aunque, en realidad, el programa propuesto sigue siendo muy rudimentario y no incorpora expresiones formalizadas de muchos otros conocimientos con los que sí cuenta una jugadora humana muy experimentada.
Como hemos dicho al inicio, este artículo de Shannon es de 1950. En 1996 Garry Kasparov, campeón mundial de ajedrez, disputó seis partidas contra DeepBlue, un ordenador específicamente diseñado por IBM para jugar al ajedrez. DeepBlue básicamente aplicaba fuerza bruta, evaluando 200 millones de posiciones por segundo. Kasparov ganó tres partidas, empató dos y perdió una, resultando vencedor frente a la máquina. El año siguiente, sin embargo, Kasparov perdió la revancha.
En 2015, fue noticia mundial que AlphaGo, ganó 5-0 al campeón de Go Fan Hui (2º dan). En 2016, Alpha-Go ganó 4-1 a Lee Sedol (9º dan). El Go es un juego de mesa que, como el ajedrez, simula una guerra entre dos bandos. Las reglas son más simples, porque todas las piezas tienen el mismo valor, pero el juego es computacionalmente mucho más complejo: donde el ajedrez presenta 10123 movimientos posibles el Go alcanza los 10360. El funcionamiento de AlphaGo se basa en el uso de redes neuronales y la aplicación de un método probabilístico, el Método de Montecarlo, desarrollado a finales de la década de 1940, precisamente cuando Shannon redactaba y publicaba el artículo.
Donde Shannon razonaba que no es viable evaluar todos los movimientos posibles para todas las posiciones, y diseñaba dos funciones para limitar el cálculo, AlphaGo explora selectivamente el árbol de posibilidades seleccionando los itinerarios de forma prácticamente aleatoria. Este método se complementa con un doble proceso de aprendizaje automático. En una primera fase, a partir de 30 millones de posiciones extraídas de 160.000 partidas. Después, a través de un proceso de aprendizaje reforzado, en el que las redes neuronales que conforman AlphaGo juegan “contra sí mismas” para mejorar su desempeño, zafándose de los hábitos implícitos en los “estilos humanos” de juego [5].
Lo que la solución que representa AlphaGo tiene en común con la propuesta de Shannon es que toma como referencia el proceso por el que un ser humano decide su siguiente movimiento. La diferencia radica en que la propuesta de Shannon parte de fijar, con sus posibles variaciones a lo largo del juego, el procedimiento algorítmico por el que se descartan unos posibles movimientos y se proyectan otros, mientras que AlphaGo procede de forma aleatoria, corregida a través de las sucesivas fases de entrenamiento y aprendizaje automático.
Pese a todo, eso sí, la propuesta de Shannon sigue gozando de vigencia en la actualidad, a través de la combinación de redes neuronales con motores de cálculo basados en fuerza bruta como Deep Blue. La incorporación del aprendizaje por refuerzo en el proceso de selección de las ramas a estudiar permite corregir los coeficientes de las funciones g(P) y h(P, M) determinados previamente por un conjunto de expertos, aumentando de este modo la eficiencia y permitiendo a la máquina ser imaginativa. De hecho, la que podríamos considerar ahora mismo como la mejor partida de ajedrez es la que jugarían Alpha Zero (o su versión de software libre Leela Chess Zero) frente a Stockfish, que es un motor de cálculo de este tipo [6].
Estas dos estrategias de desarrollo de máquinas digitales capaces de jugar al ajedrez pueden servir, retrospectivamente, para interpretar el propio proceso mental de un ser humano cuando juega al ajedrez. ¿Aplica acaso en el ejercicio del juego las reglas de ponderación que formaliza verbalmente? ¿Procede de forma intuitiva? ¿Es ese procedimiento intuitivo el resultado de la naturalización, de la incorporación inconsciente, de reglas formales de ponderación?
Sea como fuere, el carácter “bioinspirado” de las redes neuronales, que han triunfado allí donde Poe veía un imposible y Shannon un impracticable, nos invita a proyectar una tercera clase de jugador de ajedrez, que será objeto de presentación en la siguiente entrega: el multiprocesador biológico.
Notas
[1] Claude Shannon (1950). Programming a Computer for Playing Chess, Philosophical Magazine, Ser. 7, Vol. 41, No. 314. Disponible en el sitio web de la Università di Pavia: <https://vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf> [Última consulta: 10/03/2023, 10:55].
[2] Significativamente, el otro antecedente que recoge Shannon para contextualizar su trabajo es el autómata ajedrecista diseñado en 1912 por el español Leonardo Torres Quevedo, que realizaba jaque mate con un rey y una torre frente a un rey.
[3] Si bien Shannon tiene toda la razón al afirmar que no existe un método para determinar unívocamente cuál va a ser el desenlace de una posición, los nuevos motores de cálculo (también llamados módulos) de ajedrez permiten concluir con bastante certidumbre ante qué tipo de posición nos hayamos en la mayor parte de los casos. Esto ha traído consigo una serie de importantes cambios en el estudio del ajedrez, que han conducido progresivamente hacia un juego cada vez más preciso, pero también menos atractivo. De una primera fase romántica (a la que se adscribe la Partida inmortal que mencionamos en la primera entrega de esta serie), que interpretaba el ajedrez como un arte y en la que primaba la originalidad y la táctica, se pasó a una mayor sistematización y tecnificación a principios del siglo XX (escuela moderna e hipermoderna), donde primaba la estrategia, el conocimiento posicional. Con la llegada de los módulos se ha hecho necesario el estudio de las aperturas hasta fases mucho más avanzadas de las partidas (ya que ahora es posible determinar qué lineas dentro de cada apertura conducen a posiciones desventajosas) y, al mismo tiempo, la búsqueda de nuevas líneas, peores de acuerdo a los parámetros clásicos, pero menos estudiadas; lo que permite sorprender a las rivales. Este proceso evolutivo también ha conducido a una forma de jugar llamada “no humana”, que imita el funcionamiento de los motores de cálculo, basado en jugadas aparentemente absurdas, pero que conllevan una ventaja táctica a largo plazo. De esta forma, evolucionamos hacía un ajedrez cada vez más “maquinal”. ¿Estaremos cada vez más cerca de que, como reflexionaba Shannon, el ajedrez pierda su interés?
[4] No olvidemos que el texto de Shannon se escribió en los años 50 del pasado siglo: desde entonces el ajedrez ha evolucionado sustancialmente, habiéndose mejorado la comprensión de ciertos aspectos del juego. Por eso, algunos de los términos y conceptos que emplea Shannon en su artículo han quedado obsoletos, si bien la idea general de su algoritmo sigue siendo igualmente válida.
Por ejemplo, en términos más actualizados, los parámetros básicos para evaluar una posición serían: el material (valor de las piezas), la actividad de las piezas (que incluiría su movilidad y las amenazas que crean), el espacio (control de las casillas; por ejemplo, el dominio de una columna por parte de una torre) y la estructura de peones (por ejemplo, si hay peones aislados, es decir, que no tienen peones del mismo color en las columnas contiguas; o peones pasados, es decir, aquellos que no tiene peones del color contrario en las columnas contiguas; etc.).
[5] Para profundizar en el funcionamiento de AlphaGo y su diferencia con DeepBlue, ver el artículo de Christoph Koch, “How the Computer Beat the Go Master”, Scientific American, 19 de marzo de 2016, <https://www.scientificamerican.com/article/how-the-computer-beat-the-go-master/> [Última consulta: 10/03/2023, 14:20].
[6] Estos dos motores de cálculo llevan monopolizando las finales de la práctica totalidad de los torneos de ajedrez para computadoras (como el Top Chess Engine Championship) durante los últimos 5 años. Sorprendentemente, Stockfish lleva un tanteo de victorias muy superior. Pese a todo, hay que señalar que la gran parte de las partidas acaban en tablas. Por ejemplo, en el 13th Computer Chess Championship acabaron en tablas 174 de 200 partidas.
