Trabajos De Claude Shannon y Alan Turing

El 9 de Marzo de 1949 Claude E. Shannon, un investigador científico de los laboratorios Bell de New Jersey, presentó un paper en una convención en Nueva York. Éste se denominaba "Programming a Computer for Playing Chess" [68] 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 que jugasen ajedrez, pero si 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.
  • Clavadas.
• 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, para luego utilizar el algoritmo "minimax". 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:

1. Examinar variantes forzadas lo más profundamente posible, evaluando sólo posiciones estables.
2. 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.

En 1951 Alan Turing publicó los resultados de su trabajo en computadoras de ajedrez en la Universidad de Manchester [20]. Turing fue uno de los principales pioneros durante los primeros años de la computación y estuvo convencido de que los juegos constituían un modelo ideal de estudio de la inteligencia en máquinas y como éstas debían conducirse. Esta idea es seguida en los dias de hoy por quienes trabajan en Inteligencia Artificial, pero en los tiempos de Turing la opinión era mirada con bastante escepticismo.

Las primeras ideas de Turing acerca de computadoras de ajedrez datan de 1944, cuando discutía sus ideas con varios colegas de la universidad. Entre 1947 y 1948 él 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 permitieron la creación de una computadora que jugaba ajedrez con profundidad de 1 movimiento. Estos simplemente calculaban los puntajes 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 [21]. 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 grabado entre dos máquinas resultó ser una tediosa simulación realizada en las manos de Turing (pág.).

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. Curiosamente, las ideas propuestas por estos insignes investigadores corresponden a la base utilizada en la realización de software para jugar al ajedrez, lo cual da a estas referencias un valor histórico muy alto. Se mencionan las primeras ideas acerca de búsqueda en profundidad, funciones de evaluación y técnica de juegos. No se hace un análisis de medición ni comparación de niveles de fuerza para máquinas que jueguen al ajedrez.