17
Составление программы шахматной игры для электронной вычислительной машины требует решения следующих проблем:
- создание способа записи и хранения в машине информации о позиции на доске и о хode;
- создание алгоритма, с помощью которого машина должна выбирать очередной ход;
- реализация этого алгоритма в виде программы при известном способе записи и хранения информации.
Запись позиции
Занumerем клетки шахматной доски двумя начными числами, первая цифра которых означает номер вертикали (в общей шахматнойотации он обозначает буквой), а второй — номер горизонтали (обе номера начиная с цифры 0). Так как горизонталей и вертикалей по восемь, то можно воспользоваться удобной для машины восеммерной системой числами, в которой применяются цифры 0, 1, 2, …, 7*). Таким образом, после а1 будет иметь номер 00, после а8 — номер 07, после d5 — номер 34, а после h8 — номер 77.
Занumerем также и шахматные цифры, присвоив пешке номер 1, коню — 2, слону — 3, ладье — 4, ферзю — 5 и королю — 6, причем белым цифрам — положительные номера, а черным — отрицательные. Каждый докси в позиции сопоставим число — номер стоящей на этом поле цифры или 0, если поле свободно.
В предложенной нумерации номером цифры является восеммерная цифра, для изображения которой достаточно трех двойных разрядов, и знак (цвет цифры), для записи которой нужно еще один разряд. По-
*) Читатель будет полезно вспомнить или прочитать статьи: P. C. Гутер, Вычислительные машины и системы числения, «Квант», 1971, № 9, Язык человека и языки машин, «Квант», 1971, № 10,
18
этому для записи позиции нужно отводить четыре разряда на каждое поле. Первый разряд отведем для записи знака (0 — «плюс», 1 — «минус»), а следующее три — для записи номера фигуры. В одной ячейке память помещится информация об одной горизонтали, при этом в ячейке памяты будет занято 32 разряда. Вся информация о позиции на доске займет 8 ячейек (по 1 на каждую горизонталь).
На рисунке 1 показана запись первого горизонтали начальной позиции. Читатель легко разберется в ней, вспоминив представление восемеричных цифр в виде тринадцат двойных:
(здесь индекса у числа ознакомится систему численения, в которой оно записано).
Запись хода
Ход можно представить в виде пары чисел: номера поля, на котором фигура была, и номера поля, на которой фигура пошла. Удобнее, однako, как это делается в шахматной позиции, сообщить оба поля, а также наименование и цвет (то есть номер и знак) ходившей фигуры. Тогда потребуется уже три числа, причем первоое из них будет однозначным (но со знаком), а два других — двузначными.
Так, запись
+1 41 43
означает ход белой (+) пешкой (1) с поля e2 (41) на поле e4 (43), то есть в общей шахматной позиции весь-
ma популярий ход e2 — e4, известный даже О. Бендеру. Запись
—5 37 64
соответствует ход черных, общно записьваемому как Фd8 — g5.
Выбор хода
Довольно просто «научить машину» делать ход, то есть проверить его возможность и ввести соответствующее изменение в записи позиции. Незмерimo сложнее научить ее быстрохотя и нескольких возможных в данной позиции один «наилучший». Для этого нужно умет сравнивать различные ходы.
Одним из способов может служить перебор вариантов. Но перебор «до конца», то есть до позиции, в которой известен результат, невозможен из-за необозримых размеров требуемого числа вариантов. Приходится ограничиться рассмотрением неокоторого определенного количества ходов. Но тогда нужно умет сравнивать позиции и ответать на вопрос, какая из них лучше. После этого мы можем считать, что лучшим ходом является тот, который ведет к лучшей позиции.
Нанболее простой оценкой может служить разница материалов ресурсов белых и черных. При этом каждая фигура оценвается определенным числом очков (баллов). Для оценки позиции достаточно подсчитать сумму баллов, соответствующих на доске белым и черным фигурам, и найти их разность. Конечно, такая оценка является слишком рубой: известно, что часто приходится жертвовать материалом ради
Горизонталь
Номера полей
Запись в ячейке
Рис. 1.
19
прибретения позиционных или тактических премишестств. Поэтому более тонкие оценки включают также и тактические факторы: возможность формирования выигрыша материала, наличие сдовеных пешек у себя или у противника, возможность рокировки, занятие ладьей или ферзем открытой линии и т.п.
Каким же образом воспользоваться умением оценить позицини с помощью той или иной выбранной оценочной функции? Ясно, что недостаточно оценивать позицини, получающей послед одного сделанного хода, а необходимо рассматривать все возможные позицини на несколько ходов вперед. Естественно, что чем больше «глубина перебора», то есть число ходов, после которых оценяется, тем лучше выбор хода. Однако необходимо считаться с тем, что увеличение глубины на 1 ход увеличивает время выбор хода приближительно в 40 раз.
Выбор хода осуществляется при помощи минимальной процедуры, которая мы проиллюстрируем на примере перебора на 1 ход. Пусть из позицини (ход наш) возможны ходы, приводащие к позициям … (рис. 2). Из полученных позиций возможны ходы противника, приводащие к позициям , …, оценки которых нам известны. Поскольку в позиции, скажем, , противник выберет скорее всего самый сильный возможный ход, то за оценку следует принять минимальную из оценок позицини . Так же определяются оценки остальных позицини , …, получающихся после различных наших ходов.
Зная оценки позицини , …, мы можем выбрать из них наиболее suitable. Ход, ведущий в позицию с этой максимальной оценкой, и будет лучшим при выбранной глубине перебора.
Аналогичная стратегия выбор хода применяется и при любой другой глубине перебора: из данной позиции делается заданное число ходов, и полученная позиция оценвается с помощью выбранной оценочной функции. Затем изменяется последний ход и оценвается новая полученная позиция. После того как проверены все возможные последние ходы, изменяется предпоследний и так далее, чтобы в конечном случае были оценены все позиции, которые могут получить из исходной последнего числа ходов. Полученные «на нижнем уровне» оценки переосстанавливаются «вверх», причем для позиций с ходом противника выбирается минимальная, а для позиций с нашим ходом — максимальная из оценок «ниже расположенных» позиций.
Таким образом, свой ход и ход противника следует рассматривать по-разному. В дальнейшем мы будем назвать их полуходами. Пример схемы выбор хода при переборе на
20
три получода приведен на рисунке 3. Здесь кружки ознакомют позиции, красные отрезки — свой ходы, сине — ходы противника.
Цифры в кружках ознакомют оценки позиций, полученные описанным выше путем (для «низких» позиций — с помощью оценочной функции, для «вышетorious» — по минимальной процедуре). Цифры возле отрезков показывают последовательность расстояния соответствующих ходов при переборе. Двойными линиями отмещены лучшие ходы из каждой позиции.
Отметим только, что для большей наглядности рисунка мы ограничились небольшим числом возможных ходов из каждой позиции. В результате перевести этот алгоритм на язык машинны, превращив его в программу игры. Это тяжелая работа, требующая программистского искусства, так как от качества программы осуществления алгоритмов в заменной степении зависит время работы программы, то есть время выбора хода. Мы не в состоянии, естественно, воспроизвести устройство такой программы сколько-нибудь подробно, опишем его лишь в самых общих чертах.
Существуют шесть подпрограмм — (по одной на каждой типи игры). Каждая из них составляет список ходов, возможных из данной позиции игрой данного типа. Подпрограмма координирует эти шесть подпрограмм и выписьвает все ходы, возможные в данной позиции.
Кроме перечисленных подпрограмм, имеется подпрограмма , которая выполняет оценкой ход, получая новую позицию, подпрограмма , вычисляющая оценку
полученной позиции, подпрограмма , реализующая минимальную процедуру, и, наконец, управляющая программа . Последняя решает, к какой из подпрограмм обратиться, назначает, какая позиция расматривается и какой ход из нее делается, и собственно реализует алгоритм выбора хода.
Подпрограммы — могут использовать вспомогательную информацию относительно позиции. Так, при построении возможных ходов удобно использовать «растр возможностей», который для каждой игры записывается следующим образом. Для каждой кедетки шахматной доски отводится один разряд; для всех доски достаточно занять две ячейки памяти, по 32 разряда в каждой. В разрядах, соответствующих полям, на которые можетойти данная игруга, ставится 1, остальные разряды содержат 0.
Например, для позиции, приведенной на рисунке 4, растр возможностей для ладьи Лс4 показан на рисунке 5. Нижняя ячейка соответствует здесь нижней полине доски (горизонтали 4—1 по шахматной терминологии).
Работу подпрограммы , строящей этот растр, можно представить себе так. В записи позиции подпрограмма выделяет tetradу (четыре двойных знака), соответствующую соседнему полю в той же горизонтали, и анализирует ее.
Если эта tetradа нульева, то поле свободно, ладья может на него пойти — в растреставится 1 в разряд, соответствующей данному полю. После этого проверяется, является ли данное поле крайним полем доски. Если не является, то рассматривается следующей
21
Дующее соседнее поле; если же поле было крайним, то подпрограмма переходит к расстотрению другого направления.
Если выделенная террада не является нулевой, то подпрограмма анализирует ее первую цифру, определяющую цвет занимающей это поле фигуры. Если эта цифра — 0 (знак +, фигура белая), то поле занято своей фигурой. Подпрограмма ставит в соответствующий разряд расстра 0 и переходит к расстотрению нового направления. При цифре 1 (знак —, фигура черная) подпрограмма также переходит к расстотрению нового направления, но в разряд, соответствующей данному полю, ставит 1: ладья может пойти на данное поле, побив стояшую здесь черную фигуру.
При расстотрении возможных ходов ладьи по горизонтали нужно выделять террады из одной и той же ячейки. Для вертикали нужно выделять террады, занимающие одно и то же положение в соседних ячейках, соответствующих различным горизонтальным.
На таких же принципах основана работа остальных подпрограмм. Так, подпрограмма , определяющая ходы слона, для выделения террады соседнего поля производит и сдвиг на 4 разряда, и переходит к соседней ячейке. Подпрограмма для ферзя строит все возможные ходы для ладьи с помощью подпрограммы и все возможные ходы для слона с помощью подпрограммы , а затем обединияет их.
Объчно работа программы «выбора хода» заканчивается тем, что она выбирает ход, который следует сделать в данной позиции, печатает его и оставливается. Ход можно печать в описанной выше форме, например:
а можно воспользоваться алфавитно-цифровым печатающим устройством и напечать тот же ход в привьюном для шахматства виде
К b1 — c3.
Тепер нетрудно организовать «полную игру». Для этого в дополнительке программы «выбора хода» нужна программа, связывающая ша-хматную программу «с внешним миром». Эта программа должна уметь в машину позицию, в которой требуется выбрать ход, условия выбора хода (например, глубину перебора), и обеспечивать контROL корректности введенной информации.
У этой программы есть «главаная докса», позиция на которой остается неизменной в процессе выбора хода, она изменяется лишь после того, как ход выбран и напечатаан.
Не нужно думать, что описанные нами способы решения основных проблем программирования шахматной игры являются единственными. Это совсем не так, возможно и другие. Расматривая каждую из этих проблем изолированно, можно найти способы упростить или улучшить те или иные детали решения одной из них, однокого перекоискается, что это отрицательно сказывается в других частях программы. Например, можно выбрать иной способ записи позиции, отличующаяся значительно большей компактностью, то есть экономящий объем машинной памяти. Но оценка позиции при таком способе записи может потребовать газдо большого числа действия. Доступнуть же улучшения «по всем параметрам» хотя и возможно, но весма затруднительно.
Сформирование три основные проблемы программирования шахматной игры относят не равноправны, и их решение весма по-разному влияет на качество программы. Если раньше способы решения первого
22
и третий проблем могли как-то влиять на время работы программы, то сейчас здесь резервов почти не осталось. Совсем иначе обстоит дело с алгоритмом выбора хода: его влияние на качество и силу является решающим.
В «Канссе-72» эта проблема решена так: перебираются все варианты до глубины 7 получдов, после этой глубины перебираются только так называемые «форсированные ходы» — взяття, шахи и ответы на них. Общая глубина перебора колблется от 7 до 30 получдов.
Читатель может заметить, что при полном переборе на 7 получдов (при среднем числе в 40 ходов из каждой позиции) придется рассматривать 40⁷ позиций, даже не считая форсированных ходов. Это слишком много. Однако авторы «Канссы-72» проведели огромную работу по выработке правил, позволяющих отрабасывать некоторые позиции или ходы, что позволило существению сократить перебор. Фактически при переборе на 7 получдов (вместе с форсированными вариантими) рассматривалось около 750 000 позиций, что занимало меньше часа работы машины.
В лучшей американской шахматной программе, созданной в Массачусетском техническом институте Гринблатом, в каждой позиции рассматривают 10 ходов, «лучших» по некоторой оценке, отличной от оценки позиции, возникшей после соответствующего хода, и произвольная перебор, глубина которого колблется от 6 до 16 получдов. Есть и другие способы решения этой проблемы.
Однако, несмотря на имеющиеся условия, пока все еще нет алгоритма выбора хода, позволяющего достаточно сильные ходы при естественной ограничении на время выбора. Для нахождения такого алгоритма необходимо принципиально новые идеи. Поиск этих идеей требует детального изучения «поведения» программы при выборе хода, причин, влияющих как на выбранный ход, так и на время выбора. Это можно проследить при большом числе экспериментов с шахматной программием.