чавкать

Chomp для двух игроков, — это стратегическая игра в которую играют на прямоугольной сетке, состоящей из более мелких квадратных ячеек, которые можно рассматривать как блоки плитки шоколада . Игроки по очереди выбирают один блок и «съедают его» (снимают с доски) вместе с теми, что находятся под ним и справа от него. Левый верхний блок «отравлен», и игрок, съевший его, проигрывает.

Формулировка Chomp в виде шоколадной плитки принадлежит Дэвиду Гейлу , но эквивалентная игра, выраженная в терминах выбора делителей фиксированного целого числа, была опубликована ранее Фредериком Шухом .

Chomp — это особый случай частично упорядоченной игры , в которой частично упорядоченный набор , на котором ведется игра, представляет собой продукт общих порядков с удаленным минимальным элементом (ядовитым блоком).

Пример игры

Ниже показана последовательность ходов в типичной игре, начиная с полоски 5×4:

Игрок А съедает два блока из правого нижнего угла; Игрок Б съедает три из нижнего ряда; Игрок А берет блок справа от отравленного блока и съедает одиннадцать блоков; Игрок Б съедает три блока из оставшегося столбца, оставляя только отравленный блок. Игрок А должен съесть последний блок и поэтому проигрывает.

Обратите внимание: поскольку доказано, что игрок А может выиграть, начиная с полоски 5 × 4, по крайней мере один из ходов А является ошибкой.

Позиции в игре

Промежуточные позиции в Chomp m × n представляют собой целочисленные разбиения (невозрастающие последовательности натуральных чисел) λ ₁ ≥ λ ₂ ≥···≥ λ _r , причем λ ₁ ≤ n и р ≤ м . Их число представляет собой биномиальный коэффициент ${\binom {m+n}{n}}$ , который растет экспоненциально с m и n . ^[1]

Победа в игре

Chomp принадлежит к категории беспристрастных двух игроков игр с идеальной информацией для , что делает ее также анализируемой Нимом на основании теоремы Спрага – Гранди .

Для любой прямоугольной стартовой позиции, кроме 1×1, первый игрок может выиграть. Это можно продемонстрировать, используя аргумент о краже стратегии : предположим, что у второго игрока есть выигрышная стратегия против любого начального хода первого игрока. Предположим тогда, что первый игрок занимает только нижний правый квадрат. По нашему предположению, у второго игрока есть ответ на это, который обеспечит победу. Но если такой выигрышный ответ существует, первый игрок мог бы сделать его своим первым ходом и таким образом добиться победы. Следовательно, у второго игрока не может быть выигрышной стратегии.

Компьютеры могут легко рассчитать выигрышные ходы в этой игре на двумерной доске разумного размера. Однако, поскольку количество позиций растет в геометрической прогрессии, это невозможно для более крупных плат.

Для квадратной стартовой позиции (т. е. n × n для любого n ≥ 2) выигрышную стратегию можно легко указать явно. Первый игрок должен представить второму букву L , состоящую только из одного ряда и одного столбца одинаковой длины, соединенных в ядовитом квадрате. Затем, что бы второй игрок ни делал на одном плече L , первый игрок отвечает тем же ходом на втором плече, всегда снова предоставляя второму игроку симметричную L. форму В конце концов, этот L выродится в один ядовитый квадрат, и второй игрок проиграет.

Обобщения Чомпа

Трехмерный , состоящего из блоков , Chomp имеет начальную плитку шоколада в виде кубоида обозначенных как (i,j,k). Ход заключается в том, чтобы взять блок вместе с любым блоком, все индексы которого больше или равны соответствующему индексу выбранного блока. Точно так же Chomp можно обобщить на любое количество измерений.

Chomp иногда описывается численно. начальное натуральное число Дано , и игроки поочередно выбирают положительные делители исходного числа, но не могут выбирать 1 или кратное ранее выбранному делителю. Эта игра моделирует n- мерный Chomp, где исходное натуральное число имеет n простых множителей , а размеры доски Chomp задаются показателями степени простых чисел в его простой факторизации . В Ordinal Chomp играют на бесконечной доске, некоторые размеры которой являются порядковыми числами : например, полоска 2 × (ω + 4). Ход состоит в том, чтобы выбрать любой блок и удалить все блоки, оба индекса которых больше или равны соответствующим индексам выбранного блока. Случай ω × ω × ω Chomp — примечательная открытая проблема; было предложено вознаграждение в размере 100 долларов США ^[2] за поиск выигрышного первого хода.

В более общем смысле, в Chomp можно играть на любом частично упорядоченном наборе с наименьшим элементом . Ход заключается в удалении любого элемента вместе со всеми более крупными элементами. Игрок проигрывает, взяв наименьший элемент.

Во все разновидности Chomp также можно играть, не прибегая к яду, используя правило игры Misère : игрок, который съедает последний блок шоколада, не отравляется, а просто проигрывает, поскольку является последним игроком. Это идентично обычному правилу при игре в Chomp самостоятельно, но отличается при игре в дизъюнктивную сумму в играх Chomp, где проигрывает только последний последний блок шоколада.

См. также

Ссылки

^ Зейлбергер, Дорон (2001). «Трёхрядный ЧОМП» . Достижения прикладной математики . 26 (2): 168–179. дои : 10.1006/aama.2000.0714 .
^ с. 482 в: Игры без шансов (Р. Дж. Новаковски, изд.), Cambridge University Press, 1998.

Зейлбергер, Дорон (2004). «Чомп, рецидивы и хаос (?)». Дж. Диф. уравнение Приложение . 10 (13–15): 1281–1293. дои : 10.1080/10236190410001652720 .
Брауэр, А.Е.; Хорват, Габор; Молна-Саска, Ильдико; Сабо, Чаба (2005). «На трехрядном чавке» . Целые числа . 5 : #G07.
Фридман, Эйрк Дж. (2007). «Нелинейная динамика в комбинаторных играх: перенормировка Чомпа» . Хаос . 17 (2): 023117. Бибкод : 2007Хаос..17b3117F . дои : 10.1063/1.2725717 . ПМИД 17614671 .
Кхандхавит, Тирасан; Да, Линнель (2011). «Пережевывать графы и подмножества». arXiv : 1101.2718 [ math.CO ].
Солтыс, Майкл; Уилсон, Крейг (2011). «О сложности вычисления выигрышных стратегий для конечных игр с Посетом». Теория вычислений. Сист . 48 (3): 680–692. дои : 10.1007/s00224-010-9254-y . S2CID 2720334 .
Брауэр, А.Э. (2017). «Игра в чавканье» .
Чо, Ин Сон (2018). «Выигрышные стратегии игры в Чомп: практический подход». Дж. Историческая математика . 31 (3): 151–166. дои : 10.14477/jhm.2018.31.3.151 .

Внешние ссылки

[1] Зейлбергер, Дорон (2001). «Трёхрядный ЧОМП» . Достижения прикладной математики . 26 (2): 168–179. дои : 10.1006/aama.2000.0714 .

[2] с. 482 в: Игры без шансов (Р. Дж. Новаковски, изд.), Cambridge University Press, 1998.

[1]

[2]