Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В компьютерных шахматных программах, эвристика нулевого хода — это эвристический прием, используемый для увеличения скорости алгоритма альфа-бета отсечения.
In computer chess programs, the null move heuristic is a heuristic technique used to enhance the speed of the alpha–beta pruning algorithm.
Обоснование
Альфа-бета-отсечение ускоряет алгоритм минимакса, определяя точки отсечения в дереве игры – позиции, в которых текущая позиция настолько выгодна для стороны, имеющей ход, что оптимальная игра противника позволила бы избежать её. Поскольку такие позиции не могли возникнуть в результате оптимальной игры, они и все ветви игрового дерева, исходящие из них, могут быть проигнорированы. Чем быстрее программа находит точки отсечения, тем быстрее выполняется поиск. Эвристика нулевого хода предназначена для определения точек отсечения с меньшими затратами, чем обычно, сохраняя при этом приемлемый уровень точности. Эвристика нулевого хода основана на том, что большинство разумных шахматных ходов улучшают позицию стороны, сделавшей этот ход. Таким образом, если игрок, которому сейчас ходить, может отказаться от хода (или сделать нулевой ход – недействительное действие в шахматах) и при этом сохранить достаточно сильную позицию для достижения точки отсечения, то текущая позиция почти наверняка приведет к отсечению, если бы текущий игрок действительно сделал ход.
Alpha–beta pruning speeds the minimax algorithm by identifying cutoffs, points in the game tree where the current position is so good for the side to move that best play by the other side would have avoided it. Since such positions could not have resulted from best play, they and all branches of the game tree stemming from them can be ignored. The faster the program produces cutoffs, the faster the search runs. The null move heuristic is designed to guess cutoffs with less effort than would otherwise be required, whilst retaining a reasonable level of accuracy. The null move heuristic is based on the fact that most reasonable chess moves improve the position for the side that played them. So, if the player whose turn it is to move can forfeit the right to move (or make a null move – an illegal action in chess) and still have a position strong enough to produce a cutoff, then the current position would almost certainly produce a cutoff if the current player actually moved.
Реализация
При использовании эвристики нулевого хода компьютерная программа сначала пропускает ход стороны, которой полагается ходить, а затем выполняет поиск альфа-бета по получившейся позиции на меньшую глубину, чем она бы выполнила для текущей позиции, если бы не использовала эвристику нулевого хода. Если этот неглубокий поиск приводит к отсечению, программа предполагает, что полноглубинный поиск без пропущенного хода также привел бы к отсечению. Поскольку неглубокий поиск быстрее, чем глубокий, отсечение находится быстрее, что ускоряет работу компьютерной шахматной программы. Если неглубокий поиск не приводит к отсечению, программа должна выполнить поиск на полной глубине. Этот подход основан на двух предположениях. Во-первых, предполагается, что потеря хода более невыгодна, чем выполнение поиска на меньшей глубине. При условии, что неглубокий поиск не слишком неглубок (в практической реализации поиск нулевого хода обычно проводится на 2 или 3 полухода мельче, чем полноглубинный поиск), это обычно справедливо. Во-вторых, предполагается, что поиск нулевого хода будет приводить к отсечению достаточно часто, чтобы оправдать время, затрачиваемое на выполнение поисков нулевого хода вместо полных поисков. На практике это также обычно верно.
In employing the null move heuristic, the computer program first forfeits the turn of the side whose turn it is to move, and then performs an alpha–beta search on the resulting position to a shallower depth than it would have searched the current position had it not used the null move heuristic. If this shallow search produces a cutoff, it assumes the full depth search in the absence of a forfeited turn would also have produced a cutoff. Because a shallow search is faster than deeper search, the cutoff is found faster, accelerating the computer chess program. If the shallow search fails to produce a cutoff, then the program must make the full depth search. This approach makes two assumptions. First, it assumes that the disadvantage of forfeiting one's turn is greater than the disadvantage of performing a shallower search. Provided the shallower search is not too much shallower (in practical implementation, the null move search is usually 2 or 3 plies shallower than the full search would have been), this is usually true. Second, it assumes that the null move search will produce a cutoff frequently enough to justify the time spent performing null move searches instead of full searches. In practice, this is also usually true.
Проверенная обрезка с нулевым перемещением
Еще одна эвристика для решения проблемы цугцванга — это проверенное отсечение нулевым ходом, разработанное Омидом Давидом и Натаном Нетаньяху. При проверенном отсечении нулевым ходом, если поверхностный поиск нулевым ходом указывает на неудачу с высоким приоритетом, вместо прекращения поиска из текущего узла, поиск продолжается с уменьшенной глубиной.
Another heuristic for dealing with the zugzwang problem is Omid David and Nathan Netanyahu's verified null move pruning. In verified null move pruning, whenever the shallow null move search indicates a fail high, instead of cutting off the search from the current node, the search is continued with reduced depth.