Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

Отметим сначала следующие особенности, присущие

Ниже, без особых оговорок, под игрой подразумевается такая игра, которая обладает перечисленными свойствами 1—4.

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

На рис. 1 для определенности изображено дерево сле­ дующей игры (видоизменение игры «Одиннадцать предме­ тов»),

18

Двое берут поочередно спички со стола. Первоначально на столе лежит 6 спичек, а за один раз разрешается брать не более двух. Проигрывает тот, кто берет последнюю спичку.

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

В нашем примере в любом ходе (кроме последнего) возможны два варианта. Для определенности примем, что левая ветвь, выходящая из любой вершины, соответствует изъятию одной спички, а правая — двух. Партия изобра­ жается ломаной, которая начинается с самой нижней вер­ шины а дерева {корень дерева), причем каждый ход изобра­ жается перемещением из данной вершины в какую-нибудь из примыкающих верхних вершин. Партия закончена тог­ да, когда достигнута какая-нибудь вершина, из к о т о р о й н е в ы х о д я т в е т в и {концевая вершина). При каж­ дой концевой вершине в кружке указан исход партии.

На рис. 1 для каждой ветки указано общее число спичек, изъятых на данной стадии разыгрывания партии. Заштрихо­

в которой А выигрывает.

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

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

19

игрывает (заштрихованная ломаная). Дерево рис. 2, б за­ дает игру, сводящуюся к одному ходу.

Всякая неконцевая вершина дерева может быть рас­ смотрена как корень «поддерева» меньшего ранга, задаю­ щего тоже некоторую игру.

Изображение игры посредством дерева позволяет пред­ ставить графически любую стратегию для игрока Л в виде системы стрелок* выходящих из вершин нечетного ранга и ведущих к смежным вершинам четного ранга. При этом должны соблюдаться следующие требования:

Рис. 2. Рис. а.

а) из каждой вершины выходит не более одной стрелки (стратегия игрока А однозначно определяет его выбор в дан­ ной ситуации);

б) если имеется стрелка, ведущая к вершине у (четного ранга), то и всякая вершина следующего ранга, примыкаю­ щая к вершине у, тоже является началом стрелки (рис. 3); это условие гарантирует как раз то, что стратегия преду­ сматривает л ю б у ю ситуацию, в которой может оказать­ ся А.

Аналогично определяется стратегия для В.

На рис. 4 изображена на дереве игры «Шесть предме­ тов» (ср. рис. 1) стратегия Л, заключающаяся в том, что он всегда берет в точности одну спичку. При этой стратегии

2.4.Существование выигрышной стратегии.

Те о р е м а. Во всякой игре для одного из игроков суще-

ствует выигрышная стратегия.

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

20

игрывает В). Допустим, что этот ход делает по правилам

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

Совершенно аналогично рассматривается случай, когда а изображает позицию, в которой ходит В. Именно, если среди О; имеется хотя бы один минус, то В имеет выигрыш­ ную стратегию; в противном же случае А имеет выигрыш­ ную стратегию.

П е р е х о д O T V — 1 к v, Пусть теорема уже установ­ лена для всех рангов s < v; докажем ее для s = v. В этом случае дерево игры имеет вид, представленный на рис. 6, где треугольниками изображены поддеревья, корнями ко­

жают игры, в которых первый ход делает В, причем в каж­ дой из них наибольшая длина партии не превосходит v — 1.

21

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

В имеет выигрышную стратегию, изображаемую объедине­

цесс на примере дерева игры «Шесть предметов» (рис. 7). Идя от конца, т. е. от вершин высшего ранга к вершинам низшего ранга, мы размещаем в вершинах дерева знак «-f-» или «—» в зависимости от того, имеет А или В выигрышную стратегию в соответствующей подыгре.

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

22

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

Продолжая этот процесс, доходим до вершины первого ранга, к которой относится «+». Итак, А имеет выигрыш­ ную стратегию. Размещение стрелок (стратегии) можно те­ перь вести в обратном порядке: от корня дерева к его кон­ цевым вершинам. От корня проводим стрелку к «плюсо­ вой» вершине второго ранга (имеется лишь одна такая вер­ шина). От каждой из вершин третьего ранга, примыкающих к ней сверху, проводится по одной стрелке к «плюсовой» вершине. В нашем случае этим и завершается построение стратегии, которая изображена на рис. 7. Как видно из рисунка, при этой стратегии игрока А возможны лишь две партии, причем обе заканчиваются поражением В.

Заметим теперь, что теорема этого параграфа и лежа­ щий в ее основе алгоритм легко распространяются и на такие игры, для которых условия 1 и 2 пункта 2.3 не соблю­ дены, лишь бы выполнялись условия 3 и 4, которые и яв­ ляются существенными. Можно, например, рассматривать игры двух партнеров А и В, в которых, кроме выигрыша А или В, возможна и ничья. Здесь может оказаться, что ни один из игроков не имеет выигрышной стратегии, но тогда алгоритм строит для каждого игрока стратегию, гаранти­ рующую ему по крайней мере ничью (а при неразумной игре противника, быть может, и выигрыш).

Поскольку шахматы относятся к играм такого типа, то наш алгоритм устанавливает для них, какая именно ситуа­ ция имеет место и какова лучшая стратегия для белых. Для этого достаточно (I) построить дерево шахматной игры и восстановить по нему лучшие стратегии для игроков. Если при этом окажется, что белые (игрок А) имеют выигрышную стратегию, то исход игры предрешен в пользу белых, если они только будут строго следовать этой стратегии. Точно так же исход игры будет предрешенным, если выяснится, что черные имеют выигрышную стратегию или что оба парт­ нера имеют ничейные стратегии.

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

23