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