Brug af kunstig intelligens til at løse 2048-spillet (JAVA-kode)

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

Indtil videre har de fleste af jer hørt/spillet 2048 spil af Gabriele Cirulli. Det er et simpelt, men stærkt vanedannende brætspil, som kræver, at du kombinerer numrene på cellerne for at nå tallet 2048. Som forventet stiger spillets sværhedsgrad, efterhånden som flere celler fyldes med høje værdier. Personligt, selvom jeg brugte en del tid på at spille spillet, var jeg aldrig i stand til at nå 2048. Så den naturlige ting at gøre er at forsøge at udvikle en AI-løser i JAVA for at slå 2048-spillet. 🙂

I denne artikel vil jeg kort diskutere min tilgang til at bygge Artificial Intelligence Solver af Game 2048, jeg vil beskrive de heuristika, som jeg brugte, og jeg vil give den komplette kode, som er skrevet i JAVA. Koden er open source under GPL v3-licens, og du kan downloade den fra Github.

Udvikling af 2048-spillet i JAVA

Det originale spil er skrevet i JavaScript, så jeg var nødt til at omskrive det i JAVA fra bunden. Hovedidéen med spillet er, at du har et 4×4-gitter med heltalsværdier, som alle er potenser af 2. Nulværdiceller anses for tomme. På hvert tidspunkt i spillet er du i stand til at flytte værdierne i 4 retninger op, ned, højre eller venstre. Når du udfører en bevægelse, bevæger alle værdierne af gitteret sig i den retning, og de stopper enten, når de når grænserne til gitteret, eller når de når en anden celle med en værdi, der ikke er nul. Hvis den forrige celle har den samme værdi, flettes de to celler til én celle med dobbelt værdi. I slutningen af ​​hvert træk tilføjes en tilfældig værdi på brættet i en af ​​de tomme celler, og dens værdi er enten 2 med 0.9 sandsynlighed eller 4 med 0.1 sandsynlighed. Spillet slutter, når spilleren formår at skabe en celle med værdien 2048 (vinde), eller når der ikke er andre træk at lave (tabte).

I den oprindelige implementering af spillet er move-merge-algoritmen en smule kompliceret, fordi den tager højde for alle retningerne. En god forenkling af algoritmen kan udføres, hvis vi fastlægger retningen, som vi kan kombinere brikkerne i, og roterer brættet i overensstemmelse hermed for at udføre bevægelsen. Maurits van der Schee har for nylig skrevet en artikel om det, som jeg synes er værd at tjekke ud.

Alle klasserne er dokumenteret med Javadoc-kommentarer. Nedenfor giver vi en beskrivelse på højt niveau af implementeringens arkitektur:

1. Bestyrelsesklasse

Brætklassen indeholder spillets hovedkode, som er ansvarlig for at flytte brikkerne, beregne scoren, validere om spillet er afsluttet osv.

2. ActionStatus og Retning Enum

ActionStatus og retningen er 2 væsentlige enums, som lagrer resultatet af et træk og dets retning i overensstemmelse hermed.

3. ConsoleGame Class

ConsoleGame er hovedklassen, som giver os mulighed for at spille spillet og teste nøjagtigheden af ​​AI Solver.

4. AIsolver klasse

AIsolveren er den primære klasse af kunstig intelligens-modulet, som er ansvarlig for at evaluere det næstbedste træk givet et bestemt board.

Kunstig intelligensteknikker: Minimax vs Alpha-beta beskæring

Der er blevet offentliggjort flere metoder til automatisk at løse dette spil. Den mest bemærkelsesværdige er den, der er udviklet af Matt Overlan. For at løse problemet prøvede jeg to forskellige tilgange, ved at bruge Minimax-algoritmen og bruge Alpha-beta-beskæring.

Minimax algoritme

Minimax er en rekursiv algoritme, som kan bruges til at løse nulsumsspil for to spillere. I hver tilstand af spillet forbinder vi en værdi. Minimax-algoritmen søger gennem rummet af mulige spiltilstande og skaber et træ, som udvides, indtil det når en bestemt foruddefineret dybde. Når først disse bladtilstande er nået, bruges deres værdier til at estimere dem af de mellemliggende noder.

Den interessante idé med denne algoritme er, at hvert niveau repræsenterer en af ​​de to spilleres tur. For at vinde skal hver spiller vælge det træk, der minimerer modstanderens maksimale udbetaling. Her er en fin videopræsentation af minimax-algoritmen:

[Indlejret indhold]

Nedenfor kan du se pseudokoden for Minimax-algoritmen:

funktion minimax(knudepunkt, dybde, maksimering af afspiller)
    if dybde = 0 or node er en terminal node
        afkast den heuristiske værdi af node
    if maximizingPlayer bestValue := -∞
        for hver child of node val := minimax(child, dybde - 1, FALSE)) bestValue := max(bedstValue, val);
        afkast bedste værdi
    andet
        bedste værdi := +∞
        for hver child of node val := minimax(child, dybde - 1, TRUE)) bestValue := min(bedstValue, val);
        afkast bedste værdi
(* Indledende opkald for at maksimere spilleren *)
minimax (oprindelse, dybde, TRUE)

Alfa-beta beskæring

Alfa-beta beskæringsalgoritme er en udvidelse af minimax, som kraftigt reducerer (beskærer) antallet af noder, som vi skal evaluere/udvide. For at opnå dette estimerer algoritmen to værdier, alfa og beta. Hvis betaen i en given node er mindre end alfa, kan resten af ​​undertræerne beskæres. Her er en fin videopræsentation af alfabetalgoritmen:

[Indlejret indhold]

Nedenfor kan du se pseudokoden for Alpha-beta beskæringsalgoritmen:

funktion alphabeta (knudepunkt, dybde, α, β, maximizingPlayer)
    if dybde = 0 or node er en terminal node
        afkast den heuristiske værdi af node
    if maksimering af afspiller
        for hver barn af node α := max(α, alphabeta(barn, dybde - 1, α, β, FALSK))
            if β ≤ α
                bryde (* β cut-off *)
        afkast α
    andet
        for hver barn af node β := min(β, alphabeta(barn, dybde - 1, α, β, TRUE))
            if β ≤ α
                bryde (* α cut-off *)
        afkast β
(* Første opkald *)
alphabeta(oprindelse, dybde, -∞, +∞, SAND)

Hvordan bruges AI til at løse Game 2048?

For at bruge ovenstående algoritmer skal vi først identificere de to spillere. Den første spiller er den person, der spiller spillet. Den anden spiller er computeren, som tilfældigt indsætter værdier i brættets celler. Det er klart, at den første spiller forsøger at maksimere sin score og opnå 2048-fusionen. På den anden side er computeren i det originale spil ikke specifikt programmeret til at blokere brugeren ved at vælge det værst mulige træk for ham, men indsætter snarere tilfældigt værdier på de tomme celler.

Så hvorfor bruger vi AI-teknikker, der løser nulsumsspil, og som specifikt forudsætter, at begge spillere vælger det bedst mulige træk for dem? Svaret er enkelt; på trods af, at det kun er den første spiller, der forsøger at maksimere sin score, kan computerens valg blokere fremskridtet og forhindre brugeren i at fuldføre spillet. Ved at modellere computerens adfærd som en ortologisk ikke-tilfældig spiller sikrer vi, at vores valg bliver et solidt valg uafhængigt af, hvad computeren spiller.

Den anden vigtige del er at tildele værdier til spillets tilstande. Dette problem er relativt simpelt, fordi spillet i sig selv giver os en score. Desværre er det ikke en god tilgang at prøve at maksimere scoren alene. En grund til dette er, at placeringen af ​​værdierne og antallet af tomme værdifulde celler er meget vigtige for at vinde spillet. Hvis vi for eksempel spreder de store værdier i fjerntliggende celler, ville det være virkelig svært for os at kombinere dem. Derudover risikerer vi at tabe spillet, hvis vi ikke har nogen ledige celler.

Af alle de ovennævnte grunde, flere heuristika er blevet foreslået såsom monoticiteten, glatheden og brættets frie fliser. Hovedideen er ikke at bruge scoren alene til at evaluere hver spiltilstand, men i stedet konstruere en heuristisk sammensat score, der inkluderer de førnævnte scores.

Til sidst skal vi bemærke, at selvom jeg har udviklet en implementering af Minimax-algoritmen, gør det store antal mulige tilstande algoritmen meget langsom, og derfor er beskæring nødvendig. Som et resultat i JAVA-implementeringen bruger jeg udvidelsen af ​​Alpha-beta beskæringsalgoritmen. Derudover beskærer jeg i modsætning til andre implementeringer ikke computerens valg aggressivt ved hjælp af vilkårlige regler, men i stedet tager jeg dem alle i betragtning for at finde det bedst mulige træk af spilleren.

Udvikling af en heuristisk scorefunktion

For at slå spillet prøvede jeg flere forskellige heuristiske funktioner. Den, jeg fandt mest brugbar, er følgende:

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

Ovenstående funktion kombinerer brættets faktiske score, antallet af tomme celler/fliser og en metrik kaldet clustering score, som vi vil diskutere senere. Lad os se hver komponent mere detaljeret:

1. Faktisk score: Af indlysende grunde, når vi beregner værdien af ​​et bræt, skal vi tage hensyn til dets score. Boards med højere score foretrækkes generelt i forhold til boards med lavere score.
2. Antal tomme celler: Som vi nævnte tidligere, er det vigtigt at have få tomme celler for at sikre, at vi ikke taber spillet i de næste træk. Boardstater med flere tomme celler foretrækkes generelt i forhold til andre med færre. Et spørgsmål rejser sig om, hvordan ville vi værdsætte disse tomme celler? I min løsning vægter jeg dem efter logaritmen af ​​den faktiske score. Dette har følgende effekt: Jo lavere score, jo mindre vigtigt er det at have mange tomme celler (Dette skyldes, at det i begyndelsen af ​​spillet er ret nemt at kombinere cellerne). Jo højere score, jo vigtigere er det at sikre, at vi har tomme celler i vores spil (Dette skyldes, at det i slutningen af ​​spillet er mere sandsynligt at tabe på grund af manglen på tomme celler.
3. Klyngeresultat: Vi bruger clustering-score, som måler, hvor spredte værdierne i vores board er. Når celler med lignende værdier er tætte, er de nemmere at kombinere, hvilket betyder, at det er sværere at tabe spillet. I dette tilfælde har clustering-score en lav værdi. Hvis værdierne på tavlen er spredte, så får denne score en meget stor værdi. Denne score trækkes fra de to foregående scoringer og fungerer som en straf, der sikrer, at klyngede brædder vil blive foretrukket.

I den sidste linje af funktionen sikrer vi, at scoren er ikke-negativ. Scoren skal være strengt taget positiv, hvis brættets bedømmelse er positiv, og kun nul, når brættets bræt er nul. Max og min funktionerne er konstrueret således, at vi får denne effekt.

Til sidst bør vi bemærke, at når spilleren når en terminal spiltilstand, og der ikke er flere træk tilladt, bruger vi ikke ovenstående score til at estimere værdien af ​​staten. Hvis spillet vindes, tildeler vi den højest mulige heltalsværdi, mens hvis spillet går tabt, tildeler vi den laveste ikke-negative værdi (0 eller 1 med lignende logik som i det foregående afsnit).

Mere om Clustering Score

Som vi sagde tidligere måler klyngeresultatet, hvor meget spredte værdierne af brættet er og fungerer som en straf. Jeg konstruerede dette partitur på en sådan måde, at det inkorporerer tips/regler fra brugere, der "mestrede" spillet. Den første foreslåede regel er, at du forsøger at holde cellerne med lignende værdier tæt for at kombinere dem lettere. Den anden regel er, at celler med høj værdi skal være tæt på hinanden og ikke vises i midten af ​​brættet, men snarere på siderne eller hjørnerne.

Lad os se, hvordan klyngeresultatet estimeres. For hver celle på tavlen estimerer vi summen af ​​absolutte forskelle fra dens naboer (eksklusive de tomme celler), og vi tager den gennemsnitlige forskel. Grunden til, at vi tager gennemsnittet, er for at undgå at tælle mere end én gang effekten af ​​to naboceller. Den samlede clustering-score er summen af ​​alle disse gennemsnit.

Clustering-resultatet har følgende egenskaber:

1. Det får høj værdi, når værdierne på tavlen er spredt, og lav værdi, når celler med lignende værdier er tæt på hinanden.
2. Det overvægter ikke effekten af ​​to naboceller.
3. Celler i marginerne eller hjørnerne har færre naboer og dermed lavere score. Som et resultat, når de høje værdier er placeret i nærheden af ​​marginerne eller hjørnerne, har de mindre score, og dermed er straffen mindre.

Algoritmens nøjagtighed

Som forventet afhænger nøjagtigheden (også kendt som procentdelen af ​​spil, der vindes) af algoritmen meget af den søgedybde, vi bruger. Jo højere dybden af ​​søgningen er, jo højere nøjagtighed og jo mere tid tager det at køre. I mine test varer en søgning med dybde 3 mindre end 0.05 sekunder men giver 20% chance for at vinde, en dybde på 5 varer cirka 1 sekund men giver 40% chance for at vinde og endelig varer en dybde på 7 27-28 sekunder og giver omkring 70-80% chance for at vinde.

Fremtidige udvidelser

For dem af jer, der er interesseret i at forbedre koden, er her et par ting, du kan se nærmere på:

1. Forbedre hastigheden: Forbedring af hastigheden af ​​algoritmen vil give dig mulighed for at bruge større dybde og dermed få bedre nøjagtighed.
2. Opret grafik: Der er en god grund til, at Gabriele Cirullis implementering blev så berømt. Det ser flot ud! Jeg gad ikke udvikle en GUI, men jeg udskriver hellere resultaterne på konsollen, hvilket gør spillet sværere at følge og spille. At lave en god GUI er et must.
3. Tune heuristik: Som jeg nævnte tidligere, har flere brugere foreslået forskellige heuristika. Man kan eksperimentere med måden, scorerne udregnes på, vægtene og tavlens egenskaber, der tages i betragtning. Min tilgang til at måle klyngescore formodes at kombinere andre forslag såsom Monotonicity og Smoothness, men der er stadig plads til forbedringer.
4. Justering af dybden: Man kan også prøve at tune/justere dybden af ​​søgningen afhængigt af spillets tilstand. Du kan også bruge Iterativ uddybning af dybde-først søgning algoritme, som er kendt for at forbedre alfa-beta beskæringsalgoritmen.

Glem ikke at downloade JAVA-koden fra Github og eksperimentere. Jeg håber du kunne lide dette indlæg! Hvis du gjorde det, så brug et øjeblik på at dele artiklen på Facebook og Twitter. 🙂