Claude E. Shannon

El 9 de Marzo de 1949 Claude E. Shannon, un investigador  científico de los Laboratorios Bell de New Jersey, presentó un trabajo  en   una  convención en Nueva York. Éste se denominaba “Programming a Computer for Playing Chess” y su enorme importancia 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 para que fueran 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
  • Posición de las piezas.
  • Posibilidades de ataque.
  • 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 reconoció que la estrategia “tipo-A`” presenta varias desventajas, siendo la principal el enorme costo de tiempo para calcular todas las posibles variantes del árbol. Por ello 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  y D.G.Champernowne (influenciados por los trabajos de Ada Lovelace, Charles Babbage y Shannon) 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.

Ferranti Mark I El Mark I estaba dentro del armario

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. Lo importante del trabajo de Turing radica en haber sido la primera persona que diseñó un programa que podía jugar al ajedrez.

Con todo ello, se propuso hacer una prueba y el resultado fue que 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.” (L. Pachmann)

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 más 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.

Kasparov y Turochamp

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.

Compujedrez 2016

Anuncios