tiberiu92 / tron-many Goto Github PK

##Tron-Many: Proiectarea algoritmilor - Proiect 2013##

Nume echipa: Shift-Delete
Membri: Manta Paul-Cristian (323CB), Popescu Gabriel-Cosmin (323CB), Scarlat Tiberiu (323CB), Velea Cosmin (323CB)

HackerRank: hackerrank.com/ShiftDelete
Gmail: [email protected]

###Etapa II###

Tag: stage-ii-submission

Pentru aceasta etapa am implementat un algoritm ce foloseste echilibrul Nash pentru a gasi mutarea care minimizeaza sansele de a pierde meciul. Pentru a evalua starea hartii (si a decide care jucator este in avantaj), am aproximat cat de raspandita este zona accesibila fiecarui jucator in urmatorul fel (pseudocod):

area       := getProximalArea(player) 
rowSpread  := rowVariance(area)
colSpread  := colVariance(area)
areaSpread := rowSpread * colSpread  

Functiile rowVariance si colVariance calculeaza varianta sufrafetei date (din statistica), dupa cele doua axe. Daca toate celulele se afla pe o singura linie sau coloana, atunci rowSpread, respectiv colSpread, va fi zero deci si produsul celor doua va fi zero.

Algoritmul ce foloseste echilibrul Nash cauta cu o adancime foarte mica (din motive de eficienta), ceea ce inseamna ca nu va avea o performanta foarte buna cand jucatorul este prea departe. Pentru a combate asta, am implementat si algoritmul A*, pentru a ne putea apropria de adversar cand suntem prea departe. Euristica folosita impreuna cu A* este distanta Manhattan.

Solutie: hackerrank.com/.../submissions/game/635151
Meciuri stage2bot: a - b - c - d - e - f - g - h - i - j - k - l - m - n - o - p

###Etapa I###

Tag: stage-i-submission

Pentru etapa I am implementat un AI foarte rudimentar: tot ce face este sa se duca tot timpul in directia celui mai lung coridor pe care il poate vedea la un moment dat. Am cazut de comun acord sa abordam o solutie cat mai simpla posibil in aceasta prima etapa pentru a ne putea incadra in timp.

Insa codul pe care l-am scris este facut in asa fel incat sa poata fi extins si facut mai complex in etapele urmatoare; spre exemplu, clasa GameWorld, pe care am facut-o in asa fel incat sa ne fie mai usor in viitor sa implementam un algoritm de tip minimax.

Nota: Codul trimis pentru aceasta etapa nu este de pe branch-ul principal, asa ca unule parti ale clasei GameWorld nu sunt cele mai recente pe care le avem pe repository-ul de pe GitHub.

Solutie: hackerrank.com/.../submissions/game/624187
Meciuri RandomBot: a - b - c - d - e - f - g - h - i - j - k - l - m - n - o - p
Meciuri explorer: a - b - c - d - e - f - g - h - i - j - k - l - m - n - o - p