Problema tine de teoria
combinatoriala a jocurilor.
(Combinatorial Game
Theory)
Jocul este o
varianta mai simple a unui joc combinatorial
cunoscut
in
literatura de specialitate din strainatate sub
denumirea de Green
Hackenbush.
Totul se
reduce la jocul de Nim. La nim, doi jucatori
efectueaza
mutari alternativ. Jocul se joaca cu N gramezi de
obiecte. O
mutare consta in luarea oricator obiecte (cel
putin 1)
dintr-o
_singura_ gramada. Jucatorul care nu mai poate
efectua nici
o mutare
(toate gramezile s-au terminat) pierde.
Pentru mai
multe detalii despre jocul de Nim si despre modul
in
care Green
Hackenbush se reduce la acest joc, puteti
consulta:
http://www.math.ucla.edu/~tom/GameTheory/Contents.html
Ideea de
baza la rezolvarea problemei este urmatoarea
teorema:
- nodurile
oricarui ciclu din graf pot fi _compactate_
intr-un
singur nod,
fara a modifica rezultatul jocului. Prin
compactare
se intelege
stergerea nodurilor respective si crearea unui nou
nod
care sa
contina toate muchiile aferente nodurilor sterse
(inclusiv
buclele).
In acest mod
problema se reduce de la un graf cu radacina la un
arbore cu
radacina (buclele nu conteaza, pot fi transformate
in
muchii
adaugand un nod fictiv).
O noua
teorema reduce orice arbore la un arbore mai
particular:
- cand mai
multe ramuri de lungime (L1,L2,...LN) se unifica
intr-un nod,
ele pot fi inlocuite cu o ramura de lungime
L1 xor L2
xor ... xor LN
Prin ramura
se intelege o succesiune de noduri x1, x2, ..., xn
in care xi
este adiacent cu xi+1, xn este frunza iar x2, ...,
xn-1
au grad 2.
Ajungem
astel la un caz particular. Un arbore format
dintr-o radacina
si mai multe
ramuri. Dar acest caz este clar echivalent cu
jocul initial
de nim.
Daca in
jocul de nim avem gramezi de dimensiune X1, X2,
..., XN
atunci
jucatorul care este la mutare castiga daca si
numai daca
X1 xor X2
xor ... xor XN este != 0.
Demonstratiile teoremelor
de mai sus se gasesc pe pagina web de mai sus.
La
implementare, pentru compactarea nodurilor, se pot
gasi componentele
biconexe.
Orice componenta biconexa poate fi compactificata
intr-un
singur nod.
Odata arborele construit, rezolvarea este simpla.
|