В конкурентных играх для двух игроков эвристика убийцы — это метод упорядочивания ходов, основанный на наблюдении, что сильный ход или небольшой набор таких ходов в определенной позиции может быть одинаково сильным в похожих позициях на том же ходу (слое) в дереве игры. Сохранение таких ходов устраняет необходимость в повторном открытии их в родственных узлах.
Этот метод повышает эффективность альфа-бета-отсечения , что в свою очередь повышает эффективность алгоритма минимакса . [1] Альфа-бета-отсечение работает лучше всего, когда сначала рассматриваются лучшие ходы. Это происходит потому, что лучшие ходы — это те, которые с наибольшей вероятностью приведут к отсечению , состоянию, когда игровая программа знает, что позиция, которую она рассматривает, не могла быть результатом лучшей игры обеих сторон, и поэтому не нуждается в дальнейшем рассмотрении. То есть игровая программа всегда будет делать свой лучший доступный ход для каждой позиции. Ей нужно только рассмотреть возможные ответы другого игрока на этот лучший ход, и она может пропустить оценку ответов на (худшие) ходы, которые она не будет делать.
Эвристика убийцы пытается произвести отсечение, предполагая, что ход, который произвел отсечение в другой ветви дерева игры на той же глубине, вероятно, произведет отсечение в текущей позиции, то есть ход, который был очень хорошим ходом из другой (но, возможно, похожей) позиции, может также быть хорошим ходом в текущей позиции. Пробуя ход-убийцу перед другими ходами, игровая программа часто может произвести раннее отсечение, экономя себе усилия по рассмотрению или даже генерации всех допустимых ходов из позиции.
В практической реализации игровые программы часто отслеживают два убийственных хода для каждой глубины игрового дерева (больше глубины 1) и смотрят, производит ли какой-либо из этих ходов, если он допустим, отсечку, прежде чем программа сгенерирует и рассмотрит остальные возможные ходы. Если неубийственный ход производит отсечку, он заменяет один из двух убийственных ходов на своей глубине. Эту идею можно обобщить в набор таблиц опровержения .
Обобщением эвристики-убийцы является эвристика истории . [2] Эвристика истории может быть реализована как таблица, индексированная по некоторым характеристикам хода, например, полям «от» и «до» или перемещением фигуры и полем «до». Когда происходит отсечение, соответствующая запись в таблице увеличивается, например, путем добавления d² или 2 d , где d — текущая глубина поиска. За пределами глубины приращения около 2 информация истории быстро вырождается в «шум». [ требуется цитата ]
{{cite journal}}: Цитировать журнал требует |journal=( помощь )