Técnicas de Búsqueda

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.