h1. Teoria jocurilor: numerele Sprague Grundy

(Categoria -, Autor _Cosmin Negruşeri_)
 

'Articol de transcris':downloads?action=download&file=SpragueGrundy.pdf

Teoria jocurilor: numerele
Sprague Grundy
Cosmin-Silvestru Negruşeri

(toc){width: 20em}*{text-align:left;} *Continut*
* 'Introducere':numerele-sprague-grundy#intro
* 'Ce este jocul NIM?':numerele-sprague-grundy#nim
* 'Probleme care folosesc strategia NIM':numerele-spreague-grundy#probleme1
* 'Numerele Sprague Grundy':numerele-sprague-grundy#nsg
h2(#intro). Introducere

Domeniu relativ nou şi încã necercetat în adâncime, teoria jocurilor este o ramurã a matematicii în care de multe ori primeazã inventivitatea şi nu cunoştinţele. Tocmai din acest motiv, în cadrul acestui articol vom introduce câteva noţiuni teoretice care ne vor ajuta în rezolvarea uner probleme din teoria jocurilor.

Domeniu relativ nou şi încã necercetat în adâncime, _teoria jocurilor_ este o ramurã a matematicii în care de multe ori primeazã inventivitatea şi nu cunoştinţele. Tocmai din acest motiv, în cadrul acestui articol vom introduce câteva noţiuni teoretice care ne vor ajuta în rezolvarea uner probleme din teoria jocurilor.

Ingeniozitatea celor pasionaţi poate fi testatã prin introducerea unor probleme de teoria jocurilor la concursurile de matematicã şi informaticã. Deoarece în România, teoria jocurilor nu este studiatã în şcoli, problemele din acest domeniu pot pune în dificultate concurenţii.

NIM
Pentru început ne vom familiariza cu jocul clasic NIM:

h2(#nim). Ce este jocul NIM?
 
Pentru început ne vom familiariza cu jocul clasic *NIM*:
 
    _Se considerã n grãmezi de pietre. Doi jucãtori, vor ridica (alternativ) oricâte pietre dintr-o singurã grãmadã. Câştigãtorul este cel care ia ultima piatrã._
 
h4. Soluţie

Se considerã n grãmezi de pietre. Doi jucãtori, vor ridica (alternativ) oricâte pietre dintr-o singurã grãmadã. Câştigãtorul este cel care ia ultima piatrã.

* Pentru cazul trivial în care numãrul de grãmezi este egal cu 1, primul jucator are evident strategie de câştig, el putând lua toate pietrele din grãmadã.
* Dacã numãrul de grãmezi este egal cu 2, primul jucãtor are strategie de câştig atunci când numãrul de pietre din prima grãmadã este diferit de numãrul de pietre din cea de-a doua, strategia lui fiind cea de a aduce tot timpul grãmada mai mare la numãrul de pietre al grãmezii mai mici, şi cum jocul este finit, înseamnã cã primul jucãtor o sã aducã jocul în starea (0, 0).
* Dacã numãrul de grãmezi este mai mare decât doi strategia se complicã şi nu se mai observã cu "ochiul liber". Stãrile câştigãtoare pentru mai multe grãmezi sunt acele stãri pentru care suma XOR a numerelor de pietre din grãmezi este diferitã de 0, restul stãrilor fiind de pierdere.
 
    De exemplu, dacã avem o gramadã cu o piatrã, o gramadã cu trei pietre, o gramadã cu cinci pietre şi o gramadã cu şapte pietre:

Pentru cazul trivial în care numãrul de grãmezi este egal cu 1, primul jucator are evident strategie de câştig, el putând lua toate pietrele din grãmadã.
Dacã numãrul de grãmezi este egal cu 2, primul jucãtor are strategie de câştig atunci când numãrul de pietre din prima grãmadã este diferit de numãrul de pietre din cea de-a doua, strategia lui fiind cea de a aduce tot timpul grãmada mai mare la numãrul de pietre al grãmezii mai mici, şi cum jocul este finit, înseamnã cã primul jucãtor o sã aducã jocul în starea (0, 0).
Dacã numãrul de grãmezi este mai mare decât doi strategia se complicã şi nu se mai observã cu "ochiul liber". Stãrile câştigãtoare pentru mai multe grãmezi sunt acele stãri pentru care suma XOR a numerelor de pietre din grãmezi este diferitã de 0, restul stãrilor fiind de pierdere.
De exemplu, dacã avem o gramadã cu o piatrã, o gramadã cu trei pietre, o gramadã cu cinci pietre şi o gramadã cu şapte pietre:

o
ooo
ooooo
oooooo

Atunci vom avea:
1 = (0001)
3 = (0011)
5 = (0101)
7 = (0111)
Efectuând XOR (operatorul ^ în C/C++) între reprezentãrile binare ale numerelor  obţinem 0 = (0000) .
Conform propoziţiei de mai sus aceastã stare este de pierdere.
Sã demonstrãm cele afirmate. Dintr-o poziţie cu suma XOR egalã cu 0, pentru orice mutare ajungem evident la o poziţie cu suma XOR diferitã de 0, pentru cã luând dintr-o grãmadã un numãr x de pietre, în suma XOR corespunzãtoare noii stãri bitul cel mai semnificativ al lui x va avea valoarea 1.
Mai rãmâne de demonstrat cã din orice poziţie cu suma XOR diferitã de 0 putem trece printr-o mutare convenabilã într-o poziţie cu suma XOR egalã cu 0. Cãutãm o grãmadã care are un numãr de pietre mai mare sau egal cu cea mai mare putere a lui 2 care apare în suma XOR. Fie x valoarea sumei XOR a tuturor grãmezilor şi y numãrul de pietre din grãmada gãsitã mai devreme. O mutare "câştigãtoare" este extragerea din grãmada gãsitã care are y pietre a y - (x XOR y) pietre (x XOR y este mai mic decât y pentru cã se anuleazã biţii cei mai semnificativi ai lui y şi x). Atunci noua sumã XOR va fi egalã cu 0.
De exemplu: 4 ^ 8 ^ 17 = (00100) ^ (01000) ^(10001) = (11101) = 29.
Mutarea câştigãtoare constã în a lua din cea de-a treia gramadã un numãr de pietre egal cu:
17 - (17 ^ 29) = 17 - 17 ^ 29 = 5 = (00101) .
Dupã acest pas grãmezile vor avea 4, 8, 12 pietre. Ne aflãm astfel într-o stare cu suma XOR egalã cu 0.

    Atunci vom avea:
1 = (0001){~2~}
3 = (0011){~2~}
5 = (0101){~2~}
7 = (0111){~2~}
 
    Efectuând 'XOR':http://www.fredosaurus.com/notes-cpp/expressions/bitops.html (operatorul ^ în C/C++) între reprezentãrile binare ale numerelor  obţinem 0 = (0000){~2~}. Conform propoziţiei de mai sus aceastã stare este de pierdere.
 
    Sã demonstrãm cele afirmate. Dintr-o poziţie cu suma XOR egalã cu 0, pentru orice mutare ajungem evident la o poziţie cu suma XOR diferitã de 0, pentru cã luând dintr-o grãmadã un numãr x de pietre, în suma XOR corespunzãtoare noii stãri bitul cel mai semnificativ al lui x va avea valoarea 1.
 
    Mai rãmâne de demonstrat cã din orice poziţie cu suma XOR diferitã de 0 putem trece printr-o mutare convenabilã într-o poziţie cu suma XOR egalã cu 0. Cãutãm o grãmadã care are un numãr de pietre mai mare sau egal cu cea mai mare putere a lui 2 care apare în suma XOR. Fie x valoarea sumei XOR a tuturor grãmezilor şi y numãrul de pietre din grãmada gãsitã mai devreme. O mutare "câştigãtoare" este extragerea din grãmada gãsitã care are y pietre a y - (x XOR y) pietre (x XOR y este mai mic decât y pentru cã se anuleazã biţii cei mai semnificativi ai lui y şi x). Atunci noua sumã XOR va fi egalã cu 0.
    De exemplu:
%{color:gray}4{@ ^ 8 ^ @}17 = (00100){~2~}{@ ^ @}(01000){~2~}{@ ^ @}(10001){~2~} = (11101){~2~} = 29%.

Exemplificãm în continuare câteva probleme în care se foloseşte strategia de la jocul NIM.

    Mutarea câştigãtoare constã în a lua din cea de-a treia gramadã un numãr de pietre egal cu:
%{color:gray}17 - (17 ^ 29) = 17 - 17 ^ 29 = 5 = (00101){~2~}%.

Problema 1
Pe o tablã de şah, care are n • m cãsuţe, sunt plasaţi pe prima linie n pioni albi şi pe ultima linie n pioni negri. Fiecare dintre cei doi jucãtori poate muta un singur pion, care îi aparţine, un numãr strict pozitiv de cãsuţe în sus sau în jos, astfel încât sã nu ajungã vreun pion alb sã fie mai jos decât pionul negru de pe aceeaşi coloanã. Pierde jucãtorul care nu mai poate muta.

    Dupã acest pas grãmezile vor avea 4, 8, 12 pietre. Ne aflãm astfel într-o stare cu suma XOR egalã cu 0.
 
 
 
h2(#probleme1). Probleme care folosesc strategia NIM
 
h3. Problema 1
 
    _Pe o tablã de şah, care are n • m cãsuţe, sunt plasaţi pe prima linie n pioni albi şi pe ultima linie n pioni negri. Fiecare dintre cei doi jucãtori poate muta un singur pion, care îi aparţine, un numãr strict pozitiv de cãsuţe în sus sau în jos, astfel încât sã nu ajungã vreun pion alb sã fie mai jos decât pionul negru de pe aceeaşi coloanã. Pierde jucãtorul care nu mai poate muta._

Aceastã problemã este o deghizare a jocului NIM, numãrul de pãtrãţele libere între pionul alb şi pionul negru de pe coloana i putând fi considerat numãrul de pietre din grãmada i. Singura diferenţã este cã se pot adãuga pietre la grãmadã (existând posibilitatea mutãrii înapoi).
Aceastã problemã se rezolvã uşor, jucãtorul care are strategie de câştig putând evita asemenea mutãri. O astfel de mutare poate fi utilã numai pentru jucãtorul care este întro poziţie de pierdere.
Când jucatorul care nu are strategie de câştig mutã înapoi x casuţe, celãlalt jucãtor va muta pionul propriu de pe aceeaşi coloanã cu x cãsuţe în faţã, astfel ajungându-se la aceeaşi stare cu cea existentã cu douã mutãri anterior (considerând diferenţa poziţiilor).

Problema 2

h3. Problema 2
 

Aceastã problemã a fost propusã spre rezolvare participanţilor la barajul pentru lãrgirea  lotului naţional din 1997.

Pe o linie sunt plasate la coordonate întregi 2 • n piese roşii şi albastre.
Fiecare piesã roşie poate fi mutatã în dreapta oricâte poziţii astfel încât sã nu sarã peste o piesã albastrã, iar piesele albastre pot fi mutate oricâte poziţii la stânga astfel încât sã nu depãşeascã vreo piesã roşie. Piesele vor alterna: roşu, albastru, roşu, albastru etc. Pierde jucãtorul care nu mai poate muta.

    _Pe o linie sunt plasate la coordonate întregi 2 • n piese roşii şi albastre. Fiecare piesã roşie poate fi mutatã în dreapta oricâte poziţii astfel încât sã nu sarã peste o piesã albastrã, iar piesele albastre pot fi mutate oricâte poziţii la stânga astfel încât sã nu depãşeascã vreo piesã roşie. Piesele vor alterna: roşu, albastru, roşu, albastru etc. Pierde jucãtorul care nu mai poate muta._

Aceastã problemã poate fi, de asemenea, redusã la jocul NIM. Diferenţele poziţiilor perechilor de piese roşii şi albastre consecutive constituie numãrul de pietre al grãmezilor din jocul NIM.

Problema 3
(El Judge MIPT online programming contest Nim Game Give Away!)

h3. Problema 3 _(El Judge MIPT online programming contest Nim Game Give Away!)_

Se considerã n grãmezi de pietre, jucãtorii mutã alternativ, fiecare jucãtor extrãgând oricâte pietre dintr-o singurã grãmadã. Cel care ia ultima piatrã pierde jocul.

    _Se considerã n grãmezi de pietre, jucãtorii mutã alternativ, fiecare jucãtor extrãgând oricâte pietre dintr-o singurã grãmadã. Cel care ia ultima piatrã pierde jocul._

Strategia acestui joc este similarã cu cea aplicatã în jocul NIM cu câteva mici diferenţe. Jucãtorul care are strategie de câştig în poziţia curentã în cadrul jocului NIM face aceeaşi mutare pe care ar face-o în cazul jocului NIM, exceptând cazul în care aceastã mutare lasã doar grãmezi cu o singurã piatrã şi numãrul acestor grãmezi este par.  În aceastã situaţie, dacã ar trebui sã ia x pietre, jucãtorul poate lua x - 1 pietre din grãmada actualã, pentru ca numãrul de grãmezi sã fie impar şi el sã facã ultima mutare.

Numerele Sprague Grundy

 
h2(#nsg). Numerele Sprague Grundy
 

Jocurile care prezintã interes pentru jucãtori sunt acelea care necesitã examinarea unui numãr foarte mare de stãri pentru determinarea strategiei de câştig, deoarece în caz contrar câştigãtorul s-ar cunoaşte chiar de la început. Spre deosebire de aceştia, matematicienii sau informaticienii sunt interesaţi de determinarea unor strategii pentru astfel de jocuri.
Toate jocurile imparţiale cu doi jucãtori cu informaţie totalã pot fi reduse la jocul NIM care se joacã cu nişte grãmezi virtuale, în care mutãrile posibile sunt extragerea oricâtor pietre dintr-o grãmadã sau adãugarea oricâtor pietre la o grãmadã (aşa cum am menţionat anterior, adãugarea de pietre la o grãmadã nu complicã analiza jocului).
Afirmaţia anterioarã constituie un rezultat al Teoriei Sprague-Grundy. Roland Percival Sprague (1936) şi Patrick Michael Grundy (1939) sunt doi matematicieni care s-au ocupat, independent, de teoria jocurilor imparţiale.