Формирование зон и перебор. Псевдоперебор

Теперь, когда мы познакомились с понятием зоны игры, можно перейти к формированию зон и тем самым МО.

Все начинается с формирования нулевых зон нападения, когда МО создается заново. В пределах горизонта Н_L определяются все комлевые траектории нападения; это единственная операция при формировании зоны, не зависящая от перебора. Все дальнейшие операции, по предложению Б. Штильмана, идут параллельно с перебором: происходит одновременно и перебор, и формирование зон, и оценка вариантов. Такой метод работы программы наиболее экономичен, ибо, как только оценка определит окончание варианта, перебор, связанный с этим вариантом, а, следовательно, и формирование зоны, прекращаются. Это позволяет свести к минимуму объем как сформированной зоны игры, так и перебора.

Можно напомнить, что нулевая зона игры создается с траекториями фигур (-) в горизонте Н_L и с траекториями фигур ( + ) из одного передвижения; траектория отступления фигуры (-) с ак-поля состоит из одного передвижения. Как уже отмечалось, принцип, по которому определяется горизонт Н_х прост: принято, что сторона ( + ) в зоне имеет право двигать лишь свою комлевую α_k-фигуру (поэтому все остальные фигуры этой же стороны находятся от своих конечных полей на расстоянии не более одного передвижения, они уже готовы к бою), а сторона (-) включает в зону лишь те свои фигуры, которые могут поспеть к тому или иному полю, чтобы вовремя помешать продвижению какой-либо фигуры.

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

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

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

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

Знаменитый пешечный этюд Рихарда Рети (Белые: Kph8, Пс6. Черные: Краб, Пh5. Белые начинают и делают ничью) на заключительном этапе решения иллюстрирует этот принцип удлинения вилочных траекторий.

После 1. Kpg7 Kpb6 2. Kpf6 h4 мы имеем две вилочные траектории Kpf6-е5- d6 и Kpf6-е5-f4. Вилочная часть траектории Kpf6-е5 состоит из одного передвижения; число невилочных частей равно двум (условие n-1≤1, т. е. 2-1≤1 удовлетворяется). Путем 3. Кре5! король белых успевает принять участие в игре в той или иной зоне (либо на ферзевом фланге, либо на королевском) и ничья неизбежна.

Теперь вернемся к комлевой траектории зоны: задача заключается в том, чтобы проверить, проходимо ли α₁-поле для α₀-фигуры, каков результат борьбы, если (α₀-фигура ступит на α₁-поле?

Для того чтобы определить результаты борьбы на α₁-поле, мы должны заранее знать ту часть нулевой зоны, которая связана с α₁-полем, т. е. найти траектории отрицающих фигур ( + ) и (-), для которых α₁-поле (а также любое β-поле между α₀- и α₁-полями) является концевым α_л-полем. Для этого должен быть создан механизм псевдоперебора для поиска траекторий, суть которого состоит в том, что ходу фигуры в переборе дол-Жен предшествовать псевдоход, идентичный ходу этой фигуры, но являющийся фиктивным, предпринимаемым лишь для разведки.

Получение траекторий (кроме траекторий отступления и деблокады), по предложению Б. Штильмана, происходит по единому методу: когда в заданном горизонте на свободной от фигур доске одна фигура "видит" другую, то формируется траектория "нападения". Поэтому и совершается псевдоход α₀-фигурой на α₁-поле. Когда фигуры (-) в заданном горизонте видят α₀-фигуру ( + ) на α₀-поле, появляются отрицающие траектории фигур (-). Аналогично решается задача поиска отрицающих траекторий блокады β-полей на участке α₀-α₁: программа "передвигает" дальнобойную фигуру не прямо с α₁- на α₁-поле, а "ставит"- фигуру на каждое β-поле последовательно, определяя при этом все отрицающие траектории блокады.

Когда траектории отрицания фигур (-), траектории, у которых cti-поле является концевым α_л-полем, известны, можно сделать "настоящий" ход α₀-фигуры на α₁-noле. Фигура (-) бьет α₀-фигуру ( + ), но не сразу, сначала делается псевдоход фигурой (-) на α₁-поле, определяются траектории в одно передвижение фигур ( + ) и, если таковые находятся, они включаются в перебор и все начинается сначала. Так и действует этот механизм псевдо- и подлинного перебора: как только псевдоперебор обнаруживает новые траектории, перебор начинается сначала. Лишь тогда, когда оценка определяет обрыв варианта и псевдоперебор не дает новых траекторий, прекращается и перебор и формирование зоны: вариант перебора определен.