Bruk av kunstig intelligens for å løse 2048-spillet (JAVA-kode)

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

Nå har de fleste av dere hørt / spilt 2048 spill av Gabriele Cirulli. Det er et enkelt, men svært vanedannende brettspill som krever at du kombinerer antall celler for å nå tallet 2048. Som forventet øker vanskeligheten med spillet etter hvert som flere celler er fylt med høye verdier. Selv om jeg har brukt en god del tid på å spille spillet, klarte jeg aldri å nå 2048. Så det naturlige å gjøre er å prøve å utvikle en AI-løsning i JAVA for å slå 2048-spillet. 🙂

I denne artikkelen vil jeg kort diskutere min tilnærming for å bygge den kunstige intelligensløseren av spillet 2048, jeg vil beskrive heuristikken som jeg brukte, og jeg vil gi den komplette koden som er skrevet i JAVA. Koden er åpen med GPL v3-lisensen, og du kan laste den ned fra Github.

Utvikle spillet 2048 i JAVA

Det originale spillet er skrevet i JavaScript, så jeg måtte skrive det om i JAVA fra bunnen av. Hovedideen med spillet er at du har et 4×4 rutenett med heltallsverdier, som alle er potenser på 2. Nullverdiceller anses som tomme. På hvert tidspunkt i løpet av spillet kan du flytte verdiene mot 4 retninger Opp, Ned, Høyre eller Venstre. Når du utfører en bevegelse, beveger alle verdiene til rutenettet seg i den retningen, og de stopper enten når de når grensene til rutenettet eller når de når en annen celle med en verdi som ikke er null. Hvis den forrige cellen har samme verdi, slås de to cellene sammen til én celle med dobbel verdi. På slutten av hvert trekk legges det til en tilfeldig verdi på brettet i en av de tomme cellene, og verdien er enten 2 med 0.9 sannsynlighet eller 4 med 0.1 sannsynlighet. Spillet avsluttes når spilleren klarer å lage en celle med verdi 2048 (vinn) eller når det ikke er andre trekk å gjøre (tape).

I den opprinnelige implementeringen av spillet er flyttfusjonsalgoritmen litt komplisert fordi den tar hensyn til alle instruksjonene. En fin forenkling av algoritmen kan utføres hvis vi fikser retningen vi kan kombinere brikkene og rotere brettet deretter for å utføre trekket. Maurits van der Schee har nylig skrevet en artikkel om den som jeg mener er verdt å sjekke ut.

Alle klassene er dokumentert med Javadoc-kommentarer. Nedenfor gir vi en beskrivelse på høyt nivå av arkitekturen for implementeringen:

1. Styreklasse

Brettklassen inneholder hovedkoden for spillet, som er ansvarlig for å flytte brikkene, beregne poengsummen, validere om spillet avsluttes osv.

2. ActionStatus og retning Enum

ActionStatus og Retningen er to essensielle enum som lagrer resultatet av et trekk og retningen deretter.

3. ConsoleGame-klasse

ConsoleGame er hovedklassen som lar oss spille spillet og teste nøyaktigheten til AI Solver.

4. AIsolver-klasse

AIsolver er hovedklassen i Artificial Intelligence-modulen som er ansvarlig for å evaluere det neste beste trekket gitt et bestemt styre.

Kunstig intelligens teknikker: Minimax vs Alpha-beta beskjæring

Flere tilnærminger har blitt publisert for å løse dette spillet automatisk. Den mest bemerkelsesverdige er den som er utviklet av Matt Overlan. For å løse problemet prøvde jeg to forskjellige tilnærminger, ved å bruke Minimax algoritme og bruke Alpha-beta-beskjæring.

Minimax algoritme

De Minimax er en rekursiv algoritme som kan brukes til å løse to-spillers null-sum-spill. I hver tilstand av spillet knytter vi en verdi. Minimax-algoritmen søker gjennom rommet til mulige spilltilstander og skaper et tre som utvides til det når en bestemt forhåndsdefinert dybde. Når disse bladstatene er nådd, blir verdiene deres brukt til å estimere delene av mellomknutene.

Den interessante ideen med denne algoritmen er at hvert nivå representerer svingen til en av de to spillerne. For å vinne må hver spiller velge trekk som minimerer motstanderens maksimale gevinst. Her er en fin videopresentasjon av minimax-algoritmen:

[Innebygd innhold]

Nedenfor kan du se pseudokode til Minimax-algoritmen:

funksjon minimax (node, dybde, maksimaliserende spiller)
    if dybde = 0 or node er en terminal node
        retur den heuristiske verdien av noden
    if maximizingPlayer bestValue := -∞
        for hver child of node val := minimax(child, dybde - 1, FALSE)) bestValue := max(bestValue, val);
        retur beste verdi
    ellers
        beste verdi: = + ∞
        for hver child of node val := minimax(child, dybde - 1, TRUE)) bestValue := min(besteValue, val);
        retur beste verdi
(* Innledende samtale for å maksimere spilleren *)
minimax (opprinnelse, dybde, SANN)

Alfabetisk beskjæring

De Alfa-beta-beskjæringsalgoritme er en utvidelse av minimax, som kraftig reduserer (beskjærer) antall noder som vi må evaluere / utvide. For å oppnå dette estimerer algoritmen to verdier alfa og beta. Hvis betaen er mindre enn alfa i en gitt node, kan resten av undertrærne beskjæres. Her er en fin videopresentasjon av alfabetalgoritmen:

[Innebygd innhold]

Nedenfor ser du pseudokoden til Alfa-beta-beskjæringsalgoritmen:

funksjon alfabeta (node, dybde, α, β, maksimaliserende spiller)
    if dybde = 0 or node er en terminal node
        retur den heuristiske verdien av noden
    if maksimere spilleren
        for hver barn av node α := max(α, alfabeta(barn, dybde - 1, α, β, FALSE))
            if β ≤ α
                bryte (* ß avskjæring *)
        retur α
    ellers
        for hver barn av node β := min(β, alphabeta(barn, dybde - 1, α, β, TRUE))
            if β ≤ α
                bryte (* α cut-off *)
        retur β
(* Innledende samtale *)
alfabeta (opprinnelse, dybde, -∞, + ∞, SANN)

Hvordan AI brukes til å løse spillet 2048?

For å bruke algoritmene ovenfor må vi først identifisere de to spillerne. Den første spilleren er personen som spiller spillet. Den andre spilleren er datamaskinen som tilfeldig setter inn verdier i cellene på brettet. Det er klart den første spilleren prøver å maksimere poengsummen sin og oppnå fusjonen i 2048. På den annen side er datamaskinen i det originale spillet ikke spesielt programmert til å blokkere brukeren ved å velge det verst tenkelige trekket for ham, men heller tilfeldig sette inn verdier på de tomme cellene.

Så hvorfor bruker vi AI-teknikker som løser nullsumspill og som spesifikt antar at begge spillerne velger det best mulige trekket for dem? Svaret er enkelt; til tross for at det bare er den første spilleren som prøver å maksimere poengsummen sin, kan datamaskinens valg blokkere fremdriften og hindre brukeren i å fullføre spillet. Ved å modellere oppførselen til datamaskinen som en ortologisk ikke-tilfeldig spiller, sikrer vi at vårt valg vil være et solid valg uavhengig av hva datamaskinen spiller.

Den andre viktige delen er å tildele verdier til delstatene i spillet. Dette problemet er relativt enkelt fordi selve spillet gir oss en poengsum. Det er dessverre ikke en god tilnærming å prøve å maksimere poengsummen på egen hånd. En grunn til dette er at plasseringen av verdiene og antall tomme verdsatte celler er veldig viktig for å vinne spillet. For eksempel hvis vi sprer de store verdiene i eksterne celler, ville det være veldig vanskelig for oss å kombinere dem. Hvis vi ikke har noen tomme celler tilgjengelig, risikerer vi å tape spillet når som helst.

Av alle ovennevnte grunner flere heuristikker har blitt foreslått for eksempel Monoticity, glattheten og Free Fliser på brettet. Hovedideen er ikke å bruke poengsummen alene for å evaluere hver spilltilstand, men i stedet konstruere en heuristisk sammensatt poengsum som inkluderer de nevnte score.

Til slutt skal vi merke oss at selv om jeg har utviklet en implementering av Minimax-algoritmen, gjør det store antallet mulige tilstander algoritmen veldig treg og dermed er beskjæring nødvendig. Som et resultat i implementeringen av JAVA bruker jeg utvidelsen av Alpha-beta-beskjæringsalgoritmen. I motsetning til andre implementeringer, beskjærer jeg ikke aggressivt datamaskinens valg ved å bruke vilkårlige regler, men i stedet tar jeg dem alle i betraktning for å finne spillerens beste trekk.

Utvikle en heuristisk poengsumfunksjon

For å slå spillet prøvde jeg flere forskjellige heuristiske funksjoner. Den jeg fant mest nyttig 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));
}

Ovennevnte funksjon kombinerer den faktiske poengsummen til brettet, antall tomme celler / fliser og en metrikk kalt clustering score som vi vil diskutere senere. La oss se hver komponent mer detaljert:

1. Faktisk poengsum: Av åpenbare grunner, når vi beregner verdien av et brett, må vi ta hensyn til poengsummen. Tavler med høyere score er generelt foretrukket sammenlignet med tavler med lavere score.
2. Antall tomme celler: Som vi nevnte tidligere, er det viktig å holde noen tomme celler for å sikre at vi ikke taper spillet i de neste trekkene. Board-stater med flere tomme celler er generelt å foretrekke i forhold til andre med færre. Et spørsmål stiger om hvordan vil vi verdsette de tomme cellene? I min løsning veier jeg dem etter logaritmen til den faktiske poengsummen. Dette har følgende effekt: Jo lavere poengsum, jo ​​mindre viktig er det å ha mange tomme celler (Dette skyldes at i begynnelsen av spillet er det ganske enkelt å kombinere cellene). Jo høyere poengsum, jo ​​viktigere er det å sikre at vi har tomme celler i spillet vårt (Dette er fordi det på slutten av spillet er mer sannsynlig å tape på grunn av mangel på tomme celler.
3. Klyngescore: Vi bruker klyngescore som måler hvor spredte verdiene til styret vårt er. Når celler med lignende verdier er nærme, er de lettere å kombinere, noe som betyr at det er vanskeligere å tape spillet. I dette tilfellet har klyngescore en lav verdi. Hvis verdiene på brettet er spredt, får denne poengsummen en veldig stor verdi. Denne poengsum trekkes fra de to foregående score og fungerer som en straff som sikrer at klyngebrettet blir foretrukket.

I den siste linjen i funksjonen sikrer vi at poengsummen er ikke-negativ. Poengsummen skal være strengt positiv hvis poengsummen til brettet er positiv og null bare når poengsummen er null. Maks og min funksjonene er konstruert slik at vi får denne effekten.

Til slutt skal vi merke oss at når spilleren når en terminal spilltilstand og det ikke tillates flere trekk, bruker vi ikke poengsummen ovenfor for å estimere verdien av staten. Hvis spillet er vunnet tildeler vi høyest mulig heltallverdi, mens hvis spillet er tapt tildeler vi den laveste ikke-negative verdien (0 eller 1 med lignende logikk som i forrige avsnitt).

Mer om Clustering Score

Som vi sa tidligere, måler klyngescore hvor mye spredt er verdiene på tavlen og fungerer som en straff. Jeg konstruerte denne poengsummen på en slik måte at den inneholder tips / regler fra brukere som "mestrer" spillet. Den første foreslåtte regelen er at du prøver å holde cellene med lignende verdier i nærheten for å kombinere dem lettere. Den andre regelen er at celler med høyt verdi skal være nær hverandre og ikke vises midt på brettet, men heller på sidene eller hjørnene.

La oss se hvordan klyngescore blir estimert. For hver celle i brettet estimerer vi summen av absolutte forskjeller fra naboene (unntatt de tomme cellene), og vi tar gjennomsnittlig forskjell. Årsaken til at vi tar gjennomsnittet er å unngå å telle mer enn en gang effekten av to naboceller. Total klyngescore er summen av alle disse gjennomsnittene.

Clustering Score har følgende attributter:

1. Det får høy verdi når verdiene på tavlen er spredt og lav verdi når celler med lignende verdier ligger nær hverandre.
2. Det overveier ikke effekten av to naboceller.
3. Celler i marginene eller hjørnene har færre naboer og dermed lavere score. Som et resultat når de høye verdiene er plassert i nærheten av kantene eller hjørnene, har de mindre score, og dermed er straffen mindre.

Nøyaktigheten til algoritmen

Som forventet avhenger nøyaktigheten (også prosentandelen av spill som er vunnet) til algoritmen sterkt av søkedybden vi bruker. Jo høyere dybde på søket, jo høyere nøyaktighet og desto mer tid krever det å løpe. I mine tester varer et søk med dybde 3 mindre enn 0.05 sekunder, men gir 20% vinnersjanse, en dybde på 5 varer omtrent 1 sekund, men gir 40% sjanse for å vinne og til slutt en dybde på 7 varer 27-28 sekunder og gir omtrent 70-80% vinnersjanse.

Fremtidige utvidelser

For de av dere som er interessert i å forbedre koden her, er det få ting du kan se nærmere på:

1. Forbedre hastigheten: Å forbedre hastigheten på algoritmen vil tillate deg å bruke større dybde og dermed få bedre nøyaktighet.
2. Lag grafikk: Det er en god grunn til at implementeringen av Gabriele Cirulli ble så berømt. Den er fin! Jeg gadd ikke å utvikle et GUI, men jeg skriver heller ut resultatene på konsoll som gjør spillet vanskeligere å følge og å spille. Å lage en fin GUI er et must.
3. Tune heuristikk: Som jeg nevnte tidligere, har flere brukere antydet forskjellige heuristikker. Man kan eksperimentere med måten score blir beregnet på, vektene og brettegenskapene som tas i betraktning. Min tilnærming til å måle klyngescore skal visstnok kombinere andre forslag som Monotonicity og Smoothness, men det er fortsatt rom for forbedringer.
4. Stille dybden: Man kan også prøve å stille inn / justere dybden på søket avhengig av spilltilstand. Du kan også bruke Iterativ fordypning dybde-første søk algoritme som er kjent for å forbedre alfa-beta-beskjæringsalgoritmen.

Ikke glem å laste ned JAVA-koden fra Github og eksperimentere. Jeg håper du likte dette innlegget! Hvis du gjorde det, ta deg tid til å dele artikkelen på Facebook og Twitter. 🙂