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