Gra Poset

W teorii gier kombinatorycznych gry poset są matematycznymi grami strategicznymi , uogólniającymi wiele dobrze znanych gier, takich jak Nim i Chomp . W takich grach dwóch graczy zaczyna od poset ( zestaw częściowo uporządkowany ) i na zmianę wybiera jeden punkt w poze, usuwając go i wszystkie większe punkty. Gracz, który nie ma już żadnego punktu do wyboru, przegrywa.

Rozgrywka

Biorąc pod uwagę częściowo uporządkowany zbiór ( P , <), niech

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

oznaczają poset utworzony przez usunięcie x z P .

Gra posetowa na P , rozgrywana pomiędzy dwoma graczami o umownych imionach Alicja i Bob , wygląda następująco:

• Alicja wybiera punkt x ∈ P ; w ten sposób zastępując P przez P _x , a następnie przekazuje kolejkę Bobowi, który gra na P _x , i przekazuje kolejkę Alicji.
• Gracz przegrywa, jeśli jest jego kolej i nie ma punktów do wyboru.

Przykłady

Jeśli P jest skończonym, całkowicie uporządkowanym zbiorem , to gra w P jest dokładnie taka sama, jak gra w grę Nim ze stertą wielkości | P. |. Albowiem w obu grach można wybrać ruch, który prowadzi do gry tego samego rodzaju, której rozmiar jest dowolną liczbą mniejszą niż | P. |. W ten sam sposób gra posetowa z rozłączną sumą rzędów całkowitych jest równoważna grze Nim z wieloma stosami o rozmiarach równych łańcuchom w pozecie.

Szczególny przypadek Hackenbusha , w którym wszystkie krawędzie są zielone (możliwe do przecięcia przez dowolnego gracza), a każda konfiguracja ma postać lasu , można wyrazić podobnie jako grę posetową na pozecie, w której dla każdego elementu x , istnieje co najwyżej jeden element y , dla którego x obejmuje y . Jeśli x obejmuje y , to y jest rodzicem x w lesie, w którym toczy się gra.

Chomp można wyrazić podobnie, jako grę posetową na iloczyn całkowitych zamówień, z których usunięto infimum .

Wartość Grundy'ego

Gry Poset są grami bezstronnymi , co oznacza, że ​​każdy ruch dostępny dla Alicji byłby również dostępny dla Boba, gdyby Alicja mogła spasować i na odwrót. Dlatego, zgodnie z twierdzeniem Sprague-Grundy'ego , każda pozycja w grze posetowej ma wartość Grundy'ego, liczbę opisującą równoważną pozycję w grze Nim. Wartość Grundy'ego posetu można obliczyć jako najmniejszą liczbę naturalną, która nie jest wartością Grundy'ego dowolnego P _x , x ∈ P . To jest,

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

Liczba ta może być wykorzystana do opisania optymalnej rozgrywki w grze posetowej. W szczególności wartość Grundy'ego jest różna od zera, gdy gracz, którego jest tura, ma zwycięską strategię i zero, gdy obecny gracz nie może wygrać z optymalną grą swojego przeciwnika. Zwycięska strategia w grze polega na przesunięciu się na pozycję, której wartość Grundy'ego wynosi zero, kiedy tylko jest to możliwe.

Kradzież strategii

Argument kradnący strategię pokazuje, że wartość Grundy'ego jest różna od zera dla każdego posetu, który ma supremum . Niech x będzie supremum częściowo uporządkowanego zbioru P . Jeśli P _x ma wartość Grundy'ego zero, to samo P ma wartość różną od zera, zgodnie z powyższym wzorem; w tym przypadku x jest zwycięskim ruchem w P . Z drugiej strony, jeśli P _x ma niezerową wartość Grundy'ego, to musi istnieć wygrywający ruch y w P _x , tak że wartość Grundy'ego ( P _x ) _y wynosi zero. Ale przy założeniu, że x jest supremum, x > y i ( P _x ) _y = P _y , więc wygrywający ruch y jest również dostępny w P i znowu P musi mieć niezerową wartość Grundy'ego.

Z bardziej trywialnych powodów poset z infimum ma również niezerową wartość Grundy'ego: przejście do infimum jest zawsze zwycięskim ruchem.

Złożoność

Decydowanie o zwycięzcy dowolnej skończonej gry poset jest PSPACE-zupełne . Oznacza to, że jeśli P = PSPACE, obliczenie wartości Grundy'ego dowolnej gry posetowej jest trudne obliczeniowo.