Sprague-Grundy funktion

Sprague-Grundy-funktionen används flitigt i spelteorin för att hitta en vinnande strategi i kombinatoriska spel som Nîmes spel . Sprague-Grundy-funktionen är definierad för tvåspelarspel där spelaren som inte kan göra ett nytt drag förlorar.

I fallet med diskreta spel, ibland kallat en nimber .

Sprague-Grundy-satsen är en allmän deduktion från resultat som var oberoende angivna och bevisade av R. Sprague (1935) och P. M. Grandy (1939). Den består i det faktum att för varje opartiskt spel där spelaren som gjorde det sista draget vinner, för varje position bestäms värdet av Sprague-Grundy-funktionen unikt, vilket bestämmer den vinnande strategin eller dess frånvaro.

Definitioner

Definition 1

En Sprague-Grundy funktion är en funktion F definierad för x och tar icke-negativa värden som:

F(x)=\min\{n\geq 0:n\neq F(y),y\in G(x)\},

var

n är vilket icke-negativt heltal som helst,
y är en av positionerna som kan flyttas direkt från position x i ett drag,
F( y ) - Sprague-Grandy värden för positioner som kan flyttas direkt från position x i ett drag,
G( x ) är en lista över positioner som kan flyttas direkt från position x i ett drag.

Således är F( x ) det minsta icke-negativa heltal som inte finns bland Sprague-Grundy-värdena för vissa x .

Definition 2

Funktionen F definieras på uppsättningen av alla spelpositioner enligt följande: $G$

F(P)=0,

om position P otvetydigt förlorar (ingen rörelse kan göras)

F(P)=\min(\Omega \setminus \{F(Q)|Q\in G(P)\})

annat,

där är mängden icke-negativa heltal, och är mängden av alla tillåtna drag från position P . $\Omega$ $G(P)$

Grundläggande egenskaper

Om x är slutpositionen så är F( x ) = 0. Positioner x för vilka F( x ) = 0 är P-positioner (förlust för spelaren vars tur det är att flytta), medan alla andra positioner är respektive H- positioner (vinst för spelaren vars tur det är att göra ett drag). En vinnande strategi är att vid varje steg välja ett drag där Sprague-Grundy-värdet är noll.
Från position x för vilken F( x ) = 0, finns det bara förflyttningar till position y så att F( y ) ≠ 0.
Från position x för vilken F( x ) ≠ 0, finns det minst ett drag till position y där F( y ) = 0.

Applikation

En av de användbara egenskaperna hos Sprague-Grundy-funktionen är att den är noll för alla förlorande positioner och positiv för alla vinnande positioner. Detta ger en metod för att hitta en vinnande strategi:

Hitta Sprague-Grundy-funktionen, till exempel genom att bygga den rekursivt , med början från de slutliga positionerna.
Om Grundy-funktionen i utgångsläget är lika med noll, är spelet förlorat för den första spelaren.
Annars kan den första spelaren vinna genom att flytta varje drag till en position med nollvärde för Grundy-funktionen.

Summan av spel

Om vi har spel , då kan vi överväga en kombination av dessa spel, för vilka spelplanen består av en uppsättning spelplaner för spel och i ett drag kan spelaren välja några och göra ett drag på spelplanen för att spela . En sådan kombination kallas summan av spel och betecknas med . Situationen på spelplanen , när spelplanen är på plats , betecknas lämpligen som . $n$ $G_{1},G_{2},\dots ,G_{n}$ $G_{1},G_{2},...,G_{n}$ $i,1\leq i\leq n$ $G_{i}$ $G_{1},G_{2},\dots ,G_{n}$ $G_{1}+G_{2}+\dots +G_{n}$ $G_{1}+G_{2}+\dots +G_{n}$ $G_{i}$ $Pi}$ $(P_{1},P_{2},\dots ,P_{n})$

Sprague-Grundy-funktionen har en överraskande egenskap som gör att du optimalt kan spela summan av spel , genom att känna till Sprague-Grundy-funktionen för alla positioner i varje spel . Den är formulerad enligt följande: $G_{1}+G_{2}+...+G_{n}$ $G_{i}$

F(P_{1},P_{2},\dots ,P_{n})=F(P_{1})\oplus F(P_{2})\oplus \dots \oplus F(P_{ n}),

där - exklusivt "eller" (alias XOR). $\ plus$

Exempel

En uppgift

Det finns ett område som består av 10 celler. Två spelare spelar. I ett drag är det tillåtet att dela upp området i två ojämna områden som inte är noll så att enheten i varje enskild cell inte kränks (det vill säga att cellen inte kan delas). Den som inte kan göra ett drag förlorar. Vem vinner under förutsättning av korrekt fair play?

Lösning

Problemet är löst från slutet. Överväg alternativen för att dela området för alla fall från 1 till 10 celler och hitta värdena för Sprague-Grandy-funktionen för dem. Observera att för det här spelet, som ett resultat av att man delar upp området varje gång i två nya områden, hittas värdet av Sprague-Grundy-funktionen med hjälp av Nim-summan .

Sprague-Grundy-värdet för n = 10 visar sig vara 0. Därför förlorar spelaren som gör draget först. I något av sina drag flyttar den andra spelaren till positionerna 4 + 4 eller n = 1/2/7, för vilka Sprague-Grundy-värdet också är lika med 0.

Svar

Den som flyttar tvåa vinner.

Se även

Länkar

Berge K. Teori om grafer och dess tillämpningar. M.: IL, 1962. 320c.
Nivasch G. The Sprague-Grundy teorin om opartiska spel (nedlänk sedan 2013-05-13 [3456 dagar] - historia )
Kummer B. N. §2.2. Grundy-funktionen och ordersummor p // Grafspel. — 1982.
BCA Milvang-Jensen. Kombinatoriska spel, teori och tillämpningar (obestämd tid) . — 2000.
Thomas S. Ferguson SPELTEORI
Sprague-Grundy teorin om opartiska spel (nedlänk sedan 2013-05-13 [3456 dagar] - historia ) (eng.) , 9 november 2005
Sprague-Grundy Values of Grundy's Game
PM Grundy. Matematik och spel (neopr.) // Eureka. - 1964. - T. 27 . Arkiverad från originalet den 27 september 2007.