Capitolul 1 . Despre Othello

1.1 IstoricJocul Reversi a fost inventat n jurul anilor 1880 de ctre 2 englezi , Lewis Waterman i John W. Mollett . Mai trziu a devenit foarte popular cnd Mattel a produs jocul Reversi sub numele de Othello , iar acum jocul Reversi este cunoscut sub numele de Othello. Numele a fost luat din piesa lui Shakespeare , Othello referindu-se probabil la conflictul dintre Othello i Iago .n 1978 a fost primul campionat mondial ,official, de Othello iar ctigtorul current al acestui campionat este Hideshi Tamenori din Japonia .1.2 ReguliVersiunea standard a jocului se joac pe o tabl de 8 x 8 i ncepe cu 4 piese (2 pentru fiecare culoare) aflate deja pe tabl.

Piesele albe sunt plasate pe D4 i E5 iar cele negre pe E4 i D5 . Juctorii decid ce culoare vor avea piesele fiecruia , dar nntotdeauna negrul ncepe jocul. n figura de mai sus negrul plaseaz urmtoarea pies pe E6 i ncadreaz piesa alb de pe E5 care i schimb culoarea . Urmeaz albul la mutare. Fiecare juctor trebuie s fac o mutare fie c vrea sau nu i astfel fiecare juctor este forat s mute dac sunt mutri valide. Fiecare pies(piese) care este ncadrat ntre piesele adversarului i va schimba culoarea, ncadrarea fiind valabil pe vertical,orizontal i diagonal . Astfel se continu jocul pn cnd tabla este umplut sau nu mai sunt mutri valide. Ctigtorul este cel care are cele mai multe piese pe tabl iar jocul se poate termina cu o victorie, o nfrngere sau o remiz.1.3 StrategiiReversi este un joc de sum zero(zero-sum) cu o informaie perfect i se termin ntr-un numr finit de mutri .Din moment ce toate piesele sunt pe tabl i se poate face un look-a-head (privire nnainte cu1,2,3mutri ) pentru a vedea dac este o victorie sau nu , acesta este jocul perfect de jucat pentru un calculator. Regulile sunt simple, mult mai simple dect la ah sau Go, astfel calculatorul fcnd un look-a-head la fiecare mutare , theoretic poate juca perfect tot timpul , fiind nenvins.Cea mai important strategie , este probabil prinderea colurilor.Cu acestea poi ncadra piesele adversarului de pe margine , sau pe toat diagonal plcii de joc. n plus ctigi ansa de a nu fi prins la aceste coluri.Deci ptratele din jurul colurilor sunt periculoase de jucat n interiorul lor.Marginile sunt rndurile de la 1 la 8 i coloanele de la A la H unde nu sunt coluri.Marginile sunt importante i ele , deoarece i d avantajul s acaparezi ct mai multe piese . Poi folosi o margine pentru a ctiga 8 piese pe tabl.Marginile sunt al 2-lea punct ca siguran dup coluri.Una dintre cele mai grele strategii este de a-i limita mutrile adversarului pn cnd acesta nu mai are mutri valide de fcut, i trebuia s sar o mutare.Aceasta necesit un look-a-head exins i dominarea unei pri ale tablei dealulngul marginii . Odat ce aceste scopuri sunt ndeplinite atunci se ctig o mutare n plus i crete ansa ca mai multe piese s-i schimbe culoarea.Acesta este sfritul jocului unde mai sunt ntre 8 i 12 piese de jucat.Aceasta este probabil cea mai important parte a jocului unde un joc bun se poate transforma ntr-o victorie chiar dac pe parcursul jocului s-au pierdut mai multe piese.Un look-a-ahead n acest moment este foarte simplu avnd n vedere c mai sunt cteva ptrate de jucat.Oricine poate face un look-a-head pentru cteva piese foarte uor. Look-a-head este o strategie nsi, la fel de bun ca cea mai bun strategie de gsit mutarea cea mai bun pentru jocul perfect.Au fost multe programe fcute pentru a jucat Reversi nc din 1980 cnd acesta era popular. Cel mai bun cunoscut program este Logistello ce l-a nvins pe campionul uman Takeshi Murakami n anul 1997 ntr-o victorie cu 6-0 . Dei strategia look-a-head poate garanta aproape o victorie sigur n Reversi , calculele pentru o asemenea mutare sunt intense. 1.4 ReprezentareReprezentarea tablei de Othello este destul de simpl avnd n vedere c jocul este deja o matrice i toate informaiile disponibile sunt pe tabl.Doar se folosete matricea reprezentnd piesele albe cu 1 i cele negre cu -1, iar poziiile goale cu cifra 0Regulile sunt destul de complicate , prima fiind verificarea dac poziia curent este liber ca aceasta s fie disponibil altfel nu e valid odat ce fiecare juctor trebuie s ncadreze piesele adversarului. Urmtoarea regul : poziia trebuie s ncadreze mcar una din piesele adversarului ,aceasta fiind ndeplinit prin verificarea tuturor direciilor pentru o culoare diferit i deasemenea se ncheie cu aceeai culoare a juctorului. Fiecare direcie poate fi reprezentat prin dou bucle for de la -1 la 1 excuznd (0,0).Aceasta reprezint 8 direcii de la poziia curent . Jocul se termin atunci cnd unul din juctori fie nu mai are mutri disponibile , fie table este plin de piese i nici un juctor nu mai are mutri disponibile .Pentru a verifica dac nici un juctor nu mai are mutri valide procedm astfel : verificm fiecare poziie de pe tabl i vedem dac aceasta este goal , apoi verificm fiecare juctor i vedem dac acesta are mutri valide pe aceast poziie . Dac exist o mutare valid atunci jocul nu s-a terminat , dac toate poziiile sunt verificate i nu sunt mutri valide atunci jocul se termin. Se numr piesele de fiecare culoare i se declar ctigtorul . 1.5 Inteligen Artificial Se va folosi o matrice de prioritate pe care Peter Frey a folosit-o n cutrile sale din deciziile umane .Prima prioritate sunt colurile iar ultima vor fi locurile din prejurul lor .Toate celelalte greuti vor fi distribuite marginilor de la 1 la 8 i coloanelor de la A la H. Matricea lui Frey se ncadreaz perfect. Aceasta a fost implementat destul de uor odat ce fiecare poziie are o anumit greutate i este normal ca acestea s fie adugate ntr-o list sortat , iar cnd se ocup una , aceasta este tears din list . Lista conine doar poziiile goale i odat ce este sortat putem verifica poziia cu cea mai mare prioritate i s fie ocupat.Cea mai bun versiune de Inteligen Artificial folosit de computer funcioneaz tot cu ajutorul unei matrici de prioritate doar c face mutarea look-a-head cu un anumit numr de mutri , de obicei 12. Duplicheaz table i simuleaz restul jocului. Dac jocul se termin cu o victorie returneaz 1, pentru o nfrngere returneaz -1 iar pentru remiz va returna 0. Aceste numere sunt folosite pentru a determina care este cea mai bun mutare de fcut. Poziia dinaintea ultimei mutri reunete toi copii si i i adun .Se compar cu vecinul su i cea mai bun poziie se trimite mai sus. Rdcin are atunci cea mai bun poziie ceea ce-I d computerului mai multe anse de ctig.Se returneaz o valoare atunci cnd adversarul nu mai poate muta ceea ce nseamn c trebuie s sar peste o mutare sau c jocul s-a terminat, amndou posibilitti fiind favorabile celui care este la conducere. Acesta limiteaz timpul algoritmului de IA pentru a lua n considerare o poziie nefiind nevoit s simuleze pn la sfritul jocului , ci doar pn cnd adversarul nu mai poate muta. n diagrama urmtoare se observ cum printele i adun copii dnd o euristic a raiei ctig-pierdere. Dac este pozitiv atunci sunt mai multe ctiguri de sfrit de joc , iar dac este negativ atunci adversarul are o ans mai bun la ctig.

Aceast metod nu ia n considerare poziii care pot garanta victoria , de exemplu o rut definit care se termin cu victorie are ntotdeauna printele 1 . Algoritmul de AI nu va allege aceast poziie deoarece sunt alte poziii care au o euristic mai nalt i care nu pot garanta ci pot asigura victoria. Aceast metod deasemeni nu ia n considerare dificultile poziiilor , de exemplu colurile care sunt cruciale n sfritul jocului. Adugarea n dificultate pare c distruge sistemul odat ce dificultatea poziiei va bombarda cu valori sfritul de joc.1.6 ConcluziiMatricea prioritar merge surprinztor de bine i performana sa este mult mai bun dect o presupunere aleas la ntmplare de ctre computer. mpotriva unui nou juctor , folosind presupuneri alese la ntmplare cu siguran se poate ctiga.Din pcate nu se poate nva n timp iar utilizatorul se obinuiete cu jocul i poate nfrnge algortmul. Reeaua neuronal artificial poate fi folosit deasemeni n alte metode de programare a computerului cum s joace i mai ales cum s devin mai bun.Sunt multe avantaje folosind aceste tehnici pe jocul de Othello dect pe alte jocuri. Lumea pare a fi intit spre GO dar Othello a ncununat calea.