Эвристика нулевого перемещения

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

Обоснование

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

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

Выполнение

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

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

Проблемы с эвристикой нулевого перемещения

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

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

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

Проверенная обрезка с нулевым ходом

Еще одна эвристика для решения проблемы цугцванга — это предложенное Омидом Давидом и Натаном Нетаньяху проверенное отсечение нулевого хода, . ^[1] При проверенном сокращении с нулевым ходом всякий раз, когда неглубокий поиск с нулевым ходом указывает на высокий уровень сбоя, вместо того, чтобы отрезать поиск от текущего узла, поиск продолжается с уменьшенной глубиной.

Ссылки

^ Давид-Табиби, Омид; Нетаньяху, Натан С. (сентябрь 2002 г.). «Проверенная обрезка нулевого хода». Журнал ICGA . 25 (3): 153–161. arXiv : 0808.1125 . Бибкод : 2008arXiv0808.1125D . doi : 10.3233/ICG-2002-25305 . S2CID 1041 .

Гетч, Г.; Кэмпбелл, MS (1990). «Эксперименты с эвристикой нулевого хода». В Марсленде Т. Энтони; Шеффер, Джонатан (ред.). Компьютеры, шахматы и познание . Спрингер-Верлаг. стр. 159–168. ISBN 3-540-97415-6 .

[1] Давид-Табиби, Омид; Нетаньяху, Натан С. (сентябрь 2002 г.). «Проверенная обрезка нулевого хода». Журнал ICGA . 25 (3): 153–161. arXiv : 0808.1125 . Бибкод : 2008arXiv0808.1125D . doi : 10.3233/ICG-2002-25305 . S2CID 1041 .

[1]