Нулевой ход - Null move

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

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

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

Рекомендации

  1. ^ Бил, Дон Ф. (1990), "Обобщенный алгоритм поиска в состоянии покоя", Искусственный интеллект, 43 (1): 85–98, Дои:10.1016/0004-3702(90)90072-8.
  2. ^ Goetsch, G .; Кэмпбелл, М.С. (1990), «Эксперименты с эвристикой нулевого хода», в Марсленде, Т. Энтони; Шеффер, Джонатан (ред.), Компьютеры, шахматы и познание, Springer-Verlag, стр. 159–168..