Poset игра

В комбинаторной теории игр , посетом игры являются математические игры стратегии , обобщающие многие известные игры , такие как Нима и Chomp . ^[1] В таких играх два игрока начинают с poset ( частично упорядоченного набора ) и по очереди выбирают одну точку в poset, удаляя ее и все точки, которые больше. Игрок, которому не остается выбора, проигрывает.

Игра [ править ]

Для частично упорядоченного множества ( P , <) пусть

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

Обозначим посета , образованный путем удаления х из Р .

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

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

Примеры [ править ]

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

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

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

Гранди значение [ править ]

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

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

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

Стратегия кражи [ править ]

А заимствование стратегии показывает , что Гранди ненулевое значение для каждого посета , который имеет верхнюю грань . Действительно, пусть й верхняя грань частично упорядоченное множество P . Если P _x имеет нулевое значение Гранди, то само P имеет ненулевое значение по формуле выше; в этом случае, х является выигрышным движение в 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, вычисление значения Гранди для произвольной игры poset является вычислительно трудным.

Ссылки [ править ]