Next: Programas Contemporáneos
Up: Trabajos De La Segunda
Previous: Trabajos De La Segunda
  Índice General
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:
- Mover e4, o d4 (movimientos primarios)
- Prevenir los
movimientos primarios del oponente.
- Preparar los movimientos
primarios propios mediante :
- Apoyo de piezas
- Eliminación de piezas o peones
adversarios que controlen el centro.
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: Programas Contemporáneos
Up: Trabajos De La Segunda
Previous: Trabajos De La Segunda
Índice General
Santiago de Chile, Julio 2003