Använda konstgjord intelligens för att lösa 2048-spelet (JAVA-kod)

• 7 april 2014
• Vasilis Vryniotis
• . 6 kommentarer

Nu har de flesta av er hört / spelat 2048 spel av Gabriele Cirulli. Det är ett enkelt men mycket beroendeframkallande brädspel som kräver att du kombinerar antalet celler för att nå 2048. Som förväntat ökar spelets svårighet när fler celler fylls med höga värden. Personligen trots att jag tillbringade en hel del tid på att spela spelet kunde jag aldrig nå 2048. Så det naturliga att göra är att försöka utveckla en AI-lösare i JAVA för att slå 2048-spelet. 🙂

I den här artikeln kommer jag kort att diskutera mitt tillvägagångssätt för att bygga artificiell intelligenslösare för spel 2048, jag kommer att beskriva heuristiken som jag använde och jag kommer att tillhandahålla den fullständiga koden som är skriven i JAVA. Koden är öppen från GPL v3-licensen och du kan ladda ner den från Github.

Utvecklar 2048-spelet i JAVA

Originalspelet är skrivet i JavaScript, så jag var tvungen att skriva om det i JAVA från grunden. Huvudidén med spelet är att du har ett 4 × 4 rutnät med heltalvärden, som alla har krafter på 2. Nollvärderade celler anses vara tomma. Vid varje punkt under spelet kan du flytta värdena mot fyra riktningar Upp, Ned, Höger eller Vänster. När du utför en flyttning rör sig alla värden i rutnätet i den riktningen och de stannar antingen när de når gränserna för rutnätet eller när de når en annan cell med ett värde som inte är noll. Om den föregående cellen har samma värde slås de två cellerna samman till en cell med dubbelt värde. I slutet av varje drag läggs ett slumpmässigt värde till i brädet i en av de tomma cellerna och dess värde är antingen 4 med 2 sannolikhet eller 0.9 med 4 sannolikhet. Spelet slutar när spelaren lyckas skapa en cell med värdet 0.1 (vinna) eller när det inte finns några andra drag att göra (förlora).

I den ursprungliga implementeringen av spelet är flyttningsalgoritmen lite komplicerad eftersom den tar hänsyn till alla riktningar. En trevlig förenkling av algoritmen kan utföras om vi fixar den riktning vi kan kombinera bitarna i och rotera brädet för att utföra rörelsen. Maurits van der Schee har nyligen skrivit en artikel om det som jag anser är värt att kolla in.

Alla klasser är dokumenterade med Javadoc-kommentarer. Nedan ger vi en högnivåbeskrivning av implementeringsarkitekturen:

1. Styrelseklass

Brädklassen innehåller spelets huvudkod, som ansvarar för att flytta bitarna, beräkna poängen, validera om spelet avslutas etc.

2. ActionStatus och Direction Enum

ActionStatus och Direction är två viktiga enums som lagrar resultatet av ett drag och dess riktning därefter.

3. ConsoleGame-klass

ConsoleGame är huvudklassen som låter oss spela spelet och testa noggrannheten hos AI Solver.

4. AIsolver-klass

AIsolver är den primära klassen i modulen Artificial Intelligence som ansvarar för att utvärdera det näst bästa drag som ges en viss styrelse.

Artificiell intelligens: Minimax vs Alpha-beta beskärning

Flera metoder har publicerats för att automatiskt lösa detta spel. Den mest anmärkningsvärda är den som utvecklats av Matt Overlan. För att lösa problemet försökte jag två olika tillvägagångssätt, med Minimax-algoritm och med Alpha-beta-beskärning.

Minimax algoritm

Smakämnen minimax är en rekursiv algoritm som kan användas för att lösa två spelare med nollsumma. I varje tillstånd av spelet kopplar vi ett värde. Minimax-algoritmen söker igenom möjliga speltillstånd och skapar ett träd som utvidgas tills det når ett särskilt fördefinierat djup. När dessa bladtillstånd har uppnåtts används deras värden för att uppskatta de mellanliggande noderna.

Den intressanta idén med denna algoritm är att varje nivå representerar turen för en av de två spelarna. För att vinna måste varje spelare välja det drag som minimerar motståndarens maximala utdelning. Här är en trevlig videopresentation av minimax-algoritmen:

[Inbäddat innehåll]

Nedan kan du se pseudokod för Minimax-algoritmen:

fungera minimax (nod, djup, maximizingPlayer)
    if djup = 0 or nod är en terminal nod
        avkastning det heuristiska värdet av noden
    if maximizingPlayer bestValue: = -∞
        för varje child of node val: = minimax (child, depth - 1, FALSE)) bestValue: = max (bestValue, val);
        avkastning bästa värde
    annars
        bestValue: = + ∞
        för varje child of node val: = minimax (child, depth - 1, TRUE)) bestValue: = min (bestValue, val);
        avkastning bästa värde
(* Initialt samtal för att maximera spelaren *)
minimax (ursprung, djup, SANT)

Beskärning av alfa-beta

Smakämnen Beskärningsalgoritm för Alpha-beta är en expansion av minimax, vilket kraftigt minskar (beskärar) antalet noder som vi måste utvärdera / expandera. För att uppnå detta uppskattar algoritmen två värden alfa och beta. Om beta i en given nod är mindre än alfa kan resten av underträdet beskäras. Här är en trevlig videopresentation av alphabeta-algoritmen:

[Inbäddat innehåll]

Nedan kan du se pseudokoden för Alpha-beta-beskärningsalgoritmen:

fungera alfabeta (nod, djup, α, β, maximizingPlayer)
    if djup = 0 or nod är en terminal nod
        avkastning det heuristiska värdet av noden
    if maximera spelare
        för varje barn till nod α: = max (α, alphabeta (barn, djup - 1, α, β, FALSE))
            if β ≤ α
                bryta (* β cut-off *)
        avkastning α
    annars
        för varje barn till nod β: = min (β, alfabeta (barn, djup - 1, α, β, SANT))
            if β ≤ α
                bryta (* α cut-off *)
        avkastning β
(* Första samtalet *)
alfabeta (ursprung, djup, -∞, + ∞, SANT)

Hur används AI för att lösa spelet 2048?

För att kunna använda ovanstående algoritmer måste vi först identifiera de två spelarna. Den första spelaren är den person som spelar spelet. Den andra spelaren är datorn som slumpmässigt sätter in värden i cellerna på brädet. Uppenbarligen försöker den första spelaren maximera sin poäng och uppnå 2048-sammanslagningen. Å andra sidan är datorn i det ursprungliga spelet inte särskilt programmerad för att blockera användaren genom att välja det värsta möjliga drag för honom utan snarare slumpmässigt infogar värden på de tomma cellerna.

Så varför använder vi AI-tekniker som löser nollsummispel och som specifikt antar att båda spelarna väljer bästa möjliga drag för dem? Svaret är enkelt; trots att det bara är den första spelaren som försöker maximera sin poäng, kan datorns val blockera framstegen och hindra användaren från att slutföra spelet. Genom att modellera datorns beteende som en ortologisk icke-slumpmässig spelare ser vi till att vårt val kommer att vara solidt oberoende av vad datorn spelar.

Den andra viktiga delen är att tilldela värden till spelets tillstånd. Detta problem är relativt enkelt eftersom själva spelet ger oss en poäng. Tyvärr är det inte bra att försöka maximera poängen på egen hand. En anledning till detta är att positionen för värdena och antalet tomma värderade celler är mycket viktigt för att vinna spelet. Om vi ​​till exempel sprider de stora värdena i avlägsna celler, skulle det vara väldigt svårt för oss att kombinera dem. Dessutom, om vi inte har några tomma celler tillgängliga, riskerar vi att förlora spelet när som helst.

Av alla ovanstående skäl, flera heuristik har föreslagits såsom Monoticity, mjukhet och Free Tiles på brädet. Huvudidén är att inte använda poängen ensam för att utvärdera varje speltillstånd utan istället konstruera en heuristisk kompositpoäng som inkluderar ovannämnda poäng.

Slutligen bör vi notera att även om jag har utvecklat en implementering av Minimax-algoritm så gör det stora antalet möjliga tillstånd algoritmen mycket långsam och därför är beskärning nödvändig. Som ett resultat av JAVA-implementeringen använder jag expansionen av Alpha-beta-beskärningsalgoritmen. Till skillnad från andra implementeringar beskär jag inte aggressivt datorns val med godtyckliga regler, utan istället tar jag hänsyn till dem alla för att hitta bästa möjliga drag för spelaren.

Utveckla en heuristisk poängfunktion

För att slå spelet försökte jag flera olika heuristiska funktioner. Den som jag tyckte var mest användbar är följande:

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

Ovanstående funktion kombinerar den faktiska poängen för brädet, antalet tomma celler / brickor och ett mått som kallas klusterpoäng som vi kommer att diskutera senare. Låt oss se varje komponent mer detaljerat:

1. Faktiskt resultat: Av uppenbara skäl måste vi ta hänsyn till dess poäng när vi beräknar värdet på en tavla. Brädor med högre poäng föredras i allmänhet jämfört med brädor med lägre poäng.
2. Antal tomma celler: Som vi nämnde tidigare är det viktigt att hålla några tomma celler för att säkerställa att vi inte tappar spelet i nästa drag. Kortstatus med fler tomma celler föredras i allmänhet jämfört med andra med färre. En fråga uppstår angående hur skulle vi värdera dessa tomma celler? I min lösning väger jag dem med logaritmen för den faktiska poängen. Detta har följande effekt: Ju lägre poäng, desto mindre viktigt är det att ha många tomma celler (det beror på att i början av spelet är det enkelt att kombinera cellerna). Ju högre poäng, desto viktigare är det att se till att vi har tomma celler i vårt spel (detta beror på att det i slutet av spelet är mer troligt att förlora på grund av bristen på tomma celler.
3. Clusteringsresultat: Vi använder klustringspoängen som mäter hur spridda värdena på vårt bräde är. När celler med liknande värden är nära är de lättare att kombinera, vilket betyder att det är svårare att förlora spelet. I det här fallet har klustringspoängen ett lågt värde. Om värdena på brädet är spridda får poängen ett mycket stort värde. Denna poäng subtraheras från de två föregående poängen och fungerar som ett straff som säkerställer att grupperade brädor föredras.

I den sista raden i funktionen ser vi till att poängen inte är negativ. Poängen bör vara strikt positiv om poängen på brädet är positiv och noll endast när poängen för poängen är noll. Max- och min-funktionerna är konstruerade så att vi får denna effekt.

Slutligen bör vi notera att när spelaren når ett terminalt speltillstånd och inga fler drag är tillåtna, använder vi inte ovanstående poäng för att uppskatta tillståndets värde. Om spelet vinns tilldelar vi det högsta möjliga heltalet, medan om spelet går förlorat tilldelar vi det lägsta icke-negativa värdet (0 eller 1 med liknande logik som i föregående stycke).

Mer om Clustering Score

Som vi sa tidigare mäter klusterpoängen hur mycket spridda är brädans värden och fungerar som ett straff. Jag konstruerade den här poängen på ett sådant sätt att den innehåller tips / regler från användare som "behärskar" spelet. Den första föreslagna regeln är att du försöker hålla cellerna med liknande värden nära för att kombinera dem enklare. Den andra regeln är att celler med högt värde ska vara nära varandra och inte visas i mitten av brädet utan snarare på sidorna eller hörnen.

Låt oss se hur klusterpoängen uppskattas. För varje cell på tavlan uppskattar vi summan av absoluta skillnader från sina grannar (exklusive de tomma cellerna) och vi tar den genomsnittliga skillnaden. Anledningen till att vi tar medelvärdena är att undvika att räkna mer än en gång effekten av två grannceller. Den totala grupperingspoängen är summan av alla dessa medelvärden.

Clustering Score har följande attribut:

1. Det blir högt värde när kortets värden sprids och lågt värde när celler med liknande värden ligger nära varandra.
2. Det överväger inte effekten av två grannceller.
3. Celler i marginalerna eller hörnen har färre grannar och därmed lägre poäng. Som ett resultat, när de höga värdena placeras nära marginalerna eller hörnen, har de mindre poäng och därmed är straffet mindre.

Algoritmens noggrannhet

Som förväntat beror algoritmens noggrannhet (aka procentandelen spel som vinns) starkt på det sökdjup vi använder. Ju högre sökdjup, desto högre noggrannhet och mer tid det tar att köra. I mina tester varar en sökning med djup 3 mindre än 0.05 sekunder men ger 20% chans att vinna, ett djup på 5 varar ungefär en sekund men ger 1% chans att vinna och slutligen ett djup på 40 varar 7-27 sekunder och ger ungefär 28-70% chans att vinna.

Framtida utvidgningar

För de av er som är intresserade av att förbättra koden är det några saker du kan titta på:

1. Förbättra hastigheten: Genom att förbättra algoritmens hastighet kan du använda större djup och därmed få bättre noggrannhet.
2. Skapa grafik: Det finns en bra anledning till varför Gabriele Cirullis implementering blev så känd. Det ser snyggt ut! Jag brydde mig inte om att utveckla ett GUI men jag skriver snarare ut resultaten på konsolen vilket gör spelet svårare att följa och spela. Att skapa ett bra GUI är ett måste.
3. Tune Heuristics: Som jag nämnde tidigare har flera användare föreslagit olika heuristik. Man kan experimentera med hur poängen beräknas, vikterna och brädeegenskaperna som beaktas. Mitt tillvägagångssätt för att mäta klusterpoängen ska kombinera andra förslag som monotonicitet och jämnhet, men det finns fortfarande utrymme för förbättringar.
4. Ställa in djupet: Man kan också försöka ställa in / justera sökdjupet beroende på spelets tillstånd. Du kan också använda Iterativ fördjupning djup-första sökning algoritm som är känd för att förbättra alfa-beta-beskärningsalgoritmen.

Glöm inte att ladda ner JAVA-koden från Github och experimentera. Jag hoppas att du gillade det här inlägget! Var snäll och ta en del av artikeln på Facebook och Twitter. 🙂