Uporaba umetne inteligence za reševanje igre 2048 (koda JAVA)

• April 7, 2014
• Vasilis Vryniotis
• . 6 komentarjev

Do zdaj vas je večina že slišala / igrala 2048 igre avtor Gabriele Cirulli. To je preprosta, a zelo zasvojijoča ​​družabna igra, ki zahteva, da združite število celic, da dosežete številko 2048. Kot je bilo pričakovano, se teža igre povečuje, ko je več celic napolnjenih z visokimi vrednostmi. Osebno, čeprav sem preživel precej časa za igranje igre, nikoli nisem mogel doseči leta 2048. Zato je naravno, da v JAVI poskušam razviti rešitev za umetno inteligenco, ki bo premagala igro 2048. 🙂

V tem članku bom na kratko razpravljal o svojem pristopu k ustvarjanju rešitve za umetno inteligenco igre 2048, opisal bom uporabljene hevristike in posredoval popolno kodo, ki je napisana v JAVA. Koda je odprta pod licenco GPL v3 in jo lahko prenesete iz GitHub.

Razvoj igre 2048 v JAVI

Izvirna igra je napisana v JavaScript, zato sem jo moral iz nič napisati v JAVA. Glavna zamisel igre je, da imate mrežo 4 × 4 z vrednostmi Integer, ki so pooblastila 2. Celice z ničelno vrednostjo se štejejo za prazne. Na vsaki točki med igro lahko premikate vrednosti v 4 smeri gor, dol, desno ali levo. Ko izvedete premik, se vse vrednosti mreže premaknejo v to smer in se ustavijo, ko dosežejo meje mreže ali ko pridejo do druge celice z vrednostjo, ki ni enaka nič. Če ima prejšnja celica enako vrednost, se celici združita v eno celico z dvojno vrednostjo. Na koncu vsakega premika se na deski v eni od praznih celic doda naključna vrednost, katere vrednost je bodisi 2 z verjetnostjo 0.9 ali 4 z verjetnostjo 0.1. Igra se konča, ko igralcu uspe ustvariti celico z vrednostjo 2048 (zmaga) ali ko ni drugih potez (izguba).

Pri prvotni izvedbi igre je algoritem premikanja in spajanja nekoliko zapleten, ker upošteva vse smeri. Lepo poenostavitev algoritma lahko izvedemo, če popravimo smer, v katero lahko združimo koščke in ustrezno zavrtimo ploščo, da izvedemo premik. Maurits van der Schee je pred kratkim napisal članek o tem, za katerega menim, da ga je vredno preveriti.

Vsi razredi so dokumentirani s komentarji Javadoc. Spodaj podajamo opis arhitekture izvedbe na visoki ravni:

1. Razred plošče

Razred na deski vsebuje glavno kodo igre, ki je odgovorna za premikanje figur, izračun rezultata, potrditev, če se igra konča itd.

2. ActionStatus in Direction Enum

ActionStatus in Direction sta dva bistvena naštevanja, ki shranjujeta rezultat poteze in njeno smer.

3. Razred ConsoleGame

ConsoleGame je glavni razred, ki nam omogoča igranje igre in preizkušanje natančnosti rešitve AI.

4. Razred AIsolver

AIsolver je primarni razred modula za umetno inteligenco, ki je odgovoren za oceno naslednje najboljše poteze določenega odbora.

Tehnike umetne inteligence: obrezovanje Minimax proti alfa-beta

Objavljeno je bilo več pristopov za samodejno reševanje te igre. Najbolj opazen je tisti, ki ga je razvil Matt Overlan. Za rešitev težave sem preizkusil dva različna pristopa, z uporabo algoritma Minimax in obrezovanjem Alpha-beta.

Minimax algoritem

O Minimax je rekurzivni algoritem, ki ga lahko uporabimo za reševanje iger z vsoto z dvema igralcema. V vsakem stanju igre povežemo vrednost. Algoritem Minimax išče po prostoru možnih igralnih stanj in ustvarja drevo, ki se širi, dokler ne doseže določene vnaprej določene globine. Ko so ta stanja listov dosežena, se njihove vrednosti uporabijo za oceno vrednosti vmesnih vozlišč.

Zanimiva ideja tega algoritma je, da vsaka stopnja predstavlja na vrsti enega od obeh igralcev. Za zmago mora vsak igralec izbrati potezo, ki zmanjša nasprotnikovo največje izplačilo. Tu je lepa video predstavitev algoritma minimax:

[Vgrajeni vsebina]

Spodaj si lahko ogledate psevdokodo algoritma Minimax:

funkcija minimax (vozlišče, globina, maksimiranje predvajalnika)
    if globina = 0 or vozlišče je končno vozlišče
        vrnitev hevristična vrednost vozlišča
    if maximizingPlayer bestValue: = -∞
        za vsakogar podrejena vozlišča val: = minimax (podrejena, globina - 1, FALSE)) bestValue: = max (bestValue, val);
        vrnitev najboljša vrednost
    ostalo
        bestValue: = + ∞
        za vsakogar podrejeni vozlišča val: = minimax (podrejeni, globina - 1, TRUE)) bestValue: = min (bestValue, val);
        vrnitev najboljša vrednost
(* Začetni klic za maksimiranje igralca *)
minimax (izvor, globina, TRUE)

Obrezovanje alfa-beta

O Alfa-beta algoritem obrezovanja je razširitev minimaksa, ki močno zmanjša (slive) število vozlišč, ki jih moramo oceniti / razširiti. Da bi to dosegel, algoritem oceni dve vrednosti alfa in beta. Če je v danem vozlišču beta manj kot alfa, je mogoče preostala poddrevesa obrezati. Tu je lepa video predstavitev algoritma abecede:

[Vgrajeni vsebina]

Spodaj si lahko ogledate psevdokodo algoritma obrezovanja Alpha-beta:

funkcija abeceda (vozlišče, globina, α, β, maksimiziranje predvajalnika)
    if globina = 0 or vozlišče je končno vozlišče
        vrnitev hevristična vrednost vozlišča
    if maximizingPlayer
        za vsakogar otrok vozlišča α: = max (α, abeceda (otrok, globina - 1, α, β, FALSE))
            if β ≤ α
                odmor (* β-meja *)
        vrnitev α
    ostalo
        za vsakogar otrok vozlišča β: = min (β, abeceda (otrok, globina - 1, α, β, TRUE))
            if β ≤ α
                odmor (* α-meja *)
        vrnitev β
(* Začetni klic *)
abeceda (izvor, globina, -∞, + ∞, TRUE)

Kako se AI uporablja za reševanje igre 2048?

Za uporabo zgornjih algoritmov moramo najprej identificirati oba igralca. Prvi igralec je oseba, ki igra igro. Drugi predvajalnik je računalnik, ki naključno vstavlja vrednosti v celice plošče. Očitno prvi igralec poskuša maksimirati svoj rezultat in doseči združitev 2048. Po drugi strani računalnik v izvirni igri ni posebej programiran za blokiranje uporabnika z izbiro najslabše možne poteze zanj, ampak naključno vstavi vrednosti v prazne celice.

Zakaj torej uporabljamo tehnike umetne inteligence, ki rešujejo igre z ničelno vsoto in ki izrecno predvidevajo, da oba igralca zanje izbereta najboljšo možno potezo? Odgovor je preprost; kljub temu, da je le prvi igralec tisti, ki skuša maksimirati svoj rezultat, lahko izbire računalnika blokirajo napredek in preprečijo uporabniku dokončanje igre. Z modeliranjem vedenja računalnika kot ortološkega nenaključnega predvajalnika zagotovimo, da bo naša izbira zanesljiva, neodvisno od tega, kar računalnik igra.

Drugi pomemben del je dodeljevanje vrednosti stanjem igre. Ta težava je razmeroma preprosta, saj nam igra sama daje oceno. Žal poskušati maksimirati rezultat sam po sebi ni dober pristop. Eden od razlogov za to je, da sta položaj vrednot in število praznih celic zelo pomembna za zmago v igri. Če na primer velike vrednosti razpršimo po oddaljenih celicah, bi jih res težko kombinirali. Poleg tega, če nimamo na voljo praznih celic, tvegamo, da bomo vsako minuto izgubili igro.

Zaradi vseh zgoraj navedenih razlogov več hevristik so bili predlagani kot so Monotičnost, gladkost in Brezplačne ploščice plošče. Glavna ideja ni, da se rezultat uporabi samo za oceno vsakega stanja igre, temveč se ustvari hevristični sestavljeni rezultat, ki vključuje zgoraj omenjene rezultate.

Na koncu moramo še opozoriti, da čeprav sem razvil implementacijo algoritma Minimax, veliko število možnih stanj naredi algoritem zelo počasen, zato je potrebno obrezovanje. Kot rezultat pri izvajanju JAVA uporabljam razširitev algoritma obrezovanja Alpha-beta. Poleg tega v nasprotju z drugimi izvedbami ne obrezujem agresivno izbire računalnika z uporabo poljubnih pravil, temveč jih upoštevam, da najdem najboljšo možno potezo predvajalnika.

Razvijanje hevristične točkovne funkcije

Da bi premagal igro, sem preizkusil več različnih hevrističnih funkcij. Najbolj uporabna se mi je zdela naslednja:

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));
}

Zgornja funkcija združuje dejanski rezultat plošče, število praznih celic / ploščic in metriko, imenovano rezultat združevanja, o kateri bomo razpravljali kasneje. Oglejmo si vsako komponento podrobneje:

1. Dejanska ocena: Iz očitnih razlogov moramo pri izračunu vrednosti plošče upoštevati njen rezultat. Plošče z višjimi ocenami so na splošno boljše kot plošče z nižjimi ocenami.
2. Število praznih celic: Kot smo že omenili, je ohranjanje malo praznih celic pomembno, da zagotovimo, da igre ne bomo izgubili v naslednjih potezah. Članice odbora z več praznimi celicami so na splošno boljše kot druge z manj. Postavlja se vprašanje, kako bi ocenili te prazne celice? V svoji rešitvi jih tehtam z logaritmom dejanske ocene. To ima naslednji učinek: Nižji kot je rezultat, manj pomembno je, da imamo veliko praznih celic (To je zato, ker je na začetku igre združevanje celic dokaj enostavno). Višji kot je rezultat, pomembneje je zagotoviti, da imamo v igri prazne celice (To je zato, ker je na koncu igre zaradi pomanjkanja praznih celic bolj verjetno, da bomo izgubili.
3. Ocena grozdov: Uporabljamo skupinsko oceno, ki meri, kako razpršene so vrednosti naše plošče. Ko so celice s podobnimi vrednostmi blizu, jih je lažje kombinirati, kar pomeni, da je težje izgubiti igro. V tem primeru ima ocena grozdanja nizko vrednost. Če so vrednosti plošče razpršene, potem ta rezultat dobi zelo veliko vrednost. Ta rezultat se odšteje od prejšnjih dveh rezultatov in deluje kot enajstmetrovka, ki zagotavlja, da bodo imeli prednost gručirane deske.

V zadnji vrstici funkcije zagotovimo, da ocena ni negativna. Rezultat mora biti strogo pozitiven, če je rezultat plošče pozitiven, nič pa le, če je plošča rezultata enaka nič. Funkciji max in min sta zgrajeni tako, da dobimo ta učinek.

Na koncu moramo opozoriti, da ko igralec doseže končno stanje igre in ni dovoljena nobena poteza, zgornje ocene ne uporabimo za oceno vrednosti stanja. Če igro dobimo, dodelimo najvišjo možno celoštevilčno vrednost, medtem ko če igro izgubimo, damo najnižjo nenegativno vrednost (0 ali 1 s podobno logiko kot v prejšnjem odstavku).

Več o oceni grozdenja

Kot smo že omenili, ocena grozda meri, koliko razpršenih so vrednosti table in deluje kot kazen. Ta rezultat sem zgradil tako, da vključuje nasvete / pravila uporabnikov, ki so "obvladali" igro. Prvo predlagano pravilo je, da poskušate celice s podobnimi vrednostmi obdržati blizu, da jih lažje kombinirate. Drugo pravilo je, da bi morale biti visokocenjene celice med seboj blizu in ne na sredini plošče, temveč na straneh ali vogalih.

Poglejmo, kako se ocenjuje ocena grozdenja. Za vsako celico plošče ocenimo vsoto absolutnih razlik od njenih sosedov (brez praznih celic) in vzamemo povprečno razliko. Razlog, zakaj upoštevamo povprečja, je, da se izognemo štetju učinka dveh sosednjih celic več kot enkrat. Skupna ocena grozdov je vsota vseh teh povprečij.

Ocena grozdov ima naslednje lastnosti:

1. Visoko vrednost dobi, ko so vrednosti plošče razpršene, nizko pa, ko so celice s podobnimi vrednostmi blizu.
2. Ne prevlada nad učinkom dveh sosednjih celic.
3. Celice na robovih ali vogalih imajo manj sosedov in s tem nižje rezultate. Kot rezultat, ko so visoke vrednosti postavljene blizu robov ali vogalov, imajo manjše rezultate in je tako kazen manjša.

Natančnost algoritma

Po pričakovanjih je natančnost (tj. Odstotek dobljenih iger) algoritma močno odvisna od globine iskanja, ki ga uporabljamo. Večja kot je globina iskanja, večja je natančnost in več časa je potrebno za zagon. V mojih testih iskanje z globino 3 traja manj kot 0.05 sekunde, vendar daje 20% možnosti za zmago, globina 5 traja približno 1 sekundo, vendar daje 40% možnosti za zmago in končno globina 7 traja 27-28 sekund in daje približno 70-80% možnosti za zmago.

Prihodnje širitve

Za tiste, ki vas zanima izboljšanje kode, si lahko ogledate nekaj stvari:

1. Izboljšajte hitrost: Izboljšanje hitrosti algoritma vam bo omogočilo uporabo večje globine in s tem boljšo natančnost.
2. Ustvari grafiko: Obstaja dober razlog, zakaj je izvedba Gabriele Cirulli postala tako znana. Lepo je videti! Nisem se trudil z razvojem grafičnega uporabniškega vmesnika, ampak rezultate raje natisnem na konzolo, zaradi česar je igro težje spremljati in igrati. Ustvarjanje lepega GUI je nujno.
3. Uglasite hevristiko: Kot sem že omenil, je več uporabnikov predlagalo različne hevristike. Lahko eksperimentirate z načinom izračuna rezultatov, utežmi in značilnostmi plošče, ki se upoštevajo. Moj pristop k merjenju ocene grozda naj bi združeval druge predloge, kot sta monotonost in gladkost, vendar je še vedno mogoče izboljšati.
4. Nastavitev globine: Poskusite lahko tudi prilagoditi / prilagoditi globino iskanja, odvisno od stanja igre. Uporabite lahko tudi Iterativno poglabljanje iskanja po globini algoritem, za katerega je znano, da izboljša algoritem obrezovanja alfa-beta.

Ne pozabite prenesti kode JAVA iz GitHub in eksperimentirajte. Upam, da vam je bila ta objava všeč! Če ste ga, prosimo, vzemite si trenutek in ga delite s Facebookom in Twitterjem. 🙂