Главная » Игры, Теория » Эвристика убийцы

0

Порядок ходов при alpha-beta переборе имеет принципиальное значение. Хеш-таблица позволяет запоминать проделанную работу, и если позиция встретится вновь, мы имеем, как минимум, лучший ход для этой позиции, который можем попробовать сначала. Это все справедливо для очень боль­шой хеш-таблицы и одинаковых позиций. Но часто ситуация бывает сле­дующая: позиции отличаются в несущественных моментах, а лучший ход, вызывающий отсечку, совпадает. Возникла идея: попробовать сначала луч­ший ход для этого уровня, в надежде, что он будет лучшим и в данной по­зиции. Это часто срабатывает. Если у двух позиций один общий предок, то часто лучший ход в них один и тот же. Данная эвристика получила назва­ние эвристики убийцы (Killer heuristic). Она работает неточно, но может давать хорошую прибавку в скорости. Все дело в приоритете конкретной эвристики для оптимизации перемещений. Я, например, опытным путем пришел к следующему порядку:

1.    Пробуем результат из хеша в надежде получить отсечку.

2.    Пробуем нулевой ход с уменьшенной глубиной.

3.    Пробуем лучший ход из хеша.

4.    Взятия в отсортированном порядке. Сначала идут взятия, бьющие только ходившую фигуру противника, имеющие наилучшее соотношение цены атакованной фигуры и нападающего.

5.    Прежде чем пробовать основную массу "тихих" перемещений, попробуем ход Killer heuristic.

Из приведенного списка видно, что Killer move не может быть взятием. В качестве описателя перемещения для Killer heuristic можно использовать обычный описатель хода, но тогда придется проверять допустимость данно­го хода в этой позиции. Можно хранить просто номер хода, что значительно упрощает программу, но возможно не во всех реализациях.

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

Я всегда использовал Killer heuristic, т. к. она предельно проста и улучшает порядок ходов. Если программа не использует хеш, то ускорение от Killer heuristic очень существенно — 50% и более, но это не актуально в наши дни, т. к. практически все программы используют таблицы перестановок.

Killer move можно настроить и более тонким образом. Тогда ускорение от него сравнимо с небольшой хеш-таблицей. Генератор взятий должен пер­вым выдавать взятия последней ходившей фигуры противника. Тонкость состоит в том, что в Killer нельзя записывать взятия, бьющие последнюю ходившую фигуру противника, и в преузле Killer должен сбрасываться, т. к. имеет более низкий приоритет, чем взятия последней ходившей фигуры противника. Работает это очень хорошо. Два узла в дереве, имеющие обще­го предка, очень часто имеют один и тот же значимый ход. Единственное отличие — нужно попытаться сначала взять последнюю ходившую фигуру противника. Для организации Killer требуется всего 100 байт, если исполь­зуются номера ходов в буфере, или 100 описателей перемещений. 100 — это просто разумное число использования глубины Killer. А эффективность очень неплохая. Настройка Killer увеличит и без того значительное ускоре­ние от нулевого хода (если он применяется). Для Killer нет никакой разни­цы, в основном он поиске работает или в нулевом ходе. При поиске на большую глубину задержка от нулевого хода очень значительна (при хоро­шем порядке ходов и небольшом коэффициенте затухания). Это связано с тем, что перемещения в поиске нулевого хода плохо упорядочены, а про­грамма пытается считать глубоко. Хочется отметить, что эта пара: взятие последней ходившей фигуры противника и Killer move — работает очень хорошо на любой глубине без хеша и нулевого хода. Можно не записывать в Killer взятия вообще и использовать его после взятий.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии