Tuesday, March 10, 2009

¿Cómo es que funcionan las tablas de Nalimov?

El ajedrez por computadora es uno de los terrenos más antiguos de la inteligencia artificial, habiendo empezado en los años 1940. Claude Shannon propuso los criterios formales para hacer que un programa jugara al ajedrez en un artículo ya clásico al respecto. Fue hasta 1951 cuando Alan Turing (ver primera foto), diseñó un programa primitivo que jugaba al ajedrez, que asignaba valores para material y movilidad, el programa “jugaba” al ajedrez basándose en los cálculos manuales de Turing porque de hecho, no había código de computadora, era una simulación en papel.

De todo lo anterior ya han pasado unos cincuenta años y el desarrollo de programas de ajedrez ha manifestado un contínuo avance. Gracias al software de esta naturaleza los ajedrecistas hemos visto cómo algunas grandes combinaciones han sido refutadas por los ingenios de silicio que no tienen empacho en mostrarnos nuestros errores. La computadora no sabe de sentimientos, de miedo, de psicología del rival, de nada de eso. Por ello siempre juega con una constancia inalterable y todas sus jugadas se basan en la valoración que les da el código previamente programado.

También hemos notado las debilidades inherentes de estos programas, particularmente en lo que se refiere a los finales de partida. Es tan difícil el ajedrez que en muchas ocasiones hallar el triunfo (o el empate) en una posición con pocas piezas parece mucho más complejo que cuando se tienen más figuras en el tablero. Por ejemplo, los finales de torres y peones, muchos de ellos son extremadamente difíciles y ya algún gran maestro habría dicho aquella famosa frase de “nadie en el mundo juega bien los finales de torres”, aunque no sé a quién se le atribuye dicha afirmación.

Ante esta situación, en 1965, Richard Bellman propuso la creación de una base de datos para resolver finales de ajedrez y damas utilizando ajedrez retrospectivo. Esto significa que en lugar de analizar hacia adelante a partir de la posición actual, la base de datos analizaría hacia atrás desde posiciones donde un jugador da jaque mate. Así, una computadora de ajedrez no necesitaría analizar nunca más posiciones finales durante la partida porque estarían resueltas de antemano. No volvería a haber errores porque las bases de datos de tablas siempre jugarían el mejor movimiento posible. Ingeniosa idea, sin duda.

En 1970, Thomas Ströhlein publicó una tesis doctoral con análisis de las siguientes clases de finales: RDR, RTR, RPR, RDRT y RTRC. Ken Thompson, de Laboratorios Bell y creador de la primera computadora a la que se le otorgara el título de maestro nacional en los Estados Unidos, ayudó a extender las bases de datos para cubrir todos los finales de cuatro y cinco piezas. Las contribuciones más recientes en este campo se deben a:

  • Eugene Nalimov (ver foto más arriba) por el que las base de datos de tablas de finales reciben su nombre.
  • Eiko Bleicher, que ha adaptado el concepto de base de datos de tablas a un programa llamado "Freezer".
  • Guy Haworth, un académico de la Universidad de Reading, que ha publicado intensivamente en el ICGA Journal.
  • Marc Bourzutschky y Yakov Konoval, que han colaborado para analizar los finales con siete piezas en el tablero.

El análisis de todos los finales de hasta seis piezas (incluyendo los dos reyes) se completó en 2006. (Sin embargo, las bases de datos de tablas con cinco piezas contra un sólo rey no se han generado porque el resultado es casi siempre obvio.) Las bases de datos para todas las posiciones de hasta siete piezas se sigue elaborando y se estima que se termine para el año 2015. Cuando las bases de datos de siete piezas estén completas, componer una miniatura tradicional será obsoleto.

Un ejemplo sencillo puede ser ilustrativo. Imaginemos el final de Rey y Dama contra R. En este caso una tabla de finales para este particular final seria escribir un software que hallara todas las posibles posiciones de esas tres piezas. Obviamente hay restricciones, por ejemplo, los reyes no pueden estar en casillas contiguas. Así como el rey enemigo no debe estar en casilla contigua con la dama tampoco. Si los cálculos no me fallan, hay menos de 262144 posiciones (64 al cubo), pues en este cálculo no he quitado las restricciones mencionadas. Digamos pues que tenemos entonces todas las posibles posiciones de este final elemental. Ahora clasificamos las posiciones que son mate y las colocamos en una jerarquía aparte. A partir de ahí, nos vamos moviendo hacia atrás, retrocediendo y así podremos saber qué jugadas, o mejor dicho, secuencias de posiciones, nos llevan a las posiciones de jaque mate. Un documento del propio Ken Thompson explica este procedimiento.
Ken Thompson

De esta manera se han generado las tablas hasta de seis piezas. Esto es equivalente a jugar ajedrez simplemente buscando en una gigantesca base de datos (un terabyte, algo así como 1000 gigabytes de datos), la posición que nos interesa y así saber qué posición es la que sigue que debemos jugar. Esto, a decir de Ken Thompson es “Jugar al ajedrez con Dios”. Aunque todo esto parece ser sencillo es muy laborioso y se necesita evaluar cada posición para saber cómo seguir de una posición a la siguiente (si es que se busca el triunfo o bien se intenta encontrar un empate en una posición difícil).

Una simpática anécdota que involucra estas tablas de finales me tocó vivirla en el 2003, en el Torneo de Linares. Estábamos viendo en la sala de prensa el difícil final de Rey, Dama y peón contra Rey y Dama, en donde Garry Kasparov estaba luchando por el empate. Peter Leko buscaba denodadamente en triunfo y ambos consumían los últimos minutos antes de llegar a las siete horas de juego. Aquí si mal no recuerdo llegó Leontxo García a decir: “¡que jugadores más malos! ¿no ven que es mate en 92 jugadas?”. Las tablas de Nalimov mostraban el triunfo en un horizonte de jugadas imposible para los seres humanos. La partida mencionada terminó en tablas.

Otro interesante caso fue la partida que Kasparov jugó contra el mundo en 1999 a través de Internet. Se llegó al final que se muestra en el siguiente diagrama y que en ese momento no se sabía si las negras estaban perdidas o acaso podían rescatar medio punto. La posición del diagrama muestra el momento después de 55.Dxb4 cuando la partida se redujo a una posición de seis piezas.

Kasparov vs. el Mundo
Internet 1999


Un análisis hecho con la tabla de finales ahora demuestra que la partida está totalmente perdida para el negro en 82 movimientos. Sin embargo, no se conocía en ese momento y la partida continuó durante siete movimientos más para el blanco antes de que el Equipo del Mundo decidiera rendirse.

Por todo lo anterior, se me ocurrió que habría una manera más ilustrativa de comprender todo este asunto. Para ello tomé un juego más sencillo, el de tres en línea también llamado gato o tic-tac-toe. Este uno de los pasatiempos más interesantes para programar por computadora. Por un lado, es lo suficientemente sencillo para que no requiera de demasiados recursos. Por otra parte, es relativamente complejo y por ende, tampoco resulta un ejercicio trivial. Soluciones del juego del gato y programas que lo juegan correctamente hay muchos. En mis cursos de Prolog (programación lógica, inteligencia artificial), es una tarea que dejo de rigor a los alumnos.

De hecho, el matemático Martin Gardner alguna vez contó que cuando era estudiante de secundaria estaba en una clase de matemáticas intentando hallar alguna fórmula para resolver el gato. Su maestro lo vio (de acuerdo a su criterio, jugando al gato el solo), y le reprendió. Le dijo que mejor estudiara matemáticas y dejara esos jueguitos tontos para su tiempo libre.

A partir de esto se me ocurrió como un buen ejercicio para entender las tablas de Nalimov el hacerlas para el juego del gato. Los resultados de esto pueden verse aquí.

1 comment:

Javier G. Maneiro said...

Me ha gustado mucho este artículo, muy interesante.

Un saludo.

Tablajedrez.