Me encanta poder dar un como titular como éste. Ha sido una de las cuestiones que relacionada con teoría de juegos e informática que desde siempre me ha parecido intrigante y apasionante. Hace un par de años ya comenté de pasada los trabajos de Jonathan Schaeffer sobre juegos como el póker y las damas. En los años 90 este ingeniero creó Chinook, el primer programa que jugaba a las damas a nivel de torneo, que llegó a ganar al campeón del mundo humano de la época, el mítico Marion Tinsley. Esa historia está narrada maravillosamente en One Jump Ahead, un precioso libro que narra la historia del desarrollo de ese software desde el punto de vista de su programador, aunque el verdadero protagonista fuera el software de «la máquina».
A pesar de su aparente sencillez y de que cualquier niño puede aprender en un rato a jugar, las damas (checkers o draughts en inglés) encierran cierta complejidad. Existen diferentes reglas de juego según las versiones y países, que tienen que ver con los movimientos de las «reinas/damas» o incluso el tablero, que puede ser más o menos grande (8×8 ó 10×10). Chinook y el estudio se refieren a la versión «americana» o «inglesa».
La competición de damas de alto nivel entre humanos atravesó por diversas épocas, y de hecho a diferencia del ajedrez o el Go en las competiciones de más alto nivel de Damas hubo que adaptar las reglas para que hubieran de jugarse ciertas aperturas predeterminadas, sorteadas al azar, debido a que el alto nivel de los jugadores garantizaba las tablas con ciertas estrategias ganadoras o defensas para forzar el empate (tablas).
El trabajo de Schaeffer, de la Universidad de Alberta en Canadá, ha requerido 18 años, comprobando todas las posibles combinaciones del juego que comienza con las 16 piezas en el tablero de 8×8. El total son unas 1020 posiciones diferentes. El proceso comenzó por el tejado: computando las bases de datos de finales con pocas piezas, de modo que una posición anterior pudiera simplificarse a otra menos compleja. De este modo se calculaba si el movimiento era ganador, perdedor o podría forzar las tablas. Las tablas o «librerías de finales» de unas pocas piezas ya ayudaron a Chinook a ganar al campeón del mundo en los 90. Desde hace tiempo ya se conocían todas las soluciones para diez piezas o menos (39 billones de posiciones) y que se resolviera el resto era cuestión de tiempo. Con unos 200 ordenadores trabajando a tiempo completo, que en los últimos años pudieron reducirse a unos 50 más potentes, se pudo completar el trabajo. Schaeffer tuvo que simplificar el número de posiciones totales a examinar eliminando ciertas ramas del árbol de jugadas equivalentes, procurando evitar cualquier posible error.
El resultado final es que matemáticamente un juego perfecto de damas acaba siempre en tablas. Un ordenador que empieza a jugar con las negras, con todos los conocimientos del análisis, es capaz de no perder nunca, y podría incluso ganar si el adversario comete un error. Pero si ambos contendientes juegan siempre «la partida perfecta» en base al análisis completo y perfecto, las tablas están garantizadas. Incrédulos y optimistas pueden jugar en línea en la Web contra Chinook para comprobarlo:
Las librerías de finales exhaustivas también se han empleado en los programas que juegan al ajedrez. Gracias a estas tablas con finales de reyes y varias piezas mayores las máquinas puede comenzar diez o quince jugadas antes una secuencia que las lleve a alguna posición ganadora que ya está almacenada en su memoria, algo que sería realmente complejo para un ser humano por lo tortuoso del camino. Debido a su complejidad, algunas soluciones de esos finales requieren más de cien o doscientos movimientos para forzar una victoria. En su día esto hizo que se cambiaran varias veces las reglas del ajedrez (la conocida regla de los 50 movimientos para declarar una partida en tablas), pero se encontraron tantas excepciones que se volvió a la formulación original. La resolución matemática del rey de los juegos de tablero es ciertamente uno de los Santos Griales del Ajedrez. El ingeniero Ken Thompson califica a estos finales deterministas como «jugar al ajedrez con Dios.» Más conocido por ser uno de los padres del sistema operativo UNIX, Thompson tiene desde hace años en su web publicadas las tablas de finales con pocas piezas que desarrolló él mismo hace años y se han usado en diversos programas.
Hay más información sobre el importante avance que ha supuesto esta «resolución matemática del juego de las damas» en varios sitios, como G de Geek, Chinook, el programa que jamás pierde a las damas y también en inglés en NewScientistTech, Checkers 'solved' after years of number crunching y Physorg.com, Computer Program Can't Lose at Checkers. La revista Science publicará los resultados de Schaeffer en los próximos días.
La próxima parada será sin duda resolver matemáticamente el mucho más complejo juego del ajedrez. ¿Juegan blancas y ganan?
{Foto (CC) Paul Brennan @ publicdomainpictures.net.}
Relacionado:
- Kasparov vs Deep Blue, un buen libro sobre el reto hombre-máquina en ajedrez, con información sobre las estrategias y técnicas de diversos programas ajedrecísticos.
