Poset spel

I kombinatorisk spelteori är poset-spel matematiska strategispel , som generaliserar många välkända spel som Nim och Chomp . I sådana spel börjar två spelare med en poset (en delvis ordnad uppsättning ), och turas om att välja en punkt i poset, ta bort den och alla poäng som är större. Spelaren som inte har någon poäng att välja på förlorar.

Spelspel

Givet en delvis ordnad uppsättning ( P , <), låt

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

beteckna den poset som bildas genom att ta bort x från P .

Ett posetspel på P , som spelas mellan två spelare som vanligtvis heter Alice och Bob , är följande:

• Alice väljer en punkt x ∈ P ; ersätter alltså P med P _x , och skickar sedan turen till Bob som spelar på P _x , och skickar turen till Alice.
• En spelare förlorar om det är hans/hennes tur och det inte finns några poäng att välja på.

Exempel

Om P är en ändlig fullständigt ordnad uppsättning , är spelet i P exakt detsamma som spelet i ett spel Nim med en hög av storlek | P |. För i båda spelen är det möjligt att välja ett drag som leder till ett spel av samma typ vars storlek är valfritt antal mindre än | P |. På samma sätt är ett posetspel med en osammanhängande förening av totala order likvärdigt med ett spel Nim med flera högar med storlekar lika med kedjorna i poset.

Ett specialfall av Hackenbush , där alla kanter är gröna (kan skäras av båda spelarna) och varje konfiguration har formen av en skog , kan uttryckas på liknande sätt, som ett posetspel på en poset där, för varje element x , det finns högst ett element y för vilket x täcker y . Om x täcker y är y förälder till x i skogen där spelet spelas.

Chomp kan uttryckas på liknande sätt, som ett posetspel på produkten av totala beställningar från vilka infimumet har tagits bort.

Grundy värde

Poset-spel är opartiska spel , vilket innebär att varje drag som är tillgängligt för Alice också skulle vara tillgängligt för Bob om Alice fick passera, och vice versa. Därför, enligt Sprague-Grundy-satsen , har varje position i ett posetspel ett Grundy-värde, ett tal som beskriver en likvärdig position i spelet Nim. Grundy-värdet för en poset kan beräknas som det minsta naturliga talet som inte är Grundy-värdet för någon P _x , x ∈ P . Det är,

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

Detta nummer kan användas för att beskriva det optimala spelet i ett posetspel. I synnerhet är Grundy-värdet icke-noll när spelaren vars tur det är har en vinnande strategi, och noll när den aktuella spelaren inte kan vinna mot optimalt spel från hans eller hennes motståndare. En vinnande strategi i spelet består av att flytta till en position vars Grundy-värde är noll, närhelst detta är möjligt.

Strategistöld

Ett strategistöldargument visar att Grundy-värdet inte är noll för varje post som har ett högsta . För, låt x vara det högsta av en delvis ordnad mängd P . Om P _x har Grundy-värdet noll, så har P i sig ett värde som inte är noll, enligt formeln ovan; i detta fall x ett vinnande drag i P . Om, å andra sidan, P _{x har ett} Grundy -värde som inte är noll, måste det finnas ett vinnande drag y i P _x , så att Grundy-värdet för ( P _{x ) y} är noll. Men med antagandet att x är ett supremum, x > y och ( P _x ) _y = P _y , så är det vinnande draget y också tillgängligt i P och återigen P måste ha ett Grundy-värde som inte är noll.

Av mer triviala skäl har en poset med ett infimum också ett Grundy-värde som inte är noll: att flytta till infimum är alltid ett vinnande drag.

Komplexitet

Att avgöra vinnaren av ett godtyckligt finite poset-spel är PSPACE-komplett . Detta betyder att om inte P=PSPACE är det beräkningsmässigt svårt att beräkna Grundy-värdet för ett godtyckligt posetspel.