Opartiskt spel

I kombinatorisk spelteori är ett opartiskt spel ett spel där de tillåtna dragen endast beror på positionen och inte på vilken av de två spelarna som för närvarande rör sig, och där vinsterna är symmetriska. Med andra ord, den enda skillnaden mellan spelare 1 och spelare 2 är att spelare 1 går först. Spelet spelas tills en slutposition nås. En terminalposition är en från vilken inga rörelser är möjliga. Då utses en av spelarna till vinnare och den andra till förlorare. Dessutom spelas opartiska spel med perfekt information och inga slumpmässiga rörelser, vilket innebär att all information om spelet och operationerna för båda spelarna är synliga för båda spelarna.

Opartiska spel inkluderar Nim , Sprouts , Kayles , Quarto , Cram , Chomp , Subtrahera en kvadrat , Notakto och posetspel . Go och schack är inte opartiskt, eftersom varje spelare bara kan placera eller flytta pjäser av sin egen färg. Spel som poker , tärningar eller dominos är inte opartiska spel eftersom de är beroende av slumpen.

Opartiska spel kan analyseras med hjälp av Sprague-Grundy-teorem , som säger att varje opartiskt spel under normal spelkonvention är likvärdig med en nimber . Representationen av denna nimber kan ändras från spel till spel, men alla möjliga tillstånd av alla varianter av en opartisk spelbräda bör kunna ha något nimber värde. Till exempel kan flera nim-högar i spelet nim beräknas, sedan summeras med hjälp av nimber-addition, för att ge ett nimber-värde för spelet.

Ett spel som inte är opartiskt kallas ett partisanspel , även om vissa partisanspel fortfarande kan utvärderas med hjälp av nimbers som Domineering . Dominering skulle inte klassificeras som ett opartiskt spel eftersom spelare använder olika pjäser, en spelare med vertikala dominobrickor, en med horisontella, och därmed bryter regeln att varje spelare måste kunna agera med samma operationer.

Krav

Alla opartiska spel måste uppfylla följande villkor:

Två spelare måste växla tills ett sluttillstånd uppnås.
En vinnare utses när en spelare inte längre kan ändra position eller göra någon operation.
Det måste finnas ett begränsat antal operationer och positioner för båda spelarna. Till exempel, i Nim måste spelare ta bort en delmängd av en stack som för närvarande är i spel. Eftersom det finns ett ändligt antal mynt i varje stack, kan en spelare bara ta bort ett ändligt antal mynt.
Alla operationer måste kunna utföras av båda sidor. I alla opartiska spel gör spelarna åtgärder till någon spelbräde, oavsett om det är i form av stackar för Nim eller rader och kolumner Cram. Båda spelarna agerar på brädet tills brädet inte längre kan förändras på något sätt.
Ingen handling i spelet kan vara beroende av slumpen. Varje inkludering av slumpen skulle innebära att det inte finns perfekt information om spelet, dessutom kan handlingar inte begränsas till att utesluta någon form av induktiv strategi.

Vidare läsning

E. Berlekamp ; JH Conway ; R. Guy (1982). Vinnande sätt för dina matematiska pjäser . Vol. 2 vol. Akademisk press. ; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (1982). vol. 1 . ISBN 0-12-091101-9 . ; Berlekamp, Elwyn R. (1982). vol. 2 . ISBN 0-12-091102-7 .
E. Berlekamp; JH Conway; R. Guy (2001–2004). Vinnande sätt för dina matematiska pjäser . Vol. 4 vol. (2:a upplagan). AK Peters Ltd. ; Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (16 januari 2001). vol. 1 . ISBN 1-56881-130-6 . ; vol. 2 . ISBN 1-56881-142-X . ; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 juni 2003). vol. 3 . ISBN 1-56881-143-8 . ; Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 juni 2004). vol. 4 . ISBN 1-56881-144-6 .