Посет игра

В теории игр комбинаторной ЧУМ-игры — это математические стратегические игры , обобщающие многие известные игры, такие как Ним и Чомп . ^[1] В таких играх два игрока начинают с ЧУ ( частично упорядоченного множества ) и по очереди выбирают одну точку в ЧУ, удаляя её и все точки, которые больше. Игрок, у которого не осталось выбора, проигрывает.

Геймплей

Учитывая частично упорядоченный набор ( P , <), пусть

P_{x}=P-\{a\mid a\geq x\}

обозначаем ЧУУ, образованную x из P. удалением

Частная игра на P , в которую играют два игрока, условно называемых Алисой и Бобом , выглядит следующим образом:

Алиса выбирает точку x ∈ P ; таким образом заменяя P на Px _Px , а затем передает ход Бобу, который играет на , _и передает ход Алисе.
Игрок проигрывает, если настал его ход и у него нет очков для выбора.

Примеры

Если P — конечное полностью упорядоченное множество , то ход игры в P точно такой же, как ход игры в игре Ним с кучей размера | П |. Ибо в обеих играх можно выбрать ход, который приведет к игре того же типа, размер которой равен любому числу, меньшему | П |. Точно так же игра в частичном наборе с непересекающимся объединением полных порядков эквивалентна игре Ним с множеством куч с размерами, равными цепям в частичном наборе.

Особый случай Хакенбуша , в котором все ребра зеленые (могут быть разрезаны любым игроком) и каждая конфигурация принимает форму леса , может быть выражен аналогичным образом как игра в частичном наборе на частичном множестве, в которой для каждого элемента x существует не более одного элемента y, для которого x покрывает y . Если x покрывает y , то y является родителем x в лесу, в котором ведется игра.

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

Значение Гранди

Poset-игры являются беспристрастными играми , а это означает, что каждый ход, доступный Алисе, также был бы доступен Бобу, если бы Алисе было позволено пройти , и наоборот. Следовательно, по теореме Спрага–Грунди каждая позиция в игре с ЧУМ имеет значение Гранди, число, описывающее эквивалентную позицию в игре Ним. Значение Гранди частичного набора может быть рассчитано как наименьшее натуральное число, которое не является значением Гранди ни для какого P _x , x ∈ P . То есть, ^[2]

G(P)=\min {\bigl (}\mathbb {N} \setminus \{G(P_{x})\mid x\in P\}{\bigr )}.

Это число можно использовать для описания оптимального игрового процесса в частично-определенной игре. В частности, значение Гранди не равно нулю, когда игрок, чей ход имеет выигрышную стратегию, и нулю, когда текущий игрок не может выиграть при оптимальной игре своего противника. Выигрышная стратегия в игре состоит в переходе к позиции, значение Гранди которой равно нулю, когда это возможно.

Стратегия воровства

показывает Аргумент кражи стратегии , что значение Гранди не равно нулю для каждого ЧУ-множества, имеющего супремум . Действительно, пусть x верхняя грань частично упорядоченного множества P. — Если P _x имеет нулевое значение Гранди, то P сам по себе имеет ненулевое значение по приведенной выше формуле; в этом случае x выигрышный ход в P. — Если, с другой стороны, P _x имеет ненулевое значение Гранди, то должен существовать выигрышный ход y в P _x , такой, что значение Гранди ( P _x ) _y равно нулю. Но если предположить, что x является супремумом, то x > y и ( P _x ) _y = P _y , поэтому выигрышный ход y также доступен в P , и снова P должно иметь ненулевое значение Гранди. ^[1]

По более тривиальным причинам ЧУМ с нижней границей также имеет ненулевое значение Гранди: переход к нижней нижней границе всегда является выигрышным ходом.

Сложность

Определение победителя в произвольной конечной игре с ЧУП является PSPACE-полным . ^[3] Это означает, что, если P = PSPACE, вычисление значения Гранди произвольной игры с ЧУМ является вычислительно трудным.

Ссылки

^ Перейти обратно: ^а ^б Солтыс, Майкл; Уилсон, Крейг (2011), «О сложности вычисления выигрышных стратегий для игр с конечным ЧУУ», Theory of Computing Systems , 48 (3): 680–692, CiteSeerX 10.1.1.150.3656 , doi : 10.1007/s00224-010- 9254-у , МР 2770813 , S2CID 2720334 .
^ Бирнс, Стивен (2003), «Периодичность игры Посет» (PDF) , Целые числа , 3 (G3): 1–16, MR 2036487 .
^ Гриер, Дэниел (2012), «Определение победителя в произвольной игре с конечными числами ЧП является PSPACE-полной», Автоматы, языки и программирование , Конспекты лекций по информатике, том. 7965, стр. 497–503, arXiv : 1209.1750 , Bibcode : 2012arXiv1209.1750G , doi : 10.1007/978-3-642-39206-1_42 , ISBN 978-3-642-39205-4 , S2CID 13129445 .

[MSCW2011-1] Перейти обратно: ^а ^б Солтыс, Майкл; Уилсон, Крейг (2011), «О сложности вычисления выигрышных стратегий для игр с конечным ЧУУ», Theory of Computing Systems , 48 (3): 680–692, CiteSeerX 10.1.1.150.3656 , doi : 10.1007/s00224-010- 9254-у , МР 2770813 , S2CID 2720334 .

[Byrnes2003-2] Бирнс, Стивен (2003), «Периодичность игры Посет» (PDF) , Целые числа , 3 (G3): 1–16, MR 2036487 .

[Grier2012-3] Гриер, Дэниел (2012), «Определение победителя в произвольной игре с конечными числами ЧП является PSPACE-полной», Автоматы, языки и программирование , Конспекты лекций по информатике, том. 7965, стр. 497–503, arXiv : 1209.1750 , Bibcode : 2012arXiv1209.1750G , doi : 10.1007/978-3-642-39206-1_42 , ISBN 978-3-642-39205-4 , S2CID 13129445 .

[1]

[2]

[3]