Quiescencia de búsqueda es un algoritmo usado típicamente para extender la búsqueda en nodos inestables en minimax árboles de juego en juego -playing programas de ordenador . Es una extensión de la función de evaluación diferir la evaluación hasta que la posición sea lo suficientemente estable como para ser evaluada estáticamente, es decir, sin considerar el historial de la posición o 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 intuición suficiente para decidir si abandonar un movimiento de mala apariencia o buscar un movimiento prometedor a gran profundidad. Una búsqueda en reposo intenta emular este comportamiento indicando a una computadora que busque posiciones "volátiles" a una profundidad mayor que las "silenciosas" para asegurarse de que no haya trampas ocultas y obtener una mejor estimación de su valor.
Se puede utilizar cualquier criterio sensato para distinguir las posiciones "tranquilas" de las posiciones "volátiles". Un criterio común es que existen movimientos en la posición que pueden 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 inactividad es obtener un valor estable de una función de evaluación estática , también puede tener sentido detectar amplias fluctuaciones en los valores devueltos por un evaluador heurístico simple en varias capas , es decir, un criterio histórico. La búsqueda de reposo continúa mientras la posición permanezca volátil según el criterio. Para que la búsqueda de reposo termine, las capas se restringen generalmente a movimientos que se ocupan directamente de la amenaza, como los movimientos que capturan y recapturan (a menudo llamado "búsqueda de captura") en el ajedrez. En juegos altamente "inestables" como Go y reversi , se puede dedicar una proporción bastante grande del tiempo de la computadora a la búsqueda de reposo.
El efecto horizonte
El efecto horizonte es un problema en la inteligencia artificial que puede ocurrir cuando todos los movimientos de un nodo dado en un árbol de juego se buscan a una profundidad fija. Las amenazas y oportunidades más allá de la profundidad de búsqueda permanecerán sin ser detectadas. Esto puede resultar en la estratagema peculiar de un programa que hace movimientos dilatorios que degradan la posición hasta que empuja una amenaza más allá de la profundidad de búsqueda u "horizonte". En el momento en que se debe hacer frente a la amenaza, la posición se ha degradado demasiado para poder salvarla. La búsqueda de reposo 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.
Pseudocódigo
Este pseudocódigo ilustra el concepto algorítmicamente:
función quiescence_search (nodo, profundidad) es si el nodo parece tranquilo o el nodo es un nodo terminal o profundidad = 0, luego devuelve el valor estimado del nodo else ( busca recursivamente los niños del nodo con quiescence_search) devuelve el valor estimado de los niñosla función normal_search (nodo, profundidad) es si el nodo es un nodo terminal, luego devuelve el valor estimado del nodo en caso contrario, si la profundidad = 0, entonces si el nodo parece silencioso, luego devuelve el valor estimado del nodo else devuelve el valor estimado de quiescence_search (nodo, valor_de_profundidad razonable) else (recursivamente niños del nodo de búsqueda con búsqueda_normal) devuelven el valor estimado de los niños
Referencias
Beal, Don (abril de 1990). "Un algoritmo de búsqueda de quiescencia generalizada" . Inteligencia artificial . 43 : 85–98. doi : 10.1016 / 0004-3702 (90) 90072-8 . Consultado en diciembre de 2020 . Verifique los valores de fecha en: |access-date=
( ayuda )