Jump to content

Убийственная эвристика

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

Этот метод повышает эффективность альфа-бета-отсечения , что, в свою очередь, повышает эффективность минимаксного алгоритма . [1] Альфа-бета-отсечение работает лучше всего, когда в первую очередь рассматриваются лучшие ходы. Это связано с тем, что лучшие ходы с наибольшей вероятностью приведут к отсечению - состоянию, при котором игровая программа знает, что рассматриваемая позиция не могла возникнуть в результате лучшей игры обеих сторон и поэтому не нуждается в дальнейшем рассмотрении. Т.е. игровая программа всегда будет делать лучший доступный ход для каждой позиции. Ему нужно только учитывать возможные ответы другого игрока на этот лучший ход, и он может пропустить оценку ответов на (худшие) ходы, которые он не сделает.

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

На практике игровые программы часто отслеживают два убийственных хода для каждой глубины игрового дерева (глубины больше 1) и проверяют, приводит ли какой-либо из этих ходов, если это допустимо, к отсечению, прежде чем программа сгенерирует и рассмотрит остальные возможные ходы. Если неубийственный ход приводит к отсечению, он заменяет один из двух убийственных ходов на своей глубине. Эту идею можно обобщить в виде набора таблиц опровержений .

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

См. также

[ редактировать ]
  1. ^ Губерман (Лисков), Барбара Джейн (1968). «Программа для игры в шахматные эндшпили» (PDF) . Факультет компьютерных наук Стэнфордского университета, Технический отчет CS 106, Памятка Стэнфордского проекта искусственного интеллекта AI-65. Архивировано из оригинала (PDF) 5 сентября 2020 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  2. ^ Улучшения исторической эвристики и альфа-бета-поиска на практике, Джонатан Шеффер
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 70f2526829327bc84d55096e68d5b739__1721762280
URL1:https://arc.ask3.ru/arc/aa/70/39/70f2526829327bc84d55096e68d5b739.html
Заголовок, (Title) документа по адресу, URL1:
Killer heuristic - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)