Folosirea inteligenței artificiale pentru a rezolva jocul 2048 (cod JAVA)

• Aprilie 7, 2014
• Vasilis Vryniotis
• . 6 comentarii

Până acum cei mai mulți dintre voi ați auzit/jucat Joc 2048 de Gabriele Cirulli. Este un joc de masă simplu, dar extrem de captivant, care necesită să combinați numerele celulelor pentru a ajunge la numărul 2048. După cum era de așteptat, dificultatea jocului crește pe măsură ce mai multe celule sunt umplute cu valori mari. Personal, deși am petrecut destul de mult timp jucând jocul, nu am reușit niciodată să ajung la 2048. Așa că lucrul natural de făcut este să încerc să dezvolt un solutor AI în JAVA pentru a învinge jocul 2048. 🙂

În acest articol voi discuta pe scurt despre abordarea mea pentru construirea soluției de inteligență artificială a jocului 2048, voi descrie euristica pe care am folosit-o și voi furniza codul complet care este scris în JAVA. Codul este open source sub licență GPL v3 și îl puteți descărca de la Github.

Dezvoltarea jocului 2048 în JAVA

Jocul original este scris în JavaScript, așa că a trebuit să-l rescriu în JAVA de la zero. Ideea principală a jocului este că aveți o grilă 4×4 cu valori întregi, toate acestea fiind puteri de 2. Celulele cu valoare zero sunt considerate goale. În fiecare moment al jocului, puteți muta valorile în 4 direcții Sus, Jos, Dreapta sau Stânga. Când efectuați o mișcare toate valorile grilei se deplasează în direcția respectivă și se opresc fie când ajung la marginile grilei, fie când ajung la o altă celulă cu valoare diferită de zero. Dacă acea celulă anterioară are aceeași valoare, cele două celule sunt îmbinate într-o singură celulă cu valoare dublă. La sfârșitul fiecărei mișcări se adaugă o valoare aleatorie pe tablă într-una dintre celulele goale și valoarea ei este fie 2 cu 0.9 probabilitate, fie 4 cu 0.1 probabilitate. Jocul se termină atunci când jucătorul reușește să creeze o celulă cu valoarea 2048 (câștig) sau când nu există alte mișcări de făcut (pierde).

În implementarea inițială a jocului, algoritmul de mutare-imbinare este puțin complicat, deoarece ține cont de toate direcțiile. O simplificare plăcută a algoritmului poate fi realizată dacă fixăm direcția spre care putem combina piesele și rotim tabla în consecință pentru a efectua mutarea. Maurits van der Schee a scris recent un articol despre el pe care cred că merită verificat.

Toate clasele sunt documentate cu comentarii Javadoc. Mai jos oferim o descriere la nivel înalt a arhitecturii implementării:

1. Clasa Board

Clasa de tablă conține codul principal al jocului, care este responsabil pentru mutarea pieselor, calcularea punctajului, validarea dacă jocul este încheiat etc.

2. ActionStatus and Direction Enum

ActionStatus și Direction sunt 2 enumerari esențiale care stochează rezultatul unei mișcări și direcția acesteia în consecință.

3. Clasa ConsoleGame

ConsoleGame este clasa principală care ne permite să jucăm jocul și să testăm acuratețea AI Solver.

4. Clasa AIsolver

AIsolver este clasa principală a modulului de inteligență artificială, care este responsabilă de evaluarea următoarei mișcări bune, având în vedere o anumită placă.

Tehnici de inteligență artificială: tăiere Minimax vs Alpha-beta

Au fost publicate mai multe abordări pentru a rezolva automat acest joc. Cel mai notabil este cel dezvoltat de Matt Overlan. Pentru a rezolva problema am încercat două abordări diferite, folosind algoritmul Minimax și folosind tăierea Alpha-beta.

Algoritmul Minimax

minimax este un algoritm recursiv care poate fi folosit pentru rezolvarea jocurilor cu sumă zero pentru doi jucători. În fiecare stare a jocului asociem o valoare. Algoritmul Minimax caută prin spațiul posibilelor stări ale jocului, creând un arbore care este extins până când atinge o anumită adâncime predefinită. Odată atinse acele stări ale frunzelor, valorile lor sunt folosite pentru a estima pe cele ale nodurilor intermediare.

Ideea interesantă a acestui algoritm este că fiecare nivel reprezintă rândul unuia dintre cei doi jucători. Pentru a câștiga fiecare jucător trebuie să aleagă mișcarea care minimizează câștigul maxim al adversarului. Iată o prezentare video frumoasă a algoritmului minimax:

[Conținutul încorporat]

Mai jos puteți vedea pseudocodul algoritmului Minimax:

funcţie minimax(nod, adâncime, maximizingPlayer)
    if adâncime = 0 or nodul este un nod terminal
        reveni valoarea euristică a nodului
    if maximizingPlayer bestValue := -∞
        pentru fiecare fiul nodului val := minimax(copil, adâncime - 1, FALSE)) bestValue := max(bestValue, val);
        reveni cel mai bun pret
    altfel
        cea mai bună valoare := +∞
        pentru fiecare fiul nodului val := minimax(copil, adâncime - 1, TRUE)) bestValue := min(bestValue, val);
        reveni cel mai bun pret
(* Apel inițial pentru maximizarea jucătorului *)
minimax(origine, adâncime, TRUE)

Tăiere alfa-beta

Algoritm de tăiere alfa-beta este o expansiune a minimax, care scade (tunde) puternic numărul de noduri pe care trebuie să le evaluăm/extindem. Pentru a realiza acest lucru, algoritmul estimează două valori: alfa și beta. Dacă într-un anumit nod beta este mai mică decât alfa, restul subarborilor pot fi tăiați. Iată o prezentare video frumoasă a algoritmului alphabeta:

[Conținutul încorporat]

Mai jos puteți vedea pseudocodul algoritmului de tăiere Alpha-beta:

funcţie alphabeta(nod, adâncime, α, β, maximizingPlayer)
    if adâncime = 0 or nodul este un nod terminal
        reveni valoarea euristică a nodului
    if maximizingPlayer
        pentru fiecare copil al nodului α := max(α, alphabeta(copil, adâncime - 1, α, β, FALSE))
            if β ≤ α
                rupe (* β cut-off *)
        reveni α
    altfel
        pentru fiecare copilul nodului β := min(β, alphabeta(copil, adâncime - 1, α, β, TRUE))
            if β ≤ α
                rupe (* α cut-off *)
        reveni β
(* Apel inițial *)
alphabeta (origine, adâncime, -∞, +∞, TRUE)

Cum se folosește AI pentru a rezolva Jocul 2048?

Pentru a folosi algoritmii de mai sus trebuie mai întâi să identificăm cei doi jucători. Primul jucător este persoana care joacă jocul. Al doilea jucător este computerul care inserează aleatoriu valori în celulele tablei. Evident, primul jucător încearcă să-și maximizeze scorul și să realizeze fuziunea 2048. Pe de altă parte, computerul din jocul original nu este programat în mod special să blocheze utilizatorul selectând cea mai proastă mișcare posibilă pentru el, ci mai degrabă inserează aleatoriu valori în celulele goale.

Deci, de ce folosim tehnici AI care rezolvă jocuri cu sumă zero și care presupun în mod specific că ambii jucători selectează cea mai bună mișcare posibilă pentru ei? Răspunsul este simplu; în ciuda faptului că este doar primul jucător care încearcă să-și maximizeze scorul, alegerile computerului pot bloca progresul și împiedică utilizatorul să finalizeze jocul. Prin modelarea comportamentului computerului ca jucător ortologic non-aleatoriu ne asigurăm că alegerea noastră va fi una solidă, independent de ceea ce joacă computerul.

A doua parte importantă este să atribuiți valori stărilor jocului. Această problemă este relativ simplă deoarece jocul în sine ne oferă un scor. Din păcate, încercarea de a maximiza scorul pe cont propriu nu este o abordare bună. Un motiv pentru aceasta este că poziția valorilor și numărul de celule goale valorice sunt foarte importante pentru a câștiga jocul. De exemplu, dacă împrăștiem valorile mari în celulele îndepărtate, ne-ar fi foarte greu să le combinăm. În plus, dacă nu avem celule goale disponibile, riscăm să pierdem jocul în orice moment.

Din toate motivele de mai sus, mai multe euristici au fost sugerate cum ar fi Monoticitatea, netezimea și plăcile libere ale tablei. Ideea principală este să nu folosiți doar scorul pentru a evalua fiecare stare de joc, ci să construiți un scor euristic compus care să includă scorurile menționate mai sus.

În cele din urmă, ar trebui să remarcăm că, deși am dezvoltat o implementare a algoritmului Minimax, numărul mare de stări posibile face algoritmul foarte lent și astfel este necesară tăierea. Ca rezultat, în implementarea JAVA, folosesc extinderea algoritmului de tăiere Alpha-beta. În plus, spre deosebire de alte implementări, nu tund agresiv alegerile computerului folosind reguli arbitrare, ci le iau în considerare pe toate pentru a găsi cea mai bună mișcare posibilă a jucătorului.

Dezvoltarea unei funcții de scor euristic

Pentru a învinge jocul, am încercat mai multe funcții euristice diferite. Cea care mi s-a părut cel mai util este următoarea:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Funcția de mai sus combină scorul real al tablei, numărul de celule/dale goale și o metrică numită scor de grupare despre care vom discuta mai târziu. Să vedem fiecare componentă mai detaliat:

1. Scorul real: Din motive evidente, atunci când calculăm valoarea unei table trebuie să luăm în considerare scorul acesteia. Panourile cu scoruri mai mari sunt, în general, preferate în comparație cu panourile cu scoruri mai mici.
2. Număr de celule goale: După cum am menționat mai devreme, păstrarea câtorva celule goale este importantă pentru a ne asigura că nu vom pierde jocul în mișcările următoare. Stările de bord cu mai multe celule goale sunt în general preferate în comparație cu altele cu mai puține. Se ridică o întrebare cu privire la cum am aprecia acele celule goale? În soluția mea le ponderez cu logaritmul scorului real. Acest lucru are următorul efect: Cu cât scorul este mai mic, cu atât este mai puțin important să aveți mai multe celule goale (Acest lucru se datorează faptului că la începutul jocului, combinarea celulelor este destul de ușoară). Cu cât scorul este mai mare, cu atât este mai important să ne asigurăm că avem celule goale în jocul nostru (Acest lucru se datorează faptului că la sfârșitul jocului este mai probabil să pierdem din cauza lipsei celulelor goale.
3. Scor de grupare: Folosim scorul de grupare care măsoară cât de dispersate sunt valorile tablei noastre. Când celulele cu valori similare sunt apropiate, acestea sunt mai ușor de combinat, ceea ce înseamnă că este mai greu să pierdeți jocul. În acest caz, scorul de grupare are o valoare scăzută. Dacă valorile tablei sunt împrăștiate, atunci acest scor primește o valoare foarte mare. Acest scor este scăzut din cele două scoruri anterioare și acționează ca o penalizare care asigură că vor fi preferate tablele grupate.

În ultima linie a funcției ne asigurăm că scorul este nenegativ. Scorul ar trebui să fie strict pozitiv dacă scorul tablei este pozitiv și zero numai când tabla scorului este zero. Funcțiile max și min sunt construite astfel încât să obținem acest efect.

În cele din urmă, ar trebui să remarcăm că atunci când jucătorul ajunge la o stare de joc terminală și nu mai sunt permise mișcări, nu folosim scorul de mai sus pentru a estima valoarea stării. Dacă jocul este câștigat, atribuim cea mai mare valoare întreagă posibilă, în timp ce dacă jocul este pierdut, atribuim cea mai mică valoare nenegativă (0 sau 1 cu o logică similară ca în paragraful anterior).

Mai multe despre scorul de grupare

După cum am spus mai devreme, scorul de grupare măsoară cât de dispersate sunt valorile tablei și acționează ca o penalizare. Am construit acest scor în așa fel încât să încorporeze sfaturi/reguli de la utilizatorii care au „stăpânit” jocul. Prima regulă sugerată este că încercați să păstrați aproape celulele cu valori similare pentru a le combina mai ușor. A doua regulă este că celulele cu valoare mare ar trebui să fie aproape una de alta și să nu apară în mijlocul tablei, ci mai degrabă pe laturi sau colțuri.

Să vedem cum este estimat scorul de grupare. Pentru fiecare celulă a plăcii estimăm suma diferențelor absolute față de vecinii săi (excluzând celulele goale) și luăm diferența medie. Motivul pentru care luăm mediile este să evităm să numărăm de mai multe ori efectul a două celule vecine. Scorul total de grupare este suma tuturor acestor medii.

Scorul de grupare are următoarele atribute:

1. Obține valoare mare atunci când valorile plăcii sunt împrăștiate și valoare scăzută atunci când celulele cu valori similare sunt apropiate una de cealaltă.
2. Nu supraponderează efectul a două celule vecine.
3. Celulele din margini sau colțuri au mai puține vecine și, prin urmare, scoruri mai mici. Ca urmare, atunci când valorile mari sunt plasate lângă margini sau colțuri, acestea au scoruri mai mici și astfel penalizarea este mai mică.

Precizia algoritmului

După cum era de așteptat, precizia (denumită în continuare procentul de jocuri câștigate) a algoritmului depinde în mare măsură de adâncimea de căutare pe care o folosim. Cu cât este mai mare adâncimea căutării, cu atât este mai mare precizia și cu atât este nevoie de mai mult timp pentru a rula. În testele mele, o căutare cu adâncimea 3 durează mai puțin de 0.05 secunde, dar oferă 20% șanse de câștig, o adâncime de 5 durează aproximativ 1 secundă, dar oferă 40% șanse de câștig și, în final, o adâncime de 7 durează 27-28 de secunde și oferă aproximativ 70-80% șanse de câștig.

Extinderi viitoare

Pentru cei dintre voi care sunt interesați să îmbunătățească codul, iată câteva lucruri pe care le puteți analiza:

1. Îmbunătățiți viteza: Îmbunătățirea vitezei algoritmului vă va permite să utilizați o adâncime mai mare și, astfel, să obțineți o precizie mai bună.
2. Creați grafică: Există un motiv întemeiat pentru care implementarea lui Gabriele Cirulli a devenit atât de faimoasă. Arata frumos! Nu m-am deranjat să dezvolt o interfață grafică, ci mai degrabă imprimez rezultatele pe consolă, ceea ce face jocul mai greu de urmărit și de jucat. Crearea unui GUI frumos este o necesitate.
3. Tune Euristic: După cum am menționat mai devreme, mai mulți utilizatori au sugerat euristici diferite. Se poate experimenta modul în care se calculează scorurile, ponderile și caracteristicile tablei care sunt luate în considerare. Abordarea mea de măsurare a scorului cluster ar trebui să combine alte sugestii, cum ar fi Monotonitatea și Netezimea, dar există încă loc de îmbunătățire.
4. Reglarea adâncimii: De asemenea, se poate încerca să reglați/ajustați adâncimea căutării în funcție de starea jocului. De asemenea, puteți utiliza Căutare iterativă de adâncime în primul rând algoritm despre care se știe că îmbunătățește algoritmul de tăiere alfa-beta.

Nu uitați să descărcați codul JAVA de pe Github și experimentează. Sper că v-a plăcut această postare! Dacă ați făcut-o, vă rugăm să acordați un moment pentru a distribui articolul pe Facebook și Twitter. 🙂