La búsqueda de quiescencia es un algoritmo que se utiliza normalmente para ampliar la búsqueda en nodos inestables en árboles de juego minimax en programas informáticos de juegos . Es una extensión de la función de evaluación para aplazar la evaluación hasta que la posición sea lo suficientemente estable como para ser evaluada estáticamente, es decir, sin tener en cuenta el historial de la posición o los movimientos futuros desde la posición. Mitiga el efecto del problema del horizonte al que se enfrentan los motores de IA para varios juegos como el ajedrez y el Go .
Los jugadores humanos suelen tener la suficiente intuición para decidir si abandonar una jugada que parece mala o buscar una jugada prometedora a gran profundidad. Una búsqueda en estado de quietud intenta emular este comportamiento ordenando a una computadora que busque posiciones "volátiles" a mayor profundidad que las "tranquilas" para asegurarse de que no haya trampas ocultas y obtener una mejor estimación de su valor.
Cualquier criterio sensato puede utilizarse para distinguir posiciones "tranquilas" de posiciones "volátiles". Un criterio común es que existan movimientos en la posición que puedan cambiar drásticamente la valoración de la posición, como capturas en ajedrez o Go. Como el motivo principal de la búsqueda de quiescencia es obtener un valor estable de una función de evaluación estática , también puede tener sentido detectar fluctuaciones amplias en los valores devueltos por un evaluador heurístico simple a lo largo de varios ply , es decir, un criterio de historial. La búsqueda de quiescencia continúa mientras la posición permanezca volátil de acuerdo con el criterio. Para lograr que la búsqueda de quiescencia finalice, los plies generalmente se restringen a movimientos que tratan directamente con la amenaza, como los movimientos que capturan y recapturan (a menudo llamados "búsqueda de captura") en ajedrez. En juegos altamente "inestables" como Go y reversi , una proporción bastante grande del tiempo de la computadora puede dedicarse a la búsqueda de quiescencia.
El efecto horizonte es un problema en la inteligencia artificial que puede ocurrir cuando se buscan todos los movimientos desde un nodo determinado en un árbol de juego hasta una profundidad fija. Las amenazas y oportunidades más allá de la profundidad de búsqueda permanecerán sin detectar. Esto puede dar lugar a la peculiar estrategia de un programa que realiza movimientos demoradores que degradan la posición hasta que empuja una amenaza más allá de la profundidad de búsqueda u "horizonte". Para cuando se debe lidiar con la amenaza, la posición se ha degradado demasiado como para ser recuperable. La búsqueda de inactividad intenta mitigar este problema ampliando la profundidad de búsqueda en posiciones volátiles donde el valor heurístico puede tener fluctuaciones significativas entre movimientos.
Este pseudocódigo ilustra el concepto algorítmicamente:
La función quiescence_search(nodo, profundidad) es si el nodo parece tranquilo o el nodo es un nodo terminal o profundidad = 0 , entonces devuelve el valor estimado del nodo ; de lo contrario , ( busca recursivamente los hijos del nodo con quiescence_search) devuelve el valor estimado de los hijosfunción normal_search(nodo, profundidad) es si el nodo es un nodo terminal entonces devuelve el valor estimado del nodo de lo contrario si profundidad = 0 entonces si el nodo parece tranquilo entonces devuelve el valor estimado del nodo de lo contrario devuelve el valor estimado de quiescence_search(nodo, valor_de_profundidad_razonable) de lo contrario (busca recursivamente hijos del nodo con normal_search) devuelve el valor estimado de los hijos