Búsqueda de Ventana

A fines de los 70 la búsqueda de ventana empezó a ser utilizada en los programas de ajedrez en conjunto con la búsqueda con profundidad iterativa. Su uso incrementó la eficiencia del proceso de búsqueda al lograr obtener una mayor cantidad de "cortes" en las variantes analizadas. La búsqueda de ventana está basada en la idea de que en una misma variante es muy probable que el score a encontrar en la iteración actual será probablemente el mismo que el encontrado en la iteración anterior. Un "score esperado" (RS) es supuesto al principio de la nueva iteración, usualmente el score guardado en la raíz del árbol en la iteración previa, y una búsqueda de ventana es realizada en torno a ese score. Entonces durante la búsqueda una serie de "cortes" ocurren en posiciones cuyos scores no están dentro del rango de la ventana.

El "tamaño" de la ventana es típicamente de 2 peones (2P). Al principio de cada iteración el score de la raíz es inicializado en RS - P y cuando la búsqueda obtenga una evaluación en la nueva posición su score tendrá el valor de RS + P, donde P corresponde al valor de un peón. Estos valores corresponden a -∞ y +∞ cuando la búsqueda de ventana no es utilizada. Se dice que la ventana es inicializada en los valores <RS-P,RS+P>. La búsqueda entonces procede como es usual. Si un movimiento posee una evaluación que está dentro de los rangos de la ventana cuando la iteración termina, la próxima iteración comienza con una ventana de ancho 2P pero centrada en el nuevo valor obtenido. Se dice que la búsqueda ha fallado "alto" si el score es igual o mayor a RS + P y ha fallado "bajo" si el score es menor o igual a RS - P. Si la búsqueda falla la iteración debe ser repetida para encontrar el real valor de la raíz y corregir la continuación principal.

En el caso de una falla "alta" la ventana debe limitarse a <RS+P,+∞> para asegurar que la segunda evaluación no fallará. Similarmente en el caso de una falla "baja" la ventana debe limitarse en los valores <&infin,RS -P>. Mientras más limitado el ancho de la ventana la primera evaluación terminará antes, pero con mayor chance de fallar. Cuando es utilizada la búsqueda de ventana, cada´iteración de búsqueda debe considerarse como consistente de dos etapas, la segunda innecesaria si la primera es exitosa.

Tipos más sofisticados de búsqueda de ventana que permiten setear la ventana y realizar búsquedas sobre sub árboles de variantes en todas las posiciones del árbol principal son utilizadas por algunos programas. Estos procedimientos recursivos fueron descritos en papers de J.Pearl en 1980 y de A.Reinfeld en 1985.