Рассказ о программировании борьбы за материал был бы неполным без упоминания о работах М.М.Ботвинника, который внес серьёзный вклад в теорию и практику шахматного программирования (Ботвинник М. М. Алгоритм игры в шахматы. М.: Наука, 1968; Ботвинник М. М. Блок-схема алгоритма игры в шахматы. М.: 1972. Пепринт; Ботвинник М. М. О кибернетической цели игры. М.: Советское Радио, 1975; Ботвинник М. М. О решении неточных переборных задач. Советское радио, 1979.).

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

Вопросам борьбы за материал М.М.Ботвинник придаёт важнейшее значение, и его подход к этим вопросам сильно отличается от подхода других авторов. Многие исходили из представления, что существует «истинное» соотношение материала в позиции, нередко «скрытое». т.е. не равное результату сравнения материальных весов фигур противников, стоящих на доске. Другие разрабатывали методы определения целей ходов в борьбе за материал и отбора целей и ходов. Третьи рекомендовали идти от представлений, бытующих среди широких кругов шахматистов. М.М.Ботвинник исходит из своего представления о собственной игре, а оно своеобразно, как, наверное, представления всех корифеев, оставивших глубокий след в своей области.

Прежде чем перейти к более систематическому изложению основ метода Ботвинника, рассмотрим несколько шахматных примеров.

На диаграмме 51 белые угрожают выиграть пешку а7 при помощи манёвра Лe1—a1:a7. Хотя сначала нужно освободить первую горизонталь ходом
1. Сb1 — c2,
чёрные не успевают защитить пешку. Им необходимы минимум три хода (Kpg8—g7 и Лh5—h8—а8 или уход пешек d7 и f7 с седьмой горизонтали и Лh7). Чёрные могут долго оттягивать нежелательный финал, например
1. ... d5
2. cd
(пешка c4 недостаточно защищена, а на
2. СbЗ
следует
2. ... Лh2
и белый король не может одновременно защищать обе пешки d3 и g2)
2. ... ed
3. Ла1 Лh2
4. Kpf2,
но избежать хода Л:a7 им не удастся.

Чтобы увидеть выигрыш пешки в модели абсолютной схемы, глубина перебора должна быть не меньше восьми полуходов, а в модели тихой игры нужно не менее шести тихих ходов па ветке. В модели активной игры выигрыш вообще может оказаться незамеченным, так как ход
1. Сc2
неактивный. Программа, отбирающая ходы, цели в борьбе за материал, также может пройти мимо этого хода. Правда, он деблокирует линию e1—a1 ладьи a1, но не видно, какие выгоды может это принести пока ладья не станет на a1, не будет известно, что с этого поля она нападает на незащищенную пешку a7.

Изменим немного этот пример, сняв белую пешку еЗ и чёрную g6. Тогда у чёрных появляется манёвр Кe5—g6—f4:g2 (так как с поля f4 конь даёт шах, чёрные выигрывают темп). Правда, прямолинейная попытка
1. ... Kg6
2. Лa1 Kf4+
3. Kpf2 Лh2
4. Kpg3 Л:g2
5.Kp:f4 Л:c2
6. Л:а7
не проходит, так как под ударом оказывается пешка d7 и белые успевают выиграть либо её, либо пешку b6, но чёрные могут играть
2. ... d5
3. cd Л:d5!
и, нападая на пешку Ь5, чёрные выигрывают темп для защиты
4. ... Лd7.
Если же белые берут пешку ходом
3. Л:а7,
то
3. ... dc
4. dc Kf4+
5. Kpf2 Лh2.
6. Kpg3 Л:g2+
7. Kp:f4 Л:с2.
Белым надо либо защищать пешку с4, либо обменять её на пешку b6, т. е. пешки они не выигрывают. Разумеется, этими вариантами не исчерпаны возможности игры как белых, так и чёрных.

В позиции, изображенной на диаграмме 52, белые атакуют коня f6 манёвром Ch6—g5:f6. Чёрные успевают защититься:
1. Cg5 Kpg7
2. Лf3 Kd7 (e4),
но теперь белые могут изменить цель:
3. C:f6+ K:f6
4. ЛbЗ
и на
4. ... Лb8
ответить
5. С:а6.
Этот выигрыш будет найден в моделях активной игры и отбора ходов, имеющих цели в борьбе за материал, так как он основан на двухходовых манёврах: Ch6—g5:f6, ЛеЗ—f3:f6 и bЗ:b7, точнеё их угроз. Вторые ходы таких манёвров выигрывают в модели форсированной игры размена на соответствующем поле. Следовательно, первые ходы являются активными и агрессивными.

По утверждению М.М.Ботвинника — шахматиста, 15 лет бывшего чемпионом мира, в основе любой планируемой операции на шахматной доске находится многоходовое передвижение фигуры с целью уничтожить некоторую фигуру противника (в приведенных выше примерах это были движения Ле1—a1:a7, Лh5—h2:g2, Ke5—g6—f4:g2, Ch6—g5:f6, ЛеЗ—f3:f6 и т.д.). Если даже противнику удаётся защититься, то в процессе борьбы за поставленную материальную цель можно добиться общего улучшения позиции и возможности сменить цель.

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

Алгоритм Ботвинника основан на планировании такой борьбы, которую он рассматривает как функционирование многоуровневой системы управления. ( Обнаружив глубокие аналогии в системах управления разнообразными сложными процессами, М.М.Ботвинник указал на возможность использовать идеи шахматных программ для автоматизации управления. Под его руководством, в частности, была создана программа планирования ремонта электротехнических объектов. ) Каждый уровень имеет свои локальные цели. Цели нижнего уровня — это движения комлевых фигур по траекториям. Более высокий уровень рассматривает какую-либо из этих целей и ставит нижним уровням новые цели — помогать её достижению или мешать достижению цели противника. Он формирует из выбранной цели и вспомогательных целей обоих противников так называемую зону игры. Следующий уровень следит за взаимодействием зон и объединяет взаимодействующие зоны в одну. Наконец, высший уровень руководит перебором, в который допускаются только плановые ходы, и осуществляет выбор хода из исходной предъявленной машине позиции (или позиции, случившейся в партии).

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

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

Если все кратчайшие траектории пришлось удлинить, то следует посмотреть, не могут ли конкурировать с ними более длинные, на которых меньше препятствий. Эти траектории машина уже не может запоминать заранее: их слишком много. Траектории длины 3 и 4 М.М.Ботвинник предлагает строить из двух фрагментов длины 2 (или 1), отобрав двухходовые траектории нападающей фигуры и одно-двухходовые траектории с концов этих траекторий на поля, где стоят фигуры противника (он ограничивается четырёхходовыми траекториями без препятствий и трёхходовыми не больше, чем с одним препятствием) .

На диаграмме 53 изображена позиция, в которой естественным намерением белых является уничтожение чёрной пешки а5. Однако кратчайшие траектории Лd2—а2:а5 и Лd2—d5:a5 исключены: поле а2 находится под ударом чёрного коня b4, которого нельзя ни уничтожить, ни прогнать, а линия d5—а5 непроходима из-за блокированной белой пешки d5 и защищенной чёрной пешки с5. Четырёхходовых траекторий без препятствий нет, но есть трёхходовая с одним препятствием: Лd2—d1—a1:a5. Чёрные не могут двинуться конем, а королю или ладье для защиты необходимы четыре! хода (Kpf8—е8—d8—с7—Ь6, Лg5—g6—f6—f7—а7 и другие траектории). Следовательно, белые могут выполнить свой план (обычно в таких позициях у противника есть контрнападения, но в данной позиции их нет).

Пусть траектория нападения выбрана. Тогда нужно рассмотреть варианты, в которых фигуры противника будут препятствовать движению по ней, а свои фигуры — поддерживать движение. М.М.Ботвинник предлагает определить заранее, какие фигуры будут участвовать в такой игре. Это называется формированием зоны игры. Фигуры противника могут защищать объект нападения, брать под контроль поля траектории, блокировать её линии. Объект нападения может попытаться уйти. Если же он прикован к месту из-за связки или необходимости защищать какую-либо фигуру или поле, можно попытаться устранить причину неподвижности.

Однако не всякие меры противодействия следует включать в зону игры. Бессмысленно, например, взять под контроль поле траектории после того, как движущаяся по ней фигура его пройдет. Ещё не двигая фигур, следует произвести учёт времени и отобрать только своевременные меры. На диаграмме 54 белые могут в два хода уничтожить пешку b7 манёвром СbЗ—d5:b7, и, значит, в один ход на неё напасть. Чёрным необходимо два хода для защиты (если на
1. Cd5
ответить
1. ... Сс6,
то
2. С:с6 bc,
и пешка b6 проходит в ферзи), но, отвечая на
1. Cd5
ходом
1. ... СЬ5,
они нападением на коня е2 выигрывают темп для защиты
2. ... Са6.

В чём состоит поддержка движения фигуры по траектории? Если поле траектории занято другой своей фигурой или она блокирует линию траектории, то для поддержки она должна уйти (пример: ход
1. Сс2
из позиции, изображенной на диаграмме 51). Если какая-либо фигура противника противодействует движению по траектории (способами, указанными выше), то поддержкой является противодействие мешающей фигуре: нападение на её исходное положение или на те, которые она будет занимать в процессе движения к полю боя, и блокада соответствующей траектории. Противодействующие фигуры М.М.Ботвинник тоже включает в зону игры. На диаграмме 55 это — пешка еЗ. Она блокирует траекторию g6—с2 движения слона чёрных на защиту пешки bЗ ходом
1. еЗ—е4,
а затем ходом
2. Се2—d1
(траектория Се2—d1:b3) белые выигрывают эту пешку.

Работа программы, реализующей алгоритмы Ботвинника, начинается с построения траекторий нападения (точнее, пучков таких траекторий) с одинаковыми началом и концом. Затем формируются группы вилочных траекторий, т. е. начинающихся одними и теми же ходами. Движение по общей части вилочных траекторий даёт возможность выиграть темп (например, ответ
1. ... Сb5
на ход
1. Cd5
из позиции, изображенной на диаграмме 54). В некоторых случаях этот выигрыш темпа можно учесть заранее, не производя перебора. После этого выбирается ход, который будет исследоваться. Он является ходом вилочных траекторий (в крайнем случае, одной невилочной). С этого момента начинается соответствующий выбранному ходу фрагмент перебора и формирования зоны игры, которые производятся параллельно.

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

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

Итак, отправляясь от некоторой группы траекторий, производят перебор позиций дерева игры шахматной модели, формируемой при помощи псевдоперебора. Если в ней обнаружится материальный выигрыш, то программа ещё смотрит, не может ли противник за то же время скомпенсировать его в какой-либо из зон своего нападения. Если же выигрыш не достигнут, нужно определить причину этого: объект нападения может отступить, противник может успеть его защитить или остановить продвижение нападающей фигуры. Во всех случаях следует попытаться найти критическое поле, воздействие на которое усилит нападение, траектории нападения на него своих фигур (с учётом времени) и сформировать зону из новых траекторий, добавляемую к исходной. М.М.Ботвинник называет её связанной с рассматриваемой в данный момент зоной и объединяет обе зоны в одну — составную.

В позиции, изображенной на диаграмме 56, белые могут попробовать уничтожить королем коня h1 при помощи манёвра Kpe1—f1—g2:h1, но тот уходит на g3, а затем в свой лагерь. Значит, критическим является поле g3, траекторией нападения на него Cd2—f4—g3, а мешающей фигурой король чёрных (траектории Kpd7—е6—f5:f4 и Kpd7—е6—f5—g4:g3). Перебор в составной зоне показывает, что противник не успевает:
1. Cf4 Кре6
2. Kpf1 Kpf5,
кажется, чёрные успели, но
3. Сс7(b8) Kpg4
4. Kpg2
— и на g3 бьют две фигуры белых.

На диаграмме 57 белые грозят дать мат (траектория Фd2—h6—g7), но чёрные успевают защититься (траектория Фа6—с8—f8)
1. Фh6 Фс8+
2. Кр ~ Фf8.
Критическим является поле с8, а связанная зона порождается траекторией Cg2—h3:с8. Из-за потери темпа увеличивается и основная зона: чёрные могут попробовать уйти от мата
(1. .. .Kpf8)
или напасть на поле h6, лежащее на траектории белого ферзя
(1. ... Kph7).
В обоих случаях белые должны включить в зону новые траектории нападения: в первом случае Фh6—h8:c8
(1. Ch3 Kpf8
2. Фh6+ Kpe8
3. Фh8 × ),
вo втopoм Фd2—h6—h8 (например,
1. Ch3 Kph7
2. Фh2 g5
3. Cf5+ Kpg8
4. Фh7+ Kpf8
5. Фh8 × ).

На диаграмме 58 у белых есть траектория нападения Ch5—f3—e4:h7. Однако если они попробуют сразу играть
1. Cf3,
то чёрные ответят
1. ... Кс5,
чтобы уничтожить белого слона при его движении по траектории. Таким образом, поле с5 является критическим, поэтому нужно найти траекторию нападения на него (Kc1—b3:с5) и включить соответствующую связанную зону в основную. Поздняя попытка поддержать движение слона по траектории не проходит: после
1. Cf3 Кс5
приходится поддерживать движение коня, иначе его просто «съедят»,
2. Крс2 Се7
(белые потеряли темп) и чёрные успевают осуществить деблокаду траектории защиты Kc5—d7—f8:h7
3. КbЗ Kd7
4. Се4 Kf8
и пешка h7 защищена. Нужно сразу помешать ходу Кс5:е4 ходом
1. КbЗ,
после чего белые беспрепятственно проведут манёвр Ch5—f3—e4:h7.

Пусть есть несколько зон. Если в них действуют разные фигуры, то зоны независимы и их можно исследовать по отдельности. Достаточно лишь учесть сдвиг во времени, обычно состоящий из одного темпа. В примере на диаграмме 51 зоны нападения Лe1—a1:a7 и контрнападений Лh5—h2:g2 и d7—d5:c4 независимы. Поэтому нет необходимости рассматривать девятиполуходовые варианты типа
1. Сс2 Лh2
2. Kpf2 d5
3. cd ed
4. Ла1
и
5. Л:а7.
Действительно, игра в первой зоне даёт белым выигрыш пешки, а в обеих зонах контрнападения белые успевают защититься, даже уступив противнику темп. Следовательно, ход
1. Сс2
выигрывает пешку.

Если же разные зоны содержат траектории одной и той же фигуры, то их нужно объединить в одну составную зону. В примере, о котором мы сейчас говорили, снимем с доски чёрную пешку g6 и белую еЗ. Тогда возможен ход Kg6 и ладья h5 поставляет траектории во многие зоны. Одна зона порождена её траекторией контрнападения Лh5—h2:g2. Другая, порождённая траекторией контрнападения d7—d5:c4, содержит траекторию поддержки Лh5—d5. С ней связаны траектории контрнападения Лd5:b5 и защиты Лd5—d7:a7. Последняя должна быть включена в зону основного нападения.

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

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

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

Сказанным не исчерпывается вклад М.М.Ботвинника в теорию и практику шахматного программирования. Более полное их изложение содержится в указанных выше работах. Однако, по-видимому, многое ещё не опубликовано и нам неизвестно. Мы позволим себе сделать одно замечание. Часто траекторий нападения слишком много, причем их изучение по приведенным выше рецептам является напрасной тратой времени. Например, в партии Петросян—Бронштейн на турнире памяти Пауля Кереса (Таллин, 1979) встретилась позиция, изображенная на диаграмме 59. Перечислим только траектории нападения на пешку h7, имеющие на пустой доске длину не более трех ходов:
КсЗ—d5—f6:h7,
КсЗ—е4—f6:h7,
Cc4—d3:h7
Cc4—a2—b1:h7,
Cc4—b3—c2:h7,
Лс1—сЗ— h3:h7,
Лc1—c7:h7,
Лd1—dЗ—hЗ:h7,
Фd3:h7,
однако все они бессмысленны. Белые, не думая ни о какой попытке выиграть материал, сыграли из этой позиции 15. hЗ.

Даже в тех случаях, когда следует искать тактическое решение, многие траектории явно не имеют к нему никакого отношения. Таковы, например, приведенные ниже траектории белых из острой позиции, встретившейся в партии шахматных программ «Каисса»—«Франц» (диаграмма 60):
КсЗ—а2:b4,
Kc3—d1—e3:f5,
Kf3—d2:e4,
Kf3—h4:f5,
Кf3—g5:h7,
Cf4—d6:b4,
Cf4—d2:b4,
Лd1—d5:b5,
Лd1—d6:c6,
Лd1—d7:f7,
Лd1—d8:c8,
Лd1—d8:e8,
Лd1—b1:b4,
Ле1-еЗ—сЗ:с6,
Ле1—е2—d2—d8:c8,
Ле1—e2—d2—d8:e8,
Фb2:b5,
Фb2—d4:e4
и т.д. (другая позиция из той же партии изображена на диаграмме 38). М.М.Ботвинник надеется, что перебор в соответствующих зонах будет быстро кончаться из-за невозможности добиться успеха, но это ещё нужно доказать.

Чтобы сократить число рассматриваемых зон и тем самым время работы программы, можно производить предварительный отбор траекторий. Например, есть такие основания для отказа от траектории:

1) движущаяся по траектории нападения или защиты фигура не обеспечивает благоприятного исхода в модели 1 размена на поле цели;

2) объект нападения имеет достаточную подвижность;

3) противник контролирует поле траектории или блокирует его линию;

4) своя фигура стоит на поле или линии траектории и не может с неё уйти (чаще всего это — пешка, блокированная пешкой противника).

Иногда одного обстоятельства достаточно для исключения траектории, например: когда подвижный объект траектории успевает уйти с поля цели, двигаясь по своей траектории нападения, или поле на траектории контролируется хорошо защищенной пешкой противника. В других случаях игру в основной зоне следует временно отложить и заняться игрой во вспомогательной зоне, связанной с ликвидацией причины отказа. Если же оснований для отказа несколько, то почти всегда игра в соответствующей зоне обречена на неудачу, кроме случаев, когда обстановка может измениться в результате игры в других зонах. Но тогда появится возможность пересмотреть отказ в процессе перебора или на следующих ходах партии.