Переключательная игра Шеннона

Квант 1980, №9 с. 14, 15, 16, 17, 18, 20 Тег Q02F

Е. Глушанков,
П. Певзнер

Переключательная игра Шенона

Нельзя ли без полного перебора?

Стремительное развитие в XX веке произвolvedства, экономики и транспорта поставило перед математикой новые проблемы. Как управлять современным предприятием, как спланировать большой комплект работы, как составить удобное расписание движения поездов — со всеми этим вопросами инженеры стали обращаться к математикам. Однако методы классической математики, предзначаенные, в основном, для решения задач физики и механики, не могли дать ответ на такие вопросы. Это привело к появлению новых математических дисциплин — теории игры, теории графов, теории кодирования и многих других, объединяемых сейчас называемем «дискретная математика».

Первая работа по дискретной математике (она принадлежит Леонарду Эйлеру), появившаяся в 1736 году, была посвящена известной головоломке о кенигсбергских местах: можно ли совершить прогулку по Кенигсбергу (план города изображен на рисунке) таким образом, чтобы выйдет из дома, вернуться обратно, пройдя по каждому местуровно один раз? Долгое время дискретная математика занималась почти исключительно головоломками, и поэтому находилась у серверных математиков на положении Золушки. Однако уже в XIX веке дискретные методы применились при изучении электронических цепей и молекулярных схем в химиии.

Настоящий расчет дискретной математики наблюдается в последние два—tri decrytления. Физика, химия, программирование, экономика, генетика, социология, лингвисти-

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

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

С одной стороны задачей занимающей математикой стalkиваются edва ли не каждый день. Это задача поиска доказательства данной теоремы. В самом деле, если доказательство дано, то проверить его правильность в принципе не трудно. Нужно лишь убедиться в том, что каждый шаг сделан в соответствии с правилами логики, а промежуточные утверждения следует из аксиом и известных теорем. Но как это доказательство найти? Нужели перебирать все возможные рассуждания, начиная с аксиом? Если бы кто-нибудь мог объяснить, как он «догадывается», решая задачи, может быть, это помогло бы математикам научить машину делать то же самое.

А вот более простой пример: задача о разбиении. Пусть $A = \{s_1, \dots, s_N\}$ — конечное множество, содержащие натуральные числа. Требуется разить множество $A$ на два подмножества $I$ и $J$ ( $I \cap J = \emptyset$ , $I \cup J = A$ ) так, чтобы сумма элементов из $I$ равная сумме элементов из $J$ . Как, и в предыдущем примере, для данного разбиения множество $A$ на множество $I$ и $J$ очень легко проверить, равны ли соответствующие суммы. Но как найти искомое разбиение? К сожалению, наука не может пока предложить ничего существенного лучшего, чем перебор всех $2^N$ вариантов. Но уже при $N = 100$ современной вычислительной машине понадются миллиарды лет для проверения такого перебора.

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

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

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

В настоящее время предложено несколько подходов к программированию игра. О методе, основанным на переборе с отсутствием беспереспективных (с некоторой точки зрения) вариантов, «Квант» уже писал*. Другой метод (на его основе в середине 60-х годов А. Леман предложил «идеального играка» в ПИШ), связанный с полным отказом от перебора вариантов, опирается на некоторых новые результаты дискретной математики.

О том, как можно играть в ПИШ, не перебирая вариантов, мы и рассскажем ниже.

Бридж-ит

В конце 50-х годов американец Гейл придумал игру Бридж-ит. Стандартное поле для игры Бридж-ит показано на рисунке 1. Один игрок соединяет с ним карандашом синего точки, другой — красным карандашом красные. «Ходят» (то есть проводят отрезки) игри по очереди. Выигравает тот, кто первым построит ломанную, соединяющую две противоположные стороны своего цвета (на рисунке 2 партия закончилась победой красных).

*) Р. С. Гутер, М. В. Донской Машина церает в шахматы («Квант», 1974 № 11).

Попробуйте, поиграв в бридж-ит на маленьких полях (рис. 3), понять, у какого игрока — преимущество в этой игре, а затем попытаться разрабатыть выигрышную стратегию для этого игрока.

Задача 1. Докажите, что в игре бридж-ит «ничных» не бывают.

Если в цереге не былает «ничных», то один из церков имел выигрышную стратегию. Действительно, пусть, например, игрок $A$ не имеет выигрышной стратегиии, то есть на любой его ход у игрока $B$ существует такой ответ, что игра не кончится победой $A$ . Поскольку предположено, что в рассматриваемой игре нет «ничных» партии кончится победой игрока $B$ , то есть у $B$ есть такая последовательность ходов, что, как бы ни играл $A$ , все равно выиграет $B$ . Таким образом, у игрока $B$ существует выигрышная стратегия.

Только что приведенное рассуждение есть чистое доказательство существования: доказывается, что стратегия есть, но как ее найти — ни слова. А ведь это и есть самый интересный вопрос.

ПИШ

Чтобы описать выигрышную стратегию для игры Бридж-ит, передем от бридж-ит к ПИШ. Для этого изменим немного правила игры. На рисунке 4 все возможные ходы «синнего» игрок отмечены синими отрезками, а «красного» игрок — красными. Мы будем называть такие рисунки «графами возможных ходов». Если вы уже погалли в бридж-ит, то наверное поняли что игрокам бессмысленно проводить отрезки, обозначенные на рисунке 4 пунктом. Поэтому давйте вообще не будем их рассматривать и сделаем следующее: стянем все верхние точки в одну и то же самое сделаем с левыми, правыми и нижними точкими (рис. 5). Теперь цель «синнего» игрок — соединить путем из синних ребер вершины $s$ и $t$ , а цель «красного» — соединить красным путем вершины $s'$ и $t'$ .

Заметьте, что каждый красный отрезок пересекаетровно один синий. Поэтому, если «красный» игрок делает ход, то это, по существу, означает, что он делает невозможным один (и только один) ход «синнего» игрок, то есть «красный» игрок своим ходом как бы вы червиает ребро синнего графа. Но вместе того чтобы вычеркивать синее ребро, можно просто закрасить его красным цветом. Теперь мы можем вообще удалить красный граф из рисунка 5 и считать, что игра проходит так:

Два игрока по очереди красят ребра графа, у которой выделены вершины $s$ и $t$ : один — синим цветом, другой — красным (рис. 6). Цель «синнего» игрок — соединить выделенные вершины путем*) из синних ребер, а цель «красного» игрок — помещать ему (что это значит, мы уточним позднее).

*)Напомним, что граф называется конечное множество точки (вершин графа) и соединиших их отрезков (ребер графа). Путь — это линяя на графе, не проходящая ни по какому ребру более одного раза.

Это и есть переключатель изра Шенона ПИШ). Только Шенон предложил ее в более общей постановке: во-первых, играть можно на любом графе и, во-вторых, на данном графе можно выделить любую пару вершин.

Каждай граф с двумя виделенными вершинами задает неокотрый варциант ПИШ. Первый ход в каждом варинате может делать любой игрок — как «синей», так и «красный». Поскольку «синей» игрок соединяет вершины, его уместно называют Соединицим или С-цероком. А красного игрока мы назовем Режущим или P-цероком.

Совершенно очевидно, что «ничых» в ПИШ не бывают — С либо соединит виделенные вершины, либо нет. Поэтому один из игроков в ПИШ имеет выигрышную стратегию. Но какой? Как найти эту стратегию?

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

Таким образом, с точки зрения возникности выиграть для каждой варината ПИШ возникен один и только один из следующих трех слияев:

соединиций имеет выигрышную стратегию, независимо от того, играет он первым или вторым;
режущий имеет выигрышную стратегию, независимо от того, играет он первым или вторым;
выигрышную стратегию имеет игрок, делаюший первый ход.

Варинаты ПИШ первой группы мы назовем С-церами, второй —

2 Квант № 9

Р-церami, третий — Н-церami. На рисунках 7, а) — в) изображены графы, дающие С-церу, P-церу и Н-церу соответственно.

Задача 2. Докажите, что бридж-ит является Н-игрой.

Немного теории

Давайте на некоторое время отвлечемся от игр и даим несколько определений из теории графов, которые попадются в дальнейшем*.

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

Легко видеть, что удаление любого ребра из дерева приводит к графуровно с двумя компонентами, причем концы удаленного ребра лежат в разных компонентах (рис. 9).

Ребро графа с концами x и y будем обозначать [x, y]. Ту компоненту, которая образуется при выбрасывании ребра [x, y] из дерева A и содержит вершину x, обозначим через A(x), а ту, которая содержит вершину y,— через A(y).

Лемма о двух деревьях. Пусть A и B — два дерева на одном и том же множестве вершин и [x, y] — ребро дерева A. Тогда в дереве B существует ребро b, один конец которого лежит в A(x), а другой — в A(y) (рис. 10).

Новые правила игры

Чтобы научиться играть в ПИШ, мы опять немного изменим поле и правила игры. Для этого введем понятие стягивания графа.

*) Подробнее о графах расссказано, например, в книге Л. Ю. Березиной «Графы и их применение» (М., «Просвещение», 1979).

Эта лемма подсказывает стратегию для соединяющего игрока.

Цель игрока $C$ — подерживать в графе существование двух деревьев, удовлетворяющих условию Лемана (деляя это, он обеспечивает существование двух путей между вершинами $s$ и $t$ , и игроку $P$ никака не удался разведить эти две вершины). И игрок $C$ действительно может это сделать, если такие два деревья имелись в исходном графе. Если игрок $P$ удаляет ребро $a$ в одном из этих деревьев, то игрок $C$ в ответ должен стянуть ребро из другого деревья, существующего по последней лемме. Если же игрок $P$ удаляет ребро, которое не принадлежит ни одному из наших двух деревьев, то игрок $C$ может стянуть ребро в одном из деревьев; ясно, что в новом графе по-прежнему найдется два деревья Лемана (какие?).

После каждой пары ходов количество вершин в каждой из наших деревьев уменьшается на единицу, поэтому вершины $s$ и $t$ рано или поздно сольются и игрок $C$ выиграет.

Мы начили вас играть в $C$ -игру, используя два деревья Лемана. Но как находится эти деревья? Конечно, можно использовать полный перебор, однako это связано с огромными затратами времени даже на современных ЭВМ. Леману не удалось найти эффективного алгоритма для отыскания двух таких деревьев, поэтому неокупPOSE время казалось, что теорема Лемана имеет лишь теоретический интерес. Только в начале 70-х годов Бруно и Вейнбергу удалось построить такой алгоритм.

На самом деле, Леман полностью решил переключательную игру Шенона: он доказал также, что вариант ПИШ тогда и только тогда является $P$ -игрой, когда в графе имеются два подграфа определенного вида. Если же вариант ПИШ является $H$ -игрой, то после первого разумного хода мы получаем на новом графе вариант ПИШ, который является $P$ -игрой или $C$ -игрой — в зависимости от того, кто делал первый ход: $P$ или $C$ соответственно. Такой ход существует. Такой ход существует по определенному $H$ -игры. На эти ход в принципиме можно перебором.

Стратегия для бридж-ит

Итак, мы расссказали, как играть в $C$ -игры. Но ведь бридж-ит, согласно задаче 2, есть $H$ -игра. Как же играть начинающему, чтобы выиграть?

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