Перебрось мостик (HyjyQjkv, bkvmnt)
| Перебрось мостик | |
|---|---|
 | |
| Игроков | 2 |
| Возраст | от 7 и выше |
| Подготовка к игре | ~1 минута |
| Длительность партии | < 20 минут |
| Сложность правил | простая |
| Уровень стратегии | средний |
| Влияние случайности | отсутствует |
| Развивает навыки | стратегическое мышление |
 Медиафайлы на Викискладе | |
«Перебрось мостик», бридж-ит, «трубопровод», «птичья клетка», переключательная игра Шеннона или игра Гейла — абстрактная игра типа гекса для двух игроков[1][2]. Игра придумана в середине XX века Дэвидом Гейлом; одновременно Клод Шеннон исследовал обобщённый вариант. В 1958 году Мартин Гарднер показал игру широкой публике в своей колонке в Scientific American. Хотя в бридж-ит можно играть и на бумаге, компания Hassenfeld Brothers (ныне Hasbro) делала пластмассовые игральные комплекты[3].
Правила
[править | править код]-
1. Пустая доска -
2. Красные победили -
3. Выигрышная стратегия -
4. Автомат, играющий в «перебрось мостик» (объяснение ниже по тексту) -
5. «Графизация» игры, показывающая связь между классическим и обобщённым вариантом
Игроки, красный и синий, проводят отрезки между двумя соседними точками своего цвета. Побеждает тот, кто сумел перебросить мостик от края до края доски: красный игрок по горизонтали, синий по вертикали.
Выигрышная стратегия
[править | править код]Первый игрок при правильной игре победит, это неконструктивно доказывается методом заимствования стратегии (синий-первый заимствует стратегию у синего-второго) с учётом симметрии доски.
Простую и красивую стратегию впервые предложил О. Гросс[1][2]. Первый ход отмечен на рисунке 3. Когда второй игрок перечёркивает один конец тонкой чёрной линии, первый в ответ перечёркивает другой. По выражению Гросса, стратегия — «тупое оружие против тупого игрока, хитрое — против хитрого, но в том и другом случае ведёт к победе».
Такую стратегию можно реализовать даже простейшим автоматом из перемычек и лампочек, схема такого автомата показана на рисунке 4[4]. Первая лампочка подсвечивает первый ход автомата и горит постоянно. Остальные лампочки (ходы автомата) соединяются с гнёздами для перемычек (ходами человека), как показано на рисунке 3. Как только человек делает ход (вставляет перемычку в гнездо), загорается лампочка, означающая ответ автомата. Лампочки лучше располагать в вытянутых плафонах, имитирующих мостики. Если вдруг человек «смухлюет» и сделает свой ход поверх мостика автомата, то же самое сделает и автомат.
Стратегию Гросса удавалось поместить в 7 шагов калькулятора Б3-34[5]. Поскольку стратегия не требует никакой памяти, программа может вести сеанс одновременной игры.
Гекс, несмотря на внешнее сходство, совсем другая игра, поиск выигрышной стратегии для него — PSPACE-полная задача.
Обобщённый бридж-ит
[править | править код]
Если левую и правую красные кромки стянуть в две вершины, а верхнюю и нижнюю синие — «соединить проводом» и стянуть в одну, красная и синяя сетки становятся двойственными графами. Другими словами, красный соединяет вершины плоского графа без мостов,[6] синий — грани того же графа (рисунок 5). Можно отказаться от ограничений на граф, если заставить синего не соединять грани, а стирать рёбра. Поэтому у обобщённой игры правила получаются такие:
Есть связный мультиграф,[7] на котором отмечены две вершины А и Б. Игрок «Вырубить» своим ходом вырезает из графа ребро, игрок «Закоротить» фиксирует ребро, делая его неуязвимым к вырубанию. Закорачивающий выигрывает, если он смог зафиксировать маршрут от А до Б. Вырубающий — если он разделил эти вершины[8].
Легко видеть, что в зависимости от графа выигрывает «Вырубить», «Закоротить» или делающий первый ход. У обобщённого бридж-ита также существует стратегия, описанная на языке матроидов.[9]
Примечания
[править | править код]- ↑ 1 2 Занимательные игры. Бридж-ит | Город игрушек. Дата обращения: 29 июля 2013. Архивировано из оригинала 11 апреля 2013 года.
- ↑ 1 2 М. Гарднер. Глава 5. Бридж-ит и другие игры // Математические досуги = New Mathematical Diversions from Scientific American + The Unexpected Hanging and Other Mathematical Diversions / Перевод с англ. Ю. А. Данилова. Под ред. Я. А. Смородинского. — М.: Оникс, 1995. — С. 58. — 496 с. — ISBN 5-88361-014-5.
- ↑ BRIDG-IT | Image | BoardGameGeek. Дата обращения: 31 июля 2013. Архивировано 22 ноября 2011 года.
- ↑ Б. Игошев. Перебрось мостик // Юный техник. — 1975. — № 4. — С. 71—73.
- ↑ Кузнецов С.Т., Распопов В.Б. Компьютерная азбука. — К.: Веселка, 1989. — С. 36—40. — 63 с.
- ↑ Если граф не плоский — значит, у него нет граней. К мосту с обеих сторон примыкает одна и та же грань, так что непонятно, что соединять.
- ↑ Обобщение до псевдографа бессмысленно: ходы в петли явно «самоубийственные».
- ↑ Грузман М. З. Упражнения // Логические игры с калькулятором / Под ред. И. Ф. Тесленко. — М.: Просвещение, 1991. — С. 141. — 160 с. — ISBN 5-09-001594-5. Архивировано 25 октября 2014 года.
- ↑ Lehman, Alfred. A solution of the Shannon switching game (англ.) // Journal of the Society for Industrial and Applied Mathematics[англ.] : journal. — 1964. — Vol. 12, no. 4. — P. 687—725. — .
Ссылки
[править | править код]- Одна из реализаций игры на JS Архивная копия от 14 августа 2013 на Wayback Machine
- Глушанков Е., Певзнер П. Переключательная игра Шеннона // Квант. — 1980. — № 9. — С. 14—21.