Игра с переключением Шеннона
-
История и правила игры
- Игра Шеннона с переключением изобретена Клодом Шенноном в 1951 году.
- Игроки по очереди раскрашивают ребра графа, стремясь соединить две вершины.
- Игра обычно играется на прямоугольной сетке.
-
Варианты игры
- Игра Gale, изобретенная Дэвидом Гейлом, эквивалентна игре Шеннона на прямоугольной сетке.
- Игра «Шторм» также эквивалентна игре Шеннона, но на двух сетках.
-
Вычислительная сложность
- Явное решение для игры с неориентированным переключением найдено в 1964 году.
- Оптимальные ходы можно найти за полиномиальное время.
-
Связь с другими играми
- Игра «Переключение Шеннона» связана с игрой «Создатель-разрушитель».
- Игра Hex со слабосвязанными соединениями имеет 6 уровней связности.
- Игра «точки и квадратики» также связана с игрой на связность.
-
Дополнительные игры
- Игра Qua играет на трехмерном игровом поле-кубе.
- Игра TwixT — более сложная игра с подключением на квадратной сетке.