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

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

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

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

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

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

использованная литература

  1. ^ Хуберман (Лисков), Барбара Джейн (1968). «Программа для игры в шахматы» (PDF). Факультет компьютерных наук Стэнфордского университета, технический отчет CS 106, меморандум AI-65 Стэнфордского проекта по искусственному интеллекту. Цитировать журнал требует | журнал = (Помогите)

Смотрите также

внешняя ссылка