Teoria jocurilor

(Categoria Teoria jocurilor, Autori Filip Cristian Buruiana, Vlad Andrei Tudose, Victor Rusu)

Notiuni de baza

Prin joc se intelege un sir de decizii (actiuni, mutari), luate de parti ale caror interese se ciocnesc. Jocurile studiate in acest articol sunt cele care au doi parteneri. De asemenea, toate jocurile analizate sunt jocuri cu mutari libere: la fiecare pas, jucatorul aflat la mutare poate alege sa efectueze una in mod constient, in functie de regulament si de situatia jocului la momentul respectiv. Decizia nu este constransa de niciun factor aleator, precum zaruri, carti de joc sau monede.
Se spune ca un jucator are strategie sigura de castig daca acesta va castiga, indifierent de modul in care ar incerca adversarul sa ii impiedice victoria. Daca un joc respecta toate cele cinci conditii de mai jos si unul dintre jucatori alege intotdeauna strategia cea mai buna, atunci rezultatul este predeterminat:

Se termina dupa un numar finit de pasi
Nu contine un element intamplator introdus de zaruri, carti de joc, etc.
Este un joc cu informatie completa, in care un jucator inainte de a executa o mutare cunoaste rezultatele tuturor mutarilor precedente
Un jucator poate vedea toate mutarile adversarului
Jucatorii muta alternativ

Jocul NIM

Numere Sprague-Grundy

Majoritatea jocurilor impartiale se pot reduce la urmatorul joc: "Se considera un graf orientat aciclic care contine pioni in anumite noduri. Cei doi jucatori muta alternativ. Prin mutare se intelege miscarea unui pion aflat in nodul x intr-un nod y, astfel incat sa existe un arc care iese din nodul x si intra in nodul y. Jucatorul care nu mai poate muta pierde."

De exemplu, pentru graful din figura de mai sus, daca exista doi pioni, unul in nodul 1 si celalalt in nodul 2, primul jucator aflat la mutare are strategie sigura de castig.

Cum graful este aciclic, jocul este finit si are intotdeauna un castigator. Daca in graf exista un singur pion, castigatorul poate fi determinat prin metoda programarii dinamice. Astfel, win_x va fi true daca si numai daca primul jucator aflat la mutare are strategie de castig atunci cand pionul se afla in nodul x. Astfel, win_x = true daca si numai daca exista un nod y astfel incat sa existe arc intre x si y si win_y = false. In caz contrar, win_x = false. Pentru exemplul de mai sus, atunci cand avem un singur pion, win₂ = true, iar win₁ si win₄ vor fi false. Valorile vectorului win se vor calcula in ordinea din sortarea topologica a nodurilor, in complexitate O(N + M), unde N este numarul de noduri iar M numarul de muchii din graful dat.

Folosind teoria dezvoltata independent de Roland Percival Sprague (1936) si Patrick Michael Grundy (1939), putem reduce complexitatea jocului cu mai multi pioni la complexitatea analizei jocului cu un pion. Ca in algoritmul de programare dinamica de mai sus, se incearca determinarea pozitiilor castigatoare si a celor necastigatoare pentru un singur pion.

Definitie: Functia Sprague-Grundy pentru un graf G = (V, E) este o functie mex (minimum excludant) definita pe V cu valori in multimea numerelor naturale, unde mex(x) = minim(n ≥ 0 |n diferit de g(y), oricare ar fi y vecin al lui x).

Altfel spus, valoarea Sprague-Grundy pentru un nod x al grafului aciclic dat este cel mai mic numar natural care nu este atribuit niciunui vecin al nodului x. Valorile Sprague-Grundy pentru nodurile grafului de mai jos sunt scrise cu rosu in dreptul fiecarui nod.

Se observa ca daca mex(x) = 0, in jocul cu un singur pion situat in nodul x jucatorul care muta primul nu are strategie sigura de castig, iar daca mex(x) este diferit de 0 atunci jucatorul care muta primul va castiga intotdeauna, in cazul in care joaca optim. Aceasta afirmatie este usor de demonstrat: daca mex(x) este diferit de 0 atunci exista un nod y, vecin al lui x, astfel incat mex(y) sa fie egal cu 0. In consecinta, primul jucator il va aduce intotdeauna pe adversarul sau in noduri care au valoarea Sprague-Grundy egala cu 0. Mai mult, primul jucator va ramane intotdeauna in noduri cu valoare diferita de 0, deoarece al doilea jucator nu il poate forta sa ajunga in aceste noduri: din nodurile cu valoarea 0 se poate ajunge doar in noduri cu valoarea nenula. In consecinta, jucatorul al doilea va pierde, deoarece va fi adus intr-un nod final (fara urmasi).

Valorile Sprague-Grundy se pot calcula si pentru jocuri in care nu apar precizate explicit grafuri. Fiecare stare posibila a jocului va fi un nod in graf, iar un arc va indica o posibila mutare: o trecere de la o stare la alta, conform regulilor existente.

Adunarea jocurilor

Sa presupunem ca avem N jocuri notate G₁, G₂, ..., G_N pe care vrem sa le adunam. Fiecare din cele N jocuri poate fi reprezentat ca un graf orientat fara circuite in care multimea nodurilor (notata V_i pentru jocul i) este data de multimea starilor iar multimea arcelor (notata E_i pentru jocul i) este data de perechile ordonate de stari adiacente (exista arc de la x la y daca se poate ajunge printr-o mutare din starea x in starea y). Adunand cele N jocuri obtinem un nou joc G pentru care o stare (nod in graful asociat) este un N-uplu (v₁,v₂, ..., v_N) care ne precizeaza starea curenta pentru fiecare joc individual (v_i este starea curenta in jocul i). Pentru a afla daca pentru o anumita stare din jocul G exista sau nu strategie sigura de castig am putea aplica algoritmul simplu de programare dinamica (prezentat mai sus) pentru graful asociat jocului G. Se observa insa ca acest graf are |V₁|*|V₂|* ...*|V_N| noduri, deci algoritmul nu este eficient.
In continuare vom arata cum putem sa determinam eficient daca o stare este castigatoare sau nu pentru un joc compus folosindu-ne de informatiile preprocesate pentru fiecare joc individual.

Adunarea xor

Vom aduna jocurile G₁, G₂, ..., G_N astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Ultimul jucator care muta castiga. Un astfel de joc este si jocul NIM: atunci cand este la mutare, un jucator alege doar una din gramezile existente si efectueaza o mutare doar in aceasta gramada (ia un numar de pietre).

Teorema: Pentru un anumit joc G care este suma jocurilor G₁, G₂, ..., G_N dupa cum a fost definita mai sus o stare v = (v₁,v₂, ..., v_N) este pierzatoare daca si numai daca mex(x1) xor mex(x2) xor ... xor mex(xn) = 0.

Demonstratie: Vom arata ca jocul `G` este echivalent cu un joc `NIM` cu `N` gramezi in care gramada `i` are `mex(v_i)` pietre. In jocul NIM putem alege o gramada cu g(xi) pietre si sa luam cateva astfel incat in gramada sa ramana a<g(xi) pietre. Acestei mutari in jocul NIM ii corespunde o mutare in jocul compus G in care se alege jocul individual Gi si se muta din stare curenta xi intr-o stare y cu g(y)=a. Deoarece a<g(xi) va exista mereu o astfel de stare y. Nu vom lua in considerare mutarile cand dintr-o stare xi se muta intr-o stare y cu g(y)>g(xi) deoarece urmatorul jucator poate muta din starea y intr-o stare z cu g(z)=g(xi) si anuleaza practic mutarea precedentului. (de editat)

Adunarea or

Sa presupunem ca dorim sa adunam jocurile G₁, G₂, ..., G_N in asa fel incat la fiecare pas jucatorul care urmeaza poate sa isi aleaga oricate jocuri si sa faca o mutare in fiecare din jocurile alese. Ultimul jucator care muta castiga. Un astfel de caz se intalneste in problema Pioni.

Demonstratie: Daca toate starile v₁, v₂, ..., v_n sunt terminale atunci starea v este pierzatoare si mex(v₁) = mex(v₂) = ... = mex(v_N) = 0, deci teorema este adevarata. Daca starea x contine cel putin un joc cu valoarea Sprague-Grundy nenula se fac mutari in toate aceste jocuri astfel incat sa lase adversarul intr-o stare in care toate jocurile au valoarea SG egala cu 0. Dintr-o astfel de stare, orice mutare ar face adversarul va exista cel putin un joc cu valoarea SG nenula.

infoarena informatica de performanta