Funkce Sprague-Grundy

Funkce Sprague-Grundy je široce používána v teorii her k nalezení vítězné strategie v kombinatorických hrách, jako je hra Nîmes . Funkce Sprague-Grundy je definována pro hry pro dva hráče, ve kterých prohrává hráč, který není schopen provést další tah.

V případě diskrétních her, někdy nazývaných nimber .

Sprague-Grundyho teorém je obecná dedukce z výsledků, které nezávisle uvedli a dokázali R. Sprague (1935) a P. M. Grandy (1939). Spočívá v tom, že pro jakoukoli nestrannou hru , kde vyhrává hráč, který provedl poslední tah, je pro každou pozici jednoznačně určena hodnota funkce Sprague-Grundy, která určuje vítěznou strategii nebo její absenci.

Definice

Definice 1

Sprague-Grundy funkce je funkce F definovaná pro x a nabývající nezáporných hodnot tak, že:

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

kde

n je libovolné nezáporné celé číslo,
y je jedna z pozic, kterou lze přesunout přímo z pozice x jedním tahem,
F( y ) - Sprague-Grandy hodnoty pozic, které lze přesunout přímo z pozice x jedním tahem,
G( x ) je seznam pozic, které lze přesunout přímo z pozice x jedním tahem.

F( x ) je tedy nejmenší nezáporné celé číslo, které nebylo nalezeno mezi hodnotami Sprague-Grundy pro určité x .

Definice 2

Funkce F je definována na množině všech herních pozic následovně: $G$

F(P)=0,

pokud pozice P jednoznačně prohrává (nelze provést žádný tah)

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

v opačném případě,

kde je množina nezáporných celých čísel a je množina všech povolených tahů z pozice P . $\Omega$ $G(P)$

Základní vlastnosti

Je-li x konečná pozice, pak F( x ) = 0. Pozice x , pro které F( x ) = 0 jsou P-pozice (prohrává pro hráče, který je na řadě), zatímco všechny ostatní pozice jsou H- pozice (výhra pro hráče, který je na řadě, aby provedl tah). Vítěznou strategií je zvolit v každém kroku tah, ve kterém je hodnota Sprague-Grundy nulová.
Z pozice x , pro kterou F( x ) = 0, jsou pouze tahy do pozice y takové, že F( y ) ≠ 0.
Z pozice x , pro kterou F( x ) ≠ 0, je alespoň jeden tah do pozice y , pro kterou F( y ) = 0.

Aplikace

Jednou z užitečných vlastností funkce Sprague-Grundy je, že je nula pro všechny prohrávající pozice a kladná pro všechny vítězné pozice. To poskytuje metodu pro nalezení vítězné strategie:

Najděte funkci Sprague-Grundy například tak, že ji vytvoříte rekurzivně , počínaje od konečných pozic.
Pokud je v počáteční pozici funkce Grundy rovna nule, pak je hra pro prvního hráče ztracena.
V opačném případě může první hráč vyhrát přesunem každého tahu na pozici s nulovou hodnotou funkce Grundy.

Součet her

Pokud máme hry , pak můžeme uvažovat o kombinaci těchto her, u kterých je hrací pole tvořeno souborem hracích polí pro hry a jedním tahem si hráč může některá vybrat a provést tah na hrací ploše pro hraní . Taková kombinace se nazývá součet her a značí se . Situace na hracím poli hry , kdy je hrací pole hry v pozici , je vhodně označeno jako . $n$ $G_{1},G_{2},\tečky ,G_{n}$ $G_{1},G_{2},...,G_{n}$ $i,1\leq i\leq n$ $G_{i}$ $G_{1},G_{2},\tečky ,G_{n}$ $G_{1}+G_{2}+\tečky +G_{n}$ $G_{1}+G_{2}+\tečky +G_{n}$ $G_{i}$ $P_{i}$ $(P_{1},P_{2},\tečky ,P_{n})$

Funkce Sprague-Grundy má překvapivou vlastnost, která vám umožňuje optimálně hrát součet her , přičemž znáte funkci Sprague-Grundy pro všechny pozice každé z her . Je formulován následovně: $G_{1}+G_{2}+...+G_{n}$ $G_{i}$

F(P_{1},P_{2},\tečky ,P_{n})=F(P_{1})\oplus F(P_{2})\oplus \tečky \oplus F(P_{ n}),

kde - exkluzivní "nebo" (aka XOR). $\oplus$

Příklad

Úkol

K dispozici je oblast skládající se z 10 buněk. Hrají dva hráči. Jedním tahem je dovoleno rozdělit oblast na dvě nestejné nenulové oblasti tak, aby nebyla narušena jednota každé jednotlivé buňky (tj. buňku nelze rozdělit). Ten, kdo nemůže udělat tah, prohrává. Kdo vyhraje pod podmínkou korektního fair play?

Řešení

Problém je vyřešen od konce. Zvažte možnosti rozdělení oblasti pro všechny případy od 1 do 10 buněk a najděte pro ně hodnoty funkce Sprague-Grandy. Všimněte si, že pro tuto hru je v důsledku rozdělení oblasti pokaždé na dvě nové oblasti hodnota funkce Sprague-Grundy nalezena pomocí Nim-sumu .

Hodnota Sprague-Grundy pro n = 10 se ukáže jako 0. Hráč, který provede tah jako první, tedy prohrává. V kterémkoli ze svých tahů se druhý hráč přesune na pozice 4 + 4 nebo n = 1/2/7, pro které je hodnota Sprague-Grundy také rovna 0.

Odpovědět

Vyhrává ten, kdo se posune jako druhý.

Viz také

Odkazy

Berge K. Teorie grafů a její aplikace. M.: IL, 1962. 320c.
Nivasch G. The Sprague-Grundy theory of nestranných her (downlink od 13-05-2013 [3456 dní] - historie )
Kummer B. N. § 2.2. Grundyho funkce a součty řádu p // Grafové hry. — 1982.
BCA Milvang-Jensen. Kombinační hry, teorie a aplikace (neurčité) . — 2000.
Thomas S. Ferguson TEORIE HER
The Sprague-Grundy theory of nestranných her (downlink od 13.05.2013 [3456 dní] - historie ) (anglicky) , 9. listopadu 2005
Sprague-Grundy Values of Grundy's Game
Premiér Grundy. Matematika a hry (neopr.) // Eureka. - 1964. - T. 27 . Archivováno z originálu 27. září 2007.