Kunstmatige intelligentie gebruiken om het 2048-spel op te lossen (JAVA-code)

• 7 april 2014
• Vasilis Vryniotis
• . 6 opmerkingen

Inmiddels hebben de meesten van jullie het gehoord / gespeeld 2048 spel door Gabriele Cirulli. Het is een eenvoudig maar zeer verslavend bordspel waarbij je de cijfers van de cellen moet combineren om het getal 2048 te bereiken. Zoals verwacht neemt de moeilijkheid van het spel toe naarmate meer cellen gevuld worden met hoge waarden. Persoonlijk, hoewel ik behoorlijk wat tijd aan het spelen van het spel besteedde, kon ik 2048 nooit bereiken. Het is dus natuurlijk om te proberen een AI-oplosser in JAVA te ontwikkelen om het spel van 2048 te verslaan. 🙂

In dit artikel zal ik kort mijn aanpak bespreken voor het bouwen van de Artificial Intelligence Solver of Game 2048, ik zal de heuristieken beschrijven die ik heb gebruikt en ik zal de volledige code geven die in JAVA is geschreven. De code is open source onder de GPL v3-licentie en u kunt deze downloaden van GitHub.

Het ontwikkelen van de 2048 Game in JAVA

Het originele spel is geschreven in JavaScript, dus ik moest het helemaal opnieuw in JAVA schrijven. Het belangrijkste idee van het spel is dat je een 4 × 4-raster hebt met integerwaarden, die allemaal machten zijn van 2. Cellen met nulwaarde worden als leeg beschouwd. Op elk punt tijdens het spel kun je de waarden in 4 richtingen omhoog, omlaag, naar rechts of naar links verplaatsen. Wanneer u een verplaatsing uitvoert, bewegen alle waarden van het raster in die richting en stoppen ze ofwel wanneer ze de randen van het raster bereiken of wanneer ze een andere cel bereiken met een waarde die niet nul is. Als die vorige cel dezelfde waarde heeft, worden de twee cellen samengevoegd tot één cel met dubbele waarde. Aan het einde van elke zet wordt een willekeurige waarde toegevoegd op het bord in een van de lege cellen en de waarde is ofwel 2 met een kans van 0.9 of 4 met een kans van 0.1. Het spel eindigt wanneer de speler erin slaagt om een ​​vakje te maken met waarde 2048 (winnen) of wanneer er geen andere zetten meer zijn (verlies).

In de oorspronkelijke implementatie van het spel is het algoritme voor het samenvoegen van bewegingen een beetje ingewikkeld omdat het rekening houdt met alle richtingen. Een mooie vereenvoudiging van het algoritme kan worden uitgevoerd als we de richting bepalen waarin we de stukken kunnen combineren en het bord dienovereenkomstig roteren om de beweging uit te voeren. Maurits van der Schee heeft er onlangs een artikel over geschreven waarvan ik denk dat het de moeite waard is om te bekijken.

Alle lessen zijn gedocumenteerd met Javadoc-opmerkingen. Hieronder geven we een beschrijving op hoog niveau van de architectuur van de implementatie:

1. Bestuursklasse

De bordklasse bevat de hoofdcode van het spel, die verantwoordelijk is voor het verplaatsen van de stukken, het berekenen van de score, het valideren of het spel is beëindigd enz.

2. ActionStatus en richting Enum

De ActionStatus en de Direction zijn 2 essentiële enums die de uitkomst van een zet en de richting daarvan dienovereenkomstig opslaan.

3. ConsoleGame-klasse

De ConsoleGame is de hoofdklasse waarmee we het spel kunnen spelen en de nauwkeurigheid van de AI Solver kunnen testen.

4. AIsolver-klasse

De AIsolver is de primaire klasse van de Artificial Intelligence-module die verantwoordelijk is voor het evalueren van de volgende beste zet voor een bepaald bord.

Kunstmatige intelligentie technieken: Minimax vs Alpha-beta snoeien

Er zijn verschillende benaderingen gepubliceerd om dit spel automatisch op te lossen. De meest opvallende is die van Matt Overlan. Om het probleem op te lossen, probeerde ik twee verschillende benaderingen, met behulp van het Minimax-algoritme en met Alpha-beta-snoeien.

Minimax-algoritme

De Minimax is een recursief algoritme dat kan worden gebruikt voor het oplossen van zero-sum games voor twee spelers. In elke staat van het spel associëren we een waarde. Het Minimax-algoritme doorzoekt de ruimte van mogelijke speltoestanden en creëert een boom die wordt uitgebreid tot het een bepaalde vooraf gedefinieerde diepte bereikt. Zodra die bladtoestanden zijn bereikt, worden hun waarden gebruikt om die van de tussenliggende knooppunten te schatten.

Het interessante idee van dit algoritme is dat elk niveau de beurt van een van de twee spelers vertegenwoordigt. Om te winnen moet elke speler de zet selecteren die de maximale uitbetaling van de tegenstander minimaliseert. Hier is een mooie videopresentatie van het minimax-algoritme:

[Ingesloten inhoud]

Hieronder ziet u de pseudocode van het Minimax-algoritme:

functie minimax (knooppunt, diepte, maximizingPlayer)
    if diepte = 0 or knooppunt is een eindknooppunt
        terugkeer de heuristische waarde van knooppunt
    if maximizingPlayer bestValue: = -∞
        voor elk kind van knooppunt val: = minimax (kind, diepte - 1, FALSE)) bestValue: = max (bestValue, val);
        terugkeer beste waarde
    anders
        bestValue: = + ∞
        voor elk kind van knooppunt val: = minimax (kind, diepte - 1, TRUE)) bestValue: = min (bestValue, val);
        terugkeer beste waarde
(* Eerste oproep om speler te maximaliseren *)
minimax (oorsprong, diepte, WAAR)

Alpha-beta snoeien

De Alpha-beta snoeimechanisme is een uitbreiding van de minimax, die het aantal knooppunten dat we moeten evalueren / uitbreiden sterk vermindert (snoeit). Om dit te bereiken, schat het algoritme twee waarden: de alfa en de bèta. Als in een bepaald knooppunt de bèta kleiner is dan alfa, kan de rest van de subtrees worden gesnoeid. Hier is een mooie videopresentatie van het alfabeta-algoritme:

[Ingesloten inhoud]

Hieronder ziet u de pseudocode van het Alpha-beta-snoeialgoritme:

functie alphabeta (knooppunt, diepte, α, β, maximizingPlayer)
    if diepte = 0 or knooppunt is een eindknooppunt
        terugkeer de heuristische waarde van knooppunt
    if maximaliserenSpeler
        voor elk kind van knoop α: = max (α, alfabeta (kind, diepte - 1, α, β, FALSE))
            if ≤ α
                breken (* β afsluiting *)
        terugkeer α
    anders
        voor elk kind van knoop β: = min (β, alfabeta (kind, diepte - 1, α, β, TRUE))
            if ≤ α
                breken (* α afgesneden *)
        terugkeer β
(* Eerste oproep *)
alphabeta (oorsprong, diepte, -∞, + ∞, TRUE)

Hoe AI wordt gebruikt om de Game 2048 op te lossen?

Om de bovenstaande algoritmen te gebruiken, moeten we eerst de twee spelers identificeren. De eerste speler is de persoon die het spel speelt. De tweede speler is de computer die willekeurig waarden invoegt in de cellen van het bord. Het is duidelijk dat de eerste speler probeert zijn / haar score te maximaliseren en de fusie van 2048 te bereiken. Aan de andere kant is de computer in het originele spel niet specifiek geprogrammeerd om de gebruiker te blokkeren door de slechtst mogelijke zet voor hem te selecteren, maar voegt willekeurig waarden in op de lege cellen.

Dus waarom gebruiken we AI-technieken die zero-sum games oplossen en er specifiek van uitgaan dat beide spelers de best mogelijke zet voor hen kiezen? Het antwoord is simpel; Ondanks het feit dat alleen de eerste speler probeert zijn / haar score te maximaliseren, kunnen de keuzes van de computer de voortgang blokkeren en de gebruiker ervan weerhouden het spel te voltooien. Door het gedrag van de computer als orthologische niet-willekeurige speler te modelleren, zorgen we ervoor dat onze keuze onafhankelijk van wat de computer speelt een solide keuze is.

Het tweede belangrijke onderdeel is het toekennen van waarden aan de spelstanden. Dit probleem is relatief eenvoudig omdat het spel zelf ons een score geeft. Helaas is het op zichzelf niet proberen om de score te maximaliseren. Een reden hiervoor is dat de positie van de waarden en het aantal lege cellen met waarde zeer belangrijk zijn om het spel te winnen. Als we bijvoorbeeld de grote waarden in afgelegen cellen verspreiden, zou het voor ons erg moeilijk zijn om ze te combineren. Als we bovendien geen lege cellen beschikbaar hebben, lopen we het risico het spel op elk moment te verliezen.

Om alle bovengenoemde redenen, verschillende heuristieken zijn gesuggereerd zoals de Monoticity, de gladheid en de Free Tiles van het bord. Het belangrijkste idee is niet om de score alleen te gebruiken om elke spelstatus te evalueren, maar om in plaats daarvan een heuristische samengestelde score te construeren die de bovengenoemde scores bevat.

Ten slotte moeten we opmerken dat hoewel ik een implementatie van het Minimax-algoritme heb ontwikkeld, het grote aantal mogelijke toestanden het algoritme erg traag maakt en dus snoeien noodzakelijk is. Als resultaat in de JAVA-implementatie gebruik ik de uitbreiding van het Alpha-beta-snoei-algoritme. Bovendien, in tegenstelling tot andere implementaties, snoei ik de keuzes van de computer niet agressief met behulp van willekeurige regels, maar in plaats daarvan houd ik er allemaal rekening mee om de best mogelijke beweging van de speler te vinden.

Een heuristische scorefunctie ontwikkelen

Om het spel te verslaan, heb ik verschillende heuristische functies geprobeerd. Degene die ik het nuttigst vond, is het volgende:

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

De bovenstaande functie combineert de werkelijke score van het bord, het aantal lege cellen / tegels en een metriek genaamd clustering score die we later zullen bespreken. Laten we elk onderdeel in meer detail bekijken:

1. Werkelijke score: Om voor de hand liggende redenen moeten we bij het berekenen van de waarde van een bord rekening houden met de score. Borden met hogere scores hebben over het algemeen de voorkeur boven borden met lagere scores.
2. Aantal lege cellen: Zoals we eerder vermeldden, is het belangrijk om weinig lege cellen te behouden om ervoor te zorgen dat we de game niet verliezen in de volgende zetten. Bestuurstoestanden met meer lege cellen hebben over het algemeen de voorkeur in vergelijking met andere met minder. Er rijst een vraag over hoe zouden we die lege cellen waarderen? In mijn oplossing weeg ik ze door de logaritme van de werkelijke score. Dit heeft het volgende effect: hoe lager de score, hoe minder belangrijk het is om veel lege cellen te hebben (dit komt omdat aan het begin van het spel het combineren van de cellen vrij eenvoudig is). Hoe hoger de score, hoe belangrijker het is om ervoor te zorgen dat we lege cellen in ons spel hebben (dit komt omdat het aan het einde van het spel waarschijnlijker is om te verliezen vanwege het gebrek aan lege cellen).
3. Clustering score: We gebruiken de clustering score die meet hoe verspreid de waarden van ons bord zijn. Wanneer cellen met vergelijkbare waarden dichtbij zijn, zijn ze gemakkelijker te combineren, wat betekent dat het moeilijker is om het spel te verliezen. In dit geval heeft de clustering score een lage waarde. Als de waarden van het bord verspreid zijn, krijgt deze score een zeer hoge waarde. Deze score wordt afgetrokken van de vorige twee scores en werkt als een straf die ervoor zorgt dat geclusterde borden de voorkeur krijgen.

In de laatste regel van de functie zorgen we ervoor dat de score niet negatief is. De score moet strikt positief zijn als de score van het bord positief is en nul alleen als het bord van de score nul is. De max en min functies zijn zo geconstrueerd dat we dit effect krijgen.

Ten slotte moeten we opmerken dat wanneer de speler een eindspelstatus bereikt en geen zetten meer zijn toegestaan, we de bovenstaande score niet gebruiken om de waarde van de staat te schatten. Als het spel wordt gewonnen, wijzen we de hoogst mogelijke gehele waarde toe, terwijl als het spel verloren gaat, we de laagste niet-negatieve waarde toewijzen (0 of 1 met vergelijkbare logica als in de vorige paragraaf).

Meer over de Clustering Score

Zoals we eerder zeiden, meet de clustering score hoeveel verspreid de waarden van het bord zijn en werkt als een penalty. Ik heb deze score zo geconstrueerd dat het tips / regels bevat van gebruikers die het spel "onder de knie" hebben. De eerste voorgestelde regel is dat u probeert de cellen met vergelijkbare waarden dichtbij te houden om ze gemakkelijker te combineren. De tweede regel is dat hooggewaardeerde cellen dicht bij elkaar moeten zijn en niet in het midden van het bord moeten verschijnen, maar eerder op de zijkanten of hoeken.

Laten we eens kijken hoe de clusterscore wordt geschat. Voor elke cel van het bord schatten we de som van absolute verschillen met zijn buren (exclusief de lege cellen) en nemen we het gemiddelde verschil. De reden waarom we de gemiddelden nemen, is om te voorkomen dat het effect van twee naburige cellen meer dan eens wordt geteld. De totale clusterscore is de som van al die gemiddelden.

De Clustering Score heeft de volgende kenmerken:

1. Het krijgt een hoge waarde wanneer de waarden van het bord zijn verspreid en een lage waarde wanneer cellen met vergelijkbare waarden dicht bij elkaar liggen.
2. Het weegt niet op tegen het effect van twee naburige cellen.
3. Cellen in de marge of hoeken hebben minder buren en dus lagere scores. Als gevolg hiervan, wanneer de hoge waarden dichtbij de marges of hoeken worden geplaatst, hebben ze kleinere scores en dus is de straf kleiner.

De nauwkeurigheid van het algoritme

Zoals verwacht hangt de nauwkeurigheid (ook bekend als het percentage gewonnen games) van het algoritme sterk af van de zoekdiepte die we gebruiken. Hoe hoger de diepte van de zoekopdracht, hoe hoger de nauwkeurigheid en hoe langer het duurt om te zoeken. In mijn tests duurt een zoekopdracht met diepte 3 minder dan 0.05 seconden maar geeft 20% kans om te winnen, een diepte van 5 duurt ongeveer 1 seconde maar geeft 40% kans om te winnen en uiteindelijk duurt een diepte van 7 27-28 seconden en geeft ongeveer 70-80% kans om te winnen.

Toekomstige uitbreidingen

Voor degenen onder u die geïnteresseerd zijn in het verbeteren van de code, zijn er enkele dingen waar u naar kunt kijken:

1. Verbeter de snelheid: Door de snelheid van het algoritme te verbeteren, kunt u een grotere diepte gebruiken en dus een betere nauwkeurigheid krijgen.
2. Afbeeldingen maken: Er is een goede reden waarom de implementatie van Gabriele Cirulli zo beroemd werd. Het ziet er leuk uit! Ik heb niet de moeite genomen om een ​​GUI te ontwikkelen, maar ik print de resultaten liever op de console, waardoor het spel moeilijker te volgen en te spelen is. Het maken van een mooie GUI is een must.
3. Stem heuristieken af: Zoals ik eerder al zei, hebben verschillende gebruikers verschillende heuristieken voorgesteld. Men kan experimenteren met de manier waarop de scores worden berekend, de gewichten en de bordkenmerken waarmee rekening wordt gehouden. Mijn benadering van het meten van de clusterscore zou andere suggesties zoals Monotoniciteit en Gladheid moeten combineren, maar er is nog ruimte voor verbetering.
4. De diepte afstemmen: Men kan ook proberen de zoekdiepte af te stemmen / aan te passen, afhankelijk van de spelstatus. Ook kunt u de Iteratieve verdieping - eerst zoeken algoritme waarvan bekend is dat het het alfa-bèta-snoei-algoritme verbetert.

Vergeet niet de JAVA-code te downloaden van GitHub en experimenteren. Ik hoop dat je dit bericht leuk vond! Als dat zo is, neem dan even de tijd om het artikel op Facebook en Twitter te delen. 🙂