Хакенбуш — игра для двух игроков, придуманная математиком Джоном Хортоном Конвеем . [1] В неё можно играть на любой конфигурации цветных отрезков линий, соединённых друг с другом конечными точками и с «землёй».
Игра начинается с того, что игроки рисуют линию «земли» (обычно, но не обязательно, горизонтальную линию внизу бумаги или другой игровой области) и несколько отрезков таким образом, чтобы каждый отрезок был соединен с землей, либо напрямую в конечной точке, либо косвенно, через цепочку других отрезков, соединенных конечными точками. Любое количество отрезков может встретиться в одной точке, и, таким образом, может быть несколько путей к земле.
В свой ход игрок «отрезает» (стирает) любой отрезок линии по своему выбору. Каждый отрезок линии, больше не соединенный с землей никаким путем, «падает» (т. е. стирается). Согласно обычному игровому соглашению комбинаторной теории игр, первый игрок, который не может сделать ход, проигрывает.
Доски Хакенбуша могут состоять из конечного числа (в случае «конечной доски») или бесконечного числа (в случае «бесконечной доски») отрезков прямых. Существование бесконечного числа отрезков прямых не нарушает предположение теории игр о том, что игру можно закончить за конечное время, при условии, что только конечное число отрезков прямых непосредственно «касаются» земли. На бесконечной доске, исходя из ее расположения, игра может продолжаться вечно, при условии, что земли касается бесконечное число точек.
В оригинальной фольклорной версии Hackenbush любому игроку разрешено срезать любое ребро: поскольку это беспристрастная игра , сравнительно просто дать полный анализ с использованием теоремы Спрага–Гранди . Таким образом, версии Hackenbush, представляющие интерес в комбинаторной теории игр, являются более сложными партизанскими играми , что означает, что варианты (ходы), доступные одному игроку, не обязательно будут теми, которые доступны другому игроку, если бы была его очередь ходить, учитывая ту же позицию. Это достигается одним из двух способов:
Blue-Red Hackenbush — это всего лишь частный случай Blue-Red-Green Hackenbush, но его стоит отметить отдельно, так как его анализ часто намного проще. Это потому, что Blue-Red Hackenbush — это так называемая холодная игра , что означает, по сути, что первый ход никогда не может быть преимуществом.
Hackenbush часто использовался в качестве примера игры для демонстрации определений и концепций в комбинаторной теории игр , начиная с его использования в книгах On Numbers and Games и Winning Ways for Your Mathematical Plays некоторыми основателями этой области. В частности, Blue-Red Hackenbush может использоваться для построения сюрреалистических чисел : конечные доски Blue-Red Hackenbush могут строить двоичные рациональные числа , в то время как значения бесконечных досок Blue-Red Hackenbush учитывают действительные числа , порядковые числа и многие другие общие значения, которые не являются ни тем, ни другим. Blue-Red-Green Hackenbush позволяет строить дополнительные игры, значения которых не являются действительными числами, такие как star и все другие nimbers .
Дальнейший анализ игры можно провести с помощью теории графов , рассматривая доску как совокупность вершин и ребер и исследуя пути к каждой вершине, лежащей на земле (которую следует рассматривать как выделенную вершину — не помешает идентифицировать все точки земли вместе — а не как линию на графе).
В беспристрастной версии Hackenbush (той, в которой нет цветов, определяемых игроком) можно рассматривать использование ним-куч, разбив игру на несколько случаев: вертикальный, сходящийся и расходящийся. Играя исключительно с вертикальными стопками отрезков прямых, также называемых бамбуковыми стеблями, игра сразу становится нимом и может быть напрямую проанализирована как таковая. Расходящиеся отрезки, или деревья, добавляют в игру дополнительную сложность и требуют использования принципа двоеточия, гласящего, что когда ветви сходятся в вершине, можно заменить ветви неветвящимся стеблем длины, равной их сумме ним . Этот принцип изменяет представление игры на более базовую версию бамбуковых стеблей. Последний возможный набор графов, которые можно сделать, — это сходящиеся, также известные как графы с произвольными корнями. Используя принцип слияния, мы можем утверждать, что все вершины на любом цикле могут быть слиты вместе без изменения значения графа. [3] Следовательно, любой сходящийся граф также можно интерпретировать как простой граф бамбуковых стеблей. Объединив все три типа графиков, мы можем повысить сложность игры, не меняя при этом сумму нимов игры, тем самым позволяя игре использовать стратегии нимов.
Принцип двоеточия гласит, что когда ветви сходятся в вершине, можно заменить ветви неветвящимся стеблем длины, равной их сумме нимов. Рассмотрим фиксированный, но произвольный граф G и выберем произвольную вершину x в G. Пусть H 1 и H 2 — произвольные деревья (или графы), имеющие одинаковое значение Шпрага-Гранди. Рассмотрим два графа G 1 = G x : H 1 и G 2 = G x : H 2 , где G x : H i представляет граф, построенный путем присоединения дерева H i к вершине x графа G. Принцип двоеточия гласит, что два графа G1 и G2 имеют одинаковое значение Шпрага-Гранди. Рассмотрим сумму двух игр. Утверждение, что G 1 и G 2 имеют одинаковое значение Шпрага-Гранди, эквивалентно утверждению, что сумма двух игр имеет значение Шпрага-Гранди 0. Другими словами, мы должны показать, что сумма G 1 + G 2 является P-позицией. Игрок гарантированно выиграет, если он будет вторым игроком, который сделает ход в G 1 + G 2 . Если первый игрок делает ход, рубя одно из ребер в G в одной из игр, то второй игрок рубит то же самое ребро в G в другой игре. (Такая пара ходов может удалить H 1 и H 2 из игр, но в противном случае H 1 и H 2 не будут нарушены.) Если первый игрок делает ход, рубя ребро в H 1 или H 2 , то значения Шпрага-Гранди для H 1 и H 2 больше не равны, так что существует ход в H 1 или H 2 , который сохраняет значения Шпрага-Гранди прежними. Таким образом, у вас всегда будет ответ на каждый его ход. Это значит, что вы сделаете последний ход и выиграете. [4]
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )