Игра Poset - Википедия - Poset game

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

Игра

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

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

обозначают чугуна, образованную удалением Икс из п.

Poset игра на п, играется между двумя игроками, условно названными Алиса и Боб, как следует:

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

Примеры

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

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

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

Грандиозное значение

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

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

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

Стратегия кражи

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

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

Сложность

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