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.

h3. Adunarea xor

 
(vmenu)*(section) '*Adunarea xor*':teoria-jocurilor/adunarea-xor#xor
* 'Adunarea or':teoria-jocurilor/adunarea-or#or
* 'Adunarea almost or':teoria-jocurilor/adunarea-almost#almost
* 'Adunarea and':teoria-jocurilor/adunarea-and
* 'Adunarea also':teoria-jocurilor/adunarea-also
 
h3(#xor). Adunarea xor

Vom aduna jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$} astfel incat la fiecare pas jucatorul care urmeaza trebuie sa isi aleaga exact un joc si sa faca o mutare in jocul respectiv. Jucatorul care nu mai poate muta pierde. Un astfel de joc este generalizarea jocului cu un pion din capitolul precedent si se intalneste in problema 'Pawns':problema/pawns, data la concursul national Bursele Agora. Pentru a determina castigatorul in cazul acestui joc, ne vom folosi de urmatoarea teorema:

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 {$mex(x{~i~})$} 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)

h3. Adunarea or
 
Sa presupunem ca dorim sa adunam jocurile {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~P~}$}, astfel incat la fiecare pas jucatorul care urmeaza poate sa isi aleaga oricate jocuri si sa faca o mutare in fiecare din jocurile alese. Jucatorul care nu mai poate muta pierde. Un astfel de caz se intalneste in problema 'Pioni':problema/pioni.
 
_Teorema_: Pentru un anumit joc $G$ care este suma jocurilor {$G{~1~}$}, {$G{~2~}$}, ..., {$G{~N~}$} dupa cum a fost definita mai sus o stare {$v = (v{~1~},v{~2~}, ..., v{~N~})$} este pierzatoare daca si numai daca {$mex(v{~1~}) = mex(v{~2~}) = ... = mex(v{~N~}) = 0$}.
 
_Demonstratie_: Daca toate starile {$v{~1~}$}, {$v{~2~}$}, ..., {$v{~n~}$} sunt terminale atunci starea $v$ este pierzatoare si {$mex(v{~1~}) = mex(v{~2~}) = ... = 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.
 
 

p{margin:1em; padding: 0.5em; height: 45px; border-top: 1px solid silver;}=.
'Notiuni de baza':teoria-jocurilor | 'Jocul NIM':teoria-jocurilor/jocul-nim | 'Numere Sprague-Grundy':teoria-jocurilor/numere-SG |
'*Adunarea jocurilor*':teoria-jocurilor/adunarea-jocurilor | 'w-numere':teoria-jocurilor/w-numere | 'Aplicatii si probleme':teoria-jocurilor/probleme

public

protected