Игра Шеннона с переключением — это игра на соединение для двух игроков, придуманная американским математиком и инженером-электриком Клодом Шенноном , «отцом теории информации», где-то до 1951 года. [1] Два игрока по очереди раскрашивают рёбра произвольного графа . Цель одного игрока — соединить две выделенные вершины путём из рёбер своего цвета. Другой игрок стремится предотвратить это, используя вместо этого свой цвет (или, что эквивалентно, стирая рёбра). В игру обычно играют на прямоугольной сетке ; этот особый случай игры был независимо придуман американским математиком Дэвидом Гейлом в конце 1950-х годов и известен как Гейл или Бридж-Ит . [2] [3]
Игра ведется на конечном графе с двумя специальными узлами, A и B. Каждое ребро графа может быть либо окрашено, либо удалено. Два игрока называются Short и Cut и ходят по очереди. В ход Cut, Cut удаляет из графа неокрашенное ребро по своему выбору. В ход Short, Short раскрашивает любое ребро, все еще находящееся в графе. Если Cut удается превратить граф в такой, где A и B больше не связаны, Cut выигрывает. Если Short удается создать цветной путь из A в B , выигрывает Short. Игра всегда заканчивается после конечного числа ходов, и один из двух игроков должен победить. Short, Cut или игрок, ходящий первым, гарантированно имеют выигрышную стратегию на любом заданном графе. [4]
Игры Short и Cut являются дуальностью; то есть игру можно переформулировать так, чтобы у обоих игроков была одна и та же цель: обеспечить определенный набор ребер с выделенным ребром e . Short пытается обеспечить набор ребер, который вместе с e образует контур , в то время как Cut пытается обеспечить набор ребер, который вместе с e образует набор разрезов, минимальный набор ребер, соединяющих два подграфа .
Версии игры Шеннона с переключением, играемые на ориентированном графе и ориентированном матроиде, были описаны в теоретических целях; [5] [6] , но соответствующие коммерческие игры не были опубликованы.
В этой игре, придуманной американским математиком Дэвидом Гейлом и описанной в колонке Мартина Гарднера в Scientific American в октябре 1958 года, две сетки разноцветных точек накладываются друг на друга со смещением. Один игрок соединяет ортогонально соседние точки на одной сетке, а другой игрок использует другую. Один игрок пытается связать верхнюю часть своей сетки с нижней, в то время как другой пытается связать левую сторону с правой. Игра эквивалентна игре Шеннона с переключением, сыгранной на прямоугольной сетке. Ничья невозможна; первый игрок всегда может выиграть при правильной игре.
Коммерческая настольная игра, реализующая эту схему, была выпущена на рынок в 1960 году компанией Hassenfeld Brothers под названием Bridg-It. [7] Игра состояла из пластиковой доски с двумя перемежающимися прямоугольными сетками 5x6 постаментов (один набор желтый, другой красный), двух наборов по 20 красных и желтых пластиковых мостов и соответствующих колышков для их установки. Игроки поочередно размещают мост через любые два соседних постамента соответствующего цвета, пока один из игроков не соединит две противоположные стороны доски, отмеченные цветом игрока. Вариант игры описан в инструкции: каждый игрок получает ограниченное количество мостов, скажем, 10. Если ни один из игроков не выиграл, когда все мосты были размещены, игрок в свой ход может переместить один из своих мостов, пока не будет выявлен победитель. Игра давно снята с производства.
Электронная версия игры Game of Gale доступна на портале Ludii Games.
Игру переключения Шеннона можно рассматривать как особый случай игры «Создатель-Разрушитель» , в которой выигрышными схемами для Создателя являются соединительные пути.
Слабосвязанная игра Hex играется на сетке шестиугольников и имеет 6-связность. Обобщенный Hex играется на графе, как и игра Шеннона, но вместо того, чтобы раскрашивать ребра, в Hex игроки раскрашивают вершины. Эти игры имеют совершенно разную структуру и свойства.
Другая игра на связность, в которую играют с бумагой и карандашом на прямоугольном массиве точек (или миллиметровой бумаге), — детская игра « точки и квадраты ». Игроки поочередно рисуют вертикальную или горизонтальную линию, соединяющую любые две соседние точки. Когда линия завершает квадрат, игрок ставит подпись под квадратом. После того, как все линии будут заполнены, победителем становится игрок, взявший больше всего квадратов.
Расширение Gale, называемое Qua, играется тремя игроками на 3D-кубе, состоящем из сетки из N 3 ячеек. N — нечетное число, равное количеству ячеек по краям куба игрового поля. Первоначальная раскладка игрового поля Qua Cube и правила описаны в статье Board Game Geek. [8]
Явное решение для ненаправленной игры с переключением было найдено в 1964 году для любой такой игры с использованием теории матроидов . Short должен стремиться к позиции, в которой существует набор вершин, включающий две выделенные вершины, а также два непересекающихся подмножества оставшихся невыбранных ребер, поддерживаемых на , так что любое из двух подмножеств (вместе с уже выбранными ребрами) соединило бы все вершины в . Если Short может сделать ход, который приводит к позиции с этим свойством, то Short может выиграть независимо от того, что делает другой игрок; в противном случае Cut может выиграть. [2] [9]
В отличие от некоторых других игр на соединения, которые могут быть сложными для PSPACE , [10] [11] оптимальные ходы для игры с ненаправленным переключением можно найти за полиномиальное время на ход. После удаления из графа ребер, выбранных Cut , и сжатия ребер, выбранных Short , полученный граф является минором исходного графа. Задача проверки существования двух непересекающихся деревьев, каждое из которых соединяет выделенные вершины, может быть представлена как задача разбиения матроида , которая может быть решена за полиномиальное время. В качестве альтернативы можно решить ту же задачу с помощью алгоритмов сетевого потока .
