Поиск покоя — это алгоритм, который обычно используется для расширения поиска в нестабильных узлах в деревьях минимаксных игр в компьютерных программах для игр . Это расширение функции оценки для отсрочки оценки до тех пор, пока позиция не станет достаточно стабильной для статической оценки, то есть без учета истории позиции или будущих ходов из позиции. Он смягчает эффект проблемы горизонта, с которой сталкиваются движки ИИ для различных игр, таких как шахматы и го .
У игроков-людей обычно достаточно интуиции, чтобы решить, отказаться ли от плохо выглядящего хода или поискать многообещающий ход на большой глубине. Поиск покоя пытается эмулировать это поведение, инструктируя компьютер искать «нестабильные» позиции на большей глубине, чем «тихие», чтобы убедиться в отсутствии скрытых ловушек и получить лучшую оценку его ценности.
Любой разумный критерий может быть использован для различения «тихих» позиций от «нестабильных». Одним из распространенных критериев является то, что в позиции существуют ходы, которые могут кардинально изменить оценку позиции, например, захваты в шахматах или го. Поскольку основным мотивом поиска покоя является получение стабильного значения из статической функции оценки , может также иметь смысл обнаружить большие колебания значений, возвращаемых простым эвристическим оценщиком в течение нескольких игр , т. е. критерий истории. Поиск покоя продолжается до тех пор, пока позиция остается нестабильной в соответствии с критерием. Чтобы завершить поиск покоя, игры обычно ограничиваются ходами, которые имеют дело непосредственно с угрозой, например, ходами, которые захватывают и отбивают (часто называемыми «поиском захвата») в шахматах. В крайне «нестабильных» играх, таких как го и реверси , довольно большая часть компьютерного времени может быть потрачена на поиск покоя.
Эффект горизонта — это проблема искусственного интеллекта , которая может возникнуть, когда все ходы из заданного узла в дереве игры просматриваются до фиксированной глубины. Угрозы и возможности за пределами глубины поиска останутся необнаруженными. Это может привести к своеобразной уловке программы, которая делает задерживающие ходы, которые ухудшают позицию, пока она не выдвинет угрозу за пределы глубины поиска или «горизонта». К тому времени, когда угроза должна быть устранена, позиция становится слишком плохой, чтобы ее можно было спасти. Поиск покоя пытается смягчить эту проблему, увеличивая глубину поиска в нестабильных позициях, где эвристическое значение может иметь значительные колебания между ходами.
Этот псевдокод алгоритмически иллюстрирует эту концепцию:
Функция quiescence_search(node, depth) возвращает оценочное значение узла , если узел кажется тихим или является конечным узлом или глубина = 0 , в противном случае ( рекурсивно ищет дочерние узлы с помощью quiescence_search) возвращает оценочное значение дочерних узлов. функция normal_search(node, depth) — если узел является конечным узлом , то возвращает оценочное значение узла , иначе если глубина = 0 , то если узел кажется тихим, то возвращает оценочное значение узла , иначе возвращает оценочное значение из quiescence_search(node, reasonable_depth_value), иначе (рекурсивно ищет дочерние узлы с помощью normal_search) возвращает оценочное значение дочерних узлов