Next: Búsqueda de Ventana
Up: Técnicas de Búsqueda
Previous: Extensiones Singulares
  Índice General
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.
Next: Búsqueda de Ventana
Up: Técnicas de Búsqueda
Previous: Extensiones Singulares
  Índice General
Santiago de Chile, Julio 2003