AVRAM Marius 324CB - Tema 2 PA, Joc de table 

Jocul de table necesita o combinatie de tactica, stategie si noroc. In implementarea versiunii botului meu de table m-am ocupat pe cat posibil de partea de strategie si tactica, insa intrucat norocul nu poate fi manipulat in interes propriu este posibil ca botul sa nu castige intotdeauna meciurile.

Detalii implementare:
Botul este scris in Java. Unul din primele lucruri de care m-am ocupat a fost acela de a genera toate mutarile valide penturu un zar si un jucator dat. Am creat in acest scop clasa Board care tine doi vectori cu pozitiile pieselor pe tabla, referinte catre acestia folositi in diverse circumstante, jucatorul cu care este initializat tabla. Tipul jucatorului este instantiat in functie de cel primit de la server. Pozitiile pieselor sunt initializate in constructorul lui Board, cel care primeste ca parametru un player. Mai exista un alt tip de constructor care primeste ca parametru un Board. Acesta este folosit pentru a "clona" obiectele. Board mai are si un array de bytes folosit pentru a stoca comanda ce trebuie trimisa catre server. Desi o mare parte din tablele generate nu vor folosi acest array este mult mai usor sa il stocam aici.

In cadrul metodei de generare a mutarilor pentru un zar se tine cont de anumite restrictii. De exemplu o piesa nu poate fi mutata in afara tablei doar daca jucatorul se afla in faza terminala, adica are toate piesele in propria casa. Sau o piesa nu poate fi mutata decat pe spatii care au cel mult o piesa de-a adversarului pe ea. Exista si cazuri in care nu se poate genera nici o mutare, deoarce combinatia de zaruri nu ii permite acest lucru jucatorului. Apoi am 2 metode care genereaza mutarile pentru doua zaruri. Este nevoie de 2 metode deoarece combinatia de zaruri poate fi o dubla sau nu. Practic cea de dubla apeleaza functia de generare a mutarilor pentru un zar dat de 4 ori. Problema este ca trebuie verificat la fiecare pas daca mai exista mutari valide si trebuie modificata comanda ce urmeaza sa fie trimisa catre server in mod corespunzator. Din cauza aceasta cea de-a doua metoda are dimensiuni mai mari. Mutarile se aplica dupa fiecare zar. Astfel ne asiguram ca mutarile ulterioare sunt facute pe baza deciziei luate la pasul/pasii anteriori. Pentru a reveni la tabla anterioara dupa ce am facut un numar de mutari folosim o metoda de backup care salveaza atat arrayurile cu piese pentru jucatorul alb cat si pentru cel negru intr-o stiva. Aceasta are in cel mai rau caz 4 elemente (pentru dubla). Dupa efectuarea unei mutari stiva se goleste si se revine la configuratia initiala a tablei. Toate mutarile posibile sunt salvate intr-un ArrayList de Boards. Observatie: functiile de generare si efectuare a tuturor mutarilor pot fi folosite atat de jucatorul propriu cat si de adversar pentru generarea mutarilor in algoritmul ExpectiMax.

Complexitate: 
Generarea tuturor mutarilor pentru un zar dureaza O(n), unde n este numarul de casute de pe tabla. Realizarea tuturor mutarilor pentru cazul normal dureaza O(n^2), iar pentru cazul unei duble dureaza O(n^4).

Pentru a usura mutarea pieselor pe tabla in functie de tipul jucatorului(deoarece fiecare jucator are alta directie de parcurs a tablei si alta casa) am creat o interfata Player care este iplementata pentru WhitePlayer si BlackPlayer in moduri diferite. Metodele acesteia sunt apelate in Board foarte usor fara a fi nevoie sa se stie tipul jucatorului, tipul lor aflandu-se la runtime in functie de caz. 

Algoritm: 
In cele din urma am realizat clasa ExpectiMax care are un functie de evaluare a unei table. Aceasta contine diferiti metrici cu diferite ponderi in functie de imporatanta lor, cum ar fi: capturarea unei piese a inamicului, raspundirea pe harta, existanta a mai mult de o piesa pe o casuta, si apropierea de propria casa(metrici buni - pro) sau rai - cons: retinerea a mai mult de 2 piese pe o casuta (cu cat creste mai mult numarul de piese pe o singura casuta este mai rau deoarece se scade din raspandirea pe harta care poate bloca mai usor inamicul), piesa expusa (1 pe casuta) sau piesa mancate.

Pentru a luat cea mai buna decizie in cadrul unei combinatii de zaruri am folosit algoritmul Expectimax. L-am folosit doar pentru 3 nivele: nivelul propriu in care generez toate mutarile pe baza zarurilor primite de la server, nivelul random in care generam toate combinatiile posibile de zaruri pentru inamic, si nivelul inamicului in care pentru fiecare combinatie de zaruri de la nivelul random generam toate mutarile posibile. Cand se la adancimea maxima se returneaza metrici pentru fiecare tabla. La nivelul adversarului preiau minimul, la nivelul random adun toate valorile returnate la un afla (Nu inainte de a le inmulti cu numarul de posibilitati) si la nivelul propriu preiau maximul. Tabla cu scor maxim este cea mai buna alegere. 

Complexitatea algoritmului expectimax este exponentiala: O(b^d). Branching factorul variaza mult in functie de mutare, putand ajunge si la numere foarte mari pentru o dubla (~500).

Cel mai dificil client care poate fi invins.

Am reusit sa inving uneori si botul de nivel 8 (as prefera sa se testeze si cu acesta). Insa cel mai bine am invins botul de nivel 5.