5. Составление программы для универсальной вычислительной машины для реализации стратегии типа А

Пусть имеется универсальная цифровая машина, изображенная схематично на рис. 3 и обладающая свойствами.

Рис. 3.

1) Имеется большая внутренняя память для хранения чисел. Она разделена на некоторое число ячеек, каждая из которых способна содержать, скажем, десятиразрядное число. Каждой ячейке присвоен адрес в памяти.

2) Машина имеет арифметическое устройство, которое может выполнять элементарные операции сложения, умножения и т. д.

3) Вычислительная машина работает, повинуясь программе. Программа состоит из последовательности элементарных команд. Обычная команда имеет вид:

Это означает: выбрать содержимое ячеек 372 и 451, сложить эти числа и записать их сумму в ячейку 133.

Другой тип команд содержит в себе выбор, например,

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

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

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

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

Ясно, что при таком разнообразии стратегических задач на различных стадиях игры должны быть использованы различные программы. Будем в основном касаться середины игры и совсем не будем рассматривать окончания. Не видно, однако, причин, по которым не могла бы быть построена и достаточно хорошо запрограммирована стратегия окончания игры.

Поле на шахматной доске может быть занято тринадцатью различными способами: либо оно пусто (0), либо на нем стоит одна из шести возможных белых фигур

либо одна из шести черных фигур Таким образом, состояние поля можно охарактеризовать приписыванием ему целого числа поля можно пронумеровать так, как показано на рис. 4. Положение всех фигур тогда задается в виде последовательности 64 чисел, каждое из которых находится между —6 и Для такого представления достаточно всего 256 двоичных разрядов.

Рис. 4.

Обозначения фигур

Хотя это кодирование не является оптимальным, оно достаточно удобно для вычислений. Еще одно число X будет иметь значение или —1 в зависимости оттого, принадлежит ход белым или черным соответственно. Затем необходимо добавить данные, относящиеся к возможности рокировки (двигались ли белые или черные короли и ладьи), а также к взятиям на проходе (т. е. описание последнего

кода). Однако здесь эта информация опущена. Во введенных обозначениях начальная шахматная позиция имеет вид

Любой ход (кроме рокировки и превращения пешки) можно описать указанием того, с какого поля и на какое переставляется фигура. Всего на доске 64 поля, следовательно, достаточно 6 двоичных разрядов для указания одного поля и всего 12 двоичных разрядов нужно для описания хода. Таким образом, первый ход записывается в виде 1,4; 3,4. Чтобы закодировать превращение пешки, необходимо добавить 3 двоичных разряда для указания фигуры, в которую она превращается. Рокировку можно определить по движению короля (это единственный случай, когда король может двинуться сразу на два шага). Всякий ход, следовательно, можно задать выражением , где обозначают поля, а с указывает фигуру в случае превращения пешки.

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

— выполняет ход в позиции Р, определяя новую позицию.

— составляет список возможных ходов пешек с поля в позиции Р.

— составляют аналогичные списки для других фигур: коней, слонов, ладей, ферзей и короля.

— составляет список всех возможных ходов в данной позиции.

— вычисляет оценочную функцию для данной позиции Р.

— управляющая программа; выполняет вычисления, связанные с выбором максимумов и минимумов для определения искомого хода.

Имея данную позицию Р и ход во внутренней памяти, машина может найти следующую позицию, выполняя программу

1) В памяти машины отыскивается поле а позиции Р.

2) Число х в этом квадрате заменяется на 0 (пустой квадрат).

3) а) Если и первая координата а равна 6 (белая пешка достигает поля превращения) или если и первая координата а равна 1 (черная пешка достигает поля превращения), то в поле записывается число с (заменяя то число, которое было там записано).

б) Если (короткая рокировка белых), то в поля записывается 0, а в поля 06 и 05 - числа 6 и 4 соответственно. Аналогично делается в случае (длинная рокировка белых) и (короткая или длинная рокировка черных).

в) Во всех остальных случаях в поле записывается х.

4) Изменяется знак К.

Для фигуры каждого типа имеется программа, определяющая ее возможные ходы. Типичным примером является программа для определения возможных ходов слона, которую кратко можно описать так. Пусть координаты поля, на котором стоит слон.

1) Вычислим и посмотрим содержимое «этого поля в позиции Р.

2) Если (пустое поле), внесем в список ход и вернемся в начало, поставив вместо Если — положительно (наша фигура в поле), перейдем к 3). Если — отрицательно (в поле фигура противника), внесем в список ход и перейдем к 3). Если поля не существует, перейдем к 3).

3) Вычислим и проведем аналогичные рассмотрения.

4) Аналогично с

5) Аналогично с

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

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

1) Обращаемся к полю (1,1) и определяем его содержимое х.

2) Если положительно, обращаемся к соответствующей программе и по окончании ее работы возвращаемся к 1), прибавив 1 к номеру поля. Если есть нуль или отрицательно, возвращаемся к 1), прибавив 1 к номеру поля.

3) Проверяем, допустим ли каждый из выписанных ходов, и выбрасываем недопустимые ходы. Это делается путем выполнения каждого хода в позиции Р (по программе и проверкой, находится ли король под шахом или нет.

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

такой стратегии очень низок. Автор сыграл несколько игр против такой случайной стратегии и обычно делал противнику мат в четыре-пять ходов. Следующая партия иллюстрирует полную бесцельность игры по такой стратегии:

Теперь вернемся к стратегии, основанной на оценочной функции Программа производит оценку позиции согласно значению Очевидно, это можно сделать, просматривая поля и суммируя указанные в оценочной функции члены. Нетрудно учесть такие факторы, как сдвоенные пешки и т. д.

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

1) Составляет список допустимых ходов (используя в данной позиции.

2) Делает первый ход в списке по программе получая позицию

3) Составляет список ходов черных в позиции

4) Делает первый ход за черных, получает позицию и оценивает ее по

5) Делает второй ход за черных и оценивает полученную позицию.

6) Сравнивает оценки и выбрасывает ход с меньшей оценкой (т. е. остается лучшая оценка за черных).

7) Выполняет для третьего хода сравнение с оставшейся величиной и т. д.

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

9) Конечные оценки этих двух вычислений сравниваются, и оставляется тот из ходов белых (вместе с соответствующей оценкой), у которого оценочная функция больше.

10) Этот процесс повторяется для всех ходов белых и выбирается лучший (он остается после перебора всех возможных ходов белых). Это и есть тот ход, который надо сделать.

Эти программы в высокой степени цикличны, следовательно, если они хорошо составлены, не должны занимать много места в памяти машины.

Можно оценить объем памяти для записи позиций и промежуточных результатов, когда просматриваются все варианты на три хода вперед (с каждой стороны). Вероятно, должны запоминаться три позиции: начальная позиция, последняя позиция (которая теперь оценивается) и предшествующая ей. Это потребует около 800 двоичных разрядов. Кроме того, нужно помнить пять списков ходов, каждый из которых требует около двоичных разрядов, а все они потребуют 1800 двоичных разрядов. Наконец, чтобы сделать выбор и оценку в необходимых вычислениях, требуется около 200 двоичных разрядов. Значит, всего потребуется порядка 3000 двоичных разрядов.