Othello

Cuprins

1. Generalitati
2. Prezentarea algoritmilor
   • Algoritmi pentru determinarea mutarilor posibile
   • Algoritmi pentru anularea unei mutari
   • Algoritmi pentru determinarea unei mutari avantajoase
3. Applet demonstrativ
4. Codul sursa
5. Autori si credite

Generalitati

Othello este un joc logic aparut in anul 1975 si inventat de Goro Hasegawa (1971), autorul cartii How to win at Othello. Inainte de aparitia lui Othello, exista deja un joc numit Reversi, lansat in productie (1880) si comercializat in Anglia. Vechiul joc era asemanator ca stil si ca abordare cu acesta, diferind numai prin doua aspecte:

1. Primele patru discuri erau jucate, si nu plasate in locuri predefinite.
2. Fiecare jucator dispunea de un numar fix de discuri. Daca un jucator isi epuiza discurile, celalalt completa restul jocului.

In momentul de fata exista mai multe variante ale acestui joc, majoritatea urmand conventiile de joc noi, cu primele patru discuri fixate. Noi ne vom opri la varianta cea mai raspandita, cu patru piese fixate.

Se spune despre Othello ca ar fi un joc 'invatat intr-un minut si perfectionat intr-o viata intreaga'. Nimic in acest joc nu este aleator; nu exista zaruri sau carti de joc, lucrurile se petrec la fel. Doua jocuri cu mutari identice vor duce exact la acelasi rezultat. Aceasta sugereaza ca jocul ar putea fi abordat folosind o strategie perfecta. Pana acum insa aceasta strategie perfecta nu a fost descoperita (si avand in vedere complexitatea jocului, este foarte probabil sa nu fie descoperita in viitorul apropiat). Oricum pe parcursul timpului au fost descoperite cateva idei si principii utile in abordarea jocului. Strategiile folosite pentru a castiga acest joc se pot imparti in 3 categorii, dupa partile componente ale jocului: de deschidere, intermediare si de inchidere. Jocul obisnuit de Othello are aproximativ 60 de mutari, dintre care primele 20 le putem incadra in deschidere, urmatoarele 20 in categoria celor intermediare iar ultimele 20 in inchidere.

Fiecare jucator face pe rand cate o mutare, punand pe tabla o piesa de o anumita culoare (fiecare jucator dispune de piese dintr-o singura culoare). Castigatorul jocului este cel care la sfarsitul jocului are cele mai multe piese din culoarea sa plasate pe tabla de joc. Regula intermediara este ca atunci cand un jucator inchide un set de piese de ale celuilat jucator intre doua piese ale sale (pe orice directie: orizontala, verticala sau diagonala), piesele celui de-al doilea jucator sunt prelulate de primul schimbandu-si culoarea in cea a pieselor primului jucator. Jocul se termina cand nu mai exista spatiu pe tabla de joc.

In figura anterioara se poate vedea configuratia initiala a tablei. Sunt insemnate cu o cruce posibilitatile de mutare ale negrului, care este primul la mutare.

Prezentarea algoritmilor

Ne propunem sa gasim algoritmi cat mai eficienti pentru a implementa jocul Othello. Calculatorul va trebui sa stie in permanenta daca jucatorul aflat la mutare are mutari posibile si daca nu cumva jocul s-a incheiat. In plus, dorim ca rolul oricaruia dintre jucatori sa poata fi jucat de catre calculator, cu un nivel dat de 'perspicacitate'.

Algoritmi pentru determinarea mutarilor posibile

In mod evident programul va pastra o matrice care arata situatia tablei. Valorile din celulele matricei vor codifica situatiile 'piesa alba', 'piesa neagra' sau 'neocupat'.

Cea mai grosiera abordare este urmatoarea: scanam toata matricea; daca intalnim o celula neocupata, scanam matricea in cele 8 directii pentru a vedea daca jucatorul aflat la rand are posibilitatea de a muta. Se observa usor ca in acest caz complexitatea algoritmului este O(n³).

Pornim de la ideea ca memoria este suficient de mare pentru necesitatile unui joc de Othello si cautam sa folosim structuri suplimentare de date care sa ofere posibilitatea de a rezolva aceleasi probleme in complexitati mai mici.

O prima remarca ar fi ca mutari valide nu pot exista decat langa piesele deja plasate pe tabla. Apare ideea de a pastra o lista cu pozitiile din jurul pieselor de pe tabla. Lista se initializeaza cu cele 8 pozitii din jurul celor 4 piese aflate pe tabla cand incepe jocul. La efectuarea unei mutari se extrage din lista pozitia pe care se muta si se adauga pozitiile din jurul pozitiei de mutare, care nu sunt ocupate de piese si care nu sunt deja in lista. Este de remarcat ca actualizarea face 8 teste, deci complexitatea este afectata doar de algoritmii de inserare si extragere din lista. Pentru o implementare cu movile complexitatea atat a inserarii cat si a extragerii este O(log n), deci practic putem considera ca actualizarea conturului pieselor se face in O(log n).

Folosirea listei cu pozitiile care inconjoara piesele de pe tabla reduce mult din costul scanarii intregii table de joc. Avantajul devine covarsitor pentru dimensiuni mari ale tablei (peste 8), dar este notabil chiar si pentru dimensiuni mici, pentru ca scuteste testarea tuturor celulelor de pe tabla si, pentru fiecare din ele, a celulelor alaturate.

Fireste, nu toate pozitiile din jurul pieselor jucate constituie posibilitati de mutare pentru jucatorul aflat la mutare. Daca ar juca doar jucatori umani este suficient sa testam daca pozitia indicata este o mutare valida. Dar pentru jocul calculatorului este esential sa cunoastem toate mutarile posibile, precum si numarul de piese luate in cazul fiecarei mutari. Vom prezenta in continuare doi algoritmi pentru determinarea posibilitatilor de mutare.

Algoritmul trivial, pe care l-am denumit SearchPath cauta in toate cele 8 sensuri un sir continuu de piese ale adversarului, urmat de o piesa de culoare proprie. Cu alte cuvinte, algoritmul nu face altceva decat sa implementeze definitia mutarii valide pentru jocul Othello. Cazul cel mai defavorabil este cel in care pe toate directiile sunt piese ale adversarului pana la marginea tablei. In acest caz algoritmul executa n-1 iteratii pe fiecare din cele 4 directii (unde n este dimensiunea tablei de joc), deci complexitatea este O(n). Cazul cel mai favorabil este cel in care doar o in jur este doar o piesa a adversarului, urmata imediat de o piesa de culoare proprie:

In acest caz algoritmul executa 9 iteratii. Pentru un joc normal, statisticile se plaseaza undeva intre cazul cel mai favorabil si cel mai defavorabil.

Este de remarcat ca in urma unei mutari posibilitatile de mutare nu se modifica foarte mult. Apare ideea de a salva intr-o matrice suplimentara posibilitatile de mutare. Pentru fiecare pozitie, pentru fiecare culoare si fiecare din cele 8 sensuri se pastreaza numarul de piese care s-ar captura in cazul unei mutari. Astfel am ajuns sa dezvoltam algoritmul ScanLine, care incearca, pentru o piesa care isi schimba culoarea la o mutare, sa actualizeze numai posibilitatile de mutare pe care le modifica mutarea.

In imaginea anterioara am surprins o mutare a negrului in celula cu chenar rosu. Cu X sunt marcate posibilitati de mutare care se pierd in urma mutarii, iar cu + posibilitati de mutare care apar. ScanLine se apeleaza pentru fiecare coordonata in care o piesa isi modifica culoarea si realizeaza scanari in cele 8 sensuri. Prin urmare complexitatea lui este O(n), aceeasi ca si pentru SearchPath.

La prima vedere cei doi algoritmi au timpi de executie comparabili (clasa de complexitate este aceeasi). Pentru ca analiza numarului de iteratii efectuate de fiecare algoritm este practic imposibila (depinde puternic de evolutia situatiei de pe tabla), am recurs la masuratori statistice. Am folosit concomitent ambii algoritmi, numarand celulele examinate de fiecare. Rezultatele au fost uimitoare: in timpul unui joc normal ScanLine a facut de 4 pana la 16 ori mai putine iteratii, factorul mediu fiind de aproximativ 8.

Rezultatul statistic poate fi explicat empiric folosind situatia prezentata anterior ca exemplu. ScanLine va actualiza doar 7 celule din cele 18 care inconjoara piesele de pe tabla. Mai mult, pe tabla se modifica doar 2 piese: cea care este adaugata prin mutare si cea alba capturata. Prin urmare ScanLine va fi apelat doar de doua ori, fata de SearchPath care ar fi trebuit apelat pentru fiecare din cele 18 pozitii care inconjoara piesele de pe tabla.

ScanLine se bazeaza pe cateva reguli simple, care asigura ca nu sunt omise posibilitati de mutare si totodata ca nu se fac iteratii inutile (iteratia se termina imediat ce datele sunt suficiente pentru a face o determinare precisa). ScanLine se apeleaza pentru toate cele 4 directii care trec prin piesele capturate.

Analiza algoritmului a aratat ca se pot elimita testele pentru cazul particular al marginilor tablei prin adaugarea unor linii suplimentare pe fiecare margine a tablei, adica se foloseste o tabla virtuala de (n+2)x(n+2). Liniile suplimentare se considera neocupate. Pentru a elimina costul unor teste suplimentare, matricea posibilitatilor de mutare a fost si ea extinsa la dimensiunea (n+2)x(n+2) si se fac actualizari ale posibilitatilor si pe liniile suplimentare, chiar daca datele respective nu vor fi folosite. In continuare vom prezenta principiile de functionare pentru o directie arbitrara:

• Avand in vedere ca algoritmul actualizeaza numai informatiile care s-ar fi putut modifica in urma unei mutari, trebuie sa se calculeze posibilitatile de mutare pentru ambii jucatori. De asemenea, trebuie sa se invalideze posibilitatile de mutare pe care modificarea culorii piesei le afecteaza.
• Atunci cand se detecteaza o posibilitate de mutare (coordonata si sens) pentru un jucator, celalalt sigur nu are aceeasi posibilitate de mutare.
• Singura posibilitate ca piesa sa fi modificat variantele de mutare ale jucatorului care a efectuat mutarea este ca piesele alaturate celei modificate sa fie ale adversarului. Prin urmare se va face o scanare in fiecare sens al directiei date, pornind din coordonata piesei modificate, pana se intalnesc piese de aceeasi culoare cu cea modificata sau celule neocupate. In cazul in care se detecteaza celule neocupate, jucatorul care a mutat are posibilitate de mutare.
• Singura posibilitate ca piesa capturata sa fi modificat variantele de mutare ale adversarului este ca ea sa fie in mijlocul unui sir continuu de piese de culoarea jucatorului care a facut mutarea, delimitat la un capat de o piesa a adversarului si la celalalt de o pozitie neocupata. Prin urmare se va scana in fiecare sens al directiei atata timp cat piesele sunt de aceeasi culoare cu cea capturata. Se vor obtine doua extremitati, cu urmatoarele posibilitati:
  • ambele sunt neocupate, si prin urmare nici unul dintre jucatori nu are posibilitate de mutare pe directia data (sir continuu de piese de aceeasi culoare)
  • una dintre ele e ocupata (de piesa adversarului), iar cealalta nu; rezulta ca adversarul are posibilitate de mutare in extremitatea neocupata pe directia data
  • ambele sunt ocupate, deci capturarea piesei nu a afectat nici o posiblitate de mutare

Algoritmi pentru anularea unei mutari

Experienta arata ca uneori solutiile cele mai simple sunt si cele mai eficiente. O mutare pe tabla de joc altereaza posibilitatile de mutare ale ambilor jucatori, precum si lista de celule care inconjoara piesele jucate.

In perioada de dezvoltare a aplicatiei s-au testat mai multe solutii pentru restaurarea acestora la anularea unei mutari. Rezultatele au condus la concluzia ca, datorita numarului mare de apeluri pentru aceste metode (folosite de mai multe ori la fiecare pas din algoritmul recursiv), eficienta lor este destul de scazuta. Astfel, se prefera un consum suplimentar de memorie pentru salvarea starii premergatoare mutarii, iar apoi refacerea acesteia la valoarea salvata, la intoarcerea din recursivitate. Desigur, se salveaza numai informatiile esentiale (coordonatele adaugate la conturul pieselor jucate, coordonatele pieselor capturate si posibilitatile de mutare pentru celulele de pe conturul pieselor jucate). Este de notat ca atat salvarile cat si restaurarile sunt parcurgeri liniare de liste, deci au complexitate O(n). In cazul unei implementari intr-un limbaj care permite lucrul direct cu memoria (C/C++) ar fi putut fi mai eficienta copierea liniara a blocurilor de memorie corespunzatoare matricei tablei si matricei posibilitatilor de mutare. Alocarea spatiului de memorie pentru copiere s-ar fi putut face chiar pe stiva (nu presupune decat scaderea valorii indicatorului de stiva, deci este extrem de rapida), din moment ce apelul recursiv are o adancime mica (maxim 4).

Totusi rezultatele lucrului cu liste au fost evident mai bune decat incercarile de restaurare prin diversi algoritmi complicati. S-a observat o scadere a timpului de "gandire" pentru algoritmul AlphaBeta.

Algoritmi pentru determinarea unei mutari avantajoase

Avand in vedere ca ne confruntam cu un joc de strategie de tip "2 player board-game", trebuie cautat un algoritm prin care jucatorul, pus in situatia de a face o mutare, sa aleaga varianta optima. O varianta optima de mutare nu presupune capturarea a cat mai multe piese dintre cele ale adversarului, ci asigurarea ca in pasul/pasii urmatori acesta este pus in dificultate, avand disponibile mutari de cost redus care la randul lor vor oferi jucatorului care "gandeste" mutarea un avantaj care il poate conduce catre castigarea jocului.

Un algoritm standard in elaborarea acestui tip de strategie este algoritmul Min-Max. Acesta functioneaza prin examinarea intregului arbore de joc si alegerea celui mai bun drum ce poate fi estimat. Acesta reprezinta un concept foarte usor de vizualizat, dar deloc eficient. De fiecare data cand se patrunde pe un alt nivel de cautare in arbore, marimea arborelui explorat creste exponential. Sa luam ca exemplu jocul de sah. Acesta tinde sa aiba aproximativ 35 de mutari valide in fiecare pozitie data. Deci daca se foloseste min-max pe o singura ramura de cautare se vor estima aproximativ 35 de pozitii. In cazul in care se examineaza inca un nivel in adancime se vor obtine un numar de 35² pozitii examinate. Acesta nu pare totusi atat de mare (in jur de 1000), dar numarul devine enorm foate repede. O cautare pe 6 nivele de adancime se rezuma la aproximativ 2 miliarde de pozitii, iar o cautare pe 10 nivele la un numar incredibil de 2 cvadrilioane, ceea ce este inacceptabil.

Din fericire exista o metoda de reducere a factorului de ramificare. Mai mult, metoda este perfect stabila si nu prezinta nici un neajuns: este un "castig sigur". Aceasta metoda se bazeaza pe ideea ca atunci cand dispui de o optiune despre care stii ca nu este rea, in momentul in care explorezi alte posibilitati si gasesti una despre care stii in mod sigur ca nu este mai buna decat prima, nu mai trebuie sa faci un efort suplimentar pentru a afla cu cat este mai dezavantajoasa cea din urma. Tot ceea ce este mai dezavantajos decat cea mai buna optiune pana la momentul curent este ignorat fara a fi complet explorat.

Pentru intelegerea cat mai buna a acestui concept propunem exemplul sacilor. Sa presupunem ca cel mai mare dusman al nostru are in fata sa un set de saci, datorita faptului ca a pierdut un pariu cu noi si va fi obligat sa sa ne ofere ceva din acesti saci, regulile despre ceea ce va urma sa ne ofere fiind destul de obtuze. Fiecare sac contine un set de obiecte, iar unul dintre acestea va fi al nostru. Noi vom avea dreptul sa alegem sacul, iar el va avea dreptul sa aleaga obiectul din sac pe care ni-l va oferi. Avem dreptul sa examinam fiecare sac in parte si sa vedem obiectele din el. Evident, el ne va oferi cel mai lipsit de valoare obiect din acel sac. Este usor de aplicat strategia min-max aici pentru a explica problema. Noi reprezentam jucatorul maximizant si vom alege, bineinteles, sacul de valoarea cea mai mare, in timp ce el, fiind jucatorul minimizant ne va oferi obiectul cel mai nevaloros din acel sac. Tot ceea ce trebuie sa facem este sa alegem sacul care contine cel mai valoros "obiect nevaloros". Min-Max ne da un rezultat demonstrabil corect, dar acuratetea evaluarii nu este lucrul cel mai important in aceasta situatie. Suntem presati de timp deoarece ne aflam in situatia jenanta de a cauta prin sacii adversarului sub privirile acestuia. Nu ne permitem sa evaluam toate obiectele din fiecare sac, lucru care ia o groaza de timp.

Cum putem totusi sa facem acest lucu mai eficient decat min-max ?

Sa incepem cu primul sac, examinand fiecare obiect si atribuindu-i o valoare, etichetand la sfarsit intregul sac cu un anumit cost. Sa presupunem ca acest sac ar contine un sandwitch cu unt si cheile de la o masina noua. Realizam ca sandwitch-ul valoreaza mai putin, deci prin luarea acestui sac ne vom alege cu un sandwitch. Faptul ca in sac sunt de asemenea cheile de la o masina noua nu conteaza prea mult, din moment ce realizam ca si adversarul are posibilitatea sa evalueze corect valorile obiectelor, asemenea noua. Vom continua cu urmatorul sac. Algoritmul difera putin acum de min-max. Vom compara pe rand obiectele din sac cu cel mai bun obiect pe care stim ca il vom obtine (sandwitch-ul). Atat timp cat obiectele examinate sunt mai valoroase decat acesta, algoritmul de cautare este similar min-max, tinandu-se cont de cel mai dezavantajos obiect explorat pana in acel punct, deoarece este posibil ca acesta sa fie mai valoros decat sandwitch-ul, ceea ce inseamna ca vom alege acest sac in locul primului. Dar daca intalnim tot un sandwitch sau ceva mai dezavantajos in acest sac, in acel moment se va renunta la explorarea acestuia deoarece in mod evident constituie o alegere mai proasta decat prima. Presupunand totusi ca in acest sac cel mai nevaloros obiect este o bancnota de 20 de dolari, ceea ce reprezinta mai mult decat valoarea sandwitch-ului, acesta va fi sacul preferat.

In cazul gasirii intr-unul dintre sacii urmatori a unui obiect mai putin valoros decat cel retinut pana atunci se renunta imediat la acel sac, indiferent daca in acelasi pot exista cheile unei masini, deoarece exista posibilitatea sa ne alegem doar cu acel lucru mai putin valoros si in nici un caz cu cheile de la masina.

Algoritmul AlphaBeta functioneaza exact dupa aceste principii, numai ca intr-un mod recursiv. Ideea este ca doua scoruri sunt pasate intre pasii algoritmului: unul dintre ele este scorul maximizat (alfa), iar celalalt este scorul minimizant (beta). Alfa reprezinta cel mai bun scor care poate fi fortat printr-o anumita metoda. Tot ceea ce reprezinta mai putin sau egal cu alfa poate fi neglijat, nereprezentand o imbunatatire.

Beta este cel de-al doilea scor reprezentand cazul cel mai defavorabil pentru oponent. Daca in cautare se gaseste un scor mai bun ca beta, acesta se neglijeaza, deoarece cel care este la mutare nu va oferi sansa adversarului de a obtine acest scor mai bun.

Iata algoritmul descris in pseudocod:

AlphaBeta(adancime, jucator, alpha, beta) {

daca (adancime==0) RETURN 1;
GenerareListaMutariValide(jucator);

daca jucator==beta {
  pentru fiecare mutare din lista {
    MakeMove;
    eval(scorMutare);
    val = AlphaBeta(adancime-1, next(jucator), alpha, beta)/scorMutare;
    unMakeMove;
    daca (val > alpha AND beta < alpha) break;
    else beta = val;
  }
  RETURN beta;
}
else {
  pentru fiecare mutare din lista {
    MakeMove;
    eval(scorMutare);
    val = AlphaBeta(adancime-1, next(jucator), alpha, beta)*scorMutare;
    unMakeMove;
    daca (val > alpha) alpha = val;
  }
RETURN alpha
}
} //AlphaBeta

Evaluarea unei mutari (respectiv a unei pozitii, la un anumit moment pe tabla de joc) s-a facut tinand cont de doua aspecte. O mutare este considerata "valoroasa", daca aplicarea sa are ca rezultat capturarea a cat mai multe piese dintre cele ale adversarului, si daca ocupa pe tabla de joc o pozitie avantajoasa din punct de vedere strategic. Valoarea unei mutari se evalueaza prin inmultirea acestor doi factori.

Pentru evaluarea valorii strategice a unei mutari s-a ales solutia construirii unei matrice "oglinda" pentru tabla de joc, fiecarei celule atribuindu-i-se cate o valoare. Astfel intr-un joc de Othello, sunt considerate pozitii cheie din punct de vedere strategic, cele patru colturi ale tablei de joc, acestea fiind asociate cu valori mari. Pozitia urmatoare ca valoare o ocupa marginile tablei, exceptand celulele vecine cu colturile care sunt considerate de valoare minima. De asemenea liniile alaturate marginilor sunt considerate pozitii de valoare scazuta, deoarece mutarea intr-o astfel de pozitie reprezinta o oportunitate pentru adversar de a cuceri marginile. Restul celulelor sunt considerate de costuri egale si nu reprezinta puncte strategice pe tabla de joc.

Solutia construirii unei astfel de matrice a fost preferata datorita reducerii timpului de evaluare a valorii strategice, in defavoarea unui consum minim de memorie.

Numarul de piese capturate la o mutare este de asemenea determinat eficient datorita structurilor de date alese pentru mecanismele interne ale clasei GameBoard. Practic acest numar se afla sumand elementele unui vector cu 8 componete, deci complexitatea este O(1).

Codul sursa

Codul sursa este disponibil sub GNU General Public License si poate fi descarcat de aici.

Autori si credite

Ioan Petru Nicu

• Elaborarea si implementarea algoritmilor pentru jocul calculatorului
• Elaborarea si implementarea algoritmului SearchPath
• Elaborarea si implementarea algoritmului de actualizarea a coordonatelor care inconjoara piesele de pe tabla
• Codificarea eficienta a sensurilor folosite in ScanLine si pentru reprezentarea posibilitatilor de mutare

Radu Constantin Rendec

• Elaborarea si implementarea algoritmului ScanLine
• Elaborarea si implementarea algoritmilor de actualizare a situatiei dupa intoarcerea din apelul recursiv de AlfaBeta
• Implementarea interfetei grafice

Proiectul poate fi distribuit sub GNU General Public License.

(c) 2003 Ioan Nicu, Radu Rendec