В компьютерных шахматных программах эвристика нулевого хода - это эвристический метод, используемый для повышения скорости алгоритма отсечения альфа-бета .
Обоснование [ править ]
Отсечение альфа-бета ускоряет алгоритм минимакса , определяя отсечки , точки в дереве игры, где текущая позиция настолько хороша для движения стороны, что лучшая игра другой стороны могла бы избежать этого. Поскольку такие позиции не могли быть результатом лучшей игры, их и все вытекающие из них ветви дерева игры можно игнорировать. Чем быстрее программа производит отсечки, тем быстрее выполняется поиск. Эвристика нулевого хода предназначена для угадывания отсечки с меньшими усилиями, чем потребовалось бы в противном случае, при сохранении разумного уровня точности.
Эвристика нулевого хода основана на том факте, что наиболее разумные шахматные ходы улучшают позицию стороны, которая их разыграла. Таким образом, если игрок, чья очередь делать ход, может потерять право на ход (или сделать нулевой ход - незаконное действие в шахматах ) и все еще иметь позицию, достаточно сильную, чтобы произвести отсечку, то текущая позиция почти наверняка приведет к отсечка, если текущий игрок действительно переместился.
Реализация [ править ]
При использовании эвристики нулевого перемещения компьютерная программа сначала пропускает поворот стороны, чей ход должен двигаться, а затем выполняет альфа-бета-поиск полученной позиции на меньшую глубину, чем при поиске текущей позиции. он не использовал эвристику нулевого хода. Если этот неглубокий поиск дает отсечку, предполагается, что поиск на полную глубину в отсутствие потерянного поворота также привел бы к отсечке. Поскольку неглубокий поиск выполняется быстрее, чем более глубокий поиск, отсечение происходит быстрее, что ускоряет работу компьютерной шахматной программы. Если неглубокий поиск не дает отсечки, программа должна выполнить поиск на всю глубину.
Этот подход основан на двух предположениях. Во-первых, он предполагает, что недостаток потери хода больше, чем недостаток выполнения более мелкого поиска. При условии, что более мелкий поиск не намного мельче (в практической реализации поиск с нулевым ходом обычно на 2 или 3 слоя мельче, чем был бы полный поиск), это обычно верно. Во-вторых, предполагается, что поиск с нулевым ходом будет производить обрезку достаточно часто, чтобы оправдать время, потраченное на выполнение поиска с нулевым ходом вместо полного поиска. На практике это тоже обычно верно.
Проблемы с эвристикой нулевого хода [ править ]
Есть класс шахматных позиций, в которых использование эвристики нулевого хода может привести к серьезным тактическим ошибкам. В этих позициях цугцванг (по-немецки «вынужден двигаться») игрок, чья очередь двигаться, имеет только плохие ходы в качестве своего законного выбора, и поэтому ему было бы лучше, если бы ему позволили утратить право на ход. В этих позициях эвристика нулевого хода может привести к отсечке, когда полный поиск не нашел бы ее, заставляя программу предполагать, что позиция очень хороша для стороны, хотя на самом деле она может быть очень плохой для них.
Чтобы избежать использования эвристики нулевого хода в позициях цугцванга, большинство шахматных программ, использующих эвристику нулевого хода, накладывают ограничения на ее использование. Такие ограничения часто включают неиспользование эвристики нулевого хода, если
- сторона для движения находится под контролем
- у стороны, которую нужно сделать, остались только король и пешки
- на стороне, которую нужно переместить, осталось небольшое количество фигур
- предыдущий ход поиска также был нулевым.
Подтвержденная обрезка с нулевым ходом [ править ]
Другой эвристический для борьбы с цугцванг проблемы Омид Давид и Nathan Нетаньяху «s подтвержденному нуль-ход обрезку . [1] В проверенном отсечении с нулевым перемещением всякий раз, когда неглубокий поиск с нулевым перемещением указывает на высокий сбой, вместо отсечения поиска от текущего узла поиск продолжается с уменьшенной глубиной.
Ссылки [ править ]
- ↑ Давид-Табиби, Омид; Нетаньяху, Натан С. (сентябрь 2002 г.). «Подтвержденная обрезка с нулевым ходом». Журнал ICGA . 25 (3): 153–161. arXiv : 0808.1125 . Bibcode : 2008arXiv0808.1125D . DOI : 10.3233 / МКГ-2002-25305 . Кириллович 1041 .
- Goetsch, G .; Кэмпбелл, MS (1990). «Эксперименты с эвристикой нулевого хода». В Марсленде Т. Энтони; Шеффер, Джонатан (ред.). Компьютеры, шахматы и познание . Springer-Verlag. С. 159–168. ISBN 3-540-97415-6.
