6.1. Дерево допустимых ходов

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

В начале шахматной партии каждый противник имеет возможность сделать 20 различных ходов. Следовательно, после первого обмена ходами на доске уже возможны 400 различных позиций, но, естественно, нельзя заранее определить, какая именно из них возникнет на самом деле. Проводя анализ игры, можно последовательно рассматривать ходы обеих сторон, но заметим, что к середине партии число ходов уже достигает 50, а число ветвей дерева будет составлять величину где К — постоянное число допустимых ходов на каждом уровне для каждого играющего, порядковый номер хода. На практике для шахмат можно положить и для 6 ходов число ветвей составит . При переходе на каждый следующий уровень это немалое число нужно еще умножить на К, что увеличивает объем вычислений, и, в частности, время, необходимое для поиска ходов и оценки конечной позиции. Они экспоненциально растут с увеличением глубины анализа, что делает невозможным точный просмотр ситуации на достаточно большую глубину. Даже сверхпроизводительная ЭВМ, которая в состоянии проанализировать 10 конечных состояний в 1 с, за время непрерывной работы со дня образования Солнечной системы, т. е. 4,6 млрд. лет, была бы способна проанализировать позиций, что составляет или позиций, или 12 ходов, т. е. по 6 ходов

с каждой стороны, что всего в 2 раза больше, чем рассмотренная выше глубина анализа, равная 6. Даже такая ЭВМ не смогла бы рассчитать все варианты всего на 12 ходов вперед! В то же время известно, что средняя шахматная партия продолжается обычно не менее 40 ходов. Именно это противоречие вызывает интерес к игре в шахматы и составляет ее очарование.

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

Рис. 6.2. Доска для игры в тик-так-ту.

Игра тик-так-ту ведется на поле из 9 клеток. Оба играющих имеют по три фишки. В первом туре играющие по очереди расставляют свои фишки (по одной за ход) на свободных клетках. Во втором туре, когда размещены все 6 фишек, играющие поочередно перемещают по одной фишке на свободные соседние клетки. Соседней считается клетка, расположенная в одном шаге от данной. Направления шагов, связывающих клетки, показаны на рис. 6.2. Выигрывает тот, кто первым расположит свои фишки по прямой линии.

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

Таблица 6.1 (см. скан)

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

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

В шахматах существует 16 возможных направлений перемещения фигур: 8 рассмотренных выше и 8 “специальных” направлений для коня. Для пешек разрешено только одно направление, для ферзя — 8. Каждое направление характеризуется парой чисел определяющих его наклон. В табл. 6.2 приведены значения этих пар для направлений, показанных на рис. 6.3.

Таблица 6.2

Рис. 6.3. Возможные направления ходов в тик-так-ту (и в шахматах).

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

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

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

(см. скан)

Из приведенного выше ясно, что наиболее простой способ ограничения дерева заключается в ограничении глубины анализа числом 1. В этом случае необходимо: 1) найти все допустимые ходы; 2) оценить их; 3) сделать наилучший из оцененных ходов.

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

(см. скан)

Стратегия «первого уровня». Рассмотрим позицию в игре тик-так-ту, приведенную на рис. 6.4. Покажем, как найти наилучший ход, используя стратегию первого уровня.

По правилам игры существует всего 4 допустимых хода:

Рис. 6.4. Ход черных.

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

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

например, число возможных ответных ходов противника. В конце концов после полного перебора всех позиций, вместо них используют логические величины ВЫИГРЫШ или ПРОИГРЫШ.

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

На рис. 6.5 приведен пример полного дерева для игры тик-так-ту, содержащего все допустимые ходы для случая, когда черные начинают игру ходом своей фишки в центр игрового поля. При таком ходе победа черных обеспечена при любых ответных ходах противника. Из-за симметрии игрового поля только 2 ответных хода белых являются существенно различными — ходы на клетки a и b, рассмотрением которых мы и ограничимся. Ходы на клетки и эквивалентны ходу на клетку а, в ходы на клетки и — ходу на клетку За счет этого ширина дерева сразу уменьшается в 4 раза. Затем, (для экономии места и времени) мы учтем только наилучшие ходы черных на каждом уровне, т. е. такие ходы, которые неизбежно приводят к выигрышу. Таким образом, представленное на рис. 6.5 дерево содержит легко определяемую последовательность ходов. Заметим, кстати, что кроме первого уровня, все ходы белых являются вынужденными вплоть до восьмого, который уже не имеет значения, — черные выигрывают в любом случае.

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

(кликните для просмотра скана)

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

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

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

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

Заметим, что подобные идеи впервые были использованы английским математиком Аленом Тьюрингом, который начиная с 1951 г. моделировал эту стратегию на вполне конкретных примерах.