Mi aproximación al juego de Damas comenzó como un efecto colateral de mi afición por el  Ajedrez; cuado estaba en el bachillerato, yo solía llevar un tablero pequeño con piezas provistas de imanes en mi bolso, y siempre había algún compañero que me retaba a jugar Damas durante los tiempos libres. Cuando tenía 15 años, me asocié con una par de amigos, Martín y Jesús, con los que compartí largas veladas jugando Damas, y en algunos casos nos daba por jugar hasta el amanecer. Ocho años habían pasado desde nuestra última velada de competencias en el tablero de 64 casillas, cuando me encontré con Martín en su casa. El estaba leyendo un artículo de la revista de divulgación científica “Muy Interesante”, que me cedió al finalizar para que lo leyera yo también: se trataba de un artículo sobre el primer campeonato hombre-máquina celebrado para un juego de estrategia –el match entre Marion Tinsley y Chinook. Muchos años han pasado desde aquella primera lectura, y aun hoy me sigue emocionando recordar lo que sucedió en 1992.

¿Quién era Marion Tinsley? Nada más y nada menos que el más grande jugador de Damas de la historia. Tinsley nació en un pequeño pueblo de Ohio el 3 de febrero de 1927, y, como muchos habitantes del medio oeste estadounidense, aprendió a jugar Damas a temprana edad. Se dice que de niño no mostró nada extraordinario sobre el tablero, y su primer gran rival fue la Sra. Kershaw, una anciana que lo derrotaba una y otra vez acompañando cada victoria de risas y burlas. El joven Marion, ya de 14 años de edad, estaba molesto por su falta de progresos en el juego, y fue por una casualidad que, mientras buscaba un libro de matemáticas en la biblioteca local, se encontró con dos libros sobre el juego de Damas[1]. A partir de entonces, Marion alternó el estudio del juego con sus otras dos pasiones; el estudio de la Biblia y el de las matemáticas.

Marion Tinsley, de 25 años (izq.), contra otro de los grandes de la historia: Newell Banks. Tinsley ganó el match.


A los 27 años, Tinsley comenzó su ascenso final al título de campeón mundial al triunfar en el torneo de la American Checkers Federation (ACF), y derrotando en sendos matches a Asa Long y a Walter Hellman. En 1958 obtuvo el reconocimiento como campeón mundial al derrotar al campeón inglés, Derek Oldbury con un contundente resultado de nueve victorias, una derrota y veinticuatro empates. Luego de estos éxitos, Tinsley renunció al título mundial y se dedicó a sus labores como profesor de matemáticas en la Universidad de Florida, ya que consideró que ya no había retos que lo motivaran a seguir compitiendo.

En 1970, Tinsley hizo su reaparición en el torneo nacional de la ACF celebrado en Houston, ganándolo fácilmente, éxito que repitió en el campeonato de 1974. Esto le permitió desafiar a Elbert Lane Lowder por el título mundial en 1975, derrotándolo inapelablemente. Luego de estos sucesos, Tinsley inició su segundo retiro, aunque hizo apariciones ocasionales en los principales torneos, al tiempo que daba instrucciones a un grupo selecto de discípulos. Uno de ellos, Don Lafferty, desafió a su maestro en 1989, ganando Tinsley por dos victorias sin derrotas y treinta y seis empates.

Mientras que Tinsley machacaba a cuanto rival humano se atrevía a oponérsele, un programa de investigación en inteligencia artificial avanzaba en la manera de resolver el juego de Damas[2]. En 1989, un grupo de la Universidad de Alberta, en Canadá, lanzó un proyecto de resolución centrado en un programa denominado Chinook[3]. El principal reto para la resolución de un juego radica en la complejidad del mismo[4]; la complejidad a su vez proviene de dos fuentes, la primera es la complejidad de la decisión, que incluye las dificultades para que un programa genere buenas jugadas[5], y la segunda es la complejidad espacial, que se refiere al tamaño del espacio de búsqueda[6]. En el caso de las damas, las combinaciones posibles de las 24 fichas son del orden de 10²⁰, lo cual lo hace más complejo que el Backgammon (10¹⁹ combinaciones), pero menos complejo que el Ajedrez (10⁵⁰ combinaciones). Un elemento clave en las posibilidades de resolver el juego de damas es trabajar desde las posiciones más sencillas, ya que usualmente el cambio de fichas tiende a hacer que la mayoría de las partidas posibles termine en posiciones relativamente simples. Una vez resueltas, estas posiciones simples se archivan en bases de datos y pueden ser usadas por Chinook para “saber” como liquidar un juego sin necesidad de recalcular.

Para 1989, Chinook disponía de una base de datos con todas las posibilidades de 4 fichas o menos, lo que se traducía en siete millones de posiciones; ese año el programa se coronó campeón de la Olimpiada de Computadoras. Al año siguiente, con una base de datos de posiciones resueltas para seis fichas o menos (lo que involucró la cantidad de dos mil setecientos millones de posiciones), Chinook ganó el campeonato del estado de Mississippi, para luego clasificarse en segundo lugar en el campeonato de los Estados Unidos, a pesar de haber quedado invicta y empatar las cuatro partidas que jugó con quien a la postre quedó campeón: Marion Tinsley.

De acuerdo a las reglas, Chinook se había ganado el derecho de retar a Tinsley por el título de campeón mundial, pero la ACF y la EDA (English Draughts Association) se negaron a validar a un programa como retador. Marion Tinsley, quien había encontrado una motivación para jugar con su máxima capacidad[7], renunció a su título en 1992 y acordó disputar un match con Chinook. La maniobra forzó a la ACF y la EDA a crear un nuevo título, el campeonato de hombres y máquinas, para así poder participar en el match.

Tinsley, quien además era pastor de la iglesia bautista, declaró antes del match que iba a ganar porque “estoy seguro de que tengo un mejor programador que Chinook. Dios me ha dado una mente racional”. El match comenzó el 17 de agosto de 1992 en Londres con Tinsley conduciendo las fichas blancas, y la primera partida fue como sigue[8]:

10-15 (en el sorteo[9] salió la conocida Apertura Kelso) 23-18 6-10 18-14 (Aquí comienzan una serie de cambios para debilitar la “esquina doble” del negro) 9-18 24-19 15-24 22-6 1-10 28-19 11-15 27-24 8-11 25-22 11-16 26-23 5-9 22-17 (Tinsley ya avizora una coronación) 16-20 31-27 4-8 17-13 8-11 13-6 2-9 29-25 11-16 21-17 7-11 (sería erróneo 9-13, porque luego de 25-22 al negro se le acaban las jugadas rápidamente) 17-13 (la ficha de Tinsley se encamina a la coronación, pero… )9-14 13-9 14-18 (…Chinook encuentra esta excelente reacción!) 23-7 16-23 27-18 20-27 32-23 15-29 (pero su ficha coronada está atrapada y Tinsley corona dos rápidamente)7-2 11-15 9-5 12-16 5-1 15-19 23-18 16-20 1-6 19-23 6-10 20-24 10-15 24-27 2-6 27-31 6-10 31-26 18-14 26-22 14-9 22-17 9-6 23-27 15-19 27-32 19-24 32-28 (aquí se inicia una serie de repeticiones) 24-19 28-32 19-24 32-28 24-19 28-32 19-24 32-28 24-19 28-32 19-24 32-28 24-19 28-32 19-23 32-28 23-19 28-32 6-1 32-27 1-5 17-13 19-16 27-24 10-15 24-28 16-19 28-32 19-23 32-28 15-19 28-32 19-24 3-7 24-27 7-10 (se acuerda el empate)

 Posición Final de la primera partida

Según los programadores, disponer de una nueva base de datos para siete piezas o menos (con treinta y siete mil millones de posiciones), ayudó a Chinook a resistir exitosamente la presión ejercida por Tinsley. Siguieron tres rápidos empates, hasta que en la quinta partida el campeón mundial obtuvo su primera victoria, explotando magistralmente la debilidad de las dos fichas negras (en 7 y 11) que fueron asediadas sin piedad por las dos fichas coronadas de Tinsley hasta que una de ellas cayó; y luego en la séptima también tuvo ventaja decisiva pero permitió que Chinook se escapara. Cuando todo indicaba que el campeón mundial arrasaría en el match, Chinook ganó las partidas 8 y 14, y por primera vez desde 1958, Marion Tinsley debía venir de atrás para ganar.

Para entender lo que pasó después, debemos recordar la frase que Tinsley dijo antes del match. Los programadores de Chinook son humanos, y como tales se equivocan. En la partida 18, la computadora presentó un fallo y, en una posición complicada, ¡Chinook terminó agotando su tiempo! Luego, en la partida veinticinco, Tinsley mediante una inversión de movimientos, sacó a Chinook de su “libro de aperturas”[10], lo cual implicó que cometiera un par de errores que resultaron decisivos. Con un punto de ventaja, Tinsley solo debía entablar el resto de los juegos y así ganar el match. El momento de la verdad llegó con la partida 39, la última del match. El jefe de programadores de Chinook, Jonathan Schaeffer cuenta que antes del sorteo de la apertura, estuvo pidiendo mentalmente: “que salga la White Doctor”, lo cual efectivamente ocurrió. Esta apertura fue analizada extensivamente por Marion Tinsley en uno de sus libros, en donde propone el sacrificio de una ficha como única forma en que el negro pueda sobrevivir. El juego fue como sigue, con Tinsley jugando las piezas negras:

10-14 22-18 12-16 24-20 (Esta es la posición crítica de la apertura White Doctor) 16-19 (y este es el sacrificio de ficha propuesto por Tinsley en su libro) 23-16 14-23 26-19 (Según Schaeffer, en este momento Chinook valoró esta posición en +84 a su favor[11]… ) 8-12 25-22 6-10 29-25 11-15 30-26 (…para luego “darse cuenta” de que debe devolver la pieza, con lo que su valoración cayó a +25 a su favor) 15-24 28-19 4-8 22-18 8-11 18-15 (aquí es cuando se regresa el obsequio, ya que se amenaza 10-15 ganando) 11-18 26-22 10-15 19-10 12-19 22-15 7-14 27-23 19-26 31-22 9-13 (La retaguardia blanca es un colador, mientras que el negro está en mejor posición para evitar coronaciones) 20-16 (la única oportunidad de coronación para el blanco seria colocando una ficha en 12, y pasar la que está en 15 hasta 4) 2-6 15-11 6-10 32-27 (no servía 11-7, por la respuesta 14-17) 10-15 27-24 14-18 (encaminándose a la coronación) 16-12 18-23 11-8 23-27 8-4 27-32 4-8 1-6 8-11 6-10 (¡maravillosa jugada!) 11-18 10-14 18-9 5-14 22-18 (tarde o temprano habría que regresar la ficha) 14-23 25-22 23-26 24-20 32-27 22-18 27-23 18-14 23-18 14-9 26-31 9-5 31-27 5-1 (El negro gana la partida[12])

Tinsley se proclamó ganador del encuentro con cuatro victorias, dos derrotas y treinta y tres empates. ¿Cómo fue posible que el hombre haya vencido a la maquina? La explicación que ofreció Tinsley, ahora hablando como matemático, es que entre las veinte jugadas adelante que podía calcular la maquina y la base de datos de posiciones simples había una zona oscura en donde las limitaciones del programa no podía garantizar llegar a posiciones ganadoras, así que el trató de generar posiciones donde la complejidad de la decisión sea tan grande que hiciera de la zona oscura un lugar peligroso para Chinook. ¿Por qué esa zona no era tan peligrosa para Tinsley? Lo único que puedo decir es que el, no se como ni porque, era capaz de ver la mejor jugada.

El equipo de programadores de Chinook negoció un nuevo encuentro por dos años, al tiempo que mejoraban el arsenal del aspirante al título: la capacidad de cálculo fue incrementada de 20 a 29 jugadas hacia adelante, el libro de aperturas fue ampliado y refinado, y la base de datos de posiciones simples ahora poseía todas las posibilidades de 8 fichas o menos (440 mil millones de posiciones).  En 1994 se volvieron a reunir Tinsley y Chinook en Boston, pero el match fue interrumpido luego de cuatro empates debido a que la salud de Tinsley se había resentido. Como Tinsley no pudo seguir jugando, Chinook fue declarado ganador del match. Inmediatamente, el principal discípulo de Tinsley,  Don Lafferty, retó a Chinook a un match que terminó en empate, lo que le permitió a Chinook retener el titulo.  Lafferty volvió a desafiar al campeón cibernético en 1995, pero esta vez cayó vencido por la maquina.

Marion Tinsley murió el 3 de abril de 1995 en Houston. Su cuerpo perdió la batalla final contra formidables enemigos: la enfermedad, la vejez y la muerte; pero Tinsley abandonó este mundo sin que pudiese ser derrotado en el tablero. El equipo de programadores de Chinook ha seguido trabajando en la resolución del juego de Damas, y su primer gran anuncio (2005) fue la demostración que la apertura White Doctor, la misma que se jugó en la partida decisiva del match de 1992, resulta en empate si ambos bandos juegan de la mejor manera posible[13].

[1] Uno era el clásico libro de Millard Hooper (Win at Checkers) y el otro era el famoso Guide to the Game of Checkers de James Lee.

[2] Para entender lo que implica este programa de investigación voy a tomar un ejemplo sencillo: el “juego de la vieja” (tic-tac-toe).  Resolver (débilmente) el juego de la vieja significa conocer con certeza cuál es el resultado que ocurriría si los oponentes hicieran sus mejores jugadas, este resultado se llama el valor del juego;  además de que se requiere disponer de un programa de computadora que formule estrategias que garanticen el valor del juego ante un juego correcto del rival (y un resultado mejor en caso de errores por parte de este). La vieja es un juego en el que sabemos que el resultado de un juego bien jugado es el empate, mientras que para garantizar un resultado igual o mejor al valor del juego basta con salir por el centro, y a la salida por el centro responder con una jugada por una esquina.

[3] El nombre proviene de la forma en que se denomina a unos vientos que se originan en las montañas rocosas en los Estados Unidos, y que calientan un poco la zona de Alberta durante los inviernos.

[4] En esta sección estoy siguiendo, en la medida de mis posibilidades, los trabajos de V. Allis,  en particular su Searching for Solutions in Games and Artificial Intelligence (Tesis para PhD, Universidad de Limburg, 1994).

[5] Volviendo al juego de la vieja, la toma de decisiones requiere conocer la posición inicial de la cuadricula de 9 casillas (3x3), en términos de casillas vacías y posiciones de las Xs y las Os, tener presente las reglas del juego, y poder enumerar las opciones disponibles.

[6] El espacio de búsqueda es la combinación de todas las posibles secuencias de mis jugadas y las jugadas del contrario. En el caso de la vieja, al considerar el especio de búsqueda que solo incluya la primera jugada de cada uno, se verifica de inmediato que este es de 72 posiciones posibles (9 posibilidades para la primera jugada y 8 para la segunda jugada).

[7] Tinsley recordaba más tarde que se sintió rejuvenecido al constatar la potencia de su rival cibernético. El jefe del equipo de programadores de Chinook se quedó muy impresionado cuando, en sus análisis de la primera partida que jugó con Chinook, ¡Tinsley fue capaz de rememorar partidas que él había jugado con esa variante de apertura desde los años cuarenta! Otra muestra de la gran capacidad de Marion Tinsley era que podía jugar hasta 20 partidas simultáneamente con los ojos vendados.

[8] Reproducir esta partida no es estrictamente necesario para seguir la historia, pero el interesado que desconozca la notación solo debe utilizar esta guía: http://www.jimloy.com/checkers/numbered.htm

[9] En los matches modernos de Damas, se sortea cuales van a ser las primeras tres jugadas.

[10] Como si el arsenal de software, hardware y la base de datos de posiciones simples no fuera suficiente, los programas de Damas y Ajedrez cuentan además  con un libro de aperturas construido a partir de las partidas de los Maestros humanos del juego.

[11] Las evaluaciones de la posición se miden en “tanto por ciento de una ficha”, lo que significa que a la ficha que efectivamente poseía de ventaja (+100%), Chinook descontó 16% por la desventaja en la posición de sus fichas.

[12] Con un poco de paciencia y lógica se puede constatar que, luego de 27-24, el blanco no puede mover ni 20-16 (luego de 18-15 la ficha en la 24 se pierde) ni 1-6 (por 13-17 ganando 2 por 1), así que solo le queda 1-5 y quedarse jugando atrás y adelante. Eso le permite al negro forzar el cambio de la única corona blanca y luego atrapar a la ficha que (desde la casilla 20) corona en 4.

[13] Más recientemente, se completó el trabajo de resolver todas las posiciones con 10 fichas o menos (39 billones de posiciones). Cincuenta computadoras se encuentran actualmente trabajando en paralelo para completar el programa de investigación.

Tags: Teoría de los Juegos, Juegos de Estrategia, Damas, Computación