Sprague-Grundy funkció

A Sprague-Grundy funkciót széles körben használják a játékelméletben , hogy nyerő stratégiát találjanak a kombinatorikus játékokban, például Nîmes játékában . A Sprague-Grundy funkciót olyan kétjátékos játékokhoz definiálják, amelyekben az a játékos veszít, aki nem tud újabb lépést tenni.

Diszkrét játékok esetén néha nimbernek is nevezik .

A Sprague-Grundy tétel egy általános következtetés azokból az eredményekből, amelyeket R. Sprague (1935) és P. M. Grandy (1939) egymástól függetlenül állított és bizonyított. Ez abból áll, hogy minden pártatlan játéknál, ahol az utolsó lépést megtevő játékos nyer, minden pozíció esetében egyedileg meghatározzák a Sprague-Grundy függvény értéke, amely meghatározza a nyerő stratégiát vagy annak hiányát.

Definíciók

1. definíció

A Sprague-Grundy függvény egy F függvény, amely x -hez van definiálva, és nem negatív értékeket vesz fel, például:

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

ahol

n bármely nem negatív egész szám,
y az egyik olyan pozíció, amely egy mozdulattal közvetlenül elmozdítható az x pozícióból ,
F( y ) - Sprague-Grandy pozíciók értékei, amelyek közvetlenül az x pozícióból egy mozdulattal elmozdíthatók,
A G( x ) azon pozíciók listája, amelyek egy mozdulattal közvetlenül elmozdíthatók az x pozícióból .

Így az F( x ) a legkisebb nemnegatív egész szám, amely nem található a Sprague-Grundy értékek között bizonyos x esetén .

2. definíció

Az F függvény az összes játékpozíció halmazán a következőképpen van definiálva: $G$

F(P)=0,

ha a P pozíció egyértelműen veszít (nem mozoghat)

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

másképp,

ahol a nem negatív egész számok halmaza, és a P pozícióból megengedett összes mozgás halmaza . $\Omega$ $G(P)$

Alaptulajdonságok

Ha x a végső pozíció, akkor F( x ) = 0. Azok az x pozíciók , amelyekre F( x ) = 0, P-pozíciók (az a játékos veszít, akinek a sora lépni), míg az összes többi pozíció H- pozíciókat (az a játékos nyer, akinek a sora lépést tenni). A nyerő stratégia minden lépésben olyan lépést választani, amelyben a Sprague-Grundy értéke nulla.
Az x pozícióból , amelyre F( x ) = 0, csak az y pozícióba kell mozogni úgy, hogy F( y ) ≠ 0.
Az x pozícióból , amelyre F( x ) ≠ 0, legalább egy lépés van az y pozícióba , ahol F( y ) = 0.

Alkalmazás

A Sprague-Grundy függvény egyik hasznos tulajdonsága, hogy nulla minden vesztes pozíció esetén és pozitív minden nyerő pozíció esetén. Ez egy módszert ad a nyerő stratégia megtalálására:

Keresse meg például a Sprague-Grundy függvényt úgy, hogy rekurzív módon építi fel , a végső pozícióktól kezdve.
Ha a kiindulási helyzetben a Grundy függvény nullával egyenlő, akkor az első játékos elveszíti a játékot.
Ellenkező esetben az első játékos nyerhet, ha minden lépést olyan pozícióba visz, ahol a Grundy függvény nulla értéke.

Játékok összege

Ha vannak játékaink , akkor ezeknek a játékoknak a kombinációját is fontolóra vehetjük, amelyeknél a játéktér egy sor játékmezőből áll, és egy mozdulattal a játékos kiválaszthat néhányat , és egy lépést tehet a játéktéren . Az ilyen kombinációt játékok összegének nevezzük, és jelölése . A játék játékterén kialakult helyzetet , amikor a játéktér a pozícióban van, kényelmesen jelöljük . $n$ $G_{1},G_{2},\dots ,G_{n}$ $G_{1},G_{2},...,G_{n}$ $i,1\leq i\leq n$ $GI}$ $G_{1},G_{2},\dots ,G_{n}$ $G_{1}+G_{2}+\pontok +G_{n}$ $G_{1}+G_{2}+\pontok +G_{n}$ $GI}$ $P_{i}$ $(P_{1},P_{2},\pontok,P_{n})$

A Sprague-Grundy funkciónak van egy meglepő tulajdonsága, amely lehetővé teszi, hogy optimálisan lejátszhassa a játékok összegét , ismerve a Sprague-Grundy funkciót az egyes játékok összes pozíciójában . A következőképpen van megfogalmazva: $G_{1}+G_{2}+...+G_{n}$ $GI}$

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

ahol - kizárólagos "vagy" (más néven XOR). $\oplus$

Példa

Egy feladat

Van egy terület, amely 10 cellából áll. Két játékos játszik. Egy mozdulattal megengedett a terület felosztása két egyenlőtlen, nem nulla területre, hogy az egyes cellák egysége ne sérüljön (vagyis a cella nem osztható fel). Az veszít, aki nem tud mozdulni. Ki nyer a korrekt fair play feltétele mellett?

Megoldás

A probléma a végétől megoldódik. Fontolja meg a terület felosztásának lehetőségeit minden esetben 1-től 10-ig, és keresse meg a Sprague-Grandy függvény értékeit. Ne feledje, hogy ennél a játéknál a terület minden alkalommal két új területre való felosztása eredményeként a Sprague-Grundy függvény értéke a Nim-sum használatával kerül meghatározásra .

Az n = 10 Sprague-Grundy értéke 0. Ezért az a játékos veszít, aki először lép. Bármely lépésében a második játékos a 4 + 4 vagy n = 1/2/7 pozícióba lép, amelyre a Sprague-Grundy értéke szintén 0.

Válasz

Az nyer, aki másodikként lép.

Lásd még

Linkek

Berge K. A gráfok elmélete és alkalmazásai. M.: IL, 1962. 320c.
Nivasch G. A pártatlan játékok Sprague-Grundy-elmélete (2013. május 13. óta [3456 nap] - történelem )
Kummer B. N. 2.2. A Grundy függvény és a sorrend összegei p // Grafikonos játékok. – 1982.
BCA Milvang-Jensen. Kombinatorikus játékok, elmélet és alkalmazások (határozatlan idejű) . – 2000.
Thomas S. Ferguson JÁTÉKELMÉLET
A pártatlan játékok Sprague-Grundy-elmélete (2013. 05. 13. óta lefelé irányuló kapcsolat [3456 nap] - történelem ) (eng.) , 2005. november 9.
A Grundy játék Sprague-Grundy értékei
PM Grundy. Matematika és játékok (neopr.) // Eureka. - 1964. - T. 27 . Archiválva az eredetiből 2007. szeptember 27-én.