Hay más tablas en el ajedrez

¿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 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.

Alan Turing

De todo lo anterior ya han pasado unos cincuenta años y el desarrollo de programas de ajedrez ha manifestado un continuo 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 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.

Eugene Nalimov

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 Rey. 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 diagrama y 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. 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.

Pues bien, en la Universidad Iberoamericana, este semestre estoy dando un curso de Reconocimiento de Patrones. Aunque la parte teórica nunca me ha terminado de gustar (en mi opinión hay demasiadas matemáticas y creo que el enfoque debería ser más práctico, aunque comprendo perfectamente que de esta manera se le da el formalismo y rigor necesarios), pero en la parte práctica, de experimentación, hay N temas que pueden abordarse.

De esta manera, dejé como tarea escribir un juego de gato pero que lo resolviera usando solamente patrones. La idea era generar los patrones necesarios para siempre ganar (empezando la computadora y tirando ésta siempre en el centro), y a cada jugada del adversario, el sistema debería buscar el patrón correspondiente, aplicarlo y generar la jugada correcta. ¡Algo así como generar las tablas de Nalimov para el tres en línea! Evidentemente se necesita un análisis hacia atrás, empezando por las posiciones finales del tres en línea y quitando movimientos de los jugadores.

Uno de mis estudiantes, Daniel González, hizo su programa en Java y utilizó dos trucos: primero generó 42 patrones (incluyendo el del tablero vacío) y de ahí tuvo que ubicar posibles respuestas que se salieran de los patrones utilizando giros del juego del gato (90, 180, 270 grados). De esta manera, como el juego tiene simetría, pudo eliminar información redundante y logró un bonito programa que resuelve (simplemente buscando el patrón correcto), cada jugada que debe hacer la computadora para ganar o al menos, nunca perder. Y hago énfasis en esto: el programa no tiene un algoritmo para resolver el juego del gato o jugar bien. Simplemente es un sistema de búsquedas de patrones y las acciones a realizar cuando el patrón se encuentra. Cabe señalar que están todos los patrones posibles.

Es interesante que con solamente 42 patrones el juego de tres en línea pueda resolverse a la perfección (considerando la restricción de que la computadora empieza y siempre tira en el centro, para así hacer menos difícil la tarea asignada).

Quien quiera jugar contra el software de Daniel mándeme un mensaje a mi correo [morsa(arroba)la-morsa.com] y se lo envío. Se necesita una versión de Java que sea 6.0 o superior.