Hackenbush - это игра для двух игроков, изобретенная математиком Джоном Хортоном Конвеем . [1] В нее можно играть на любой конфигурации цветных сегментов линии, соединенных друг с другом своими концами и с линией «земли».
Геймплей [ править ]
Игра начинается с того, что игроки рисуют линию «земли» (обычно, но не обязательно, горизонтальную линию внизу листа бумаги или другой игровой площадки) и несколько сегментов линии, так что каждый сегмент линии соединяется с землей либо напрямую. в конечной точке или косвенно через цепочку других сегментов, соединенных конечными точками. В одной точке может встречаться любое количество сегментов, и, следовательно, может быть несколько путей к земле.
В свой ход игрок «обрезает» (стирает) любой отрезок линии по своему выбору. Каждый сегмент линии, больше не связанный с землей каким-либо путем, «падает» (т.е. стирается). Согласно обычному игровому соглашению комбинаторной теории игр, первый игрок, который не может сделать ход, проигрывает.
Доски Hackenbush могут состоять из конечного числа (в случае «конечной доски») или бесконечного числа (в случае «бесконечной доски») отрезков прямых. Существование бесконечного числа отрезков линии не нарушает предположение теории игр о том, что игра может быть завершена за конечный промежуток времени, при условии, что только конечное число отрезков прямой «касается» земли. На бесконечной доске, в зависимости от ее расположения, игра может продолжаться бесконечно, при условии, что бесконечно много точек касается земли.
Варианты [ править ]
В оригинальной фольклорной версии «Хакенбуша» любому игроку разрешено «обрезать» любое преимущество: поскольку это беспристрастная игра, сравнительно просто провести полный анализ, используя теорему Спрага – Гранди . Таким образом, версии Хакенбуша, представляющие интерес для комбинаторной теории игр, являются более сложными партизанскими играми , а это означает, что варианты (ходы), доступные одному игроку, не обязательно были бы доступны другому игроку, если бы настала его очередь двигаться с той же позицией. . Это достигается одним из двух способов:
- Оригинальный Hackenbush: все линейные сегменты одного цвета и могут быть разрезаны любым игроком. Это означает, что выплаты симметричны, и каждый игрок выполняет одни и те же операции в зависимости от положения на доске (в данном случае структура розыгрыша).
- Сине-красный куст Hackenbush : каждый сегмент линии окрашен в красный или синий цвет. Одному игроку (обычно первому или левому) разрешается разрезать только синие отрезки линии, а другому игроку (обычно второму или правому игроку) разрешается отрезать только красные отрезки линии.
- Сине-красный-зеленый куст Hackenbush : каждый сегмент линии окрашен в красный, синий или зеленый цвет. Правила такие же, как и для сине-красного хакенбуша, с дополнительным условием, что зеленые отрезки линии могут быть отрезаны любым игроком.
Blue-Red Hackenbush - это просто частный случай Blue-Red-Green Hackenbush, но его стоит отметить отдельно, поскольку его анализ часто намного проще. Это потому, что сине-красный хакенбуш - это так называемая холодная игра , что, по сути, означает, что первый ход никогда не может быть преимуществом.
Анализ [ править ]
Hackenbush часто использовался в качестве примера игры для демонстрации определений и концепций комбинаторной теории игр , начиная с его использования в книгах « О числах и играх» и « Выигрышные способы для ваших математических игр», написанных некоторыми из основателей этой области. В частности, Blue-Red Hackenbush может использоваться для построения сюрреалистических чисел, таких как nimbers : конечные сине-красные доски Hackenbush могут создавать двоичные рациональные числа , в то время как значения бесконечных сине-красных досок Hackenbush учитывают действительные числа , порядковые числа., и многие другие общие ценности, которые ни тем, ни другим Сине-красный-зеленый Hackenbush позволяет создавать дополнительные игры, значения которых не являются действительными числами, например, звезды и все другие нимберы .
Дальнейший анализ игры может быть проведен с помощью теории графов , рассматривая доску как набор вершин и ребер и исследуя пути к каждой вершине, лежащей на земле (которую следует рассматривать как выделенную вершину - не помешает идентифицировать все точки земли вместе, а не в виде линии на графике).
В беспристрастной версии Hackenbush (в которой цвета не указаны игроком) можно подумать об использовании кучи нимов, разбив игру на несколько случаев: вертикальный, сходящийся и расходящийся. Игра, в которой используются только вертикальные стеки отрезков линий, также называемые бамбуковыми стеблями, напрямую превращается в Ним и может быть непосредственно проанализирована как таковая. Расходящиеся сегменты или деревья добавляют игре дополнительную морщину и требуют использования принципа двоеточия.утверждая, что когда ветви сходятся в вершине, можно заменить ветви неразветвленным стеблем, длина которого равна их ним-сумме. Этот принцип изменяет представление игры на более простую версию стеблей бамбука. Последний возможный набор графов, который можно создать, - это сходящиеся графы, также известные как графы с произвольным корнем. Используя принцип слияния, мы можем утверждать, что все вершины любого цикла могут быть слиты вместе без изменения значения графа. [2] Следовательно, любой сходящийся граф можно также интерпретировать как простой граф бамбукового стебля. Комбинируя все три типа графиков, мы можем усложнить игру, не изменяя при этом сумму нима игры, тем самым позволяя игре использовать стратегии Нима.
Доказательство принципа двоеточия [ править ]
Принцип толстой кишки гласит, что, когда ветви сходятся в вершине, можно заменить ветви неразветвленным стеблем, длина которого равна их ним-сумме. Рассмотрим фиксированную , но произвольный граф, G , и выберите произвольную вершину, х , в G . Пусть H 1 и H 2 - произвольные деревья (или графы), которые имеют одинаковое значение Спрага-Гранди. Рассмотрим два графа G 1 = G x : H 1 и G 2 = G x : H 2 , где G x : Hя представляю собой графикпостроенный путем присоединения дерева H I к вершине х графа G . Принцип двоеточия гласит, что два графика G1 и G2 имеют одинаковое значение Спрага-Гранди. Рассмотрим сумму двух игр, как на рисунке 5.4. Утверждение, что G 1 и G 2 имеют одинаковое значение Спрага-Гранди, эквивалентно утверждению, что сумма двух игр имеет значение Спрага-Гранди 0. Другими словами, мы должны показать, что сумма G 1 + G 2 П-позиция. Игрок гарантированно выиграет, если он будет вторым игроком, который перейдет в игру.Г 1 + Г 2 . Если первый игрок перемещается, рубя одно из ребер в G в одной из игр, то второй игрок рубит то же самое ребро в G в другой игре. (Такая пара ходов может удалить H 1 и H 2 из игр, но в противном случае H 1 и H 2 не будут нарушены.) Если первый игрок перемещается, рубя ребро в H 1 или H 2 , то алгоритм Спрага-Гранди значения H 1 и H 2 больше не равны, так что существует ход вH 1 или H 2 , при котором значения Спраг-Гранди остаются неизменными. Таким образом, у вас всегда будет ответ на каждое его движение. Это означает, что вы сделаете последний ход и выиграете. [3]
Пример, в котором игра может быть сокращена с помощью принципа двоеточия.
Ссылки [ править ]
- ^ Что такое Хакенбуш? на geometer.org
- ^ Р., Берлекамп, Элвин (2001–2004). Выигрышные пути для ваших математических игр . Конвей, Джон Х. (Джон Хортон), Гай, Ричард К. (2-е изд.). Натик, Массачусетс: AK Peters. ISBN 9781568811420. OCLC 45102937 .
- ^ Фергюсон, Томас С. (осень 2000 г.). «Теория игр» (PDF) .
- Джон Х. Конвей, О числах и играх , 2-е издание, AK Peters, 2000.
Внешние ссылки [ править ]
 | Викискладе есть медиафайлы по теме игры Hackenbush . |
- Hackenstrings и 0,999 ... vs. 1
- Хакенбуш о карандашно-бумажных играх
