ЭВМ за шахматной доской

Квант 1981, №1 с. 11-17 Тег GPH8

А. Битман, Е. Гик

ЭВМ за шахматнойDOSКОЙ

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

Смысл современной автоматизации и состоит в передаче ЭВМ таких функций, как воспрятие обстановки, переработка больших объектов информации, способность сопоставлять и оценивать различные ситуации, делать логические выводы.

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

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

Научить машину играть в шахматы — дело не слишком трудное. Достаточно выбрать некоторые способ кодирования полей шахматной

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

Некоторые сведения из теории игры
Шахматы относятся к разряду конечных игра с полной информацией. В этом отношении они ничего не отличаются, скажем, от простейшей игры в крестики-ноликки на доске $3 \times 3$ . Для таких игра теоретически почти все известно, их структура абсолотно ясна. В каждой позиции существует лучший ход (возможно, не единственный). Последовательность лучших ходов за обе стороны приводит эту воображаемую партию к однозначному результату. В этом смысле говорят, что исход игры в любой позиции, в том числе и начальной, является предопределенным. Но если в крестиках-ноликах борба при наличии игры сторон завершает ничей, то в шахматах вопрос о том, как именно предопределенна начальная позиция, по-видимому, останется открытым.

Доказательство того, что исход игры в любой шахматной позиции предопределен, было впервые данно итальянским математиком Цермело в 1913 году. Мы приведем его здесь, поскольку оно необходимо для понимания дальнейшего.

Обозначим исходную (не обязательно начальную) шахматную позицию через $P_0$ (рис. 1), пусть в ней будет ход белых (позиция с ходом белых соответствует белые кружки, а позиция с ходом черных — черные). Произведем все возможные ходы белых из $P_0$ , из каждой полученной позиции — все возможные ходы черных и т. д. Графические эта процедура представляет собой так называемое дерево церры, начатой в $P_0$ (корень дерева).

Позиции, в которых уже нельзя сделать ход (то есть на доске стоит мат или пат), называем заключительный. Введем для них естественные оценки: $1$ — выигрыш белых, $1/2$ — ничья, $0$ — выигрыш черных. Если неоктора позиция вдоль ветки повторилась, то ее также будет считать заключительной и припшем ей оценку $1/2$ . Поскольку число шахматных позиций конечно, любая партия через конечное число ходов придет к заключительной позиции.

Пусть максимальная длина партии, начатой из $P_0$ , равна $N$ ходам (под ходом понятия ход только одной из сторон). Рассмотрим все партии длины $N$ за ход до конца. На рисунке 1 ниже точки соответствует заключительным позиция ( $N$ -й уровень). Покажем, что оценки можно по простым правилам перенести с $N$ -го уровня на $(N-1)$ -й. Пусть $A$ — позиция, из которой все ходы ведут в заключительные позиции. Поскольку их оценки нам известны, можно установить и оценку позиции $A$ . Если в ней ход белых (как на рисунке 1), то ее оценка равна максимальной из оценок за-

ключительных позиций, в которых можно попасть из $A$ . Если же в $A$ ход черных, то вместо максимальной оценки следует взять минимальную. В нашем случае из $A$ белые могут сделать 4 хода. Два из них ведут к ничей, два к выигрышу. Оценка позиции $A$ равна 1.

После описанной процедуры все позиции дерева игры ( $N-1$ )-го уровня будут оценены. Действительно, некоторые из этих позиций с самого начала были заключены и уже имели оценку, остальные получили ее по указанному правилу. Теперь можно удалить из дерева игры все позиции $N$ -го уровня и продолжать описную процедуру над новым, чуть подрезанным деревом. В результате оказется оцененными все позиции ( $N-2$ )-го уровня и т. д.

Таким образом, всякий раз позиции сходом белых приписывается максимальная из оценок позиций, в которых можно попасть из нее, а позиции сходом черных — минимальная. Такая процедура называется minimumкой или минимаксом. Применив минимакс в последний раз, то есть на $N$ -м шагу, мы найдем оценку исходной позиции $P_0$ , а заодно и лучший ход из нее. Этим доказательство заканчивается.

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

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

Общий подход к созданию шахматных программ

В 1950 году известный американский математик К. Шенон опубликовал статью, в котором дал общий подход к построению шахматных программы. Прежде всего он введил понятие оценочной функции, сопоставляющей каждой шахматной позиции определяющее число (оценку). Далее он предложил вести перебор вариантов до некоторой фиксированной глубины, а возникающие при этом концевые позиции оценить с помощью оценочной функции. Лучший ход определяется после этого по правилам минимакской процедуры.

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

В качестве оценочной функции Шенон предложил использовать многочлен вида $\sum_{i=1}^{k} a_i p_i$ , где $k$ — число признаков позиции, $a_i$ — «вес» признака, $a_p$ равно 1 или 0 в зависимости от наличия или отсутствия данного признака в позиции. С помощью оценочной функции можноучеть материалное соответствие с также позиционные факторы: слабые пещки, владение центром, открытыные линии, подвижность фигур и т. д.

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

*) Строго говора, для оптимальной игры следует еще учиться, во сколько ходов выиграваться позиция. Для этого достаточно в теореме Цермело заключенным выиграным позициям приписывать оценки $\pm 1/n$ , а ничейным — 0 ( $n$ — длина ветви, ведущей в данную позицию).

To, что такая оценочная функция в принципе существует следует из теоремы Цермелю. Значения этой функции могут быть заданы в виде таблицы, левый столбец которого представляется собой набор всех шахматных позиций, а правый — их оценок (1, 0, 1, 2). Однако эта таблица будет только же необозримой, как и полное дерево шахматной игры. Разумеется, нас интересует не таблица оценочная функция, а также, которая использует в качестве аргументов статистические признаки позиции. Доказать это невозможно, но, скорее всего, идеальная оценочная функция, основанная на простых и явных признаках позиции, будет такой же громоздкой, как и таблица функция. Компактную функцию построить, по-видимому, можно, но тогда уже и признаки должны быть слишком «умными».

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

В позиции на рисунке 2 матерIALный перевес на стороне белых, но оба их слона находится под боем, и нетрудно убедиться, что окончание ничейно. Немного изменим позицию, добавив черным пешку на c5. Как будто положение черных от этого может только уличиться, одноколер они проигрывают: 1. h7+! Кр:h7 2. Ca4! Л:b2+ 3. Cc2+! Л:c2+ 4. Kpf3, и собственная печка мешает черной ладье вернуть на последнюю горизонталь. Роковая роль пешки c5 выявлась только в процессе перебора варянтов. А теперь представьте себе оценную функцию, которая могла бы во всем этом разобраться, то есть предпосеть (за белых) вторую позицию перой!

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

Рис. 2.

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

Obviously при создании программы учитываются такие факторы, как подвижность функции, владение центром и открытыми линями, безопасность короля, а в решенной структуре — фаланги, опорные пункты, прохождение, сдвоенные и изолированные пешки и т. д. Рассмотрим один из факторов — владение центром. Вот как трактует его оценная функция советской программы «Кансса»: центром с точки зрения белых считаются поля e4, d4, e5, d5, e6, d6; пешка или легкая фигура, стоящая в центре, дает 20 условных единиц; удар пешкой или фигурой на центральное поле ценится в 10 единиц. Для учонения масштаба добавим, что подвижность функции определяется числом полей, которые она быет, причем за каждое поле прибавляется одно число.

В различных站ях шахматной партии (дебют, mittelшпиль, эндшпиль) оценка некоторых позиционных факторов может существовать. В соответствии с этим сильные программы имеют настройку оценочного функцию, то есть функцию, для которой набор признаков и их весов определяется самой программы в зависимости от обстановки на доске. В частности, у «Канссы» таких состояния четы-

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

Современные методы шахматного программирования

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

1°. Метод граней и оценок
Нибольное мощный метод сокращения перебора — это метод граней и оценок, использующий в настоящее время во всех играющих программах. Остановимся на нем подробнее. Для этого выделим из дерева игры некоторый фрагмент, схематически изображенный на рисунке 3.

Пусть белые в позиции $A$ уже изучили ход $AB$ (то есть ход, ведущий из позиции $A$ в позицию $B$ ). При этом соответствующое подделево с вершиной $B$ в результате минимкаса должно позицини $B$ оценку $+20^*$ ). Это означает, что, пробуя другие ходы из $A$ при спуске вниз по дереву, белые уже никака не согласятся на оценку, меньшею или равную 20 (поскольку эту оценку им обеспечивает ход $AB$ ).

Оценка $+20$ является гарантированной оценкой позиции $A$ (для белых), или, иначе, ее нижней гранью. При движении вниз по дереву гарантированные оценки всякий раз переносится в соответствующей позиции через один уровень.

Пусть теперь белые, продолжая перебор, попробавали ход $AC$ , а черные ответили ходом $CD$ . При вершине $D$ пока что была записана ее оценка, равная $+20$ , перенесенная из $A$ . Если теперь оценка, принесенная спизу в позицию $D$ , оказется не больше 20, это будет означает следующее:

*) Здесь и в дальнейшем оценка понимается с точки зрения белых (для черных оценка этой позиции равна — 20).

Ход $AC$ не лучше, чем $AB$ (при правильном ответе черных $CD$ оценка белых будет не выше, чем при ходе $AB$ ). Будем называть ход $AC$ плохим.
Ход $CD$ определяет ход $AC$ (в указанном смысле). Будем называть его закрывающим.
Другие ходы черных из позиции $C$ можно не рассматривать.

В этом случае говорят, что произойдет отсчение, и ходы $CE$ и $CF$ уже не изучаются.

Важно отметить, что в описном методе больше значение имеет порядок рассмотрения ходов. Предположим, что сначала пробовались ходы $CE$ и $CF$ и только потом $CD$ . Если бы они один из ходов $CE$ и $CF$ не оказался закрывающим, то мы только зря потеряли бы время на перебор ненужных вариантов.

Допустим, что нижняя гранью позицини $C$ равна +30. Это означает, что в дальнейшем перебор будет рассмотряться только те позиции, оценки которых заключаются в интервале ]20, 30[.

Пусть оценка позицини $D$ , принесенная спизу, оказалась равной 25. Тогда ход $CD$ называет уличшающим, гарантированная оценка позицини $C$ становится равной 25, черные продолжают перебор ходом $CE$ и будут вести его в границах ]20, 25[.

Улучшающим ход существует последующих отсчения. Ходы $CE$ и $CF$ могут еще более улучшить оценку для черных или даже оказаться закрывающим.

В любом случае перебор сокращается, если самый лучший ход пробуется первым.

Наконец, если оценка позиции $D$ оказывается не менее 30, то ход $CD$ будет плохим. Черные продолжат перебор ходом $CE$ в прежних границах. В случае, когда все ходы из вершины $C$ оказываются плоскими, уже ход белых $AC$ становится закрывающим, и черные должны будут сменить ход, приведший в позицию $A$ .

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

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

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

Описанный алгоритм обычно называют $\alpha$ —β-процедурой, имея в виду обозначение граней $] \alpha, \beta]$ . Эффективность этого алгоритма целиком зависит от качества упорядочения ходов в переборе. Так, если лучшие ходы пробются первыми, то возникало общее отсутствие размотренем всего около $\sqrt{n}$ позиций, где $n$ — полный объем дерева перебора.

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

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

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

Рис. 4. Боголюбов-Капабланка (Нью-Иорк, 1924).

ривать не все взяття, а только те, которые сохраняют материал как минимум на уровень своей нижней границы.

Если имеет в виду сотрудничентов человека и машины, то уже знание результата ФВ в данной позиции во многом помогло бы шахматисту. Зачастую неочевидные комбинации проходят в русле чистого форсированного варанта. Расстоярим пример из партии известных гроссейстеров прошло (рис. 4).

Черные в этой позиции сыграли: 1…К:d4!, и после 2. cd Л8:c5! Боголюбов сдела, так как на 3. dc решает 3…Ф:c5+ и 4…Л:c1.. Программа, использующая ФВ, нашла бы эту комбинацию даже при глубине расчета на один полуход.

Впервые ФВ был программо реализован в 1962 году в одной из ранних версий «Канссы». В настоящее время им активно пользовется многое шахматные программы.

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

Ходы из корня дерева должны упорядочены наболее аккуратно. Это будет способствовать возникновению максимальных отсечений в процессе перебора. Для этой цели после каждого из этих ходов применяется ФВ, который и приносит оценку хода.

На более глубоких уровнях перебора средства для диагностики качества хода более разнообразны. Если можно взять незашищенную фигуру или съесть слабой фигурой сильную, то такие ходы-кандидаты расматривают в первую очередь. Это так называемые выгодные взяття. В числе первых попадают также отсутствия фигур при нападении на них (правило «напалушел»). Эффективным оказывается взятие фигуры противника, только что сделавшей ход. При прочих равных условиях выгrodнее начать с ходов на небитые поля и т. д.

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

В заключение следует отметить, что многие интересные проблемы остались нами не рассмотренными. Кроме того, не надо думать, что описанные в этой статье иден и методы, использующие при программировании шахматной игры, являются единственно возможными. Так, экс-чемпрон мира, доктор технических наук М. М. Ботвинник, который в настоящее время занимается вопросами программирования шахмат, идет по иному пути*). Будущее покажет, какой из путей решения этой задачи оказывается более плодотворным.

*) См. книгу М. М. Ботвинника «От шахматства к машине» (М., «Физкультура и спорт», 1979).