В компьютерных шахматах , эвристика нулевого хода — метод увеличения скорости алгоритма альфа-бета-отсечения .

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

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

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

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

Ссылки

• Frayn C. // Computer Chess Programming Theory
• David-Habibi O., Netanyahu N. S. (недоступная ссылка с 13-05-2013 [3889 дней] — ) // ICGA Journal, September 2002

Примечания