Введение

Игра с соединением карандаша и бумаги

Игра с переключением Шеннона — это игра на соединение для двух игроков, изобретённая американским математиком и инженером-электриком Клодом Шенноном, которого называют «отцом теории информации», за некоторое время до 1951 года. Два игрока по очереди раскрашивают рёбра произвольного графа. Цель одного игрока — соединить два выделенных вершины путём рёбер своего цвета. Другой игрок стремится этому помешать, используя свой цвет (или, что эквивалентно, удаляя рёбра). Игра обычно играется на прямоугольной сетке; этот частный случай игры был независимо изобретён американским математиком Дэвидом Гейлом в конце 1950-х годов и известен как Gale или Bridg-It.

Правила

Игра проводится на конечном графе с двумя специальными вершинами, А и В. Каждое ребро графа может быть окрашено или удалено. Два игрока называются Short и Cut, и они ходят по очереди. На ходу Cut, Cut удаляет из графа неокрашенное ребро по своему выбору. На ходу Short, Short окрашивает любое ребро, которое ещё осталось в графе. Если Cut сможет превратить граф в такой, где вершины А и В перестанут быть соединены, Cut выигрывает. Если Short сможет создать окрашенный путь из А в В, Short побеждает. Игра всегда заканчивается за конечное число ходов, и один из двух игроков обязательно выигрывает. Либо Short, либо Cut, либо игрок, ходящий первым, гарантированно имеет выигрышную стратегию для любого заданного графа. Игры Short и Cut являются двойственными; то есть, игру можно переформулировать так, чтобы у обоих игроков была одна и та же цель: обеспечить определённое множество рёбер с выделенным ребром e. Short пытается обеспечить такое множество рёбер, которое вместе с ребром e образует цикл, в то время как Cut пытается обеспечить такое множество рёбер, которое вместе с ребром e образует разрез – минимальное множество рёбер, соединяющих два подграфа.

Варианты

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

Гейл

В этой игре, изобретенной американским математиком Дэвидом Гейлом и описанной в колонке Мартина Гарднера в журнале Scientific American в октябре 1958 года, две сетки точек разных цветов накладываются со смещением. Один игрок соединяет ортогонально соседние точки на одной сетке, а другой – на другой. Один игрок стремится соединить верхнюю часть своей сетки с нижней, а другой – левую сторону с правой. Игра эквивалентна игре Шеннона на переключение контактов, играемой на прямоугольной сетке. Ничья невозможна; при правильной игре первый игрок всегда побеждает. Коммерческая настольная игра, основанная на этой схеме, была выпущена в 1960 году компанией Hassenfeld Brothers под названием Bridg It. Игра состояла из пластиковой доски с двумя перекрывающимися прямоугольными сетками 5x6 пьедесталов (одна – желтая, другая – красная), двух наборов по 20 красных и желтых пластиковых мостов и соответствующих креплений для их установки. Игроки по очереди устанавливают мост между любыми двумя соседними пьедесталами одного цвета, пока один из игроков не соединит две противоположные стороны доски, отмеченные своим цветом. В инструкции описан вариант игры: каждому игроку выдается ограниченное количество мостов, например, 10. Если после размещения всех мостов ни один из игроков не выиграл, игрок в свой ход может переместить один из своих мостов, пока не определится победитель. Игра больше не производится. Электронная версия игры Гейла доступна на игровом портале Ludii.

Отношения с другими играми

Игра с переключением Шеннона может рассматриваться как частный случай игры Maker-Breaker, в которой выигрышные конфигурации для Maker – это связные пути. Игра Hex, слабо связанная с играми на соединение, играется на сетке из гексагонов и обладает связностью 6. Обобщённый Hex играется на графе, как и игра Шеннона, но вместо раскраски рёбер, в Hex игроки раскрашивают вершины. Эти игры имеют совершенно различную структуру и свойства. Ещё одна игра на соединение, в которую играют с бумагой и карандашом на прямоугольной сетке точек (или в клетчатой бумаге), – детская игра "точки и квадраты". Игроки по очереди проводят вертикальную или горизонтальную линию, соединяющую любые две соседние точки. Когда линия завершает квадрат, игрок подписывает этот квадрат. После того, как все линии проведены, победителем становится игрок, собравший наибольшее количество квадратов. Расширение игры Гейла, называемое Qua, играется тремя игроками на трёхмерном игровом поле – кубе, состоящем из сетки N³ ячеек. N – нечётное число, равное количеству ячеек по каждой стороне куба игрового поля. Начальная раскладка и правила игры Qua Cube описаны в её записи на BoardGameGeek.

Комплексность вычислений

В 1964 году было найдено явное решение для игры с ненаправленным переключением для любой такой игры с использованием теории матроидов. Игрок Short должен стремиться к позиции, в которой существует множество вершин, включающее две выделенные вершины, а также два непересекающихся подмножества оставшихся невыбранных ребер, опирающихся на , таких, что любое из этих двух подмножеств (вместе с уже выбранными ребрами) соединит все вершины в . Если игрок Short может сделать ход, приводящий к позиции с этим свойством, то он выиграет независимо от действий другого игрока; в противном случае выиграет игрок Cut. В отличие от некоторых других игр на соединение, которые могут быть NP-трудными, оптимальные ходы для игры с ненаправленным переключением можно найти за полиномиальное время на ход. После удаления из графа ребер, выбранных игроком Cut, и сжатия ребер, выбранных игроком Short, полученный граф будет минором исходного графа. Задача проверки существования двух непересекающихся деревьев, каждое из которых соединяет выделенные вершины, может быть представлена как задача разбиения матроида, которую можно решить за полиномиальное время. Альтернативно, ту же задачу можно решить с помощью алгоритмов поиска сетевого потока.