| Перебрось мостик | |
|---|---|
 | |
| Игроков | 2 |
| Возраст | от 7 и выше |
| Подготовка к игре | ~1 минута |
| Длительность партии | < 20 минут |
| Сложность правил | простая |
| Уровень стратегии | средний |
| Влияние случайности | отсутствует |
| Развивает навыки | стратегическое мышление |
 | |
«Перебрось мостик», бридж-ит, «трубопровод», «птичья клетка», переключательная игра Шеннона или игра Гейла — абстрактная игра типа гекса для двух игроков[1][2]. Игра придумана в середине XX века независимо Дэвидом Гейлом и Клодом Шенноном. В 1958 году Мартин Гарднер показал игру широкой публике в своей колонке в Scientific American. Хотя в бридж-ит можно играть и на бумаге, американские производители игрушек делали игральные комплекты[3].
Правила
|
Игроки, красный и синий, проводят отрезки между двумя соседними точками своего цвета. Побеждает тот, кто сумел перебросить мостик от края до края доски: красный игрок по горизонтали, синий по вертикали.
Выигрышная стратегия
Хоть и неочевидно, но игра «перебрось мостик» беспристрастна. Для этого надо рассматривать пустые места между точками — если красный способен перечеркнуть какое-то пустое место, то и синий тоже.
Первый игрок при правильной игре победит, это неконструктивно доказывается методом заимствования стратегии (синий-первый заимствует стратегию у синего-второго) с учётом симметрии доски.
Простую и красивую стратегию впервые предложил О. Гросс[1][2]. Первый ход отмечен на рисунке 3. Когда второй игрок перечёркивает один конец тонкой чёрной линии, первый в ответ перечёркивает другой. По выражению Гросса, стратегия — «тупое оружие против тупого игрока, хитрое — против хитрого, но в том и другом случае ведёт к победе».
Такую стратегию можно реализовать даже простейшим автоматом из перемычек и лампочек, схема такого автомата показана на рисунке 4[4]. Первая лампочка подсвечивает первый ход автомата и горит постоянно. Остальные лампочки (ходы автомата) соединяются с гнёздами для перемычек (ходами человека), как показано на рисунке 3. Как только человек делает ход (вставляет перемычку в гнездо), загорается лампочка, означающая ответ автомата. Лампочки лучше располагать в вытянутых плафонах, имитирующих мостики. Если вдруг человек «смухлюет» и сделает свой ход поверх мостика автомата, то же самое сделает и автомат.
Эту стратегию удавалось поместить в 7 шагов калькулятора Б3-34[5]. Поскольку стратегия не требует никакой памяти, программа может вести сеанс одновременной игры.
Гекс, несмотря на внешнее сходство, совсем другая игра, поиск выигрышной стратегии для него — PSPACE-полная задача.
Обобщённый бридж-ит
Если левую и правую красные кромки стянуть в две вершины, а верхнюю и нижнюю синие — «соединить проводом» и стянуть в одну, красная и синяя сетки становятся двойственными графами. Другими словами, красный соединяет вершины плоского графа без мостов,[6] синий — грани того же графа (рисунок 5). Можно отказаться от ограничений на граф, если заставить синего не соединять грани, а стирать рёбра. Поэтому у обобщённой игры правила получаются такие:
Есть связный мультиграф,[7] на котором отмечены две вершины А и Б. Игрок «Вырубить» своим ходом вырезает из графа ребро, игрок «Закоротить» фиксирует ребро, делая его неуязвимым к вырубанию. Закорачивающий выигрывает, если он смог зафиксировать маршрут от А до Б. Вырубающий — если он разделил эти вершины[8].
У обобщённого бридж-ита также существует точное решение с использованием теории матроидов. Мы же докажем более простую теорему.
|
Легко подобрать простенькие графы с такими свойствами. Покажем, что четвёртая альтернатива — выигрывает второй — невозможна. А именно, пусть «Закоротить» выигрывает, играя вторым. Покажем, что он выиграет и первым.
«Закоротить»-первый заимствует стратегию у себя-второго. Первый ход он делает куда угодно. «Вырубить» ходит, «Закоротить» отвечает по стратегии, не обращая внимание на лишнее закороченное ребро. Может случиться, что стратегия предписывает сходить именно на это «лишнее» ребро, тогда создаём новое «лишнее», сходив куда угодно. Теорема доказана.
Примечания
- 1 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.
- ↑ BRIDG-IT | Image | BoardGameGeek
- ↑ Б. Игошев. Перебрось мостик // Юный техник. — 1975. — № 4. — С. 71–73.
- ↑ Кузнецов С.Т., Распопов В.Б. Компьютерная азбука. — К.: Веселка, 1989. — С. 36—40. — 63 с.
- ↑ Если граф не плоский — значит, у него нет граней. К мосту с обеих сторон примыкает одна и та же грань, так что непонятно, что соединять.
- ↑ Обобщение до псевдографа бессмысленно: ходы в петли явно «самоубийственные».
- ↑ Грузман М. З. Упражнения // Логические игры с калькулятором / Под ред. И. Ф. Тесленко. — М.: Просвещение, 1991. — С. 141. — 160 с. — ISBN 5-09-001594-5.
Ссылки
- Одна из реализаций игры на JS
- Глушанков Е., Певзнер П. Переключательная игра Шеннона (рус.) // Квант. — 1980. — № 9. — С. 14—21.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .