Приложение 2. Библиотека дебютов и алгоритм ее использования

А. Д. Юдин

Нет необходимости доказывать пользу применения подпрограммы - библиотеки дебютов для шахматной программы. Четыре чемпионата среди шахматных программ, проведенных в США в 1971-1974 гг., показали, что такие библиотеки имеются у большинства существующих программ. Это, главным образом, экономит время при разыгрывании начальной стадии партии, а также помогает избежать просмотры ("зевки") хотя бы в дебюте, вне зависимости от силы игры программы.

Но еще большие преимущества дает использование дебютной библиотеки при создании шахматной программы по рассматриваемому алгоритму. В результате нескольких дебютных ходов, разыгранных с помощью справочника, фигуры сближаются и начинают лучше "видеть" друг друга и большее количество нападений оказывается в пределах заданного горизонта. В данном случае цель "обучения" программы дебютам соответствует той, о которой писал X. Р. Капабланка^*:

^* (Капабланка X. Р. Учебник шахматной игры. Л-М, ОГИЗ, 1935.)

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

Рассмотрим основные вопросы, связанные с дебютной библиотекой и подпрограммой ее использования для данной шахматной программы.

Библиотека дебютов состоит из пяти деревьев, соответствующих пяти начальным ходам белых: е2 - е4, d2 - d4, c2 - с4, g2 - g3 и Kg1 - f3. Все дальнейшее описание будет относиться к одному дереву, так как начальный ход белых однозначно определяет "рабочее" дерево.

Установлена фиксированная длина вариантов - 6 ходов (или 12 полуходов). Таким образом, после 6-го хода программы происходит безусловная передача управления программы основного алгоритма (если, конечно, эта передача управления не была реализована ранее, что происходит, когда очередной ответ противника не найден в библиотеке).

Далее все варианты были оценены. Рассмотрим возможные оценки (в соответствии с терминологией, принятой "Шахматным информатором"):

0 - игра равна;

+1 - белые стоят лучше;

-1 - черные стоят лучше;

+2 - белые имеют решающее преимущество;

-2 - черные имеют решающее преимущество.

В соответствии с принятыми оценками была проделана процедура минимакса. Таким образом, каждый ход данного дерева получил оценку.

Кодирование хода происходит следующим образом. Каждый ход записан в виде ±rmn, где ±r - оценка; m и n - координаты начального и конечного полей положения фигуры при данном ходе, которые могут принимать значения от 1 до 64 (рис. 16). Так, например, ход Кс3 - е4, ведущий к решающему преимуществу белых, будет записан в виде: +21929.

Рис. 16. Кодирование полей доски

Рокировки и взятия на проходе имеют специальные коды.

При записи полей доски в виде массива из 64 элементов ходы-взятия будут записаны как обычные ходы, например ход Кс3: е4 с оценкой 4-2 будет записан в виде +21929.

Дерево вариантов записано в виде трех массивов, условно названных LIB, SON и BRAT, имеющих одинаковую длину. Элементы массива LIB - закодированные ходы с оценками. Элементы массивов SON и BRAT - обычные номера (индексы) соответствующих ходов массива LIB или нули.

Рис. 17. Дерево вариантов

Рассмотрим пример записи дерева вариантов (рис. 17) в виде трех массивов (рис. 18). Для удобства чтения в массиве LIB записаны незакодированные ходы.

Рис. 18. Запись дерева вариантов в виде трех массивов

На рис. 19 приведена блок-схема алгоритма пользования библиотекой дебютов. Поясним кратко ее работу.

Рис. 19. Блок-схема алгоритма использования библиотеки

START передает управление процедуре А, которая выясняет цвет сторон. Если программа играет белыми, то процедура С при помощи (не показано) процедуры J выбирает начальный ход (из набора возможных начальных ходов белых). Далее управление передается (из процедур В или С) процедуре D, за исключением того случая, когда противником, играющим белыми, сделан ход не из набора е2 - е4, d2 - d4, c2 - c4, g2 - g3, Kg1 - f3, и управление передается программе основного алгоритма.

В процедуре D происходит вызов в оперативную память машины библиотечных массивов, соответствующих выбранному дереву, и их подготовка к работе.

Процедуры Е и F находят в библиотеке возможные ответы на последний сделанный (любой стороной) ход и передают управление проверке G.

При отрицательном результате проверки Е происходит выход на основной алгоритм.

Если проверкой G установлено, что очередь хода за машиной, то с помощью проверки I и, если это необходимо, псевдослучайного выбора J происходит определение и выдача хода (процедура L).

При очереди хода за противником процедура Н ищет номер этого хода в массиве LIB в наборе индексов, определенном процедурой F.

Если ход, сделанный противником, найден в библиотеке, что устанавливается проверкой K, то управление передается проверке М, в противном случае - мы вне библиотеки дебютов и управление передается программе основного алгоритма.

Наконец, проверка М устанавливает, достигнуто ли окончание дебюта. Если да, управление передается программе основного алгоритма, если нет, снова работает проверка E и т. д.

Рассмотрим работу процедуры F. Допустим, что последним был сделан ход LIB(I), где I - номер этого хода в соответствующем массиве LIB. Необходимо найти возможные (на уровне данной библиотеки) ответы. Они располагаются в массив HOD. Параллельно формируется массив J - номеров, соответствующих ходам массива HOD в массиве LIB. Эти номера определяются по формулам

Сначала находится SON(I), а затем его "братья" в массиве BRAT. Процесс заканчивается, когда "брат" очередного элемента массива HOD отсутствует (т. е. равен нулю). Искомые ответы находятся по формуле

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

В настоящее время библиотека дебютов содержит 850 вариантов; объем библиотеки 20 килобайт (при размещении в оперативной памяти машины). Время поиска, выбора и выдачи хода на печать составляет 0,1-0,2 с. Все подпрограммы написаны на языке Фортран IV для машины ICL4-70.

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