Programas Contemporáneos

A partir de 1970 el desarrollo de programas computacionales se intensificó masivamente. Las competencias mundiales organizadas por la ACM ^4.2 así como los recursos destinados a investigación en el tema cooperaron mucho con su desarrollo en los Estados Unidos.

CHESS 3.0

El primer programa ganador de la competencia de la ACM (1970) fue "CHESS 3.0", desarrollado en la Universidad de Northwest, Illinois. El programa repitió el suceso en los dos años siguientes. En el campeonato mundial de computadoras realizado en Estocolmo en 1974 obtuvo el segundo puesto detrás del programa soviético KAISSA, para luego ser quinto en el siguiente torneo de la ACM. El programa original fue escrito por Larry Atkin, Keith Gorlen y David Slate [69], siendo mejorado cada año de acuerdo a la experiencia obtenida en competencias.

El programa realizaba una búsqueda selectiva de movimientos de acuerdo a 15 rutinas modularizadas. Su capacidad de rapidez de análisis radicaba en la selección previa hecha de los movimientos posibles. "CHESS 3.0" y sus descendientes tuvieron grandes resultados frente a otras máquinas. En los 3 primeros eventos de la ACM ganó las 10 partidas que jugó. En el 4to torneo de la ACM logró 3,5 puntos en 4 juegos, siendo sólo derrotado en 1974, ya como "CHESS 4.0". Más tarde el mismo año "CHESS 4.0" pierde nuevamente otro juego frente a la computadora "RIBBIT", desarrollada en la Universidad de Waterloo, siendo el primer torneo de la ACM en que el programa CHESS no logró ganar.

TECH

El programa "Technology" fue escrito por James Gillogly mientras se graduaba en la Universidad de Carnegie Mellon [45]. Su nombre se deriva de la filosofía básica desarrollada en el trabajo de su creador, quien deseaba escribir un programa basado enteramente en tecnología (computadoras rápidas) y no tanto en heurísticas ajedrecísticas. El objetivo era simplemente generar todos los movimientos legales posibles a una profundidad fija y evaluar las posiciones terminales sólo materialmente. Un programa de estas características no podía jugar un ajedrez de buen nivel, pero la idea de Gillogly no era lograr un juego de nivel de maestro, sino que tener un programa el cual pudiese ser utilizado en la medición de fuerza de otros programas.

Los experimentos de Gillogly no resultaron crear un programa muy útil, dado que su estándar de juego resultaba muy lento para cualquier nivel de profundidad. El programa obtenía frecuentemente posiciones malas e incluso cometía errores tácticos en posiciones no estables. Dado esto Gillogly decidió dedicar cierto tiempo al desarrollo de heurísticas ajedrecísticas en su programa.

Una de las novedades de "TECH" fue el uso del tiempo de su rival en sus análisis. Si su oponente realizaba la movida predecida "TECH" era capaz en muchos casos de responder en forma instantánea. La mayor fuerza del programa estaba en su módulo de táctica (búsqueda tipo fuerza bruta). Todas las movidas eran analizadas con profundidad 5 hasta lograr posiciones estables. Incluso utilizando el algoritmo alfa-beta, la búsqueda generaba cerca de 500.000 nodos terminales. El análisis era logrado debido a la simplicidad de la función de evaluación del programa.

Cabe considerar que el desarrollo de heurísticas de TECH se diferenció entre las distintas etapas del juego. La más importante de la Apertura era la de control central, con la cual lograba posiciones muy razonables al principio de cada partida.

KAISSA

En 1971 un grupo de programadores del Instituto de Control Científico comenzaron a reescribir el programa ITEP, utilizado en 1967 para el match con Stanford. El grupo estaba formado por la base de científicos que colaboraron con el proyecto ITEP más Mikhail Donskoy, quien asumió el rol de líder en la creación de este programa [1]. Al año siguiente de estar listo, fue utilizado en dos partidas por correspondencia frente a los lectores del diario "Komsomolkaya Pravda". Todos los domingos durante 1972 el diario publicaba los movimientos de KAISSA en cada una de las partidas que se jugaban. Los lectores enviaban sus sugerencias al diario las cuales eran luego computadas. En cada partida la movida con mayor votación era la realizada frente a la máquina. KAISSA empató una partida y perdió la otra (pág. ). El año previo el campeón mundial Boris Spassky había sido invitado para la misma prueba, empatando una partida y ganando la otra, lo cual hacia considerar que el resultado del programa no era para nada malo.

KAISSA poseía una profundidad de 7 jugadas, con análisis variable en variantes que involucraban capturas o movimientos forzados. Su función de evaluación era bastante compleja pues involucraba muchos parámetros. Utilizó además una variación del algoritmo alfa-beta.

Una innovación interesante fue la mantención de movimientos de amenaza en cada movida. Si existía la posibilidad de crear una amenaza seria con un movimiento, pero que ahora no era posible, esa posibilidad se guardaba para ver si era posible en el movimiento siguiente. Este concepto se asimiló a la idea de amenaza latente en ajedrez. El único inconveniente en este algoritmo de "analogías" es tomar la decisión de "cuando" la posición ha cambiado lo suficiente como para seguir considerando una movida de amenaza.

El mayor suceso de KAISSA fue la obtención del campeonato mundial de computadoras el año 1974.

Actividad a mediados de 1970

En el año 1975 las actividades de ajedrez computacional en Europa empezaron a ser más coordinadas con la organización del primer campeonato alemán de computadoras de ajedrez. Este torneo fue realizado en Dortmund y logró atraer a gran cantidad de programadores alemanes. Los esfuerzos de los participantes no lograron llegar al nivel de KAISSA o del programa de la Universidad de Nothwest, pero hubo algunos hechos que merecieron consideración.

El programa "ORWELL III", que ocupó la cuarta posición, fue creado por el matemático y artista Thomas Nitsche. Años mas tarde Nitsche crearía el primer computador "MEPHISTO" que inició su camino hacia la fama y fortuna en la compañía "Hegener & Gliser" en Munich.

La primera ocasión en que jugadores humanos empezaron a considerar a las máquinas como serios rivales fue en 1976, en el Torneo de Ajedrez Paul Masson realizado en Sarasota, California. Participaron 756 jugadores, entre ellos, "CHESS 4.5", en la sección "B" para jugadores con rating USCF 1600-1800. El resultado de "CHESS 4.5" no dejó de impresionar a nadie, pues logró un 100% de score, convirtiéndose en la primera máquina jugadora de clase "A". "CHESS 4.5" logró luego ganar el torneo de la ACM en 1976, con lo cual recuperó su reputación como el programa más fuerte del mundo.

Al año siguiente el mundo estaría nuevamente asombrado ante CHESS 4.5, puesto que lograba la victoria en el Open de Minnesota, un torneo a seis rondas en donde el programa perdió una sola partida frente a un jugador de mayor clasificación. Esta victoria clasificaba al programa para participar en la sección "cerrada" del torneo el siguiente fin de semana, donde sólo los mejores jugadores de Minnesota tomaban participación. Los jugadores humanos tomaron el asunto muy en serio, y por primera vez en la historia las partidas jugadas por una computadora fueron parte de la preparación teórica de jugadores humanos. "CHESS 4.5" logró sólo una victoria y una tabla en sus cinco encuentros, pero dejó su marca en una competencia de ajedrez.

No fue sorpresa que para el año siguiente "CHESS 4.6" lograra nuevamente el título del campeonato ACM, seguido por KAISSA. Uno de los espectadores de ese evento fue el ex campeón mundial Mikhail Botvinnik, quien expreso en la siguiente frase una profecía que pocos entonces creyeron : "Los maestros de ajedrez acostumbraban venir a los torneos entre computadoras para reír. Ahora, vienen para mirar. Pronto vendrán a aprender".

La apuesta de Levy

David Levy es uno de los mayores expertos en el mundo acerca de ajedrez y computadoras. Maestro Internacional de ajedrez, ha escrito muchas publicaciones relacionadas con el tema [11,12,13,14,15]. En 1978 jugó un match a seis partidas frente al computador "CHESS 4.7". El motivo del match era una apuesta realizada 10 años atrás con otros científicos en que Levy aseguraba que no perdería un match con una computadora durante los siguientes 10 años.

Hasta 1977 parecía que Levy ganaría su apuesta sin mayor esfuerzo, puesto que los programas si bien participaban en competencias no lograban desarrollar un nivel de maestro. Pero entonces "CHESS 4.5" comenzó a lograr buenos resultados, por lo cual no se tardó en organizar un match entre Levy y este programa. El primer enfrentamiento fue un match a dos juegos realizado en abril de 1977 en la Universidad de Carnegie Mellon. Este match fue fácilmente ganado por Levy, pero aún restando ocho meses para cumplir el plazo de la apuesta una nueva versión del programa CHESS fue realizada, "CHESS 4.7", contra la cual el MI inglés debía enfrentar su reto final.

El match comenzó en Agosto de 1978 en el Centro de Exhibiciones Canadienses en Toronto. El programa estaba representado por David Slate y el match fue pactado al mejor de seis encuentros. La primera partida de este match resultó ser un shock emocional para todo el mundo, puesto que "CHESS 4.7" logró una posición ganadora en la apertura, pero luego teniendo la ventaja no supo rematar terminando la partida en tablas (pág. ). Levy aprendió la lección de esta partida y adoptó una estrategia de juego "anti-computadora", la cual le reportó dos victorias seguidas (pág. ). La cuarta partida del match fue un hito histórico en el encuentro, pues Levy jugando con un estilo más arriesgado terminó perdiendo su primera partida del match, siendo la primera ocasión en que una máquina derrotaba a un jugador de nivel de maestro (pág. ).

Queriendo asegurar el resultado del match Levy volvió a la estrategia inicial de espera con lo cual ganó las siguientes partidas del match y por ende la apuesta. Según palabras del propio Levy luego de este match la posibilidad de ver a una máquina derrotando a un gran maestro de ajedrez era algo que podríamos ver en un futuro no lejano.

La carrera en la década de 1980

El equipo desarrollador de la Universidad de Northwest (Slate y Atkin) había logrado a fines de los 70 crear una máquina con gran nivel de juego. Luego de su separación en 1979, Atkin concentró sus esfuerzos en escribir programas de juego para microcomputadoras. Slate escribió un nuevo programa llamado "NUCHESS", el cual finalizó en segundo puesto en el ACM de 1981 (detrás de "BELLE"), primero en 1982, 4to en el Campeonato mundial de 1983 y sexto en 1984. Si bien aun permanecía en las "grandes ligas", Slate estaba siendo eclipsado por el equipo de BELLE.

El programa "BELLE" fue escrito por Ken Thompson y Joe Condon [7], logrando como primer resultado importante el campeonato ACM de 1978. Thompson había tomado parte en distintos proyectos de programas de ajedrez, pero no había logrado demostrar superioridad sobre el equipo de Northwest. Él y Condon hacían mención al hecho de que el real avance de las computadoras de ajedrez se vería con el progreso que se obtenga en hardware. La conclusión a la que llegaron era la necesidad de crear hardware especialmente diseñado para este tipo de máquinas, con tal de reemplazar tareas normalmente realizadas por software.

Figura: El computador BELLE

En el torneo realizado en Toronto participaron con una máquina de 25 chips finalizando en cuarto lugar. Luego, en Washington consiguieron nuevo hardware, una maquina de 325 chips, con la cual vencieron a "CHESS 4.7" y marcaron el fin de una era de dominio del equipo de Northwest. En 1980, durante el desarrollo del tercer Campeonato Mundial de Computadoras jugado en Linz, Austria, "BELLE" había crecido a una máquina de 1700 chips, ganando con mucha facilidad el torneo.

"BELLE" marcó entonces una nueva forma de desarrollo de máquinas para jugar al ajedrez. Los investigadores de la época creyeron que sólo iba a ser una cuestión de tiempo y de avance en hardware el lograr que una máquina logre la profundidad de búsqueda del nivel de un campeón mundial de ajedrez, pero como más tarde mencionara Berliner, no sólo un buen cálculo basta para tener nivel de gran maestro, argumentando la importancia de incluir "conocimiento ajedrecístico" en las máquinas, ya sea mediante heurísticas especiales o bien bases de datos, lo cual se vio reflejado en su propio programa, "HITECH".

Siguiendo el suceso de 1980 "BELLE" logró los campeonatos de Los Angeles 1981y Dallas 1982. En 1983 luego de contabilizar sus resultados contra jugadores humanos, "BELLE" logró el hito mundial de convertirse en la primera máquina con nivel de maestro, lo cual le valió un premio de U$ 5.000 por parte de la fundación Fredkin. Irónicamente Thompson y Condon recibieron el cheque durante el campeonato mundial de computadores de 1983, torneo que fue ganado por "CRAYBLITZ".

"CRAYBLITZ" fue creado por el científico norteamericano Robert Hyatt [50,51] haciendo su aparición en escena el año 1976, con el nombre de "BLITZ", en el torneo de la ACM en Houston logrando el segundo lugar. En 1980 el nombre del programa fue cambiado a "CRAYBLITZ" para reflejar el poder de hardware que tenía incorporado. En 1981 "CRAYBLITZ" fue el segundo programa que logró ganar un torneo de estado, al vencer en el torneo de Mississipi.

Mientras la década del 70 fue marcada por el dominio de un sólo equipo de programación, la siguiente década produjo una "encarnizada" lucha entre "CRAYBLITZ" y los tres "motores ajedrecísticos": "BELLE", "HITECH" y "DEEP THOUGHT" (originalmente llamado "CHIPTEST"). Estos obtuvieron todos los títulos importantes durante la década, seguidos de cerca por otros programas como "CHESS CHALLENGER" y "MEPHISTO" (programas para microcomputadoras).

¿ Cual fue el motivo de este crecimiento tan notorio en la fuerza de los programas ?. De acuerdo a las conclusiones sacadas por los propios científicos, cuatro fueron las razones principales:

• Primero, la disponibilidad de nuevo hardware contribuyó a mejorar el poder de las máquinas. Mientras "CRAYBLITZ" comenzó su vida en un simple monoprecesador Cray-1, en el torneo mundial de 1989 en Edmonton ya corría bajo un multiprocesador Cray-XMP.
• Combinado con este crecimiento en hardware vino un notorio abaratamiento de costos de producción de circuitos integrados para aplicaciones específicas, con lo cual diseñar un circuito específico para jugar ajedrez era algo ya factible. Esto permitió que el ex-campeón mundial de ajedrez por correspondencia Hans Berliner, diseñara un multiprocesador llamado "HITECH", con el cual logró grandes resultados contra rivales humanos. Trabajando junto a él en la Universidad de Carnegie Mellon un estudiante llamado Feng-Hsung Hsu creó un chip aún mas poderoso, el cual implementó en el programa "CHIPTEST" el que luego superó a "HITECH".
• La tercera razón para el crecimiento "desmedido" de la actividad en los 80 fue simplemente la realidad de que muchos más científicos aprendieron cómo escribir programas de ajedrez. La literatura abundante en papers, publicaciones y libros especializados en el tema fue una fuente de conocimiento disponible para gran cantidad de personas.
• Quizás la razón principal de la explosión ajedrecística fue la capacidad de adquirir máquinas de mayor poder para realizar pruebas y desarrollo de software. La facilidad de acceso a maquinaria más especializada cooperó a que programas de ajedrez estuviesen a disposición de millones de personas, logrando masificar el conocimiento y desarrollo de este tópico.

En 1984 "CRAYBLITZ" confirmó su superioridad al vencer en el torneo de la ACM realizado en San Francisco, pero al año siguiente "HITECH" de Berliner se quedó con el torneo realizado en Denver.

En 1986 se organizó el Campeonato Mundial de Computadoras en Colonia, Alemania, produciendo gran expectación por la participación de "CRAYBLITZ" y "HITECH". A pesar de tener un pésimo comienzo "CRAYBLTZ" logró empatar el primer puesto con "HITECH", "BEBE" y "SUNPHOENIX", ganando por desempate. Habiendo ganado este título en Colonia, "CRAYBLITZ" no participó en el campeonato de la ACM realizado en Dallas, el cual fue ganado por "BELLE".

Al siguiente año también en Dallas "CHIPTEST" dio la sorpresa al vencer a "CRAYBLITZ" y dejarlo en segundo lugar. Su creador Feng Hsu predijo que con la tecnología existente su programa podría lograr calcular 1 millón de posiciones por segundo, y que una profundidad de 14 jugadas sería pronto una realidad. Si bien "CRAYBLIT" era el campeón mundial en 1988 era claro que "CHIPTEST" era el programa más fuerte del mundo. Ese año Hsu removió todo el código originario de "HITECH" en el cual basó su programa y lo renombró como "DEEP THOUGHT". Bajo este nombre el programa de Hsu ganó reputación mundial, al ganar el 5#5 torneo de la ACM en Orlando, Florida.

Luego de este suceso "DEEP THOUGHT" asombró al mundo del ajedrez al ganar el torneo de maestros de California compartiendo el primer lugar con el GM Tony Miles, y superando entre otros a los GM Larsen, Tal y Browne. Esta fue la primera ocasión en que una máquina vencía a un gran maestro en una partida, al ganar su partida contra Larsen (pág. ).

Siguiendo su suceso en Long Beach, "DEEP THOUGHT" ganó el campeonato Mundial de Edmonton en 1989 con score perfecto. Su partida contra "HITECH" fue crucial, pues a pesar de que el programa de Berliner logró una gran posición, no fue capaz de realizar el remate, perdiendo en el final. El mismo año en el campeonato de la ACM "DEEPTHOUGTH" perdió en la ultima ronda contra el programa MEPHISTO, por lo cual debió jugar un desempate contra "HITECH" el cual ganó en forma convincente. A fines de ese mismo año David Levy organizó un nuevo match, pero esta vez el resultado fue dramático para los humanos, con un 4-0 a favor de "DEEP THOUGHT". Ese mismo año los logros del programa lo llevan a jugar un match a dos partidas contra el campeón mundial Gary Kasparov, quien lo derrota en ambas ocasiones mostrando una diferencia abismante en el nivel de juego (pág. ).

En 1993 Hsu, junto a Joe Hoane y Murray Campbell (figura ) fueron contratados por la IBM, empresa que apadrinó el proyecto de crear una máquina que venciera el campeón mundial. La nueva versión de la creación de estos tres investigadores se denominó "DEEP BLUE". Este programa utilizaba el mejor nivel de hardware de la época y su desarrollo lo hacía mostrar una gran diferencia respecto de los otros programas. En 1996 se juega el primer match a 6 partidas entre esta nueva versión y Gary Kasparov, venciendo el campeón mundial por 4:2 con sendas victorias al final del match. El año que transcurrió entre este match y el match de revancha fue fundamental en la mejora de la circuitería de "DEEP BLUE" y la adaptación de conocimiento ajedrecístico a su función de evaluación. El resultado fue la victoria del programa en 1997 por la cuenta de 3,5:2,5, con lo cual el fin de una carrera se había cumplido.

Figura: El equipo de Deep Blue en la sala de juego antes del inicio del match de 1997. Izq. a Der. Jerry Brody, Feng-Hsiung Hsu, Joe Hoane, Joel Benjamin y C.J.Tan. Sentado: Murray Campbell