Поиск покоя - Quiescence search
 | эта статья не цитировать любой источники. (Август 2019 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
Поиск покоя алгоритм, обычно используемый для расширения поиска в нестабильных узлах в минимакс игровые деревья в игра -играющий компьютерные программы. Это расширение функции оценки, позволяющее отложить оценку до тех пор, пока позиция не станет достаточно стабильной для статической оценки, то есть без учета истории позиции или будущих перемещений из позиции. Снижает эффект проблема горизонта столкнулся с AI двигатели для различных игр, таких как шахматы и Идти.
Игроки-люди обычно обладают достаточной интуицией, чтобы решить, следует ли отказаться от неудачного хода или искать многообещающий ход с большой глубиной. Поиск в состоянии покоя пытается имитировать это поведение, давая компьютеру команду искать «изменчивые» позиции на большей глубине, чем «тихие», чтобы убедиться в отсутствии скрытых ловушек и получить лучшую оценку их значения.
Можно использовать любой разумный критерий, чтобы отличить «тихие» позиции от «нестабильных». Одним из общих критериев является наличие ходов в позиции, которые могут резко изменить оценку позиции, например взятия в шахматы или го. Поскольку основным мотивом поиска состояния покоя является получение стабильного значения из статического функция оценки, также может иметь смысл обнаруживать большие колебания значений, возвращаемых простым эвристическим оценщиком за несколько слой, т.е. исторический критерий. Поиск состояния покоя продолжается, пока положение остается нестабильным по критерию. Чтобы завершить поиск в состоянии покоя, уровни обычно ограничиваются движениями, которые имеют дело непосредственно с угрозой, например, движениями по захвату и повторному захвату (часто называемым «поиском захвата») в шахматах. В очень "нестабильных" играх, таких как Go и реверси, довольно большая часть компьютерного времени может быть потрачена на поиск в состоянии покоя.
Эффект горизонта
В эффект горизонта проблема в искусственный интеллект что может произойти, когда все ходы от данного узла в дереве игры просматриваются на фиксированную глубину. Угрозы и возможности за пределами глубины поиска останутся незамеченными. Это может привести к своеобразной уловке программы, выполняющей замедляющие действия, которые ухудшают позицию, пока она не вытолкнет угрозу за пределы глубины или «горизонта» поиска. К тому времени, когда с угрозой нужно бороться, положение становится слишком деградированным, чтобы его можно было спасти. Поиск в состоянии покоя пытается смягчить эту проблему, увеличивая глубину поиска в нестабильных позициях, где эвристическое значение может иметь значительные колебания между ходами.
Псевдокод
Этот псевдокод иллюстрирует концепцию алгоритмически:
функция quiescence_search (узел, глубина) является если узел кажется тихим или узел является конечным узлом или глубина = 0 тогда вернуть расчетная стоимость узла еще (рекурсивно дочерние узлы поиска с quiescence_search) вернуть оценочная стоимость детейфункция normal_search (узел, глубина) является если узел является конечным узлом тогда вернуть оценочная стоимость узла иначе если глубина = 0 тогда если узел кажется тихим тогда вернуть оценочная стоимость узла еще вернуть оценочное значение из quiescence_search (узел, разумное_значение_глубины) еще (рекурсивный поиск дочерних узлов с помощью normal_search) вернуть оценочная стоимость детей