next up previous contents
Next: Programas Contemporáneos Up: Trabajos De La Segunda Previous: Trabajos De La Segunda   Índice General

Los Primeros Programas De Ajedrez

El Programa Los Alamos.
El primer trabajo documentado acerca de una máquina que jugaba al ajedrez fue realizado en el año 1956, y trataba acerca del trabajo realizado por cinco científicos (Jame Kister, Paul Stein, Stanislaw Ulam, William Walden y Mark Wells) en el Laboratorio Científico de Los Alamos en Nuevo México, famoso por sus trabajos en el "Proyecto Manhattan". El grupo Los Alamos mencionó la existencia de un artículo publicado en Pravda, que se refería a un programa que había sido escrito para una computadora BESM en Moscú, pero el artículo no daba una mención detallada acerca de su nivel de juego, sino que sólo mencionaba que un jugador de nivel débil había logrado vencer a la máquina.

El juego jugado por el programa Los Alamos no era realmente ajedrez, sino que una versión simplificada de éste (sin Alfiles y en un tablero de 6x6) con el cual los programadores pretendían simular técnicas de búsqueda y evaluación pero con un universo más limitado, con tal de extrapolar luego sus resultados al juego real. El programa corría en una computadora MANIAC cuya velocidad era de 11.000 operaciones por segundo, siendo capaz de realizar búsqueda de 4 jugadas (profundidad 2) en cerca de 12 minutos. El programa utilizaba una función de evaluación basada en material y movilidad.

Una de las versiones del programa fue enfrentada contra Martín Kruskal, un matemático de Princeton quien era también un fuerte jugador de ajedrez. Kruskal le dio a MANIAC la ventaja de la dama. La partida tomó varias horas de juego y atrajo el interés local. Luego de cerca de 15 movimientos Kruskal no había logrado recuperar ningún material e incluso empezó a llamar a su oponente "él" en vez de "eso". A medida que el juego progresaba parecía que el Dr. Kruskal iba a perder, pero cerca del movimiento 19 el programa eligió una débil continuación y Kruskal logró recuperar su dama dando mate.

El programa fue luego enfrentado con una joven mujer quien había aprendido los principios básicos del juego en pocos días. El resultado fue una victoria para el programa. Ambas partidas se encuentran documentadas en la mayoría de las fuentes históricas acerca del tema.

El programa de Bernstein.
En junio de 1958 Alex Bernstein y Michael Roberts publicaban un artículo en el "Scientific American" [37] haciendo referencia a la dificultad y complejidad del juego del ajedrez, describiendo al público un programa que habían desarrollado junto con Timothy Arbuckle y Martín Belsky. Las ideas de estos científicos habían sido expresadas por Shannon ocho años atrás, pero el paper de Shannon fue puramente teórico mientras que el artículo de Bernstein/Roberts describió un programa que jugaba razonablemente en una computadora IBM 704.

El programa tenía mucha similitud con las máquinas que conocemos hoy en día. Poseía un analizador de movimientos legales y su función de evaluación utilizaba cuatro parámetros: Movilidad, casillas controladas, defensa del Rey y material. Buscaba con profundidad de 4 movimientos (2 jugadas) y con tal de no demorar demasiado su juego el programa decidía primero entre siete posibilidades de acuerdo a un análisis previo con una rutina de selección. Esta rutina se basó en los siguientes criterios en estricto orden : criterios de jaque, ganancia de material, posibilidad de enroque, desarrollo, ocupación de casillas críticas, ocupación de columnas abiertas, movimientos de peones y movimientos de piezas. Con esto el programa lograba una profundidad de 2 movimientos. Examinaba 7 posiciones con profundidad 1; 49 con profundidad 2; 343 con profundidad 3 y 2401 con profundidad 4; un total de 2800 posiciones, algo bastante manejable para un computador de la época.

Primeros programas Soviéticos

Si bien no tuvieron mucha publicidad en occidente, hubo mucha investigación en computadoras de ajedrez en la Unión Soviética durante mediados de 1950. En 1956 V.M. Kurochkin escribió un programa que solucionaba problemas de ajedrez. Su programa corría en una computadora Strela, y podía solucionar problemas de mate en 2 movimientos más rápido que cualquier humano (2 a 4 minutos), pero problemas de 3 o 4 movimientos requerían 10 a 12 minutos para ser solucionados. Kurochkin comentaba que el problema principal era el análisis de todas las posibilidades por parte de la máquina, algo que los humanos saben descartar desde un principio.

Un año más tarde el mismo Kurochkin escribió un programa que jugaba el final de Rey y dos Alfiles v/s Rey. El primer intento de crear un programa que jugase una partida completa fue hecho por G. Sehlibs, con un programa que lograba una profundidad de 3 jugadas. No hay referencias de partidas jugadas por este programa, ni tampoco opiniones acerca de su nivel de juego.

El primer programa bien documentado escrito en la Unión Soviética hizo su debut el año 1961. Fue escrito en el Instituto Matemático Styeklov de la Academia de Ciencias de la URSS por un equipo que incluía a los profesores M.Shura-Bara, I.Zadykhalio, E.Lublinsky y V.Smilga (candidato a maestro soviético de ajedrez). Una descripción de su trabajo fue considerada lo suficientemente importante para ser publicada en el boletín numero 8 del match por el campeonato mundial de 1961 entre Tal y Botvinnick.

El programa Stylekov ocupaba las siguientes características en su función de evaluación: Material, movilidad, piezas defendidas, estructura de peones, control del centro, clavadas, protección del Rey. El programa no poseía algoritmo de búsqueda por lo que su juego era tremendamente limitado. Tomaba cerca de 30 y 58 segundos por movimiento.

Newell, Shaw y Simon (El programa NSS)

Alan Newell, John Shaw y Herbert Simon [65]comenzaron su trabajo en computadoras de ajedrez el año 1955 en el Instituto de Tecnología de Carnegie (ahora conocido como la Universidad de Carnegie Mellon) en Pittsburg. Sus progresos en el desarrollo de una máquina que jugase al ajedrez fueron bastante lentos, debido a que el principal objetivo del grupo era realizar un programa que realizara demostraciones de teoremas en lógica.

El programa NSS fue construido en base a módulos, cada uno asociado con un objetivo particular de una partida de ajedrez. Objetivos típicos son defensa del Rey, balance de material, control del centro, desarrollo, ataque y promoción de peones. Cada objetivo tenia asociado un conjunto de procesos: un generador de movimientos, un evaluador estático de posiciones y un generador de análisis.

El generador de movimientos asociado con cada módulo proponía movimientos relevantes a ese módulo. Por ejemplo el módulo de control de centro propondría el movimiento 1.e4 al principio de la partida, mientras que el módulo de material propondría movimientos que ganasen o mantuviesen igual el balance de piezas capturadas.

El valor asignado a cada movimiento propuesto por cada módulo era obtenido de una serie de evaluaciones. El "score" asociado a una determinada posición era el resultado de las distintas componentes. Cada componente expresaba la aceptación o rechazo de alguna posibilidad en base a su propio objetivo. Un ejemplo de módulo era el de "Control Central". Este módulo operaría a menos que no hubiese peones centrales para movilizar en la cuarta o quinta fila. La forma de operar de este módulo era la siguiente: La evaluación estática del control del centro simplemente contaba el número de casillas dominadas en el centro y ponderaba por las posibilidades de realizar movimientos que ayudaran a su mayor control.

La importancia de considerar objetivos principales y modularizarlos tuvo la ventaja de dar mucha mayor flexibilidad al programa en la selección de movimientos dependiendo de la etapa del juego en que se encontraba. Esta "selección" de acuerdo a objetivos principales, la cual descartaba posibilidades que no eran el objetivo principal de la partida, fue el principio del uso del algoritmo alfa-beta, cuyo primer uso en programas de ajedrez fue justamente en el programa NSS.

El programa de Anderson/Cody

En el año 1959 un programa canadiense fue exhibido en la Universidad de Toronto. Fue escrito por Frank Anderson, un maestro internacional de ajedrez, y Bob Cody. El programa corría en una computadora IBM 605 y jugaba sólo finales de peones muy simples (el más complejo era de 2 peones y Rey v/s Rey) y los programadores centraron sus esfuerzos en desarrollar una estrategia perfecta para este tipo de finales. El programa jugó una exhibición de simultáneas contra 50 oponentes, cada uno de los cuales podía elegir su posición de partida. En cada partida el programa jugó casi perfectamente. Lamentablemente no hay suficiente documentación acerca del proyecto ni de la estrategia de programación del juego de final. Ni siquiera el mismo Anderson cuando fue consultado en 1970 acerca de su método recordaba la forma en que lo hizo.

El programa Kotok/McCarthy

En 1961 Alan Kotok escribió un programa de ajedrez para su disertación de titulo en el Instituto de tecnología de Massachussets [55]. Su programa fue escrito bajo la guía de John McCarthy, una de las figuras líderes en el mundo de la Inteligencia Artificial, quien en ese entonces era profesor del MIT.

El programa de Kotok realizaba una búsqueda en profundidad con límite variable. Profundizaba en posiciones hasta que éstas fueran "estables" o bien sobrepasara su límite máximo de búsqueda. El generador de movimientos del programa era similar al utilizado por el programa NSS, mientras que la función de evaluación utilizaba 4 objetivos: Material, estructura de peones, control del centro y desarrollo.

El trabajo de Kotok se inició en el verano de 1961. Al momento de presentar su tesis en 1962 el programa había jugado cuatro partidas, utilizando un promedio de 10 minutos por movimiento. Su nivel de juego no era bueno, e incluso en alguna oportunidad realizó movimientos ilegales.

Luego de graduarse en el MIT el interés de Kotok en ajedrez y computadoras fue decreciendo, si bien su programa se mantuvo . Cuando McCarthy dejó el MIT para hacerse cargo del Laboratorio de Inteligencia Artificial en Stanford, tomó los trabajos de Kotok y realizó varias modificaciones. A fines de 1966 se realizó un match entre la nueva versión del programa, corriendo en una IBM 7090, y un programa desarrollado en una computadora soviética M20 en el Instituto de Física Experimental y Teórica (ITEP) en Moscú. El programa ITEP fue escrito por Vladimir Arlazarov, George Adelson-Velsky, Alexander Bitman (maestro soviético), Alexander Ushkov y Alexander Zhivotovsky. Utilizaba una función de evaluación basada en: Estructura de Peones (Peones centrales, cadenas de peones, peones aislados y doblados, peones pasados), Movilidad, Defensa del Rey y Balance de material.

El programa ITEP utilizaba una estrategia "tipo-A" con una profundidad de 3 jugadas. El programa americano utilizó una estrategia "tipo-B" logrando profundidad de 4 jugadas. El programa ruso ganó dos partidas mientras que las otras dos fueron tablas (pág. [*]). Las anotaciones de estas partidas fueron publicadas en un artículo de Arlazarov y Bitman que apareció en Febrero de 1968 en la revista soviética "Shakhmaty v CCCP" .

Este match hizo mucho por el desarrollo de computadoras de ajedrez dado que estimuló este tópico en los Estados Unidos. Incluso cuando el match estaba siendo realizado, un nuevo programa fue desarrollado en el MIT, y por los siguientes ocho años se vivió una explosión en el interés por el tema. Las competencias entre computadoras empezaron a ser cada vez más frecuentes y algunos científicos empezaron a creer en la posibilidad de crear una máquina con nivel de maestro.

El programa Greenblatt

A principios de 1966 se desarrolló un programa de ajedrez en una computadora PDP-6 en el laboratorio de Inteligencia Artificial del MIT. Éste fue escrito por Richard Greenblat [46], entonces estudiante, con la asistencia de Donald Eastlake. Participó en un torneo de ajedrez local, perdiendo cuatro partidas y empatando una, logrando un rating de la USCF 4.1 de 1243 puntos. En marzo de 1967 jugó otro torneo, ganando una partida y perdiendo cuatro. Su performance resultó ser de 1360. Un mes más tarde logró vencer en dos partidas cayendo en otras dos, pero logrando una performance de 1640. El programa fue bautizado como MACHACK VI y fue hecho miembro honorario de la USCF.

El programa de Greenblatt poseía varias facilidades interactivas para localizar errores y mejorar su performance. Estas ayudas incluían facilidades de visualización en pantalla de evaluaciones seleccionadas, análisis de nodos terminales, factores que causaban que una movida fuese elegida, variante principal de análisis del programa, y estadísticas de tiempo de generación de cálculo y posiciones analizadas. Utilizando esta característica y jugando cientos de partidas contra adversarios humanos Greenblat fue capaz de realizar un programa que era rápido, eficiente y relativamente libre de errores de programación.

El generador de movimientos de Greenblatt poseía tres funciones básicas. Seleccionaba los movimientos que consideraba lógicos y de acuerdo a su orden de mérito los ubicaba con tal de optimizar el uso del algoritmo alfa-beta para luego calcular valores posicionales y de desarrollo que decidirían qué movimiento realizar. La mejor cualidad del programa era su conocimiento ajedrecístico, el cual estaba representado en las cerca de cincuenta heurísticas utilizadas en computar los movimientos posibles, las cuales estaban destinadas a distintas etapas del juego.

La función de evaluación del programa consideraba balance de material, capacidad de acción de las piezas, estructura de peones, defensa del Rey y control central. El árbol de búsqueda del programa se basaba en una estrategia Shannon tipo-B.

Una novedad introducida en este programa fue el uso de un pequeño libro de Aperturas. Este "libro" fue compilado por dos estudiantes del MIT, Larry Kaufmann y Alan Baisley, ambos jugadores de ajedrez.

Trabajos de Botvinnick

Mikhail Botvinnick fue campeón mundial de ajedrez por cerca de 12 años. Su primera victoria fue en el año 1948, perdiendo el título en forma definitiva frente a Petrosian en 1963. Aparte de ser un notable maestro de ajedrez Botvinnick era también Ingeniero Eléctrico, manteniendo muchísimo interés en el tema de cómo desarrollar el proceso de análisis ajedrecístico en una máquina.

Sus ideas resultaron ser bastante originales, la mayoría de las cuales fueron publicadas en [2] publicado en 1970. En este texto Botvinnick buscó cómo mejorar, desde el punto de vista ajedrecístico, la capacidad de la máquina para evaluar posiciones y aumentar su profundidad de búsqueda. Propuso varias ideas interesantes acerca de cómo hacer que un programa analice en profundidad tal como lo hace un jugador experto.

Botvinnick propuso un algoritmo que permitía a la computadora analizar un árbol de variantes en la misma forma en que él lo realizaba. Sus publicaciones describieron como su programa PIONEER lograba solucionar problemas muy complejos, examinando sólo un número limitado de variantes y posiciones. Desafortunadamente el periodo de mayor interés de Botvinnick por el tema coincidió con una época en donde en la Unión Soviética el acceso a computadoras era tremendamente limitado. De haber tenido mayor apoyo en esto no cabe duda que sus aportes hubiesen sido mucho mayores.
next up previous contents
Next: Programas Contemporáneos Up: Trabajos De La Segunda Previous: Trabajos De La Segunda   Índice General
Santiago de Chile, Julio 2003