Búsqueda con Profundidad Iterativa

Un problema no menor el cual los programadores debieron enfrentar fue el cómo setear en forma correcta el parámetro de profundidad de búsqueda antes de iniciarla. Si éste era demasiado bajo entonces el programa realizaría movimientos innecesariamente rápidos, no tomando ventaja del tiempo restante. Si el parámetro era demasiado grande el programa tomaría un tiempo excesivo en movimientos cuyo descubrimiento no debería tomar más de tres minutos. De hecho, en los primeros programas la adecuación a un tiempo limitado era un gran problema si éstos poseían un parámetro de profundidad elevado.

La búsqueda con profundidad iterativa empezó a popularizarse a mediados de la década del 70, y prácticamente solucionó el problema de seteo del parámetro de profundidad. Slate y Atkin introdujeron esta solución en 1975 en su programa CHESS 4.5 bajo la supervisión de Peter Frey, profesor de psicología de la Universidad de Northwestern. En los dos años siguientes la técnica pasó a ser parte de cada programa de ajedrez y posteriormente encontró utilidad en otros problemas relacionados con la Inteligencia Artificial, en particular con la demostración automatizada de teoremas.

Con la búsqueda de profundidad iterativa mas allá de realizar una sola búsqueda a una profundidad dada, una secuencia de búsquedas con profundidad incremental es realizada comenzando con profundidad uno, luego dos, y continuando hasta que el tiempo de reflexión máximo se completa. Cada iteración encuentra variantes principales las cuales tienen prioridad de análisis en las iteraciones siguientes. En cada iteración se almacenan posiciones en la tabla de hash para su uso en iteraciones siguientes. El resultado global de esto fue una mejora en la eficiencia del algoritmo alfa-beta, el cual compensa la pérdida de tiempo requerida para la realización de nuevas búsquedas.

Más importante aún es el hecho de que la búsqueda con profundidad iterativa permite terminar la búsqueda en cualquier momento sin consecuencias nefastas. Lo peor que podría ocurrir es que cuando el programa está en la 43#43-ésima iteración y debe jugar, éste ya posee la mejor evaluación en la iteración 60#60. Detenerse en el medio de una búsqueda perderá la posibilidad de encontrar un mejor movimiento en esa iteración sólo si éste está bajo el orden dado al movimiento actualmente analizado. Esto ocurre cuando el mejor movimiento no es evaluado como tal en la penúltima evaluación.