Inicios de los programas de ajedrez.

publicado en: Computaodra y ajedrez, Ordenadores | 0

El hombre siempre ha querido crear una inteligencia que trabaje para él. Actualmente ya hemos desarrollado máquinas que trabajan por nosotros. Pero a estos engines ha habido que «enseñarles» a pensar, y el ajedrez ha sido un campo de investigación para ello. Pero ¿Cómo empezó el desarrollo de los actuales módulos de ajedrez?

Empecemos por el siglo XIX. Charles Babbage (1791-188 ) tuvo interés hacia el ajedrez pero no era un jugador de gran fuerza (llegó a jugar una partida contra El Turco). Fue cerca de 1840 cuando se pensó en la posibilidad de crear una máquina que lograra jugar un juego de alto nivel intelectual. En su texto «The Life of a Philosopher» presentó sus primeras ideas acerca de «como» debería actuar la máquina frente a un juego de inteligencia:

“En la primera parte de mi estudio muy pronto llegué a la conclusión de que cualquier juego de inteligencia es susceptible de ser practicado por un autómata. A cualquier movimiento que haga el autómata, una respuesta vendrá de su adversario. Ahora el estado alterado del tablero es uno de muchas posiciones de su adversario en la cual se supone el autómata será capaz de actuar. Luego la pregunta se reduce a realizar el mejor movimiento bajo cualquier combinación de posiciones posibles del adversario. Entonces, el autómata debe considerar preguntas de la siguiente naturaleza:

  • ¿Es la posición de mi adversario consistente con las reglas del juego?
  • Si es así, ¿ha perdido el juego el autómata?
  • Si no, ¿ha ganado el autómata el juego?
  • Si no, puede ganar a la próxima movida? Si es así, hacer la movida.
  • Si no, ¿puede su adversario, moviendo, ganar el juego?
  • Si es así, el autómata debe prevenir esta movida.
  • Si el adversario no puede ganar el juego, el autómata debe examinar cómo realizar una movida como esa siguiendo una secuencia de dos movimientos. Si no encuentra solución, entonces seguir una secuencia de tres o más movimientos.

En consecuencia el problema de hacer que un autómata juegue en un juego de inteligencia depende de la posibilidad de que la máquina pueda representar el esquema de combinaciones relativas al juego.»

En base a esto uno puede suponer que Babbage estimó, a mediados del siglo XIX, un esquema de búsqueda en profundidad que puede ser utilizado para automatizar el proceso analítico de una partida de ajedrez. Es decir, ideo un algoritmo básico. No llegó a desarrollar más la idea, ya que además en esa época estaba centrado en la construcción y funcionamiento de su máquina analítica.

Los autómatas El Turco (1769), Ajeeb (1868) y Mephisto (1878) aunque fuesen máquinas ingeniosas rozando la genialidad, no aportaron nada nuevo a la inteligencia artificial, ya que eran autómatas manejados por humanos. En 1914 Leonardo Torres de Quevedo mostró al mundo su “jugador de ajedrez” una máquina capaz de dar mate de rey y torre contra rey. Fue la primera máquina capaz de jugar sin intervención humana, pero no dejaba de ser un autómata electromecánico con una secuencia exacta que soluciona un único problema.

No fue hasta el 9 de Marzo de 1949 cuando Claude E. Shannon, un in-vestigador   científico de los Laboratorios Bell de New Jersey, presentó un tra-bajo   en   una  convención en Nueva York. Éste se denominaba «Programming a Computer for Playing Chess» y su enorme significancia recae en que muchas de las ideas originales expresadas en él son aún utilizadas en los programas de ajedrez de la actualidad. Shannon no hizo mención a la importancia de que las computadoras jugasen al ajedrez, pero sí hizo notar que la investigación de este tema tendría como consecuencia el progreso en otras áreas de solución automática de problemas.

Shannon propuso varias consideraciones que deben ser tomadas en cuenta en la función de evaluación de posiciones de un programa de ajedrez (aquella que determina un valor numérico para una posición):

  • Ventaja Material
  • Estructura de peones
    • Peones Aislados y retrasados.
    • Control relativo del centro.
    • Peones en color opuesto al alfil propio.
    • Peones pasados
  • Posición de las piezas.
    • Caballos avanzados, protegidos o atacados.
    • Torres en columnas abiertas o semiabiertas.
    • Torres en séptima fila.
    • Torres dobladas.
  • Posibilidades de ataque.
    • Piezas que protegen a otras piezas.
    • Ataques sobre otras piezas.
    • Ataques sobre casillas adyacentes al rey enemigo.
  • Movilidad, medida por el número de movimientos legales posibles.

Shannon describió dos tipos de estrategias para el  juego  de ajedrez por  máquinas.

  • La más primitiva, llamada «tipo-A«, consistía en la búsqueda en profundidad con un límite a lo largo de cada «rama» del árbol de variantes (el más utilizado hasta la fecha)
  • La estrategia «tipo-B» introdujo un método de búsqueda selectiva en el cual ciertas líneas eran más profundizadas que otras.

El mismo Shannon acotó que la estrategia «tipo-A`» presenta al menos tres desventajas.

  • En una posición de medio juego hay cerca de 30 posibles movimientos. Después de una movida de cada bando las posibilidades crecen a 1000 nodos terminales los cuales deben ser evaluados. Luego de tres movimientos la proporción crece a 3#3 nodos terminales, lo cual implica que a una tasa de evaluación de 1 por cada microsegundo el programa tardaría al menos 16 minutos para cada movimiento.
  • Segundo, un jugador de ajedrez examina algunas variantes con profundidad de pocos niveles y otras con cerca de 20 niveles de profundidad. Esto es lo que se llamó «búsqueda selectiva» en la estrategia «tipo-B«.
  • La tercera desventaja es el problema derivado de las posiciones «inestables», aquellas en donde hay cambios de piezas o bien secuencias de jaques.

Referido a esto último, Shannon introdujo el concepto de «estabilidad«, la cual aplicó a su segundo tipo de estrategia, proponiendo lo siguiente:

  • Examinar variantes forzadas lo más profundamente posible, evaluando sólo posiciones estables.
  • Seleccionar mediante un proceso externo las variantes importantes de ser analizadas, evitando perder tiempo analizando variantes inútiles.

Estos dos criterios son claramente utilizados por jugadores humanos, siendo el segundo nada más que el algoritmo alfa-beta, el cual fue utilizado en programas a partir de 1960.

Entre 1947 y 1948 Alan Turing (influenciado por los trabajos de Ada Lovelace, Babbage y Shannon) y D.G.Champernowne crearon un analizador de movimientos denominado TUROCHAMP. Al mismo tiempo Donald Michie y S.Wylie desarrollaron otro analizador llamado MACHIAVELLI. Estos analizadores tenían que permitir qué una computadora jugara al ajedrez con profundidad de 1 movimiento. Simplemente se calculaba la puntuación de las posiciones con profundidad 1 y entonces realizaban el movimiento con mayor puntaje. Un match entre estos dos entes se programó pero nunca fue realizado. Sólo 30 años más tarde, MACHIAVELLI jugó un match contra otro analizador, SOMA, desarrollado por Maynar Smith. SOMA utilizaba una función de evaluación en la cual 3 parámetros eran de importancia. Material, movilidad y cambio de valores.

Durante el transcurso de su investigación en computadoras de ajedrez Turing intentó programar a TUROCHAMP y MACHIAVELLI en la computadora «Ferranti Mark 1» en Manchester, pero nunca pudo completar su trabajo y fue incapaz de lograr que las máquinas jugasen en forma automática. Las conclusiones de estos trabajos están publicadas en “Digital Computers applied to games», 1953. La significancia del trabajo de Turing radica en haber sido la primera persona que diseñó un programa que podía jugar ajedrez. Siendo sinceros, el primer juego anotado entre un humano y una máquina inteligente resultó ser una tediosa simulación realizada en las manos de Turing, que efectuó los cálculos con lápiz y papel a través del borrador del programa, ya que no encontró ningún ordenador capaz de soportarlo. El primer humano que jugó contra este programa fue Alick Glennie, de 26 años, licenciado pero mal jugador de ajedrez.

Así cuenta la histórica partida Ludeck Pachmann en su libro “Ajedrez y computadoras

 Turochamp – Glennie [C26] 1952

 1.e4 e5 2.Cc3 Cf6

 A falta de una biblioteca de aperturas, así como de generador de azar, el propio Turing hubo de inventar un sistema para elegir entre diferentes movimientos iniciales que presentaban igual evaluación. Así, por ejemplo, el movimiento 1.e4 presenta la mejor evaluación como consecuencia de las consideraciones siguientes:

Por aumentar la movilidad de la dama                +2

Por aumentar la movilidad del alfil                       +2,2

Por aumentar la movilidad del caballo                 +0,3

Por no estar enrocado el rey (1)                            -0,4

Por no estar defendido el peón                             +0,1

Total                                             4,2 puntos

 

Como el proyecto de Turing concedía más importancia a la defensa que al ataque, el programa, o tal vez sería mejor decir su creador, prefirió en su segundo movimiento 2.Cc3. En la evaluación del mismo intervinieron los siguientes factores de corrección:

Por aumentar la movilidad del caballo de dama           +0,8

Por quedar más defendidos dos peones                         +0,5

Por aumentar la movilidad de la torre dama                 +1,0

El alfil de dama defiende dos peones                             +0,5

El peón de rey queda defendido por el caballo              +0,3

Total                             3,1 puntos

Normalmente el programa consideraba sólo el movimiento propio más la respuesta del contrario. La evaluación sólo podía efectuarse en posiciones “estáticas”, es decir, que no implicaran cambios de piezas ni jaques.

 3.d4 Ab4 4.Cf3 d6 5.Ad2 Cc6 6.d5 Cd4 7.h4 Ag4 8.a4 Cxf3+ 9.gxf3 Ah5 10.Ab5+ c6 11.dxc6 0–0 12.cxb7 Tb8 13.Aa6 Da5 14.De2 Cd7 15.Tg1 Cc5 16.Tg5 Ag6 17.Ab5 Cxb7 18.0–0–0 Cc5 19.Ac6 Tfc8 20.Ad5 Axc3 21.Axc3 Dxa4 22.Rd2 Ce6 23.Tg4 Cd4 24.Dd3 Cb5 25.Ab3 Da6 26.Ac4 Ah5 27.Tg3 Da4 28.Axb5 Dxb5 29.Dxd6?? Td8 0–1

“Lo principal es que este boceto de Turing sólo puede aplicarse indistintamente a las tres fases de la partida al precio de una gran imprecisión. Las condiciones de la apertura y del medio juego no sirven para los finales, que a veces exigirían criterios diametralmente opuestos. Los programas antiguos, lo mismo que el borrador de Turing, apenas tenían en cuenta esa diferencia.”

Turing utilizó una función de evaluación bastante simple en la cual el material era el factor dominante. El tamaño del árbol de variantes era de 1 jugada, examinando todas los movimientos posibles en profundidades mayores, deteniendo el análisis cuando una posición «muerta» era abordada, esto es, una posición en donde no existían movimientos considerables (captura de una pieza no defendida, recaptura de una pieza, captura de una pieza defendida con otra de menor valor y dar Jaque Mate).

En caso de ser las evaluaciones de material iguales en los movimientos analizados, los factores posicionales decidían el mejor. En estos se incluía: Movilidad, Piezas protegidas, Movilidad del Rey, Protección del rey, Enroque, Posición de peones y Amenazas de jaque o jaque mate.

Turing asumía las debilidades de sus programas señalando que muchas veces éstos eran una representación de su propio nivel de juego. «Uno no puede programar una máquina para que juegue mejor de lo que uno juega«.

Tanto Turing como Shannon propusieron las primeras técnicas e ideas básicas para la construcción de máquinas que jueguen al ajedrez, si bien con un enfoque mucho mas teórico que práctico y sentaron las bases teóricas para la programación. Se mencionan las primeras ideas acerca de búsqueda en profundidad, funciones de evaluación y técnica de juego. No se hace un análisis de medición ni comparación de niveles de fuerza para máquinas que jueguen al ajedrez.

Hay que decir que TUROCHAMP fue “resucitado” en el año 2012 con motivo del “Año de Turing” por Chessbase. Al final de la conferencia que dieron por este motivo, Kasparov participó en un encuentro histórico: jugó la primera partida pública de un ajedrecista profesional contra la reconstrucción de la «máquina de papel» (Turochamp) de Turing.

Hicimos que el módulo de Turing evaluase las jugadas con cinco segundos por jugada, es decir, con una mayor profundidad que cuando jugó contra Kasparov. Las valoraciones se muestran en el gráfico bajo el tablero. Advierta que debido a la forma en que trabaja este módulo, los valores son solo de los criterios posicionales, no materiales. Además, el módulo tiene distintas opiniones dependiendo del lado del tablero desde el que mire”. (De la web de Chessbase)

 

Turing – Kasparov,Garry [A00]

Manchester, 2 Ply Hamburg, 25.06.2012

1.e3  -4.40/6  Cf6  3.00/6  2.Cc3  -3.30/6  d5  1.80/5  3.Ch3  -2.60/5  e5  1.70/4  4.Df3  -2.50/4  Cc6  1.10/4  5.Ad3?? Con dos medias jugadas, el módulo no puede ver la horquilla que se avecina.  0.10/4  [Con cinco medias jugadas hace 5.a4 ] 5…e4  -0.20/4  6.Axe4  -2.00/4  dxe4  -1.00/4  7.Cxe4  -1.50/4  Ae7  1.10/5  8.Cg3  -2.30/4  0–0  1.70/4  9.0–0  -2.20/4  Ag4  -0.10/4  10.Df4  -1.50/4  Ad6  0.90/4  11.Dc4  -2.00/4  Axh3  0.20/4  12.gxh3  -2.40/4  Dd7  -0.30/4  13.h4  -1.10/4  Dh3  0.10/4  14.b3?  -0.60/4  [Cuando calcula con cinco medias jugadas, el módulo de Turing juega 14.f3 evitando la siguiente jugada negra.] 14… Cg4  -0.70/4  15.Te1 Permitiendo mate en dos.  -#2/4  [De nuevo con cinco ply se genera una jugada distinta, que evita el mate inmediato: 15.Dxg4 ] 15… Dxh2+  -#1/6  16.Rf1  -#1/4  Dxf2# 0–1

 La experiencia fue enriquecedora, aunque la calidad del primer programa de ajedrez escrito jamás no estaba, evidentemente, a la altura. Chessbase lo compiló y durante un tiempo se podía descargar en su web.

Defense Calculator

En 1956, Arthur L. Samuel del laboratorio de IBM en PoughkeepsieNueva York, escribió un programa para la  IBM 704 que llamó Defense Calculator para jugar a las damas utilizando un método en el que la máquina puede «aprender» a partir de su propia experiencia. Se cree que esto es el primer programa para «auto-aprendizaje,» una demostración del concepto de inteligencia artificial.

Para que os hagáis una idea, el IBM 704 ocupaba una habitación entera, y era el primer ordenador digital electrónico. Con todo, Defense Calculator podía ejecutar la nada desdeñable cifra de 1.000 instrucciones por segundo.

A pesar de que el juego de las damas es muy elemental, hasta el punto de que puede aprenderlo a jugar un niño, la probabilidad de que dos partidas de damas se desarrollen justo de la misma manera es bastante remota. Es decir, que cada movimiento teóricamente podía dar lugar a miles de configuraciones posibles sobre el tablero, una complejidad que excedía en mucho a las competencias del ordenador. Samuel, pues, no creía inteligente que aquel cerebro electrónico calculara absolutamente todos los movimientos cada vez que le tocara jugar, sino que aprendiera a jugar, que se adaptara a las circunstancias concretas de cada movimiento del contrincante. (lo que Shannon llamó “estrategia tipo B”). Todo ello empleando sólo unas cuantas instrucciones básicas como una llamada “piezas de ventaja”: el ordenador tenía que contar el número de piezas que le quedaban en el tablero y compararlo con el de su adversario: si un movimiento tenía como resultado más piezas de ventaja, entonces éste tenía prioridad sobre los demás. También había otras instrucciones básicas como intentar dominar el centro del tablero.

Samuel también enseñó a Defense Calculator a aprender de sus propios errores, tal y como explica Peter Miller en su libro La manada inteligente:

“Si un movimiento basado en ciertas características no conseguía producir un resultado favorable, el ordenador le daba menos valor a esa característica la próxima vez. Además, le enseñó a reconocer movimientos destinados a crear un “escenario” es decir, los que no consiguen resultados inmediatos pero posteriormente tienen una mayor recompensa, como por ejemplo sacrificar una pieza para poder hacer un triple salto en el siguiente turno. La máquina lo hizo después de que se aumentar el peso de las características que favorecían el movimiento que propiciaba ese escenario. Finalmente, Samuel hizo que el ordenador asumiera que su adversario sabía lo mismo que él, de manera que intentaría infligirle el mayor daño posible en todo momento. Eso obligaba al ordenador a tener en cuenta las consecuencias potencialmente negativas de los movimientos, además de las positivas. Si un adversario conseguía sorprenderlo de todos modos, ajustaría sus valoraciones para evitar ese error en lo sucesivo”.

En la década de 1960, la máquina de Samuel ya era capaz de vencer a los campeones de damas. Una lección que aún hoy los expertos en computación tienen muy en cuenta en sus investigaciones.

Los Álamos

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 Álamos 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 (todos los avances rusos en este campo son muy oscuros y aun hoy en día se desconoce casi todo de los trabajos soviéticos de esa época).

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 6×6) 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 que pasaba por allí y que 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.

Reglas

Las reglas son las mismas del ajedrez, excepto:

  • Un peón en su casilla inicial no puede avanzar dos casillas. No hay captura al paso.
  • Lospeones no pueden convertirse en alfiles al coronar;
  • No hay

Una partida normal consumía un tiempo considerable, aproximadamente 10 horas. No es de extrañar que éste primer experimento hubiera de ser abandonado al cabo de las tres partidas.

 

MANIAC 1 – Secretaria Los Alamos 1956

1.d3 b4 2. Cf3 d4 3.b3 e4 4. Ce1 a4 5.bxa4? [5. Cd2 y 6. Cd2-c4+ Cbcxc4 7.b3xc4 con un buen juego] 5…Cxa4 6. Rd2? Cc3 7. Cxc3 bxc3+ 8. Rd1 f4 9.a3 Tb6 10.a4 Ta6 11.a5 Rd5 12. Da3 Db5 13. Da2+ Re5 14. Tb1 Txa5 15. Txb5 Txa2 16. Tb1 [para pevenir 16…Ta1 mate!] 16…Ta5 17.f3 Ta4 18.fxe4 c4 19. Cf3+ Rd6 20.e5+ Rd5 21.exf6D Cc5 22. Df6xd4+ Rc6 23. De5 mate.

El júbilo entre el equipo era patente. El programa Los Álamos se había convertido en el primera máquina autónoma en derrotar a un ser humano a nivel intelectual y coronó unos dos milenios de historia.

A finales de la década de los 50 hubieron varios intentos de crear un programa que jugara decentemente al ajedrez: el programa Bernstein (Alex Bernstein 1958) y el programa NSS (grupo NSS, 1958). Pero no fue hasta  1966 cuando se dio un nuevo impulso a este campo al enfrentarse las dos potencias mundiales con un tablero y dos ordenadores de por medio. (Sigue en parte II)

Deja una respuesta

Tu dirección de correo electrónico no será publicada.