Sprague–Grundys sats

I kombinatorisk spelteori säger Sprague -Grundy-satsen att varje opartiskt spel under den normala spelkonventionen är likvärdig med ett enhögsspel av nim , eller med en oändlig generalisering av nim. Det kan därför representeras som ett naturligt tal , storleken på högen i dess ekvivalenta spel nim, som ett ordningstal i den oändliga generaliseringen, eller alternativt som ett nimber , värdet av det enhögsspelet i ett algebraiskt system vars additionsoperationen kombinerar flera högar för att bilda en enda ekvivalent hög i nim.

Grundy -värdet eller nim-värdet för ett opartiskt spel är den unika nimber som spelet motsvarar. I fallet med ett spel vars positioner indexeras av de naturliga talen (som nim självt, som indexeras av dess högstorlekar), kallas sekvensen av nimbers för på varandra följande positioner i spelet spelets nim- sekvens .

Sprague-Grundy-satsen och dess bevis kapslar in huvudresultaten av en teori som upptäckts oberoende av RP Sprague (1936) och PM Grundy (1939).

Definitioner

För syftet med Sprague-Grundy-satsen är ett spel ett sekventiellt spel för två spelare med perfekt information som uppfyller slutvillkoret (alla spel tar slut: det finns inga oändliga spellinjer) och det normala spelvillkoret (en spelare) som inte kan röra sig förlorar).

Vid varje given tidpunkt i spelet är en spelares position den uppsättning drag de får göra. Som ett exempel kan vi definiera nollspelet som ett tvåspelarspel där ingen av spelarna har några lagliga drag. Med hänvisning till de två spelarna som $A$ (för Alice) och $B$ (för Bob), skulle vi beteckna deras positioner som $(A,B)=(\{\},\{\})$ , eftersom uppsättningen drag varje spelare kan göra är tom.

Ett opartiskt spel är ett där varje spelare får exakt samma uppsättning drag vid varje given punkt i spelet. Normal-play nim är ett exempel på ett opartiskt spel. I nim finns det en eller flera högar av föremål, och två spelare (vi kallar dem Alice och Bob), turas om att välja en hög och ta bort 1 eller flera föremål från den. Vinnaren är den spelare som tar bort det sista föremålet från den sista högen. Spelet är opartiskt eftersom för varje given konfiguration av högstorlekar är de drag Alice kan göra på sin tur exakt samma drag som Bob skulle få göra om det var hans tur. Däremot är ett spel som dam inte opartiskt eftersom, om vi antar att Alice spelade rött och Bob spelade svart, för varje givet arrangemang av pjäser på brädet, om det var Alices tur, skulle hon bara få flytta de röda pjäserna , och om det var Bobs tur skulle han bara få flytta de svarta pjäserna.

Observera att varje konfiguration av ett opartiskt spel därför kan skrivas som en enda position, eftersom dragen kommer att vara desamma oavsett vems tur det är. Till exempel kan nollspelets position helt enkelt skrivas $\{\}$ , för om det är Alices tur har hon inga drag att göra, och om det är Bobs tur har han inga drag att göra heller . Ett drag kan associeras med den position den lämnar nästa spelare i.

Genom att göra det kan positioner definieras rekursivt. Tänk till exempel på följande spel av Nim som spelas av Alice och Bob.

Exempel Nim-spel

Storlekar på högar Rör sig ABC 1 2 2 Alice tar 1 från A 0 2 2 Bob tar 1 från B 0 1 2 Alice tar 1 från C 0 1 1 Bob tar 1 från B 0 0 1 Alice tar 1 från C 0 0 0 Bob har inga drag, så Alice vinner

• Vid steg 6 i spelet (när alla högarna är tomma) är positionen $\{\}$ , eftersom Bob inte har några giltiga drag att göra. Vi namnger denna position $*0$ .
• Vid steg 5 hade Alice exakt ett alternativ: att ta bort ett föremål från hög C, vilket lämnade Bob utan rörelser. Eftersom hennes drag lämnar Bob i position $*0$ skrivs hennes position $\{*0\}$ . Vi namnger denna position $*1$ .
• Vid steg 4 hade Bob två alternativ: ta bort en från B eller ta bort en från C. Observera dock att det inte spelade någon roll vilken hög Bob tog bort objektet från: Hur som helst, Alice skulle ha exakt ett objekt i exakt en hög. Så, med vår rekursiva definition, har Bob egentligen bara ett drag: $*1$ . Således är Bobs position $\{*1\}$ .
• I steg 3 hade Alice 3 alternativ: ta bort två från C, ta bort en från C eller ta bort en från B. Att ta bort två från C lämnar Bob i position ∗ $\displaystyle *1}$ . Att ta bort en från C lämnar Bob med två högar, var och en av storlek ett, dvs position ${\displaystyle \{*1\}},$ som beskrivs i steg 4. Om du tar bort 1 från B skulle dock Bob få två föremål i en enda hög. Hans drag skulle då vara $*0$ och $*1$ , så hennes drag skulle resultera i positionen $\{*0,*1\}$ . Vi kallar denna position $*2$ . Alices position är då mängden av alla hennes drag: ${\big \{}*1,\{*1\},*2{\big \}}$ .
• Efter samma rekursiva logik, vid steg 2, är Bobs position
  $${\big \{}\{*1,\{*1\},*2\},*2{\big \}}.$$
• Slutligen, vid steg 1, är Alices position
  $${\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{ *1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\ },*2\}{\big \}}{\Big \}}.$$

Nimbers

De speciella namnen $*0$ , $*1$ och $*2$ som refereras till i vårt exempelspel kallas nimbers . I allmänhet motsvarar värdet $*n$ positionen i ett spel nim där det finns exakt $n$ objekt i exakt en hög. Formellt definieras nimbers induktivt enligt följande: $*0$ är $\{\}$ , $*1=\{*0\}$ , $*2=\{*0,*1\}$ och för alla $n\geq 0$ , $*(n+1)=*n\cup \{*n\}$ .

Medan ordet nim ber kommer från spelet nim , kan nimbers användas för att beskriva positionerna för vilket ändligt, opartiskt spel som helst, och i själva verket säger Sprague-Grundy-satsen att varje instans av ett ändligt, opartiskt spel kan associeras med ett enda nimber.

Kombinera spel

Två spel kan kombineras genom att lägga ihop deras positioner. Tänk till exempel på ett annat spel nim med heaps $A'$ , $B'$ och $C'$ .

Exempelspel 2

Storlekar på högar Flytt A' B' C' 1 1 1 Alice tar 1 från A' 0 1 1 Bob tar ett från B' 0 0 1 Alice tar ett från C' 0 0 0 Bob har inga drag, så Alice vinner.

Vi kan kombinera det med vårt första exempel för att få ett kombinerat spel med sex högar: $A$ , $B$ , ${\displaystyle C} ,$ A $\displaystyle A'}$ , ${ \displaystyle B'}$ och $C'$ :

Kombinerat spel

Storlekar på högar Rör sig ABCA' B' C' 1 2 2 1 1 1 Alice tar 1 från A 0 2 2 1 1 1 Bob tar 1 från A' 0 2 2 0 1 1 Alice tar 1 från B' 0 2 2 0 0 1 Bob tar 1 från C' 0 2 2 0 0 0 Alice tar 2 från B 0 0 2 0 0 0 Bob tar 2 från C 0 0 0 0 0 0 Alice har inga drag, så Bob vinner.

För att skilja mellan de två spelen, för det första exempelspelet , märker vi dess startposition $\color {blue}S$ och färgar det blått:

$$\color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \} },{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\ {*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}$$

För det andra spelexemplet markerar vi startpositionen $\color {red}S'$ och färgar den röd:

$$\color {red}S'={\Big \{}\{*1\}{\Big \}}.$$

För att beräkna startpositionen för det kombinerade spelet , kom ihåg att en spelare antingen kan göra ett drag i det första spelet, lämna det andra spelet orört, eller göra ett drag i det andra spelet och lämna det första spelet orörda. Så det kombinerade spelets startposition är:

$$\color {blue}S\color {svart}+\color { red}S'\color {black}={\Big \{}\color {blue}S\color {svart}+\color {röd}\{*1\}\color {svart}{\Big \}} \cup {\Big \{}\color {red}S'\color {svart}+\color {blå}\{*1,\{*1\},*2\}\color {svart},\color {röd}S'\färg {svart}+\färg {blå}\{*2,\{*1,\{*1\},*2\}\}\färg {svart},\färg {röd} S'\färg {svart}+\färg {blå}\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\ }\color {svart}{\Big \}}$$

Den explicita formeln för att lägga till positioner är: ${\displaystyle S+S'=\{S+s' \mid s'\in S'\}\cup \{s+S'\mid s\in S\}} , vilket$ betyder att addition är både kommutativ och associativ.

Likvärdighet

Positioner i opartiska spel delas in i två utfallsklasser : antingen vinner nästa spelare (den vars tur det är) (en ${\boldsymbol {\mathcal {N}}}$ - position ), eller så vinner den föregående spelaren (en ${\boldsymbol {\mathcal {P}}}$ - position ). Så, till exempel, $*0$ är en ${\mathcal {P}}$ -position, medan $*1$ är en ${\mathcal {N} }$ -position.

Två positioner $G$ och $G'$ är ekvivalenta om de, oavsett vilken position $H$ som läggs till dem, alltid är i samma utfallsklass. Formellt gäller $G\approx G'$ om och endast om $\forall H$ , $G+H$ är i samma utfallsklass som $G'+H$ .

För att använda våra löpexempel, lägg märke till att i både det första och andra spelet ovan kan vi visa att Alice har ett drag i varje tur som tvingar Bob till en ${\mathcal {P}}$ -position. Sålunda är både $\color {blue}S$ och $\color {red}S'$${\mathcal {N}}$ -positioner. (Lägg märke till att i det kombinerade spelet Bob spelaren med ${\mathcal {N}}$ -positionerna. Faktum är att $\color {blue}S\color {svart} +\color {red}S'$ är en ${\mathcal {P}}$ -position, vilket som vi kommer att se i Lemma 2 betyder $\color {blue}S\ färg {svart}\approx \color {röd}S'$ .)

Första Lemma

Som ett mellansteg för att bevisa huvudsatsen visar vi att för varje position $G$ och varje ${\mathcal {P}}$ -position $A$ , är ekvivalensen $G\approx A+G$ gäller. Enligt ovanstående definition av ekvivalens motsvarar detta att visa att $G+H$ och $A+G+H$ delar en utfallsklass för alla $H$ .

Antag att $G+H$ är en ${\mathcal {P}}$ -position. Sedan har den tidigare spelaren en vinnande strategi för $A+G+H$ : svara på drag i $A$ enligt deras vinnande strategi för $A$ (som finns av genom att $A$ är en ${\mathcal {P}}$ -position), och svarar på drag i $G+H$ enligt deras vinnande strategi för $G+H$ (som existerar av den analoga anledningen). Så $A+G+H$ måste också vara en ${\mathcal {P}}$ -position.

Å andra sidan, om $G+H$ är en ${\mathcal {N}}$ -position, så är $A+G+H$ också en ${\mathcal {N}}$ -position, eftersom nästa spelare har en vinnande strategi: välj en ${\mathcal {P}}$ -position bland $G+H$ -alternativ, och vi drar slutsatsen från föregående stycke att att lägga till $A$ till den positionen fortfarande är en ${\mathcal {P}}$ -position. I det här fallet måste alltså ${\displaystyle A+G+H} vara en$${\mathcal {N}}$ -position, precis som $G+H$ .

Eftersom detta är de enda två fallen gäller lemmat.

Andra Lemma

Som ett ytterligare steg visar vi att $G\approx G'$ om och endast om $G+G'$ är en ${\mathcal {P}}$ -position.

I framåtriktningen, anta att $G\approx G'$ . Genom att tillämpa definitionen av ekvivalens med $H=G$ finner vi att $G'+G$ (vilket är lika med $G+G'$ med kommutativitet för addition) är i samma utfallsklass som $G+G$ . Men $G+G$ måste vara en ${\mathcal {P}}$ -position: för varje drag som görs i en kopia av $G$ kan den föregående spelaren svara med samma drag i den andra kopian, och gör därför alltid det sista draget.

I motsatt riktning, eftersom $A=G+G'$ är en ${\mathcal {P}}$ -position genom hypotes, följer det av det första lemmat, $G\approx G+A$ , att $G\approx G+(G+G')$ . På liknande sätt, eftersom ${\displaystyle B=G+G} också$$G'\approx G'+B$ en ${\mathcal {P}}$ -position, följer det av det första lemmat i formen att $G'\approx G'+(G+G)$ . Genom associativitet och kommutativitet är de högra sidorna av dessa resultat lika. Dessutom $\approx$ en ekvivalensrelation eftersom likhet är en ekvivalensrelation på utfallsklasser. Via transitiviteten av $\approx$ kan vi dra slutsatsen att $G\approx G'$ .

Bevis

Vi bevisar att alla positioner är likvärdiga med en nimber genom strukturell induktion . Det mer specifika resultatet, att det givna spelets utgångsposition måste motsvara en nimber, visar att spelet i sig är ekvivalent med en nimber.

Betrakta en position $G=\{G_{1},G_{2},\ldots ,G_{k}\}$ . Enligt induktionshypotesen är alla alternativ ekvivalenta med nimber, säg $G_{i}\approx *n_{i}$ . Så låt $G'=\{*n_{1},*n_{2},\ldots ,*n_{k}\}$ . Vi kommer att visa att $G\approx *m$ , där $m$ är mex (minsta uteslutning) av talen ${\displaystyle n_{ 1},n_{2},\ldots ,n_{k}} ,$ det vill säga det minsta icke-negativa heltal som inte är lika med några $n_{i}$ .

Det första vi måste notera är att $G\approx G'$ , genom det andra lemmat. Om $k$ är noll är påståendet trivialt sant. Tänk annars på $G+G'$ . Om nästa spelare gör ett drag till $G_{i}$ i $G$ , då kan föregående spelare gå till $*n_{i}$ i ${\ displaystyle G'}$ , och omvänt om nästa spelare gör ett drag i $G'$ . Efter detta är positionen en ${\mathcal {P}}$ -position av lemmas framåtriktade implikation. Därför $G+G'$ en ${\mathcal {P}}$ -position, och, med hänvisning till lemmas omvända implikation, $G\approx G '$ .

Låt oss nu visa att $G'+*m$ är en ${\mathcal {P}}$ -position, vilket, med det andra lemmat ännu en gång, betyder att $G'\approx *m$ . Vi gör det genom att ge en explicit strategi för den tidigare spelaren.

Antag att $G'$ och $*m$ är tomma. Då $G'+*m$ nollmängden, helt klart en ${\mathcal {P}}$ -position.

Eller överväg fallet att nästa spelare flyttar i komponenten $*m$ till alternativet $*m'$ där $m'<m$ . Eftersom $m$ var det minsta uteslutna talet, kan den föregående spelaren flytta in $G'$ till $*m'$ . Och, som visats tidigare, är varje position plus sig själv en ${\mathcal {P}}$ -position.

Slutligen, anta istället att nästa spelare flyttar i komponenten $G'$ till alternativet $*n_{i}$ . Om $n_{i}<m$ så flyttar den föregående spelaren in $*m$ till $*n_{i}$ ; annars, om $n_{i}>m$ , flyttar den föregående spelaren in $*n_{i}$ till $*m$ ; i båda fallen är resultatet en position plus sig själv. (Det är inte möjligt att $n_{i}=m$ eftersom $m$ definierades för att skilja sig från alla $n_{i}$ .)

Sammanfattningsvis har vi $G\approx G'$ och $G'\approx *m$ . Genom transitivitet drar vi slutsatsen att $G\approx *m$ , enligt önskemål.

Utveckling

Om $G$ är en position i ett opartiskt spel, kallas det unika heltal $m$ så att $G\approx *m$ dess Grundy-värde, eller Grundy-tal, och funktionen som tilldelar detta värde till varje sådan position kallas Sprague–Grundy-funktionen. RL Sprague och PM Grundy gav oberoende av varandra en explicit definition av denna funktion, inte baserad på något koncept av ekvivalens till nim-positioner, och visade att den hade följande egenskaper:

• Grundy-värdet för en enda nim-hög med storleken $m$ (dvs. av positionen $*m$ ) är $m$ ;
• En position är en förlust för nästa spelare att flytta (dvs en ${\mathcal {P}}$ -position) om och endast om dess Grundy-värde är noll; och
• Grundy-värdet för summan av en ändlig uppsättning positioner är bara nim-summan av Grundy-värdena för dess summor.

Det följer direkt av dessa resultat att om en position $G$ har ett Grundy-värde på $m$ , så har $G+H$ samma Grundy-värde som ${ \displaystyle *m+H}$ , och tillhör därför samma utfallsklass, för valfri position $H$ . Således, även om Sprague och Grundy aldrig uttryckligen angav satsen som beskrivs i denna artikel, följer den direkt av deras resultat och krediteras dem. Dessa resultat har därefter utvecklats till fältet kombinatorisk spelteori , särskilt av Richard Guy , Elwyn Berlekamp , ​​John Horton Conway och andra, där de nu är inkapslade i Sprague-Grundy-satsen och dess bevis i den form som beskrivs här. Fältet presenteras i böckerna Winning Ways for your Mathematical Plays och On Numbers and Games .

Se även

• Släktteori
• Oskiljbar kvot

externa länkar

• Grundys spel på cut-the-knot
• Lättläst, introduktionskonto från UCLA Math Department
• The Game of Nim på sputsoft.com
•   Milvang-Jensen, Brit CA (2000), Combinatorial Games, Theory and Applications (PDF) , CiteSeerX 10.1.1.89.805