WikiDer > Игра с переключением Шеннона

Shannon switching game

В Игра с переключением Шеннона это игра подключения для двух игроков, изобретенный Американец математик и инженер-электрик Клод Шеннон, "отец теории информации" незадолго до 1951 года.[1] Два игрока по очереди раскрашивают края произвольной график. У одного игрока есть цель соединить две выделенные вершины путем из ребер своего цвета. Другой игрок стремится предотвратить это, используя вместо этого свой цвет (или, что то же самое, стирая края). В игру обычно играют на прямоугольная сетка; этот частный случай игры был независимо изобретен американским математиком Дэвид Гейл в конце 1950-х годов и известен как Гейл или же Bridg-It.[2][3]

Правила

Player Cut сделал 3 хода (пунктирные края), игрок Short сделал 4 хода (зеленые края).

Игра ведется на конечном график с двумя специальными узлами, А и B. Каждое ребро графа можно раскрасить или удалить. Двух игроков называют короткий и Резать, и альтернативные ходы. На Резать В свою очередь, он удаляет из графа выбранное нецветное ребро. На короткий В свою очередь, он закрашивает любое ребро, оставшееся на графе. Если Резать удается превратить график в такой, где А и B больше не связаны, он побеждает. Если короткий удается создать цветной путь из А к B, он побеждает. Игра всегда заканчивается после конечного числа ходов, и один из двух игроков должен выиграть. Либо короткий, Резать, или игроку, идущему первым, гарантируется существование выигрышной стратегии на любом заданном графе.[4]

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

Варианты

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

Гейл

Победа красных в Гейле

В этой игре, изобретенной американским математиком Дэвид Гейл и описано в Мартин Гарднерстолбец в Scientific American Октябрь 1958 г., две сетки разноцветных точек наложены со смещением. Один игрок связывает ортогонально соседние точки на одной сетке, а другой игрок использует другую. Один игрок пытается связать верхнюю часть своей сетки с низом, а другой пытается связать свою левую сторону с правой. Игра эквивалентна игре переключения Шеннона на прямоугольной сетке. Ничья не может закончиться; при правильной игре всегда может выиграть первый игрок.

Коммерческая настольная игра, реализующая эту схему, была продана в 1960 году компанией Братья Хассенфельд под названием Bridg-It.[7] Игра состояла из пластиковой доски с двумя чередующимися прямоугольными решетками пьедесталов 5x6 (один - желтым, другой - красным), двумя наборами по 20 красных и желтых пластиковых мостов каждый и соответствующими колышками для их крепления. Игроки попеременно устанавливают мост через любые два соседних постамента соответствующего цвета, пока один из игроков не соединит две противоположные стороны доски, отмеченные цветом игрока. В инструкциях описан вариант игры: каждый игрок получает ограниченное количество мостов, скажем 10. Если ни один из игроков не выиграл, когда все мосты установлены, игрок в свою очередь может переставлять один из своих мостов до тех пор, пока не станет победителем. полученные результаты. Игра давно снята с производства.

Электронная реализация Игры Бурь доступна в Портал Ludii Games.

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

Игру переключения Шеннона можно рассматривать как частный случай Maker-Breaker игра, в котором выигрышные модели для Создателя - это соединительные пути.

Слабосвязанная игра связи Шестигранник Играется на сетке из шестиугольников и имеет 6 соединений. Обобщенный Hex используется на графе, как и игра Шеннона, но вместо того, чтобы раскрашивать ребра, в Hex игроки раскрашивают вершины. Эти игры имеют совершенно разную структуру и свойства.

Еще одна игра, в которую играют с бумагой и карандашом на прямоугольном массиве точек (или миллиметровой бумаге), - это детская игра "точки и квадраты". Игроки поочередно рисуют вертикальную или горизонтальную линию, соединяющую любые две соседние точки. Когда линия завершает квадрат, игрок инициализирует квадрат. После того, как все линии заполнены, игрок, который взял наибольшее количество квадратов, становится победителем. .

В расширение Gale, называемое Qua, играют три игрока на трехмерном игровом настольном кубе, состоящем из сетки из N3 клетки. N - нечетное число, равное количеству ячеек по краям куба игрового поля. Первоначальный макет и правила игровой доски Qua Cube описаны в его записи Board Game Geek.[8]

Вычислительная сложность

Явное решение для игры с неориентированным переключением было найдено в 1964 году для любой такой игры с использованием матроид теория. короткий должен стремиться к позиции, в которой существуют два непересекающихся подмножества оставшихся невыбранных ребер, так что любое из двух подмножеств соединит две выделенные вершины. Если короткий может сделать ход, который приведет к позиции с этим свойством, тогда короткий может выиграть независимо от того, что делает другой игрок; иначе, Резать может выиграть.[2]

В отличие от некоторых других игр с подключением, которые можно PSPACE жесткий,[9][10] оптимальные ходы для неориентированной игры переключения можно найти в полиномиальное время за ход. После удаления из графа ребер, выбранных Резать, и стягивая края, выбранные короткий, получившийся граф является незначительный начального графа. Задачу проверки существования двух непересекающихся деревьев, каждое из которых соединяет выделенные вершины, можно представить в виде разделение матроидов задача, которую можно решить за полиномиальное время. В качестве альтернативы можно решить ту же проблему, используя сетевой поток алгоритмы.

Смотрите также

  • TwixT, другая и более сложная игра на квадратную сетку

Рекомендации

  1. ^ Гарднер, М. (1961). Вторая книга журнала Scientific American по математическим головоломкам и решениям. Нью-Йорк: Саймон и Шустер. С. 86–87.
  2. ^ а б Леман, Альфред (1964). «Решение игры переключения Шеннона». Журнал Общества промышленной и прикладной математики. 12 (4): 687–725. JSTOR 2946344. МИСТЕР 0173250.
  3. ^ Хейворд, Райан Б .; ван Рейсвейк, Джек (2006). «Шестиугольник и комбинаторика». Дискретная математика. 306 (19–20): 2515–2528. Дои:10.1016 / j.disc.2006.01.029. МИСТЕР 2261917.
  4. ^ Стивен М. Чейз (1972). «Реализованный алгоритм графа для победы в играх Шеннона по переключению». Коммуникации ACM. 15 (4): 253–256. Дои:10.1145/361284.361293.
  5. ^ Хамидун, Яхья Ульд; Лас Вергнас, Мишель (1986). "Направленное переключение графиков и матроидов". Журнал комбинаторной теории. Серия Б. 40 (3): 237–239. Дои:10.1016/0095-8956(86)90083-3.
  6. ^ Cláudio, A. P .; Fonseca, S .; Sequeira, L .; Сильва, И. П. (2015). «Игра переключения Шеннона и направленные варианты». In Bourguignon, J.-P .; Jeltsch, R .; Pinto, A.A .; Виана, М. (ред.). Динамика, игры и наука: Международная конференция и продвинутая школа Planet Earth, DGS II, Португалия, 28 августа - 6 сентября 2013 г.. Серия CIM по математическим наукам. Springer. С. 187–199. Дои:10.1007/978-3-319-16118-1_10. ISBN 978-3-319-16117-4.
  7. ^ Bridg-it в НастольнаяИграГик
  8. ^ "Qua". НастольнаяИграГик. Получено 2020-08-28.
  9. ^ Даже С. (Октябрь 1976 г.). «Комбинаторная задача, полная в полиномиальном пространстве». Журнал ACM. 23 (4): 710–719. Дои:10.1145/321978.321989.
  10. ^ Райш, Стефан (1981). "Hex ist PSPACE-vollständig". Acta Informatica. 15 (2): 167–191. Дои:10.1007 / BF00288964. МИСТЕР 0599616.

внешняя ссылка