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