Next: Función de Evaluación
Up: Avances en Software
Previous: Generador de Movimientos
  Índice General
Las técnicas de búsqueda en el ajedrez han sido probablemente la
parte más desarrollada en términos de investigación para la mejora
de algoritmos dentro del proceso del juego. Es acá en donde el
programa realiza el mayor esfuerzo en recolectar información
suficiente para decidir por un movimiento.
Los algoritmos desarrollados para este fin han sido variados. La
primera propuesta, presentada por Shannon, fue la búsqueda por
fuerza bruta a profundidad fija, examinando todas las
continuaciones posibles hasta cierto límite de movimientos. Esta
búsqueda se realizaría mediante el algoritmo Minimax.
Hasta principios de los 70 los programas de ajedrez seguían
basándose en los modelos de Shannon para realizar su proceso de
búsqueda. Hasta ese momento el diseño de programas de ajedrez se
focalizaba principalmente en el orden de los movimientos con tal
de lograr la mejor "poda" de variantes: jaques, capturas,
"movidas asesinas", amenazas y avances de peones pasados.
Categorizando los movimientos en distintos grupos mediante
amenazas tácticas (de corto plazo) o estratégicas (de largo plazo)
se podía asegurar el que las variantes "forzadas" serían
analizadas primero. Esta técnica lograba generar cortes o
reducciones en el árbol de búsqueda para aquellas variantes que se
clasificaban como innecesarias de analizar.
También durante la década de 1970 la noción de búsqueda
iterativa fue refinada y sometida a prueba. Con un enfoque de
completitud y uniformidad las búsquedas eran generalmente hechas a
una profundidad fija (en forma iterativa dependiendo del tiempo de
reflexión restante). El uso del tiempo para controlar la búsqueda
tomó también un carácter de suma importancia, dado que ofrecía la
flexibilidad de confirmar si el movimiento encontrado en la
anterior iteración era efectivamente el mejor. Esto hizo que de
alguna manera la búsqueda selectiva (estrategia "B" de Shannon)
cayera en desuso, debido a la dificultad de su implementación en
las computadoras.
Resultó que la seguridad de buscar en todos los movimientos
posibles otorgó mejores resultados que el descarte de variantes
basado en su baja relevancia. La búsqueda selectiva vio
prácticamente su muerte en esta década, si bien fue la estrategia
líder de los 60 con el programa MackHack, el cual estaba
implementado con un selector de movimientos plausibles
[46]. A finales de la década los beneficios de la búsqueda
de posiciones estables con profundidad variable fue clara, y esto
llevó a la preponderancia de los programas de estrategia tipo A
los cuales utilizaron búsquedas basadas en distintas etapas.
Con el aumento en la velocidad de los procesadores pudieron realizarse búsquedas más
profundas causando a principio de los 80 un interés por
realizarlas en etapas. La idea fue realizar una primera búsqueda a
profundidad fija de varios movimientos seguida de una búsqueda
selectiva y terminando con una búsqueda de posiciones estables a
partir de movimientos como capturas o respuestas a jaques. Este
modelo de búsqueda demostró ser a la vez bastante robusto. De
todas maneras, este tipo de búsqueda en etapas no reflejaba
adecuadamente la noción intuitiva de que las extensiones en la
profundidad de búsqueda deben ser selectivas en vez de uniformes,
aplicándose en variantes forzadas.
Era claro que la extensión de un movimiento debía realizarse
cuando uno de los bandos se encontraba en jaque. Un idea similar
era extender la búsqueda cuando un jugador tuviera sólo un
movimiento legal posible, pero lo que realmente se deseaba buscar
era una extensión en situaciones en que cualquiera de los dos
jugadores tuviese sólo un movimiento "sensible" (por ejemplo,
una captura). Esto implicaba algún tipo de pre-poda con tal de
detener la expansión de identificación de malos movimientos. Dos
ideas de pre-poda bastante trabajadas variantes fueron los cortes
a raz y en vano ("razoring" and "futility" cutoffs). Por
ejemplo, si justo antes del horizonte de búsqueda el score está
sobre el límite beta del minimax para el bando que juega, cortar
inmediatamente (corte al raz). Alternativamente, si el movimiento
actual está bajo el límite alfa y los factores posicionales no
tienen el potencial para aumentarlo, descontinuar la variante
(corte en vano).
Métodos de búsqueda variable como estos fueron refinados para
asegurar el control de las extensiones, sobretodo en las búsquedas
sin límite (por ejemplo, jaques perpetuos) y en cambios drásticos
de equilibro material (por ejemplo en promociones de peón). Como
conclusión era clara la necesidad de algún tipo de búsqueda
selectiva de profundidad variable.
En los 90 ya estaban bien entendidos los criterios para extender
en forma automática la búsqueda, con lo cual el foco de atención
se centralizó nuevamente en la búsqueda selectiva con pre-poda
(forward pruning), una idea que había sido repetidamente intentada
en décadas pasadas pero con resultados contradictorios. Una
generalización de las podas de corte de navaja (razoring) y de
valor nulo (futility) fue el uso del "`movimiento de paso" en la
búsqueda de posiciones estables [32]. La esencia de la
tercera etapa de búsqueda es considerar sólo movimientos de
captura, algunos jaques y movimientos tácticos que alteran
considerablemente el equilibrio material. El uso de un movimiento
de paso (que en el fondo significa permitir al adversario mover
dos veces) asegura que una amenaza del rival puede ser encontrada
más rápidamente. Técnicas de movimiento de paso fueron la pre-poda
utilizada en inicios de los 90. La implementación de esta pre-poda
con mayor suceso fue desarrollada por Goetsch y Campbell
[44].
En el tiempo en que los métodos de "movimiento de paso" (null-move) eran
descritos se comenzó a trabajar en otras formas de variar la
profundidad de búsqueda. Era claro ya que las respuestas a jaques
no debían contar como un movimiento que adelanta un paso al
horizonte de búsqueda. para esto, una extensión automática puede
realizarse por cada movimiento forzado pero con respuesta única. A
principios de los 90 la noción de "Extensiones Singulares" fue
introducida e implementada [30]. Movimientos que son
sustancialmente mejores que otros de su mismo nivel de búsqueda
son analizados con un nivel más de profundidad con tal de reducir
el riesgo del efecto horizonte.
En el pasado la búsqueda selectiva fue un método de alto riesgo
pero con gran potencial de desarrollo. En la actualidad los
métodos de búsqueda variable son un área de desarrollo activo.
Recientemente algunos métodos de poda existentes fueron mejorados
por Heinz [49], quien los generalizó con tal de realizar
podas en niveles por sobre el horizonte mientras que Marsland
[58] realizó estudios sobre las búsquedas en nodos
factibles de ser podados. Ambos métodos lograron mejoras en el
nivel de juego y están siendo empleados por varios de los más
fuertes programas de la actualidad.
Con el incremento en espacio de memoria, renovado interés tuvo el
desarrollo de algoritmos de búsqueda desechados con anterioridad
como el SSS* de Stockman y el B* de Berliner [34] y
métodos combinados como el DUAL* [57] los cuales eran
computacionalmente eficientes pero lentos de ejecutar.
Next: Función de Evaluación
Up: Avances en Software
Previous: Generador de Movimientos
  Índice General
Santiago de Chile, Julio 2003