CAOS (ajedrez)

Los matemáticos Claude Shannon y Alan Turing , trabajando por separado, fueron los primeros en considerar el ajedrez como un desafío para las máquinas. Trabajando para AT&T / Bell Labs , con acceso a equipos de conmutación telefónica, Shannon construyó en 1949 una máquina basada en relés que aprendió a recorrer un laberinto bidimensional de 5x5 celdas. Shannon lo consideró una analogía de cómo los organismos aprenden sobre su entorno natural. Existe un elemento aleatorio en la búsqueda, un elemento de memoria para beneficiarse del resultado de la búsqueda y un elemento de recompensa que refuerza el aprendizaje cuando el resultado global es favorable para el organismo. ^{[ 6 ]}

Poco después, Shannon escribió un análisis matemático del juego de ajedrez, publicado en 1950. ^{[ 7 ]} Al igual que con el laberinto, descompuso el juego en los elementos necesarios para el aprendizaje por refuerzo. Asociado a cada configuración del tablero desde la que se realizará un movimiento, hay una puntuación numérica. Para decidir qué movimiento hacer, un jugador quiere maximizar la puntuación de su propia posición después del movimiento y minimizar la puntuación de su oponente (una perspectiva minimax ). Dado que hay alrededor de 32 movimientos posibles en cada una de las primeras etapas del juego, y alrededor de 40 movimientos y respuestas en cada juego, entonces hay aproximadamente${\displaystyle 32^{80}}$o sobre${\displaystyle 10^{120}}$ Posibles partidas: un conjunto imposible de evaluar por completo. Por lo tanto, debe haber una manera de limitar la cantidad de movimientos que se deben considerar para encontrar el mejor.

Reducir el juego a estos pocos elementos clave proporcionó una forma de pensar sobre la inteligencia humana en general. Shannon pasó a formar parte de un grupo más amplio que utilizaba máquinas de computación para imitar aspectos de la inteligencia humana, lo que se convirtió en la idea general de inteligencia artificial . (Otros miembros de este grupo fueron John McCarthy , Herbert Simon , Allen Newell , Alan Kotok , Alex Bernstein y Richard Greenblatt ). ^{[ 5 ]} El paradigma que evolucionó fue que existía una cuantificación de la posición en el tablero en una puntuación, un método de evaluación para encontrar resultados favorables (minimax, posteriormente poda alfa-beta ) y una estrategia para gestionar la explosión combinatoria de las posibilidades de anticipación. ^{[ a ]}

A principios de la década de 1960, existían programas informáticos que jugaban al ajedrez a un nivel rudimentario. Utilizaban funciones de evaluación muy simples para cada posición ^{[ b ]} e intentaban buscar lo más adelante posible dadas las limitaciones de tiempo ^{[ c ]} y la potencia de cálculo disponible. Naturalmente, los programadores optimizaban su código para utilizar los recursos informáticos disponibles. Esto dio lugar a una importante división filosófica entre los programas de ajedrez: aquellos que intentaban evaluar tantas posiciones como fuera posible y aquellos que intentaban evaluar las secuencias de movimientos más prometedoras con la mayor profundidad posible. CHAOS se situaba firmemente en el bando que creía que solo los movimientos más prometedores debían evaluarse en profundidad. Swartz afirmó: «Los que se basan en la fuerza bruta... analizan cada (movimiento posible) sin importar lo malo que sea. La mayoría de los movimientos son simplemente pésimos, pésimos, y la mayor parte del tiempo de cálculo se dedica a pura basura». ^{[ 2 ]} El programa dedicaba más tiempo a evaluar cada posición del tablero con la expectativa de encontrar las líneas de juego más prometedoras para explorar en profundidad. En 1983, el programa de ajedrez más rápido de la época (Belle) evaluaba 110.000 posiciones por segundo, y los programas típicos entre 1.000 y 50.000 por segundo, mientras que CHAOS evaluaba entre 50 y 100 por segundo. ^{[ 5 ]}

Desde aproximadamente 1949 en adelante, Arthur Samuel comenzó a trabajar para IBM en aprendizaje automático , ^{[ 10 ]} culminando en un programa para jugar a las damas en 1952 ^{[ 11 ]} y publicaciones sobre el tema. ^{[ 11 ]} Simultáneamente, Christopher Strachey creó Checkers , un programa para jugar al juego de mesa de las damas en 1951, ^{[ 12 ]} pero no tenía capacidad de aprender de su juego. Ambos autores eligieron Checkers porque era más simple que el ajedrez pero contenía las características básicas de una actividad intelectual y, en opinión de Samuel, era un banco de pruebas en el que se podían evaluar rápidamente los procedimientos heurísticos y los procesos de aprendizaje. Los programas para jugar a las damas introdujeron la noción del árbol de juego y la evaluación del juego a varias profundidades para elegir el mejor movimiento. ^{[ 12 ] [ 11 ]}

La complejidad del ajedrez, sin embargo, lo elevó al estatus de análogo de la inteligencia humana y atrajo la atención de los científicos informáticos, quienes lo denominaron investigación en inteligencia artificial (IA). ^{[ 5 ]} Al igual que las damas, requería una evaluación numérica de cada disposición de las piezas en el tablero. También requería anticipar movimientos futuros para decidir cómo jugar la posición actual. Debido a la enorme cantidad de movimientos posibles, era necesario encontrar una manera de limitar la búsqueda anticipada a las líneas de juego más prometedoras. A partir de estos factores, se desarrolló la noción de evaluación de puntuación minimax ^{[ 11 ]} y, posteriormente, la poda de árboles alfa-beta para dejar de considerar posiciones peores que cualquiera que ya se haya examinado.

La comunidad de IA consideraba que la inteligencia artificial constaba de dos partes: una forma de cuantificar simbólicamente el conocimiento disponible (una posición en el tablero de ajedrez) y un conjunto de heurísticas para limitar la anticipación a las consecuencias de un movimiento. Los primeros programas de ajedrez intentaban anticiparse lo máximo posible, quizás hasta tres movimientos por cada jugador, y elegir el mejor resultado. Esto dio lugar al efecto horizonte, por el cual un movimiento clave cuatro o más movimientos por delante no se examinaba y, por lo tanto, se pasaba por alto. ^{[ 13 ]} En consecuencia, los programas eran bastante débiles y las heurísticas para gestionar la búsqueda se volvieron importantes en su desarrollo. CHAOS utilizó una estrategia de búsqueda selectiva con ampliación iterativa . ^{[ 14 ]}

A medida que los programas de ajedrez evolucionaron, incorporaron libros de líneas de juego de aperturas de fuentes históricas. ^{[ 15 ]} Hoy en día, los movimientos de los libros se catalogan en un formato legible por máquina, pero originalmente los programadores tenían que escribirlos. ^{[ 16 ]} CHAOS tenía un libro extenso para su época de alrededor de 10 000 movimientos ^{[ 14 ]} que O'Keefe ayudó a desarrollar. Un problema con el juego a partir de un libro de aperturas es el comportamiento del programa cuando el juego sale del libro: la ventaja posicional puede ser tan sutil que el esquema de evaluación puede ser incapaz de entenderla, lo que lleva a búsquedas muy amplias y superficiales para establecer una línea de juego. El efecto horizonte nuevamente afecta la selección de movimientos después de salir del libro. CHAOS mitigó estos problemas usando solo líneas de libros que podía entender y basándose en análisis en caché de continuaciones fuera del libro realizadas mientras el reloj del oponente estaba corriendo.