Sprague-Grundy funktion

Sprague-Grundy-funktionen er meget brugt i spilteori til at finde en vindende strategi i kombinatoriske spil såsom Nîmes' spil . Sprague-Grundy-funktionen er defineret for to-spiller-spil, hvor den spiller, der ikke er i stand til at lave endnu et træk, taber.

I tilfælde af diskrete spil, nogle gange kaldet en nimber .

Sprague-Grundy-sætningen er en generel deduktion fra resultater, der uafhængigt blev angivet og bevist af R. Sprague (1935) og P. M. Grandy (1939). Den består i, at for ethvert upartisk spil, hvor den spiller, der lavede det sidste træk, vinder, for hver position er værdien af Sprague-Grundy-funktionen entydigt bestemt, hvilket bestemmer vinderstrategien eller dens fravær.

Definitioner

Definition 1

En Sprague-Grundy funktion er en funktion F defineret for x og tager ikke-negative værdier som:

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

hvor

n er ethvert ikke-negativt heltal,
y er en af de positioner, der kan flyttes direkte fra position x i et træk,
F( y ) - Sprague-Grandy værdier for positioner, der kan flyttes direkte fra position x i et træk,
G( x ) er en liste over positioner, der kan flyttes direkte fra position x i et træk.

Således er F( x ) det mindste ikke-negative heltal, der ikke findes blandt Sprague-Grundy-værdierne for visse x .

Definition 2

Funktionen F er defineret på sættet af alle spilpositioner som følger: $G$

F(P)=0,

hvis position P entydigt taber (ingen bevægelse kan foretages)

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

Ellers,

hvor er mængden af ikke-negative heltal, og er mængden af alle tilladte træk fra position P . $\Omega$ $G(P)$

Grundlæggende egenskaber

Hvis x er den endelige position, så er F( x ) = 0. Positioner x hvor F( x ) = 0 er P-positioner (taber for den spiller, hvis tur det er til at flytte), mens alle andre positioner er henholdsvis H- positioner (vinder for den spiller, hvis tur det er til at lave et træk). En vindende strategi er at vælge ved hvert trin et træk, hvor Sprague-Grundy værdien er nul.
Fra position x , hvor F( x ) = 0, er der kun bevægelser til position y , således at F( y ) ≠ 0.
Fra position x , hvor F( x ) ≠ 0, er der mindst et træk til position y , hvor F( y ) = 0.

Ansøgning

En af de nyttige egenskaber ved Sprague-Grundy-funktionen er, at den er nul for alle tabende positioner og positiv for alle vindende positioner. Dette giver en metode til at finde en vindende strategi:

Find Sprague-Grundy-funktionen, for eksempel ved at bygge den rekursivt , startende fra de endelige positioner.
Hvis Grundy-funktionen i startpositionen er lig nul, så er spillet tabt for den første spiller.
Ellers kan den første spiller vinde ved at flytte hvert træk til en position med nul værdi af Grundy-funktionen.

Summen af spil

Hvis vi har spil , så kan vi overveje en kombination af disse spil, hvor spillefeltet består af et sæt spillebaner til spil, og i et træk kan spilleren vælge nogle og lave et træk på spillefeltet for at spille . En sådan kombination kaldes summen af spil og betegnes med . Situationen på spillets spillebane, når spillets spillefelt er på plads , betegnes bekvemt 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}$ $P_{i}$ $(P_{1},P_{2},\dots,P_{n})$

Sprague-Grundy-funktionen har en overraskende egenskab, der giver dig mulighed for optimalt at spille summen af spil , idet du kender Sprague-Grundy-funktionen for alle positioner i hvert af spillene . Den er formuleret som følger: $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}),

hvor - eksklusiv "eller" (aka XOR). $\plus$

Eksempel

En opgave

Der er et område bestående af 10 celler. To spillere spiller. I et træk er det tilladt at opdele arealet i to ulige ikke-nul-områder, så enheden i hver enkelt celle ikke krænkes (det vil sige, at cellen ikke kan opdeles). Den, der ikke kan lave et træk, taber. Hvem vinder under forudsætning af korrekt fair play?

Løsning

Problemet er løst fra slutningen. Overvej mulighederne for at opdele området for alle tilfælde fra 1 til 10 celler, og find værdierne for Sprague-Grandy-funktionen for dem. Bemærk, at for dette spil, som et resultat af at dele området hver gang i to nye områder, findes værdien af Sprague-Grundy-funktionen ved hjælp af Nim-sum .

Sprague-Grundy-værdien for n = 10 viser sig at være 0. Derfor taber den spiller, der tager træk først. I ethvert af sine træk, flytter den anden spiller til position 4 + 4 eller n = 1/2/7, hvor Sprague-Grundy-værdien også er lig med 0.

Svar

Den, der rykker på andenpladsen, vinder.

Sprague-Grundy funktion

Definitioner

Grundlæggende egenskaber

Ansøgning

Summen af spil

Eksempel

Se også

Links

Sprague-Grundy funktion

Definitioner

Grundlæggende egenskaber

Ansøgning

Summen af ​​spil

Eksempel

Se også

Links

Summen af spil