Teoria jocurilor: numerele Sprague Grundy

(Categoria -, Autor Cosmin Negruşeri)

Articol de transcris

• Continut
• Introducere
• Ce este jocul NIM?
• Probleme care folosesc strategia NIM
• Numerele Sprague Grundy
• Probleme care se pot rezolva cu numerele Sprague Grundy
• Bibliografie

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.
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.

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ã.

Soluţie

• 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.

Probleme care folosesc strategia NIM

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

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.

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!)

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

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.

Majoritatea jocurilor imparţiale se pot reduce la jocul prezentat în problema Pioni de la runda 47 a concursului de programare Bursele Agora. Acolo se menţiona urmãtorul joc:

Se considerã un graf aciclic care conţine în noduri câţiva pioni, jucãtorii alterneazã la mutare şi fiecare poate muta câte un pion pe un arc care iese din nodul în care este situat pionul. Pierde jucãtorul care nu poate muta.

Cum graful este aciclic, jocul este finit şi are întotdeauna un câştigãtor. Practic, acest joc este suma unor jocuri, mai precis suma a mai multor jocuri cu un singur pion pe graful aciclic. Jocul cu un singur pion poate fi analizat destul de uşor, fiecare nod al grafului putând fi colorat cu alb sau negru dupã cum existã sau nu strategie de câştig dacã în nodul curent ar fi poziţionat pionul. Aceastã colorare poate fi realizatã uşor dacã se porneşte de la nodurile fãrã urmaş şi la fiecare pas se coloreazã câte un nod ai cãrui urmaşi sunt deja coloraţi. Orice joc imparţial poate fi redus la un joc cu un singur pion. Nodurile sunt poziţiile jocului şi arcele grafului sunt mutãrile posibile din fiecare poziţie. Jocul iniţial poate fi şi el transformat, dar numãrul de noduri creşte foarte mult (pentru n pioni şi m noduri, numãrul de noduri din jocul transformat este n^m) şi nu este practic sã colorãm graful rezultat. Folosind teoria dezvoltatã de Sprague şi Grundy, putem reduce complexitatea analizei jocului cu n pioni la complexitatea analizei jocului cu un pion.

Vom introduce funcţia mex cu semnificaţia: mex(S) este elementul minimal natural care nu aparţine mulţimii S. Pentru fiecare nod x al grafului aciclic considerat, vom calcula valoarea funcţiei gx = mex(gx₁, gx₂, …, gx_k), unde x₁, x₂, …, x_k sunt urmaşii nodului x în graf. Pentru nodurile fãrã urmaşi gx = 0.

Analog jocului cu un singur pion, graful poate fi etichetat din aproape în aproape, pornind de la nodurile fãrã urmaşi. Observãm cã, dacã gx = 0 în jocul cu un singur pion situat în nodul x nu avem strategie de câştig, iar dacã gx este diferit de 0 avem strategie de câştig. Restul informaţiei ne ajutã la determinarea unei strategii pentru jocul cu n pioni. Observãm cã putem reduce acest joc la jocul NIM în care grãmada virtualã asociatã pionului i are un numãr de pietre egal cu valoarea g a nodului în care este situat pionul i.

De ce este acest joc echivalent cu jocul NIM?

Aşa cum la NIM puteam lua oricâte pietre dintr-o grãmadã, aici putem muta pionul dintr-un nod cu valoarea g într-un nod astfel încât noua valoare pentru pionul i poate fi orice numãr de la 0 la g - 1. Prin urmare, pentru a verifica dacã suntem într-o poziţie de câştig în jocul cu pionii, putem aplica strategia jocului NIM şi obţinem cã suntem într-o poziţie de câştig dacã suma XOR a numerelor din nodurile ocupate de cei n pioni este diferitã de 0. Aceastã sumã se numeşte funcţia Sprague Grundy, SG(i₁, …, i_n) = gi₁ ^ gi₂ ^ gi₃ ^ … ^ gi_n.

Problema de la runda 47 (Pioni) se rezolvã acum uşor efectuând o sortare topologicã a nodurilor grafului aciclic şi numerotând nodurile folosind funcţia mex.

Probleme care se pot rezolva folosind numerele Sprague Grundy

Problema 4

Problema Joc a rundei 13 a concursului de programare Bursele Agora putea fi rezolvatã în acest mod.
În acea problemã se cerea sã verificãm existenţa unei strategii de câştig pentru un joc similar cu NIM în care se putea lua dintr-o grãmadã o piatrã sau un numãr prim de pietre.

Dacã determinãm valorile Sprague Grundy pentru grãmezi de dimensiuni mici putem observa cã se repeta o succesiune de numere: 0 1 2 3 0 1 2 3 …
Putem demonstra prin inducţie cã aceastã secvenţã se va repeta la nesfârşit.
Pentru o grãmadã de dimensiune n valoarea asociatã va fi n modulo 4. Pentru 0 ≤ n ≤ 3 afirmaţia este adevãratã. Vom presupune afirmaţia adevãratã pentru toate valorile m < n. Sã demonstrãm acum cã este adevãratã şi pentru n. Deoarece putem lua din n pietre una, douã sau trei pietre, mai rãmâne valoarea n modulo 4 care nu este eliminată încã din valorile potenţiale asociate grãmezii de dimensiune n. Vom arãta în continuare cã aceastã valoare nici nu va fi eliminatã. Eliminarea ei ar însemna cã putem lua din n un numãr p de pietre şi atunci din (n - p) modulo 4 = n modulo 4, am avea: p modulo 4 = 0, dar p este un numãr prim, deci valoarea Sprague Grundy asociatã unei grãmezi de dimensiune n este n modulo 4.

Problema 5 (El Judge MIPT online programming contest, Stone game)

Se considerã k grãmezi cu n₁, n₂, …, n_k pietre fiecare. Când este rândul sãu, un jucãtor poate lua dintr-o gramadã 2^m pietre. Jucãtorul care ia ultima piatrã câştigã.
Restricţii: k ≤ 50, n_i ≤ 10200.

Sã determinãm valorile Sprague Grundy pentru grãmezi mici:
0 : 0;  1 : 1;  2 : 2;  3 : 0;  4 : 1;  5 : 2;  6 : 0
Observãm şi aici secvenţa repetitivã 0 1 2 0 1 2, deci am putea trage concluzia cã valoarea Sprague Grundy asociatã unei grãmezi de dimensiune n este n modulo 3. Aceastã afirmaţie este adevaratã şi urmeazã aceeaşi demonstraţie ca în cazul problemei anterioare, iar restul modulo 3 pentru n numãr cu 200 de cifre este simplu de gãsit determinând suma cifrelor numãrului.

Problema 6 (El Judge MIPT online programming contest, Stone game II)

Se considerã k grãmezi de pietre cu n₁, n,₂ …, n_k pietre. Un jucãtor poate lua dintr-o grãmadã la mutarea lui un numãr pozitiv de pietre dar nu mai mult de jumãtate din pietrele din grãmadã. Jucãtorul care nu mai poate muta pierde.
Restricţii: k ≤ 50, n_i ≤ 100000.

Numãrul 100000 nu este foarte mare şi valorile Sprague Grundy pot fi determinate off-line şi incluse în programul nostru ca şi constante. Putem scrie pentru valori mici secvenţa Sprague Grundy:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 0 2 1 3 0 4 2 5 1 6 3 7
Pentru n impar valoarea asociatã este aceeaşi cu valoarea asociatã lui n/2, şi pentru n par valoarea asociatã este n/2. Acest lucru se poate demonstra prin inducţie matematicã.

Problema 7 (CEOI 2000, Cluj-Napoca, problema Sticks)

Se considerã n (n ≤ 10) rânduri de beţe pe o masã, cu S_i (S_i ≤ 10) beţe aliniate pe fiecare rând şi doi jucãtori. Beţele de pe rândul i sunt numerotate secvenţial de la 1 la S_i. Cei doi jucãtori mutã alternativ. Fiecare mişcare constã în eliminarea a unu, douã sau trei beţe de pe acelaşi rând. Beţele trebuie sã fie numerotate secvenţial, adicã sã fie consecutive. De exemplu, un rând are 10 beţe şi primul jucãtor eliminã beţele 4, 5, 6, deci vor rãmâne numai beţele 1, 2, 3, 4, 8, 9, 10. Al doilea jucãtor poate lua la rândul sãu beţele 1, 2, 3, dar nu beţele 3, 7, 8 pentru cã acestea nu sunt numerotate consecutiv (bineînţeles cã existã şi alte mutãri valide). Câştigã jucãtorul care ia ultimul bãţ de pe masã.

Problema generalã are o soluţie ingenioasã care ţine seama de paritãţile rândurilor, dar la aceastã problemã, datoritã mãrginirii lui S_i (S_i ≤ 10) nu este necesar sã fim ingenioşi. Restricţia S_i ≤10, ne ajutã prin faptul cã numãrul total de poziţii (dacã jucãm pe o singurã gramadã), este 2¹⁰. Vom reprezenta o poziţie printr-un întreg, iar dacã acel întreg are în codificarea lui binarã pe poziţia i un bit de 1 înseamnã cã el reprezintã un rând de beţe care conţine în el bãţul numerotat cu i. Este uşor de realizat un graf aciclic al mişcãrilor pentru un rând (graful este aciclic pentru cã la fiecare mutare luãm beţe din configuraţie). Numerotãm fiecare poziţie cu numerele Sprague Grundy, şi acum problema deciderii dacã suntem sau nu într-o poziţie câştigãtoare devine banalã. În problema iniţialã trebuia sã jucãm împotriva calculatorului şi sã câştigãm. Putem realiza aceasta folosind mutarea câştigãtoare prezentatã la jocul NIM.

Problema 8

Aceastã problemã a fost propusã spre rezolvare la concursul Internet Problem Solving Contest (cel mai prestigios concurs online) şi o puteţi gãsi la această adresă. Ea a fost folositã şi la concursul organizat de .campion la o rundã online. Rezolvarea ei, complicatã, folosind numerele Sprague Grundy prezentate în acest articol, se poate gãsi în [3], pe site-ul [7], sau pe siteul concursului .campion.

Problema 9

Aceastã problemã a fost propusã spre rezolvare la ediţia din acest an a Olimpiadei Naţionale de Informaticã din Ucraina.

Doi participanţi mãnâncã alternant din nişte tablete de ciocolatã dupã urmãtoarele reguli:
• taie o tabletã în douã, tãietura trebuie sã fie paralelã cu una din laturile tabletei şi trebuie sã nu taie pãtrãţelele de ciocolatã;
• poate sã rupã şi sã mãnânce orice linie sau coloanã de pãtrãţele care nu se aflã pe marginea tabletei;
• poate sã rupã şi sã mãnânce toate patrãţelele de pe marginea tabletei, cu condiţia ca tableta rãmasã sã aibã cel puţin dimensiunea 1×1.
Nici una dintre aceste trei mutãri nu poate fi efectuatã asupra unei tablete de dimensiune 1×1. Pierde jucãtorul care nu mai poate efectua nici o mutare.
În fişierul de intrare se va afla numãrul N (1 ≤ N ≤ 100) de tablete, iar pe urmãtoarea linie sunt N perechi de numere întregi care reprezintã dimensiunile tabletelor.
În fişierul de ieşire se va afla un singur numãr întreg reprezentând numãrul mutãrilor câştigãtoare pentru primul jucãtor.

Pentru aceastã problemã vom calcula matricea SG_i,j care reprezintã valoarea Sprague-Grundy asociatã unei tablete de dimensiuni (i, j). Sã vedem care este recurenţa care va satisface elementele matricei SG:

SG_i,j = mex(SG_i,k ^ SG_i,j-k, (1 ≤ k < j) mutarea întâi
SG_k,j ^ SG_i-k,j, (1 ≤ k < i)
SG_i,k ^ SG_i,j-k-1, (1 ≤ k < j - 1) mutarea a doua
SG_k,j ^ SG_i-k-1,j, (1 ≤ k < i - 1)
SG_i-2,j-2) (i > 2 şi j > 2) mutarea a treia

Acum, pentru a calcula numãrul de mutãri câştigãtoare efectuãm asupra fiecãrei tablete din fişierul de intrare toate mutãrile posibile care sunt cel mult de 4 • 100 + 1 şi facem suma XOR a valorilor Sprague Grundy pentru restul tabletelor neimplicate în mutare şi a tabletelor rezultate din mutare. Pentru a calcula SG_i,j trebuie sã parcurgem cel mult 2 • _i + 2 • j + 1 valori obţinute. Astfel, algoritmul de determinare al valorilor matricei SG are ordinul de complexitatea O(N³).
Complexitatea algoritmului care determinã numãrul de mutãri câştigãtoare este O(N²).

Am vãzut cã aceste numere sunt folositoare pentru rezolvarea unor probleme de jocuri combinatorice. Chiar dacã numãrul stãrilor grafului nostru aciclic poate sã fie foarte mare, putem sã ne dãm seama, câteodatã, din valorile mici de o regulã pe care o urmeazã numerele, sau mãcar putem determina mai uşor configuraţii pentru care jocul are sau nu strategie de câştig, fapt care ne poate ajuta în descoperirea rezolvãrii generale.

Bibliografie

1. ***, colecţia GInfo
2. Mihai Oltean, Programarea Jocurilor Matematice, Editura Albastrã, Cluj-Napoca, 1996
3. Thomas S. Ferguson, Game Theory Text
4. http://www.ams.org/new-in-math/cover/games1.html
5. http://www.cut-the-knot.com
6. http://www.mathworld.wolfram.com
7. http://ipsc.ksp.sk/

Cosmin-Silvestru Negruşeri este student în anul III la Universitatea Babeş-Bolyai din Cluj-Napoca. El poate fi contactat prin e-mail la adresa [email protected].