Sprague-Grundy-toiminto

Sprague-Grundy-toimintoa käytetään laajasti peliteoriassa voittostrategian löytämiseen kombinatorisissa peleissä, kuten Nîmesin pelissä . Sprague-Grundy-toiminto on määritelty kahden pelaajan peleihin, joissa pelaaja, joka ei pysty tekemään uutta siirtoa, häviää.

Erillisten pelien tapauksessa sitä kutsutaan joskus nimberiksi .

Sprague-Grundyn lause on yleinen päätelmä tuloksista, jotka R. Sprague (1935) ja P. M. Grandy (1939) ovat todenneet ja todenneet itsenäisesti. Se koostuu siitä tosiasiasta, että jokaisessa puolueettomassa pelissä , jossa viimeisen liikkeen tehnyt pelaaja voittaa, jokaiselle positiolle määritetään yksilöllisesti Sprague-Grundy-funktion arvo, joka määrittää voittostrategian tai sen puuttumisen.

Määritelmät

Määritelmä 1

Sprague-Grundy-funktio on funktio F, joka on määritetty x :lle ja joka ottaa ei-negatiivisia arvoja, kuten:

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

missä

n on mikä tahansa ei-negatiivinen kokonaisluku,
y on yksi asemista, joka voidaan siirtää suoraan paikasta x yhdellä liikkeellä,
F( y ) - Sprague-Grandy-arvot paikoista, jotka voidaan siirtää suoraan paikasta x yhdellä liikkeellä,
G( x ) on luettelo paikoista, jotka voidaan siirtää suoraan paikasta x yhdellä liikkeellä.

Näin ollen F( x ) on pienin ei-negatiivinen kokonaisluku, jota ei löydy tietyn x :n Sprague-Grundy-arvoista .

Määritelmä 2

Funktio F määritellään kaikkien pelipaikkojen joukkoon seuraavasti: $G$

F(P)=0,

jos asema P on yksiselitteisesti häviämässä (liikettä ei voida tehdä)

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

muuten,

missä on joukko ei-negatiivisia kokonaislukuja ja on kaikkien sallittujen siirtojen joukko paikasta P . $\Omega$ $G(P)$

Perusominaisuudet

Jos x on lopullinen asema, niin F( x ) = 0. Positiot x , joille F( x ) = 0, ovat P-paikkoja (häviäminen pelaajalle, jonka vuoro on siirtyä), kun taas kaikki muut paikat ovat vastaavasti H- asemat (voitto pelaajalle, jonka vuoro on tehdä siirto). Voittava strategia on valita jokaisessa vaiheessa liike, jossa Sprague-Grundyn arvo on nolla.
Asemasta x , jossa F( x ) = 0, siirtyy vain asentoon y siten, että F( y ) ≠ 0.
Asemasta x , jolle F( x ) ≠ 0, on vähintään yksi siirto paikkaan y , jossa F( y ) = 0.

Sovellus

Yksi Sprague-Grundy-funktion hyödyllisistä ominaisuuksista on, että se on nolla kaikille tappiollisille positioille ja positiivinen kaikille voittosijoille. Tämä antaa menetelmän voittaa strategia:

Etsi Sprague-Grundy-funktio esimerkiksi rakentamalla se rekursiivisesti alkaen lopullisista paikoista.
Jos alkuasennossa Grundy-funktio on yhtä suuri kuin nolla, peli häviää ensimmäiselle pelaajalle.
Muuten ensimmäinen pelaaja voi voittaa siirtämällä jokaisen liikkeen asentoon, jossa Grundy-funktion arvo on nolla.

Pelien summa

Jos meillä on pelejä , niin voimme harkita näiden pelien yhdistelmää, jossa pelikenttä koostuu joukosta pelikenttiä ja yhdellä liikkeellä pelaaja voi valita joitain ja tehdä liikkeen pelikentällä pelaamista varten . Tällaista yhdistelmää kutsutaan pelien summaksi ja sitä merkitään . Tilanne pelin pelikentällä , kun pelin pelikenttä on paikoillaan , merkitään kätevästi nimellä . $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}+\pisteet +G_{n}$ $G_{1}+G_{2}+\pisteet +G_{n}$ $G_{i}$ $P_{i}$ $(P_{1},P_{2},\pisteet ,P_{n})$

Sprague-Grundy-toiminnolla on yllättävä ominaisuus, jonka avulla voit pelata optimaalisesti pelien summaa , kun tiedät Sprague-Grundy-toiminnon jokaisen pelin kaikissa asemissa . Se on muotoiltu seuraavasti: $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}),

missä - yksinomainen "tai" (alias XOR). $\oplus$

Esimerkki

Tehtävä

Siellä on alue, joka koostuu 10 solusta. Kaksi pelaajaa pelaa. Yhdellä siirrolla alue on sallittu jakaa kahteen epätasaiseen nollasta poikkeavaan alueeseen, jotta kunkin yksittäisen solun yhtenäisyyttä ei rikota (eli solua ei voida jakaa). Se, joka ei pysty liikkumaan, häviää. Kuka voittaa oikean reilun pelin ehdoilla?

Ratkaisu

Ongelma ratkeaa loppuun asti. Harkitse vaihtoehtoja alueen jakamiseksi kaikille tapauksille 1 - 10 soluun ja löydä niille Sprague-Grandy-funktion arvot. Huomaa, että tässä pelissä Sprague-Grundy-funktion arvo saadaan käyttämällä Nim-summaa , koska alue jaetaan joka kerta kahdeksi uudeksi alueeksi .

Sprague-Grundyn arvo arvolle n = 10 osoittautuu 0:ksi. Näin ollen pelaaja, joka tekee ensimmäisen liikkeen, häviää. Jokaisessa siirrossaan toinen pelaaja siirtyy paikkoihin 4 + 4 tai n = 1/2/7, jolle Sprague-Grundy-arvo on myös 0.

Vastaus

Se, joka liikkuu toiseksi, voittaa.

Katso myös

Linkit

Berge K. Graafisten teoria ja sen sovellukset. M.: IL, 1962. 320c.
Nivasch G. Sprague-Grundyn puolueettomien pelien teoria (downlink alkaen 13-05-2013 [3456 päivää] - historia )
Kummer B. N. §2.2. Grundy-funktio ja järjestyssummat p // Graafipelit. – 1982.
BCA Milvang-Jensen. Kombinatoriset pelit, teoria ja sovellukset (rajoittamaton) . – 2000.
Thomas S. Ferguson PELITEORIA
Sprague-Grundyn teoria puolueettomista peleistä (downlink alkaen 13.5.2013 [3456 päivää] - historia ) (eng.) , 9. marraskuuta 2005
Grundyn pelin Sprague-Grundy-arvot
PM Grundy. Matematiikka ja pelit (uuspr.) // Eureka. - 1964. - T. 27 . Arkistoitu alkuperäisestä 27. syyskuuta 2007.