Убийственная эвристика
Эта статья нуждается в дополнительных цитатах для проверки . ( апрель 2018 г. ) |
В соревновательных играх для двух игроков эвристика убийцы — это метод упорядочивания ходов, основанный на наблюдении, что сильный ход или небольшой набор таких ходов в определенной позиции может быть одинаково сильным в аналогичных позициях при одном и том же ходе (ходе) в игровое дерево.Сохранение таких ходов избавляет от необходимости заново обнаруживать их в родственных узлах.
Этот метод повышает эффективность альфа-бета-отсечения , что, в свою очередь, повышает эффективность минимаксного алгоритма . [1] Альфа-бета-отсечение работает лучше всего, когда в первую очередь рассматриваются лучшие ходы. Это связано с тем, что лучшие ходы с наибольшей вероятностью приведут к отсечению - состоянию, при котором игровая программа знает, что рассматриваемая позиция не могла возникнуть в результате лучшей игры обеих сторон и поэтому не нуждается в дальнейшем рассмотрении. Т.е. игровая программа всегда будет делать лучший доступный ход для каждой позиции. Ему нужно только учитывать возможные ответы другого игрока на этот лучший ход, и он может пропустить оценку ответов на (худшие) ходы, которые он не сделает.
Эвристика-убийца пытается произвести отсечение, предполагая, что ход, который привел к отсечению в другой ветви игрового дерева на той же глубине, скорее всего, приведет к отсечению в текущей позиции, то есть ход, который был очень неудачным. Хороший ход из другой (но, возможно, похожей) позиции может также быть хорошим ходом в текущей позиции. Пробуя убийственный ход перед другими ходами, игровая программа часто может произвести раннее отсечение, избавляя себя от необходимости рассматривать или даже генерировать все допустимые ходы из позиции.
На практике игровые программы часто отслеживают два убийственных хода для каждой глубины игрового дерева (глубины больше 1) и проверяют, приводит ли какой-либо из этих ходов, если это допустимо, к отсечению, прежде чем программа сгенерирует и рассмотрит остальные возможные ходы. Если неубийственный ход приводит к отсечению, он заменяет один из двух убийственных ходов на своей глубине. Эту идею можно обобщить в виде набора таблиц опровержений .
Обобщением эвристики убийцы является эвристика истории . [2] Эвристика истории может быть реализована в виде таблицы, которая индексируется по некоторым характеристикам хода, например, по полям «от» и «до» или по перемещению фигуры и полю «до». При наличии ограничения соответствующая запись в таблице увеличивается, например, путем добавления d² или 2. д где d — текущая глубина поиска. За пределами приращения глубины около 2 историческая информация быстро превращается в «шум». [ нужна ссылка ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Губерман (Лисков), Барбара Джейн (1968). «Программа для игры в шахматные эндшпили» (PDF) . Факультет компьютерных наук Стэнфордского университета, Технический отчет CS 106, Памятка Стэнфордского проекта искусственного интеллекта AI-65. Архивировано из оригинала (PDF) 5 сентября 2020 г.
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Улучшения исторической эвристики и альфа-бета-поиска на практике, Джонатан Шеффер