Пионер — электронный шахматный мастер (разработка Ботвинника)

Как все начиналось

Все началось с лекции в Берлине в Университете им. Гумбольдта, прочитанной в ноябре 1960. В январе 1961 в сокращенном виде она была опубликована в «Комсомольской правде» под названием — «Люди и машины за шахматной доской» (в полном объеме — месяц спустя в журнале «Шахматы в СССР»).

Привожу наиболее существенные моменты этой лекции:

«… рассмотрим процесс мышления шахматиста. Каждый знает, что никогда шахматист не рассчитывает все возможные варианты, не смотрит все ходы, возможные на доске… Шахматист во время партии в данной позиции, которую он обдумывает, рассматривает примерно 2-4 хода; определяет онэти ходы интуитивно, на основании опыта и т.п. Если учесть, что в среднем партия длится ходов сорок, то примерно за партию шахматист должен проанализировать не более 100 первых ходов… Разумеется, шахматист в процессе расчета в общей сложности рассматривает не 100 ходов во время партии, а анализирует несравненно больше. Если в среднем вариант рассматривается хода на 2-3, то и тогда цифра анализируемых ходов получается достаточно внушительная .

Следует учесть, что шахматист во время расчетов не видит всей доски с 64 полями. Это существенно облегчает анализ во время партии. Одновременно шахматист имеет в поле зрения , скажем, полей 8-16, то есть задача анализа облегчается в несколько раз. Надо отметить также , что на некоторые фигуры шахматист не обращает внимания. Из общего числа в расчете принимают участие 3-6 фигур. Новое облегчение задачи. Таким образом, во время партии шахматист анализирует передвижения ограниченного количества фигур на ограниченном участке доски, анализирует передвижения лишь тех фигур, которые непосредственно участвуют в столкновениях, и лишь на тех полях, где эти столкновения возможны. Иначе говоря, он рассматривает лишь те фигуры, что непосредственно взаимодействуют с неприятельскими, и лишь те поля, где это взаимодействие возможно. Но как проверить, правильно ли выбраны эти фигуры и эти поля? Для этого, пожалуй, есть один способ. Назовем этот метод условно «методом последовательных приближений». Мастер выбирает ход, анализирует его; если в процессе анализа включаются в игру новые фигуры и поля , то собранная информация используется при повторном рассмотрении и т.д. Анализ, повторенный несколько раз, позволят в достаточной (или, увы, недостаточной) точностью определить эти взаимодействующие фигуры и поля — тогда уже расчет производится начисто».

Самое главное, что содержалось лекции:

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

На формализацию и реализацию этих простых идей ушли годы. Шагнуть от мастера к машине оказалось делом сложным: надо было найти путь к формированию небольшого дерева перебора.

Цель неточной игры

На нахождение цели неточной игры ушло три с половиной года. Мат — цель точной игры; цель достигнута — игра закончена. А как же в анализе усеченного дерева? Там цель точной игры(мат) бесполезна, как правило, варианты в усеченном дереве не могут быть завершены из-за мата. Во всех играющих программах (кроме «Пионера») цели неточной игры нет. Это приводит к тому, что усеченное дерево, содержит в основном , мусор, так как варианты обрываются не по смыслу, а по достижении предельной длины. Итак, при формировании усеченного дерева должна действовать цель неточной игры.

В шахматах цель неточной игры — выигрыш материала. По типу это будет та же цель, что и точная (мат). В 1964 году я нашел, что в шахматах все начинается с нападения на фигуры противника, с выигрыша материала. Но ведь траекторий, по которым можно напасть на фигуры противника превеликое множество! Как ограничить информацию об этом ?

Шахматный горизонт

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

Оценочная функция

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

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

Когда есть в программе лишь оценочная функция, оборвать и отсечь варианты логически, определить логическое направление движения фигур нет возможности. Тогда и продолжаются все варианты до предельной длины… Некоторые специалисты утверждают, что цель игры состоит в максимизации оценочной функции — это камуфляж отсутствия цели. Максимизация оценочной функции всего лишь элемент минимаксной процедуры, и не более! Без цели игры небольшое , «человеческое» дерево перебора не сформировать.

Многоступенчатость

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

Низшие ступени (1) соединяются в средние (2), а затем — в единую высшую (3). Это весьма выгодное дело по сравнению с единой, одноступенчатой — системой — с точки зрения поиска решения. Единую систему и нужно анализировать. А когда система многоступенчатая, можно лавировать. Шахматная доска заменяется ее математическим отображением (МО), моделью, которая и подлежит анализу. В это МО мы уже можем включать не все первые ступени и не все вторые ступени, а лишь те ступени, что могут повлиять на выбор хода(принятие решения). Это приводит к дополнительному сокращению дерева перебора.

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

Чтобы понять суть дела, достаточно ознакомиться с зоной нападения. В зону входит атакующая фигура (+) с траекторией нападения(эта траектория названа комлевой), атакованная фигура(-) — они входят в первую ступень, а также две «команды» отрицающих фигур разного цвета, действующих по траекториям отрицания. Фигуры (+) поддерживают действия комлевой (атакующей) фигуры, фигуры (-)- препятствуют действиям фигур (+). Отрицающие фигуры (+) находятся на расстоянии всего в одно передвижение от конечных полей своих траекторий. Они находятся в засаде и не имеют права двигаться вперед , так как принято, что лишь одна фигура(комлевая) стороны (+) перемещается по комлевой траектории по направлению к своей цели(мишени). Пока же движется комлевая фигура (+), могут перемещаться отрицающие фигуры(-) , но чем ближе комлевая фигура к своей цели, тем меньше времени остается для фигур (-) , чтобы поспеть к конечным полям своих траекторий. Это приводит к тому, что «горизонт» для отрицающих фигур (-), который определяют фигуры(-), участвующие в зоне (в отличие от предельного «горизонта» для комлевой фигуры), является величиной переменной. Наивысшее значение этого переменного горизонта Нх связано со значением предельного горизонта, которому был присвоен индекс НL.

Таким образом, вторая ступень- зона игры — оказалась строго детерминированной, что и позволило впоследствии представить образование зоны в виде программы для ЭВМ. Третья, высшая ступень — МО была введена в алгоритм тогда же, но формализована была значительно позже — через 9 лет, да и то после того, как уже более 5 лет продолжалась работа над программой. По этим датам можно судить о том, какая ступень трехступенчатой шахматной модели игры оказалась сложнее: на первую ушло 3,5 года, на вторую — 5 лет, а на МО — около 9.

Триединый принцип

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

Начало работы

В январе 1972 года началась непосредственно работа над написанием программы. Два программиста — Борис Штильман и Александр Юдин начали с написания подпрограммы поиска хода в оригинальной позиции и создания библиотеки дебютов. Через несколько месяцев программа уже находила траектории передвижение фигур. Началась работа по созданию библиотеки эндшпиля. После устранения текущих ошибок была создана подпрограмма получения зоны игры.

Продолжение следует…

Автор: Михаил Моисеевич Ботвинник