книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

игрывает (заштрихованная ломаная). Дерево рис. 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

§3. АЛГОРИТМЫ ПОИСКА ПУТИ

ВЛАБИРИНТЕ

3.1. Лабиринты. Греческая мифология повествует о ле­ гендарном герое Тезее, который отважился проникнуть в лабиринт для того, чтобы разыскать в нем чудовищного Минотавра и убить его. Ему помогла выбраться из лаби­ ринта Ариадна, давшая Тезею клубок ниток, один конец которых держала она сама. По мере углубления Тезея в ла­ биринт клубок разматыва­ лся; наматывая потом нит­

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

Представим себе лабиринт в виде конечной системы пло­ щадок, от которых расходятся коридоры, причем каждый коридор соединяет две площадки (такие площадки будем называть смежными), но не исключается существование таких площадок, из которых можно пройти только в один коридор (такие площадки будем называть тупиками). Гео­ метрически лабиринт можно представить в виде системы точек А, В, С, ... (изображающих площадки) и совокупно­ сти отрезков АВ, ВС, ... (изображающих коридоры), со­ единяющих некоторые пары этих точек (рис. 8).

Будем говорить, что площадка Y достижима из площад­ ки А', если существует путь, ведущий от X к Учерез проме­ жуточные коридоры и площадки. Точнее, это означает, что либо X и Y — смежные площадки, либо существует после-

25

раз. В предыдущем примере путь не был простым, но, с р е ­

ясь на его поиски с площадки А, на которой его ждет Ариад­ на, должен решить след>ющую задачу: требуется выяснить, достижима ли М из Л или нет*'. Если достижима, то нужно добраться до нее по какому бы то ни было пути, но вернуть­ ся к Ариадне нужно уже по п р о с т о м у п у т и . Если же М недостижима, то вернуться к Ариадне.

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

3.2. Алгоритм поиска. Для построения такого алгорит­ ма мы рассмотрим один специальный метод поисков. На лю­ бой стадии процесса поиска в соответствии с этим методом приходится различать коридоры, еще ни разу не пройден­ ные Тезеем (условно — зеленые), пройденные один раз (желтые), пройденные дважды (красные). Далее, находясь на какой-либо площадке, Тезей может попасть на одну из смежных площадок посредством одного из следующих двух ходов:

1. Разматывание нити. Прохождение от данной пло­ щадки по любому зеленому коридору до смежной площад­ ки. При этом нить Ариадны разматывается вдоль этого ко-

*) Естественно считать, что МфА.

26

ридора, который после прохождения уже считается жел­ тым.

2. Наматывание нити. Возвращение от данной пло­ щадки по последнему пройденному желтому коридору до смежной площадки. При этом нить Ариадны, ранее размо­ танная вдоль этого коридора, обратно наматывается, а этот коридор уже объявляется красным.

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

I . Минотавр. На данной площадке обнаружен Мино­ тавр.

2: Петля. Через данную площадку уже протянута нить Ариадны; иными словами, от данной площадки расходятся

Находясь на какой-нибудь площадке, Тезей делает очередной ход так: он проверяет по порядку номеров в со­ ответствии с левым столбцом схемы, какой из перечислен­ ных признаков имеет место; обнаружив первый такой при­ знак, он (уже не проверяя остальные признаки) делает со­ ответствующий ход (или остановку) из правого столбца. Такие ходы делаются до тех пор, пока не наступает оста­ новка.

27

Пригодность предложенного метода непосредственно вытекает из следующих трех утверждений:

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

2.Если остановка наступила на площадке Минотавра, то Минотавр достижим. Более того, в этом случае нить Ариадны оказывается протянутой по простому пути, веду­ щему от А до М; наматывая нить, Тезей может теперь вер­ нуться по этому лутн к Ариадне.

3.Если остановка наступила на площадке Ариадны, то Минотавр н е д о с т и ж и м.

Прежде чем доказывать эти утверждения, покажем на

начинается поиск Минотавра, который находится в F. Про­ цесс поиска в соответствии с нашим методом удобно изобра­

Мы видим, что в данном случае Минотавр достижим. Выделив в предпоследнем столбце те из коридоров, которые остались желтыми (в соответствии с показаниями послед-

28

него столбца), получим следующий простой путь, ведущий от А к F:

/С, то процесс поиска можно изобразить в схеме, представ­

тодом индукции по числу ходов Тезея , что на любом этапе процесса поиска возникает следующая альтернатива (т. е. имеет место один из следующих двух случаев, взаимно исключающих друг друга);

а) в лабиринте нет желтых коридоров; при этом Тезей находится на площадке А (Ариадны);

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

Вместе с тем будет обнаружено, что Тезей никогда не проходит по красному коридору.

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

29