Поиск покоя

Поиск покоя — это алгоритм, обычно используемый для расширения поиска в нестабильных узлах игровых деревьев в игровых минимаксных компьютерных программах . Это расширение функции оценки, позволяющее откладывать оценку до тех пор, пока позиция не станет достаточно стабильной, чтобы ее можно было оценивать статически, то есть без учета истории позиции или будущих движений от позиции. Это смягчает эффект проблемы горизонта, с которой сталкиваются искусственного интеллекта механизмы в различных играх, таких как шахматы и го .

У игроков-людей обычно достаточно интуиции, чтобы решить, стоит ли отказаться от плохо выглядящего хода или искать многообещающий ход на большую глубину. Поиск покоя пытается имитировать это поведение, предписывая компьютеру искать «неустойчивые» позиции на большей глубине, чем «тихие», чтобы убедиться в отсутствии скрытых ловушек и получить лучшую оценку ее значения.

Любой разумный критерий может быть использован для того, чтобы отличить «спокойные» позиции от «неустойчивых». Одним из общих критериев является то, что в позиции существуют ходы, которые могут резко изменить оценку позиции, например, взятия в шахматах или го. Поскольку основным мотивом поиска покоя является получение стабильного значения из статической оценочной функции , может также иметь смысл обнаружить широкие колебания значений, возвращаемых простым эвристическим оценщиком в нескольких слоях , то есть по критерию истории. Поиск покоя продолжается до тех пор, пока положение остается изменчивым согласно критерию. Чтобы прекратить поиск покоя, ходы обычно ограничиваются ходами, которые непосредственно связаны с угрозой, например, ходами, которые захватывают и возвращают (часто называемые «поиском захвата») в шахматах. В очень «нестабильных» играх, таких как го и реверси , довольно большая часть компьютерного времени может быть потрачена на поиск состояния покоя.

Эффект горизонта

Эффект горизонта — это проблема искусственного интеллекта , которая может возникнуть, когда все ходы из заданного узла в дереве игры просматриваются до фиксированной глубины. Угрозы и возможности за пределами глубины поиска останутся незамеченными. Это может привести к своеобразной уловке программы, делающей запаздывающие действия, которые ухудшают позицию, пока она не вытолкнет угрозу за пределы глубины поиска или «горизонта». К тому времени, когда угроза должна быть устранена, положение стало слишком деградированным, чтобы его можно было спасти. Поиск в режиме покоя пытается смягчить эту проблему, увеличивая глубину поиска в изменчивых позициях, где эвристическая ценность может иметь значительные колебания между ходами.

Псевдокод

Этот псевдокод алгоритмически иллюстрирует эту концепцию:

function quiescence_search(node, depth) is
    if node appears quiet or node is a terminal node or depth = 0 then
        return estimated value of node
    else
        (recursively search node children with quiescence_search)
        return estimated value of children

function normal_search(node, depth) is
    if node is a terminal node then
        return estimated value of node
    else if depth = 0 then
        if node appears quiet then
            return estimated value of node
        else
            return estimated value from quiescence_search(node, reasonable_depth_value)
    else
        (recursively search node children with normal_search)
        return estimated value of children

Ссылки

Бил, Дон (апрель 1990 г.). «Обобщенный алгоритм поиска покоя» . Искусственный интеллект . 43 : 85–98. дои : 10.1016/0004-3702(90)90072-8 .