Шеннон переключение игры
Игра с переключением Шеннона — это игра-соединение для двух игроков, изобретенная американским математиком и инженером-электриком Клодом Шенноном , «отцом теории информации» незадолго до 1951 года. [1] Два игрока по очереди раскрашивают ребра произвольного графа . У одного игрока есть цель соединить две отмеченные вершины путем ребер их цвета. Другой игрок стремится предотвратить это, используя вместо этого свой цвет (или, что то же самое, стирая края). В игру обычно играют на прямоугольной сетке ; этот частный случай игры был независимо изобретен американским математиком Дэвидом Гейлом .в конце 1950-х годов и известен как Гейл или Бридж-Ит . [2] [3]
Игра ведется на конечном графе с двумя специальными узлами , A и B. Каждое ребро графа можно раскрасить или удалить. Два игрока называются Short and Cut и чередуют ходы. В свой ход Cut, Cut удаляет из графа неокрашенное ребро по своему выбору. В свой ход Шорт раскрашивает любое ребро, оставшееся на графике. Если Cut удается превратить граф в такой, в котором A и B больше не связаны, Cut побеждает. Если Шорту удастся создать цветной путь от А до Б, Шорт выигрывает. Игра всегда заканчивается после конечного числа ходов, и один из двух игроков должен победить. Либо Short, Cut, либо игрок, идущий первым, гарантирует существование выигрышной стратегии на любом заданном графике. [4]
Игры Short and Cut — это двойственность; то есть игру можно переформулировать так, чтобы у обоих игроков была одна и та же цель: получить определенный набор ребер с выделенным ребром e . Short пытается защитить набор ребер, который с e составляет цепь , а Cut пытается защитить набор ребер, который с e составляет набор разрезов, минимальный набор ребер, соединяющих два подграфа .
Версии игры переключения Шеннона, играемой на ориентированном графе и ориентированном матроиде , были описаны для теоретических целей; [5] [6] , но соответствующие коммерческие игры не были опубликованы.
В этой игре, изобретенной американским математиком Дэвидом Гейлом и описанной в колонке Мартина Гарднера в журнале Scientific American за октябрь 1958 года, две сетки разноцветных точек накладываются друг на друга со смещением. Один игрок связывает ортогонально соседние точки на одной сетке, а другой игрок использует другую. Один игрок пытается связать верхнюю часть своей сетки с нижней, а другой пытается связать свою левую сторону с правой. Игра эквивалентна игре переключения Шеннона, в которую играют на прямоугольной сетке. Ничья не может быть результатом; первый игрок всегда может выиграть при правильной игре.
Коммерческая настольная игра, реализующая эту схему, была продана в 1960 году компанией Hassenfeld Brothers под названием Bridg-It. [7]Игра состояла из пластиковой доски с двумя чередующимися прямоугольными сетками пьедесталов 5x6 (одна желтая, другая красная), два набора по 20 красных и желтых пластиковых мостов и соответствующие штифты для их крепления. Игроки поочередно размещают мост через любые два соседних пьедестала соответствующего цвета, пока один из игроков не соединит две противоположные стороны доски, отмеченные цветом игрока. В инструкции описан вариант игры: каждый игрок получает ограниченное количество мостов, скажем, 10. Если ни один из игроков не выиграл, когда все мосты расставлены, игрок в свою очередь может переставить один из своих мостов до тех пор, пока не выявится победитель. Результаты. Игра давно снята с производства.
