Turing y el ajedrez

PEDRO MESEGUER

Alan M. Turing desarrolló el primer programa de ordenador de la historia para jugar al  ajedrez. Fue a  finales de los años 40, y está descrito en su artículo Digital Computers Applied to Games (que se publicó en el libro Faster than Thought, editado por B. V. Bowden, Pitman, Londres 1953). Allí Turing sienta lo que serán las bases de los programas posteriores de ajedrez por ordenador: la simulación de secuencias de movimientos, la evaluación de los estados finales de esas secuencias y la propagación de esa evaluación a los estados directamente sucesores de la configuración actual de juego. Turing elegía el siguiente movimiento como el que conducía al estado de mejor evaluación entre todos los estados posibles.

Aunque este programa no fue implementado en su tiempo (los ordenadores eran muy escasos y con capacidad muy limitada), en 1952 Turing jugó una partida con Alick Glennie en donde Turing simulaba (con papel y lápiz) la ejecución de su programa (se puede ver la partida aquí). Turing perdió en 30 movimientos, pero viendo la partida uno puede comprobar que el programa de Turing no hacía movimientos estúpidos.

Actualmente, los ordenadores juegan bastante bien al ajedrez. ¿Cómo lo hacen? Conceptualmente, la idea no es complicada. Supongamos que hay dos jugadores, H y O (por humano y ordenador), el estado de la partida es s y le toca mover a O. El ordenador (jugador O) simula en su memoria todos los movimientos legales que podría hacer según las reglas de ajedrez. Para cada uno de esos estados, O simula  en su memoria la respuesta de H, considerando todos los posibles movimientos legales de H. De nuevo, para cada posible movimiento de H, el ordenador simula todos los posibles movimiento legales que O podría hacer. Este proceso se podría repetir hasta encontrar estados ganadores o perdedores, pero esto es inalcanzable porque exige demasiada memoria (mucha más memoria que la que cualquier ordenador podría tener, un número gigantesco). Esto hace que sólo se puedan desarrollar en memoria unos pocos niveles de este árbol de búsqueda (denominado técnicamente como “árbol de juego”). Como en el último nivel explorado no suele haber estados ganadores o perdedores, se ha de evaluar lo “bueno” o “malo” que es cada estado de ese nivel. En esa evaluación interviene el número y tipo de piezas de cada jugador, su disposición en el tablero, el número de piezas amenazadas del otro jugador, etc. Mediante el algoritmo mini-max (actualmente con su versión mejorada denominada alfa-beta), se puede saber cual es el mejor movimiento que O puede hacer en el estado s de la partida para llegar al mejor estado encontrado en ese último nivel desarrollado (suponiendo que H elegirá en el futuro las mejores jugadas entre las posibles).

En Nueva York, en mayo de 1997, se jugó un torneo de ajedrez al mejor de 6 partidas  entre el campeón mundial, Garry Kasparov, y el ordenador Deep Blue (un superordenador especializado para jugar al ajedrez, desarrollado por IBM). Este torneo se organizó tras otro encuentro entre Kasparov y una versión anterior de Deep Blue, que se celebró en Filadelfia en febrero de 1996, en donde Kasparov ganó a Deep Blue por 4 a 2.

Sin embargo, en 1997 las cosas sucedieron de manera diferente. Kasparov perdió por 3,5 a 2,5 (Deep Blue ganó 2 partidas, Kasparov ganó 1 partida y hubo 3 partidas empatadas). Aunque Kasparov no quedó satisfecho de ese torneo y planteó dudas sobre la honestidad de Deep Blue, también es cierto que quedó impresionado por el poder de la máquina y dijo en una conversación que “la cantidad había devenido en calidad” (quantity became quality). Tras este torneo, IBM desmanteló el equipo de Deep Blue, formado por seis personas. Hoy el ordenador se puede ver en un museo, y los componentes del equipo de Deep Blue ya no están en IBM.

¿Qué estructura tenía Deep Blue? Era un superordenador especializado para jugar al ajedrez, con una unidad de procesamiento paralelo capaz de explorar dos millones de posiciones por segundo. El programa de Deep Blue se basaba en un algoritmo alfa-beta paralelo, con una amplia librería de aperturas y finales (un buen comienzo y una buena finalización tienen mucha importancia en una partida de ajedrez). Además, Deep Blue contaba con una sofisticada función de evaluación (la función que evalúa lo “bueno” o “malo” que es un determinado estado). Deep Blue también incorporaba la idea de extensiones singulares, situaciones muy poco frecuentes en donde se debe hacer una búsqueda más profunda para encontrar una mejor solución.

Hoy día los programas de ordenador que juegan al ajedrez tienen una escala de fácil a difícil, en donde se modula la capacidad del programa según se enfrente a jugadores noveles o expertos. Básicamente, lo que cambia es la capacidad de anticipación del programa (o profundidad a la que busca el programa en el árbol de juego): juego fácil significa anticipar pocas jugadas (búsqueda a poca profundidad), y a medida que se aumenta la dificultad del juego el programa realiza mayor anticipación (búsqueda a mayor profundidad).

Parece inevitable que el futuro del ajedrez pase por los ordenadores. Por un lado, con las mejoras de velocidad en procesadores y memorias, y por otro con las mejoras en programas y algoritmos, no parece exagerado pensar que durante el siglo XXI se alcance que el campeón mundial de ajedrez sea un ordenador. Esto no impedirá que se sigan celebrando torneos entre humanos por un lado, y entre máquinas por otro, pero los torneos entre humanos y máquinas posiblemente ya no tengan lugar.

El programa de ajedrez de Turing ha sido finalmente implementado. Kasparov jugó contra él en Manchester el pasado mes de junio, en la conferencia del Centenario de Turing (se puede ver la partida aquí). Kasparov ganó al programa sin dificultad, en 16 jugadas, pero en un comentario posterior resaltó el extraordinario avance que representó este programa en el momento que fue escrito, cuando prácticamente no había ordenadores disponibles. Y añadió: “si Turing hubiera vivido más, el mundo hoy sería un lugar diferente”.

 

Pedro Meseguer es investigador científico del CSIC.

Comments

[Publicado por: Pedro Meseguer]

El último comentario sobre la velocidad de proceso de Deep Blue es correcto: era capaz de explorar 200 millones de posiciones por segundo, no dos millones como erróneamente se afirma en en artículo.

[Publicado por: Kim]

Creo que el dato sobre la velocidad de Deep Blue es erróneo. Mi ordenador actual (claro, es muy potente), realiza 3,2 mill. de jugadas por segundo. Creo que Deep Blue hacía 200 Millones y no dos como aquí se indica.

[Publicado por: guarionex luciano melo]

kasparov era jugador profesional turing pensó que el tenia mucha capacidad para jugar con kasparov donde era el expertos con la maquina IBM pero ya no estaba en el sistema.

[Publicado por: Tim]

Interesantísimas descripción y breve historia del ajedrez "mecanizado", tal vez prolegómenos a la implementación de algoritmos que permitan una suerte de toma de decisiones por parte de máquinas. Aunque la "moral" (bondad-maldad) contenida en tales algoritmos sea, en último término, la dictada por los humanos que los programen.

[Publicado por: Pedro Meseguer]

Jugar a parchís es más fácil que jugar al ajedrez. Basicamente tienes que decidir cual de las 4 fichas mueves un número de casillas determinado por el resultado de los dados, mientras que en ajedrez el número de movimientos posibles es mucho más alto.

[Publicado por: Sergio]

Yo estoy diseñando un ordenador que sepa jugar al parchís.

[Publicado por: carlos]

No,no yo no desprecio a Turing. Muy lejos de eso. Digo que al escultor que ha hecho el busto debía guilotinarsele y que precisamente este hombre se merecía algo más digno que no esa cabeza qaesimódica que le han fabricado al quere darle, ceo, unaimagen de sabio oficialista. . Turing era, curiosamente un buen atleta físico. Era un corredor de medio fondo parece que bastante potente y tenía previsto competir oficialmente como corredor. Eso sí, en tiempos de Turing creo primaba todo lo más como maquina práctica el computador analógico, válido solo para una tarea. El creo entrevió el digital que tenemos hoy para varias tareas dispares.
Pero parece Churchill tenía miedo a las ideas de Turing y mandó destruir sus máquina de Manchester o quizá quede algo oculto cen los alamacenes del agente 007. Supongo los aliados conservaron al menos sus papeles.

[Publicado por: Pedro Meseguer]

No, Turing no era un jugador profesional de ajedrez. En el artículo mencionado, Turing dice que se inspiró en su propia forma de jugar para desarrollar su programa.

[Publicado por: Miguel Ángel]

@carlos, no se puede despreciar de ese modo los avances que propició Turing. La idea no es que fuera un jugador profesional de Ajedrez, sino que estableció unas bases para que se desarrollaran después los programas de computación de ajedrez. A Turing mucho le debemos, sobre todo en el área de la investigación computacional. Será por eso que, al tener hoy en día pocos elementos tangibles asociables a él, no se le da el valor que realmente tiene.
Su valor reside en su investigación realizada, que en el fondo es base de muchos avances modernos.
Gracias, Alan Turing.

[Publicado por: carlos]

Desde luego, al tipo que ha hecho ese busto deberían obligarle a tomar cianuro como hizo Turing.
Referente al ajedrez, aparte Turing, para resolver el problema de la máquina Enigma de los alemanes, fueron llamados los componetes del equipo británico de ajedrez que estaba en Argentina, creo, cuando empezaron las hostilidades preparando un campeonato, así como toda clsse de expertos en crucigramas, acertijos y en fin, asuntos menores que las ideas de Turing pero que todos ayudaron. El no lo hizo solo. En sí, Turing creo no era un jugador profesional de ajedrez.