Перебрось мостик

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Перебрось мостик
BridgeIt2.svg
Кол-во игроков

2

Возраст

от 7 и выше

Время установки

~1 минута

Длительность партии

< 20 минут

Сложность правил

простая

Уровень стратегии

средний

Влияние случайности

отсутствует

Необходимые навыки

стратегическое мышление

«Перебрось мостик», бридж-ит, «трубопровод», «птичья клетка», переключательная игра Шеннона или игра Гейла — настольная игра типа гекса для двух игроков.[1][2] Игра придумана в середине XX века независимо Дэвидом Гейлом и Клодом Шенноном. Хотя в бридж-ит можно играть и на бумаге, американские производители игрушек делали игральные комплекты.[3]

Правила[править | править исходный текст]

1. Пустая доска  
2. Красные победили  
3. Выигрышная стратегия  
4. Автомат, играющий в «перебрось мостик» (объяснение ниже по тексту)  
5. «Графизация» игры, показывающая связь между классическим и обобщённым вариантом  

Игроки, красный и синий, проводят отрезки между двумя соседними точками своего цвета. Побеждает тот, кто сумел перебросить мостик от края до края доски: красный игрок по горизонтали, синий по вертикали.

Выигрышная стратегия[править | править исходный текст]

Первый игрок имеет выигрышную стратегию, это можно доказать методом заимствования стратегии. Простую и красивую стратегию впервые предложил О. Гросс.[1][2] Первый ход отмечен на рисунке 3. Когда второй игрок перечёркивает один конец тонкой чёрной линии, первый в ответ перечёркивает другой. По выражению Гросса, стратегия — «тупое оружие против тупого игрока, хитрое — против хитрого, но в том и другом случае ведёт к победе».

Такую стратегию можно реализовать даже простейшим автоматом из перемычек и лампочек, схема такого автомата показана на рисунке 4.[4] Первая лампочка подсвечивает первый ход автомата и горит постоянно. Остальные лампочки (ходы автомата) соединяются с гнёздами для перемычек (ходами человека), как показано на рисунке 3. Как только человек делает ход (вставляет перемычку в гнездо), загорается лампочка, означающая ответ автомата. Если вдруг человек «смухлюет» и сделает свой ход поверх мостика автомата, то же самое сделает и автомат.

Эту стратегию удавалось поместить в 7 шагов калькулятора Б3-34.[5]

Гекс, несмотря на внешнее сходство, совсем другая игра, поиск выигрышной стратегии для него — PSPACE-полная задача.

Обобщённый бридж-ит[править | править исходный текст]

6. Игрок «Закоротить» — зелёные рёбра, игрок «Вырубить» — пунктирные. Дальнейший ход игры форсированный и заканчивается победой вырубающего.

Если «соединить проводом» верхнюю и нижнюю синие кромки, красная и синяя сетки становятся двойственными графами. Другими словами, красный соединяет вершины плоского графа без мостов, синий — грани того же графа (рисунок 5). Можно отказаться от ограничений на граф, если заставить синего не соединять грани, а стирать рёбра. Поэтому у обобщённой игры правила получаются такие:

Есть произвольный мультиграф,[6] на котором отмечены две вершины А и Б. Игрок «Вырубить» своим ходом вырезает из графа ребро, игрок «Закоротить» фиксирует ребро, делая его неуязвимым к вырубанию. Закорачивающий выигрывает, если он смог зафиксировать маршрут от А до Б. Вырубающий — если он разделил эти вершины.[7]

У обобщённого бридж-ита также существует точное решение с использованием теории матроидов. Мы же докажем более простую теорему.

В зависимости от графа, выигрывает «Вырубить», «Закоротить» или делающий первый ход.

Легко подобрать простенькие графы с такими свойствами. Покажем, что четвёртая альтернатива — выигрывает второй — невозможна. А именно, пусть «Закоротить» выигрывает, играя вторым. Покажем, что он выиграет и первым.

«Закоротить» заимствует стратегию у самого себя. Первый ход он делает куда угодно. «Вырубить» ходит, «Закоротить» отвечает по стратегии, не обращая внимание на лишнее закороченное ребро. Может случиться, что стратегия предписывает сходить именно на это «лишнее» ребро, тогда создаём новое «лишнее», сходив куда угодно. Теорема доказана.

Примечания[править | править исходный текст]

  1. 1 2 Занимательные игры. Бридж-ит | Город игрушек
  2. 1 2 М. Гарднер Глава 5. Бридж-ит и другие игры // Математические досуги = New Mathematical Diversions from Scientific American + The Unexpected Hanging and Other Mathematical Diversions / Перевод с англ. Ю. А. Данилова. Под ред. Я. А. Смородинского. — М.: Оникс, 1995. — С. 58. — 496 с. — ISBN 5-88361-014-5
  3. BRIDG-IT | Image | BoardGameGeek
  4. Б. Игошев Перебрось мостик // Юный техник. — 1975. — № 4. — С. 71–73.
  5. Кузнецов С.Т., Распопов В.Б. Компьютерная азбука. — К.: Веселка, 1989. — 63 с.
  6. Обобщение до псевдографа бессмысленно: ходы в петли явно «самоубийственные».
  7. Грузман М. З. Упражнения // Логические игры с калькулятором / Под ред. И. Ф. Тесленко. — М.: Просвещение, 1991. — С. 141. — 160 с. — ISBN 5-09-001594-5

Ссылки[править | править исходный текст]