Los dias iniciales: Búsqueda Selectiva

En su paper de 1949 Shannon describió dos formas de construir un algoritmo de un programa que jugase al ajedrez:

• Buscar todos los movimientos posibles tanto propios como del adversario hasta una profundidad límite, la que llamó "estrategia A".
• Examinar sólo los mejores movimientos tanto propios como del adversario obtenidos a partir de un análisis detallado de la posición. Este método fue denominado como "estrategia B".

A primera vista la segunda alternativa aparentaba tener un mayor éxito. Después de todo es la forma en la que los humanos juegan y pareciese lógico asumir que el buscar pocas alternativas en cada movimiento será más rápido que buscar todos los movimientos posibles. Desafortunadamente, los resultados prácticos fueron en contra de lo que decía la teoría: los programas que utilizaron búsqueda selectiva no lograron jugar a un nivel avanzado. Como mejor resultado lograban un nivel de jugador de nivel medio de club, cometiendo a menudo errores casi infantiles en los peores momentos. El vencer a un Gran Maestro de Ajedrez era algo definitivamente lejano a sus capacidades.

Figura: Tipos de búsqueda realizados por una máquina y un humano dentro del árbol de variantes

El tiempo y análisis utilizado en el proceso de selección de los mejores movimientos no compensaba la reducción del árbol de variantes de análisis, por lo que muchos programas implementados con la estrategia B de Shannon fueron transformados en programas de estrategia A. Uno de los casos más emblemáticos es el del programa CHESS 4.5, cuyos primeros prototipos utilizaban la estrategia B. De acuerdo a sus autores [7], los algoritmos de selección utilizados eran demasiado complejos y no cumplían a cabalidad con seleccionar el mejor movimiento en una posición dada.

El problema radicaba también en que el "generador de mejores movimientos" para ser bueno debe en realidad ser perfecto. Supongamos que un programa es equipado con una función que busca las 5 mejores movidas en una posición y que la objetivamente mejor movida entre esas 5 se encuentra el 95% de las ocasiones (esto es un supuesto muy optimista). Esto significa que la probabilidad de que el generador contenga la mejor alternativa todas las veces durante una partida de 40 jugadas es menor que un 13%.

A mediados de 1970 el legendario equipo de la universidad de Northwestern y creador de CHESS 4.5 (Slate & Atkin) decidieron olvidar el problema del generador de mejores movimientos especificando que el tiempo ganado en evitar costosos análisis durante la generación de movimientos era suficiente para cubrir el costo de tener una búsqueda completa (examinar todos los movimientos). Este descubrimiento prácticamente enterró la búsqueda selectiva.

Un ejemplo extremo de algoritmo de búsqueda selectiva fue desarrollado en la Unión Soviética en la década de los 70 bajo la tutela del ex campeón mundial Mikhail Botvinnick.

Botvinnick era un convencido de que la única forma de lograr programar una máquina que jugase al ajedrez a nivel del mejor jugador del mundo era imitando la forma de jugar de los Grandes Maestros, es decir, examinar una pequeña cantidad de movimientos pero con gran profundidad y detalle. Su programa se aproximó a identificar e implementar el desarrollo de estrategias de alto nivel y patrones que jugadores de nivel mundial utilizarían durante una partida [2].