Шеннон переключает игру
Игра с переключением Шеннона — это игра на соединение двух игроков, изобретенная американским математиком и инженером-электриком Клодом Шенноном , «отцом теории информации» незадолго до 1951 года. [1] Два игрока по очереди раскрашивают ребра произвольного графа . У одного игрока есть цель соединить две отмеченные вершины путем из ребер их цвета. Другой игрок стремится предотвратить это, используя вместо этого свой цвет (или, что то же самое, стирая края). В игру обычно играют на прямоугольной сетке ; этот особый случай игры был независимо изобретен американским математиком Дэвидом Гейлом в конце 1950-х годов и известен как Гейл или Bridg-It . [2] [3]
Правила [ править ]
Игра ведется на конечном графе с двумя специальными узлами A и B. : Каждое ребро графа можно либо раскрасить, либо удалить. Двух игроков зовут Short и Cut , и они чередуют ходы. В свой ход Cut Cut удаляет из графа неокрашенное ребро по своему выбору. В ход Шорта Шорт окрашивает все ребра, оставшиеся на графике. Если Cut удастся превратить граф в такой, в котором A и B больше не связаны, Cut выиграет. Если Шорту удастся создать цветной путь от A до B , Шорт выиграет. Игра всегда заканчивается после конечного числа ходов, и один из двух игроков должен выиграть. Либо Short, Cut, либо игроку, двигающемуся первым, гарантировано существование выигрышной стратегии на любом заданном графе. [4]
Игры Short and Cut представляют собой двойственность; то есть игру можно переформулировать так, чтобы оба игрока преследовали одну и ту же цель: обеспечить определенный набор ребер с выдающимся ребром e . Шорт пытается защитить набор ребер, который с e образует схему , а Cut пытается защитить набор ребер, который с e составляет набор разрезов, минимальный набор ребер, соединяющих два подграфа .
Варианты [ править ]
Версии игры с переключением Шеннона, в которую играют на ориентированном графе и ориентированном матроиде , были описаны в теоретических целях; [5] [6] но соответствующие коммерческие игры опубликованы не были.
Гейл [ править ]
В этой игре, изобретенной американским математиком Дэвидом Гейлом и описанной в Мартина Гарднера колонке в журнале Scientific American в октябре 1958 года, две сетки из точек разного цвета накладываются друг на друга со смещением. Один игрок соединяет ортогонально соседние точки на одной сетке, а другой игрок использует другую. Один игрок пытается связать верхнюю часть своей сетки с нижней, а другой пытается связать левую часть с правой. Игра эквивалентна игре с переключением Шеннона, в которой играют на прямоугольной сетке. Ничьей не может быть; первый игрок всегда может выиграть при правильной игре.
Коммерческая настольная игра, реализующая эту схему, была продана в 1960 году компанией Hassenfeld Brothers под названием Bridg-It. [7] Игра состояла из пластиковой доски с двумя чередующимися прямоугольными сетками пьедесталов 5х6 (одна желтая, другая красная), двух наборов по 20 красных и желтых пластиковых мостиков в каждом и соответствующих колышков для их установки. Игроки поочередно размещают мост через любые два соседних пьедестала соответствующего цвета, пока один игрок не соединит две противоположные стороны доски, отмеченные цветом игрока. Вариант игры описан в инструкции: каждый игрок получает ограниченное количество мостов, скажем, 10. Если ни один из игроков не выиграл, когда все мосты расставлены, игрок в свой ход может переставить один из своих мостов до тех пор, пока не появится победитель. результаты. Игра давно снята с производства.
Электронная реализация Game of Gale доступна на портале Ludii Games .
Связь с другими играми [ править ]
Игру с переключением Шеннона можно рассматривать как частный случай игры Создатель-Разрушитель , в которой выигрышными шаблонами для Создателя являются соединяющиеся пути.
со слабосвязанной связностью Игра Hex ведется на сетке шестиугольников и имеет 6 связностей. В Generalized Hex играют на графе, как и в игре Шеннона, но вместо того, чтобы раскрашивать ребра, в Hex игроки раскрашивают вершины. Эти игры имеют совершенно разную структуру и свойства.
Другая игра на связность, в которую играют с бумагой и карандашом на прямоугольном множестве точек (или миллиметровой бумаге), — это детская игра « точки и коробки ». Игроки поочередно рисуют вертикальную или горизонтальную линию, соединяющую любые две соседние точки. Когда линия завершает квадрат, игрок ставит на квадрат инициалы. После того, как все строки будут заполнены, победителем становится игрок, занявший наибольшее количество клеток.
В расширение Гейла, называемое Qua, играют три игрока на трехмерном кубе игровой доски, состоящем из сетки N 3 клетки. N — нечетное число, равное количеству ячеек по граням куба игрового поля. Первоначальный макет игрового поля Qua Cube и правила описаны в статье Board Game Geek. [8]
Вычислительная сложность [ править ]
Явное решение игры с ненаправленным переключением было найдено в 1964 году для любой такой игры с использованием теории матроидов . Шорт должен стремиться к позиции, в которой существует набор вершин. включая две отмеченные вершины, а также два непересекающихся подмножества оставшихся невыбранных ребер, опирающихся на , такое, что любое из двух подмножеств (вместе с уже выбранными ребрами) соединяло бы все вершины в . Если Шорт может сделать ход, в результате которого появится позиция с этим свойством, то Шорт может выиграть независимо от того, что делает другой игрок; в противном случае Кат может победить. [2] [9]
В отличие от некоторых других игр с подключением, которые могут быть сложными для PSPACE , [10] [11] оптимальные ходы для игры с ненаправленным переключением можно найти за полиномиальное время на ход. После удаления из графа ребер, выбранных Cut , и сжатия ребер, выбранных Short , полученный граф является минорным по отношению к исходному графу. Задачу проверки существования двух непересекающихся деревьев, каждое из которых соединяет выделенные вершины, можно представить как задачу матроидного разбиения , которую можно решить за полиномиальное время. В качестве альтернативы ту же проблему можно решить, используя сетевых потоков алгоритмы .
См. также [ править ]
- TwixT , другая, более сложная игра с соединением на квадратной сетке.
Ссылки [ править ]
- ^ Гарднер, М. (1961). Вторая книга математических головоломок и развлечений Scientific American . Нью-Йорк: Саймон и Шустер. стр. 86–87.
- ↑ Перейти обратно: Перейти обратно: а б Леман, Альфред (1964). «Решение игры с переключением Шеннона». Журнал Общества промышленной и прикладной математики . 12 (4): 687–725. дои : 10.1137/0112059 . JSTOR 2946344 . МР 0173250 .
- ^ Хейворд, Райан Б.; ван Рейсвейк, Джек (2006). «Гекс и комбинаторика». Дискретная математика . 306 (19–20): 2515–2528. дои : 10.1016/j.disc.2006.01.029 . МР 2261917 .
- ^ Стивен М. Чейз (1972). «Реализованный графовый алгоритм для победы в играх с переключением Шеннона» . Коммуникации АКМ . 15 (4): 253–256. дои : 10.1145/361284.361293 . S2CID 21110956 .
- ^ Хамидун, Яхья Ульд; Лас Верньяс, Мишель (1986). «Направленное включение графов и матроидов». Журнал комбинаторной теории . Серия Б. 40 (3): 237–239. дои : 10.1016/0095-8956(86)90083-3 .
- ^ Клаудио, АП; Фонсека, С.; Секейра, Л.; Сильва, ИП (2015). «Игра переключения Шеннон и направленные варианты». В Бургиньоне, Ж.-П.; Йельч, Р.; Пинто, А.А.; Виана, М. (ред.). Динамика, игры и наука: Международная конференция и школа продвинутого уровня «Планета Земля», DGS II, Португалия, 28 августа – 6 сентября 2013 г. Серия CIM по математическим наукам. Спрингер. стр. 187–199. дои : 10.1007/978-3-319-16118-1_10 . ISBN 978-3-319-16117-4 .
- ^ Bridg-it на BoardGameGeek
- ^ «Ква» . Настольные игрыGeek . Проверено 28 августа 2020 г.
- ^ Мэнсфилд, Ричард (1996). «Стратегии игры с переключением Шеннона». Американский математический ежемесячник . 103 (3): 250–252. дои : 10.1080/00029890.1996.12004732 .
- ^ Эвен, С. (октябрь 1976 г.). «Комбинаторная задача, полная в полиномиальном пространстве» . Журнал АКМ . 23 (4): 710–719. дои : 10.1145/321978.321989 . S2CID 8845949 .
- ^ Райш, Стефан (1981). «Hex является PSPACE-полным». Акта Информатика . 15 (2): 167–191. дои : 10.1007/BF00288964 . МР 0599616 . S2CID 9125259 .
Внешние ссылки [ править ]
- Graph Game — Java-реализация игры с переключением Шеннона.