Teoria jocurilor

Definitie Prin joc vom vom intelege un sir de decizii (actiuni, mutari), luate de persoanele care participa, tinand cont de anumite regului stricte.
Definitie O mutare este o functie f, definite pe multimea pozitiilor jocului si cu valori in aceeasi multime. Daca p este o pozitie a jocului. Atunci f(p) este o noua pozitie a jocului, care se obtine dupa efectuarea unei mutari (actiuni) asupra pozitiei p.
Jocurile pot fi clasificate dupa mai multe criterii: 1. dupa numarul de jucatori 2. dupa natura mutarilor (mutari libere, intamplatoare) 3. dupa cantitatea de informatie (legata de mutarile anterioare)
Definitie Se numeste strategie a unuia dintre jucatori, un ansamblu de reguli, care definesc in mod unic mutarile libere in functie de situatia concreta ivita.
Definitie O strategie se numeste strategie sigura de castig, pentru unul din jucatori, daca acesta va castiga, indiferent de modul in care ar incerca adversarii sa-l opreasca.

Strategii de joc
Cele mai multe jocuri pe care le vom folosi pentru a exemplifica anumite strategii de joc vor fi cu doi jucatori.

 Strategia simetriei
Aceasta strategie se bazeaza pe faptul ca unul dintre jucatori imita mutarea adversarului simetric fata de o axa de simetrie sau fata de un centru de simetrie. Astfel la unele jocuri este necesar sa se gaseasca o axa de simetrie, iar la altele un centru de simetrie. Acest lucru depinde de regulile jocului.
Daca jucatorul imitat mai are de efectuat o mutare, atunci si imitatorul va avea de efectuat o mutare, deci jocul se va termina cand cel imitat nu mai are posibilitatea de a muta. In unele situatii, imitatorul va efectua prima mutare, impartind jocul in doua parti congruente (din punct de vedere al posibilitatilor de a efectua mutari), iar apoi daca adversarul va juca intr-o parte, el va efectua mutarea in cealalta parte.

Ideea strategiei consta in gruparea mutarilor pe perechi de mutari. La fiecare pas, unul din jucatori va putea efectua mutarea pereche a mutarii efectuate de adversar. Unele jocuri din aceasta categorie necesita acoperirea tablei de joc cu Domino-uri, la fiecare mutare unul din jucatori, va actiona in cel de-al doilea patratel al unui Domino, primul patratel fiind actionat de celalt jucator, la mutarea anterioara. Alte jocuri necesita acoperirea tablei cu asa numitele Dominouri virtuale, care sunt alcatuite tot din doua patratele, dar care nu sunt alaturate, ca si in cel standard (spre exemplu jocul saritura calului).
Ca si in strategia simetriei, este posibil ca prima mutare sa nu poata fi imperecheata, cu o alta mutare, dar apoi (dupa ce aceasta mutare este efectuata) sa fie posibil realizarea acestui lucru.

Strategia paritatii
Denumirea acestei strategii vine de la existenta celor doua tipuri de pozitii (para, respectiv impara) in care se poate afla la un moment dat jocul (partida). Ele sunt definite, in avantajul unuia dintre jucatori (sa-l numim pe acesta X, iar pe celalat Y), astfel la fiecare pas, jucatorul X, va putea face o mutare convenabila care sa transforme o pozitie de joc impara intr-o pozitie de joc para. Spre deosebire de X, jucatorul Y, va putea sa treaca la fiecare mutare, doar dintr-o pozitie para intr-una impara. Starea finala a jocului este o pozitie para. Sa presupunem ca avem de aface cu un joc, care indeplineste (printre altele) si urmatoarele conditii: 1. Se joaca intre doi parteneri, care muta alternativ. Cel care nu mai poate muta pierde.

Putem defini, o partitie cu doua clase (A si B) a multimii pozitiilor jocului, astfel incat: a) Pozitia finala sa apartina multimii A. b) Orice mutare aplicata unei pozitii din A, va transforma aceasta pozitie intr-o pozitie din B. Pentru pozitia finala nu exista nici o mutare care sa o transforme intr-o alta pozitie. c) Exista o mutare convenabila, care realizeaza transformarea unei pozitii din B intr-o pozitie din A. In aceste conditii va castiga (daca joaca fara greseli) acel jucataor care la momentul in care este la mutare va gasi jocul intr-o pozitie impara. Pentru a castiga el trebuie sa treaca intr-o pozitie para, lucru posibil, datorita modului cum am definit aceste pozitii. Indiferent ce va face adversarul (jucatorul Y), persoana X, va castiga.

Teorema 1 In urma oricarei mutari, aplicate unei pozitii pare, se trece intr-o pozitie impara. Demonstratie Mutarea para este caracterizata de faptul ca n mod (k+1)=0. La fiecare pas putem extrage p monede, p cuprins intre 1 si k. Atunci: (n-p) mod (k+1) = n mod (k+1) – p mod (k+1) = 0-p mod (k+1) <>0. Rezulta ca pozitia in care se trece este o pozitie impara.
Teorema 2 Dintr-o pozitie impara, se poate trece, in urma unei mutari convenabile, intr-o pozitie para. Demonstratie Sa presupunem ca in stiva avem n monede. Cea mai apropiata pozitie para (si mai mica decat n) este n-(n mod (k+1)). In aceasta pozitie putem trece, daca extragem n mod (k+1) monede. Deci jucatorul X fiind primul la mutare, va castiga (mutand correct, fara greseli) daca n mod (k+1)<>0. Observatie Problema poate fi incadrata si la strategia perechilor, fiecarei mutari a jucatorului Y ii corespunde mutarea pereche a lui A, care trece jocul intr-o pozitie para.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s