Vraag Wat is het optimale algoritme voor de game 2048?


Ik ben recentelijk op het spel gestuit 2048. Je voegt soortgelijke tegels samen door ze in een van de vier richtingen te verplaatsen om 'grotere' tegels te maken. Na elke beweging verschijnt een nieuwe tegel op een willekeurige lege positie met de waarde van een van beide 2 of 4. Het spel wordt beëindigd wanneer alle vakken zijn gevuld en er geen zetten zijn die tegels kunnen samenvoegen, of u maakt een tegel met een waarde van 2048.

Ten eerste moet ik een welomschreven strategie volgen om het doel te bereiken. Dus ik dacht erover om er een programma voor te schrijven.

Mijn huidige algoritme:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Wat ik doe is op elk moment, ik zal proberen de tegels samen te voegen met waarden 2 en 4, dat wil zeggen, ik probeer te hebben 2 en 4 tegels, zo min mogelijk. Als ik het op deze manier probeer, worden alle andere tegels automatisch samengevoegd en lijkt de strategie goed.

Maar als ik dit algoritme gebruik, krijg ik pas 4000 punten voordat het spel wordt beëindigd. Maximum aantal punten AFAIK is iets meer dan 20.000 punten wat veel groter is dan mijn huidige score. Is er een beter algoritme dan het bovenstaande?


1753
2018-03-12 05:37


oorsprong


antwoorden:


Ik heb een 2048 AI ontwikkeld met expectimax optimalisatie, in plaats van de minimax-zoekopdracht die wordt gebruikt door het algoritme van @ ovolve. De AI voert eenvoudigweg maximalisatie uit over alle mogelijke zetten, gevolgd door verwachting over alle mogelijke tegel-spawns (gewogen naar de waarschijnlijkheid van de tegels, d.w.z. 10% voor een 4 en 90% voor een 2). Voor zover ik weet, is het niet mogelijk om expectimax-optimalisatie te snoeien (behalve om takken te verwijderen die buitengewoon onwaarschijnlijk zijn), en dus is het gebruikte algoritme een zorgvuldig geoptimaliseerde brute force-zoekopdracht.

Prestatie

De AI in de standaardconfiguratie (maximale zoekdiepte van 8) neemt tussen 10ms en 200ms in beslag om een ​​verplaatsing uit te voeren, afhankelijk van de complexiteit van de positie van het bord. Tijdens het testen behaalt de AI een gemiddelde bewegingssnelheid van 5-10 bewegingen per seconde in de loop van een volledig spel. Als de zoekdiepte beperkt is tot 6 zetten, kan de AI gemakkelijk 20+ bewegingen per seconde uitvoeren, wat voor sommigen zorgt interessant kijken.

Om de scoreprestaties van de AI te beoordelen, heb ik de AI 100 keer (verbonden met het browsergame via afstandsbediening) uitgevoerd. Voor elke tegel zijn hier de verhoudingen van games waarin die tegel ten minste één keer is behaald:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

De minimale score over alle runs was 124024; de maximaal behaalde score was 794076. De mediane score is 387222. De AI heeft nooit de 2048-tegel bemachtigd (dus hij verloor nooit het spel, zelfs niet in 100 spellen); in feite heeft het de 8192 tegel minstens één keer per keer!

Dit is het screenshot van de beste run:

32768 tile, score 794076

Deze game nam 27830 zetten over 96 minuten, of een gemiddelde van 4.8 zetten per seconde.

Implementatie

Mijn benadering codeert het volledige bord (16 ingangen) als een enkelvoudig 64-bit geheel getal (waarbij tegels de nybbles zijn, d.w.z. 4-bit chunks). Op een 64-bits machine kan hiermee het hele bord worden doorgegeven in een enkel machineregister.

Bitverschuivingsbewerkingen worden gebruikt om afzonderlijke rijen en kolommen te extraheren. Een enkele rij of kolom is een 16-bits grootheid, dus een tabel met de grootte 65536 kan transformaties coderen die op een enkele rij of kolom werken. Bewegingen worden bijvoorbeeld geïmplementeerd als 4 lookups in een vooraf berekende "verplaatsingseffecttabel" die beschrijft hoe elke verplaatsing een enkele rij of kolom beïnvloedt (de "verplaats naar rechts" -tabel bevat de invoer "1122 -> 0023" die beschrijft hoe de beweging rij [2,2,4,4] wordt de rij [0,0,4,8] wanneer deze naar rechts wordt verplaatst).

Scoren gebeurt ook met behulp van opzoeken van de tabel. De tabellen bevatten heuristische scores berekend op alle mogelijke rijen / kolommen en de resulterende score voor een bord is eenvoudigweg de som van de tabelwaarden voor elke rij en kolom.

Deze bordpresentatie, samen met de table lookup-benadering voor beweging en scoren, stelt de AI in staat om in een korte tijd een enorm aantal spelstatussen te doorzoeken (meer dan 10.000.000 spelsituaties per seconde op één kern van mijn laptop van medio 2011).

De expectimax-zoekfunctie zelf is gecodeerd als een recursieve zoekactie die wisselt tussen "verwachting" -stappen (testen van alle mogelijke tegel spawn-locaties en -waarden, en wegen van hun geoptimaliseerde scores met de waarschijnlijkheid van elke mogelijkheid), en "maximalisatie" -stappen (testen van alle mogelijke zetten en het selecteren van degene met de beste score). Het zoeken naar een boom eindigt als het een eerder geziene positie ziet (met behulp van een transponeringstabel), wanneer het een vooraf gedefinieerde dieptelimiet bereikt, of wanneer het een boardstatus bereikt die hoogst onwaarschijnlijk is (deze werd bijvoorbeeld bereikt door 6 "4" tegels op een rij te krijgen vanuit de startpositie). De typische zoekdiepte is 4-8 zetten.

heuristiek

Verschillende heuristieken worden gebruikt om het optimalisatie-algoritme naar gunstige posities te leiden. De precieze keuze van heuristiek heeft een enorm effect op de prestaties van het algoritme. De verschillende heuristieken worden gewogen en gecombineerd in een positionele score, die bepaalt hoe "goed" een bepaalde bordpositie is. De optimalisatie-zoekactie is dan gericht op het maximaliseren van de gemiddelde score van alle mogelijke bordposities. De feitelijke score, zoals getoond door de game, is niet wordt gebruikt om de bordscore te berekenen, omdat deze te zwaar wordt gewogen in het voordeel van het samenvoegen van tegels (wanneer vertraagd samenvoegen een groot voordeel zou kunnen opleveren).

Aanvankelijk gebruikte ik twee zeer eenvoudige heuristieken, die "bonussen" toekenden voor open vierkanten en voor het hebben van grote waarden aan de rand. Deze heuristieken presteerden redelijk goed, bereikten vaak 16384, maar bereikten nooit 32768.

Petr Morávek (@xificurk) pakte mijn AI en voegde twee nieuwe heuristieken toe. De eerste heuristiek was een boete voor het hebben van niet-monotone rijen en kolommen die toenamen naarmate de rijen hoger werden, waardoor niet-monotone rijen kleine getallen de score niet sterk beïnvloedden, maar niet-monotone rijen van grote aantallen deden de score behoorlijk pijn. De tweede heuristiek telde naast open ruimtes ook het aantal mogelijke samenvoegingen (naast elkaar liggende gelijke waarden). Deze twee heuristieken dienden om het algoritme naar monotone kaarten te duwen (die gemakkelijker kunnen worden samengevoegd) en naar bordposities met veel samenvoegingen (moedigen het aan om samenvoegingen waar mogelijk uit te lijnen voor een groter effect).

Bovendien optimaliseerde Petr ook de heuristische gewichten met behulp van een "meta-optimalisatie" strategie (met behulp van een algoritme genaamd CMA-ES), waarbij de gewichten zelf werden aangepast om de hoogst mogelijke gemiddelde score te verkrijgen.

Het effect van deze veranderingen is buitengewoon belangrijk. Het algoritme ging van het bereiken van de 16384-tegel rond 13% van de tijd om het meer dan 90% van de tijd te bereiken, en het algoritme bereikte 32768 meer dan een derde van de tijd (terwijl de oude heuristiek nooit één 32768-tegel produceerde) .

Ik geloof dat er nog steeds ruimte is voor verbetering op de heuristieken. Dit algoritme is absoluut nog niet 'optimaal', maar ik heb het gevoel dat het aardig in de buurt komt.


Dat de AI de 32768-tegel in meer dan een derde van zijn spellen bereikt, is een enorme mijlpaal; Ik zal verbaasd zijn om te horen of menselijke spelers 32768 hebben bereikt in het officiële spel (dat wil zeggen zonder gebruik te maken van tools zoals savestates of ongedaan maken). Ik denk dat de 65536 tegel binnen handbereik is!

Je kunt de AI zelf proberen. De code is beschikbaar op https://github.com/nneonneo/2048-ai.


1130
2018-03-19 07:22



Ik ben de auteur van het AI-programma dat anderen in deze thread hebben genoemd. Je kunt de AI bekijken in actie of lees de bron.

Op dit moment behaalt het programma ongeveer 90% winst in javascript in de browser op mijn laptop met ongeveer 100 milliseconden denktijd per zet, dus hoewel het (nog) niet perfect is, presteert het redelijk goed.

Omdat het spel een discrete toestandsruimte is, perfecte informatie, turn-based spel zoals schaken en dammen, gebruikte ik dezelfde methoden waarvan is bewezen dat ze werken op die spellen, namelijk minimax  zoeken met alfa-beta snoeien. Omdat er al veel informatie over dat algoritme is, zal ik alleen praten over de twee belangrijkste heuristieken die ik gebruik in de statische evaluatiefunctie en die veel van de intuïties formaliseren die anderen hier hebben uitgedrukt.

monotoniciteit

Deze heuristiek probeert ervoor te zorgen dat de waarden van de tegels allebei zowel links als rechts en omhoog / omlaag worden verhoogd of verlaagd. Deze heuristiek alleen vat de intuïtie samen die vele anderen hebben genoemd, dat tegels met een hogere waarde in een hoek moeten worden geclusterd. Het voorkomt meestal dat tegels met een kleinere waarde verweesd raken en houdt het bord overzichtelijk, met kleinere tegels die naar binnen vallen en zich opvullen in de grotere tegels.

Hier is een screenshot van een perfect monotoon raster. Ik verkreeg dit door het algoritme uit te voeren met de eval-functie ingesteld om de andere heuristieken te negeren en alleen monotoniciteit te overwegen.

A perfectly monotonic 2048 board

Gladheid

De bovenstaande heuristiek alleen heeft de neiging structuren te creëren waarin aangrenzende tegels in waarde dalen, maar natuurlijk om samen te voegen, moeten aangrenzende tegels dezelfde waarde hebben. Daarom meet de gladheidsheuristiek alleen het waardeverschil tussen naburige tegels, in een poging om deze telling te minimaliseren.

Een commentator op Hacker News gaf een interessante formalisering van dit idee in termen van grafentheorie.

Hier is een screenshot van een perfect vloeiend raster, met dank aan deze uitstekende parodievork.

A perfectly smooth 2048 board

Gratis tegels

En tot slot is er een boete voor het hebben van te weinig gratis tegels, omdat opties snel kunnen opraken als het spelbord te krap wordt.

En dat is het! Door de spelruimte te zoeken terwijl deze criteria worden geoptimaliseerd levert opmerkelijk goede prestaties op. Een voordeel van het gebruik van een dergelijke algemene benadering in plaats van een expliciet gecodeerde verplaatsstrategie is dat het algoritme vaak interessante en onverwachte oplossingen kan vinden. Als je het bekijkt, zal het vaak verrassende maar effectieve bewegingen maken, zoals plotseling schakelen naar welke muur of hoek het zich opbouwt.

Bewerk:

Hier is een demonstratie van de kracht van deze aanpak. Ik heb de tegelwaarden ontkoppeld (dus bleef het gaan na het bereiken van 2048) en hier is het beste resultaat na acht proeven.

4096

Ja, dat is een 4096 naast een 2048. =) Dat betekent dat het drie keer de ongrijpbare tegel uit 2048 op hetzelfde bord heeft bereikt.


1224
2018-03-13 20:04



BEWERK: Dit is een naïef algoritme dat het menselijk bewuste denkproces modelleert, en krijgt zeer zwakke resultaten in vergelijking met AI die alle mogelijkheden doorzoeken omdat het slechts één tegel vooruit kijkt. Het werd vroeg in de responstijdlijn ingediend.

Ik heb het algoritme verfijnd en het spel verslagen! Het kan mislukken als gevolg van eenvoudige pech tegen het einde (je wordt gedwongen naar beneden te gaan, wat je nooit zou moeten doen) en een tegel verschijnt waar je hoogste zou moeten zijn. Probeer gewoon de bovenste rij gevuld te houden, dus links naar links is niet breek het patroon), maar in principe heb je uiteindelijk een vast onderdeel en een mobiel onderdeel om mee te spelen. Dit is je doel:

Ready to finish

Dit is het model dat ik standaard heb gekozen.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

De gekozen hoek is willekeurig, je drukt eigenlijk nooit op één toets (de verboden zet), en als je dat doet, druk je het tegendeel nogmaals in en probeer je het op te lossen. Voor toekomstige tegels verwacht het model altijd dat de volgende willekeurige tegel een 2 is en aan de tegenovergestelde kant van het huidige model verschijnt (terwijl de eerste rij onvolledig is, in de rechteronderhoek, zodra de eerste rij is voltooid, linksonder hoek).

Hier gaat het algoritme. Ongeveer 80% wint (het lijkt altijd mogelijk om te winnen met meer "professionele" AI-technieken, ik weet het echter niet zeker.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Een paar aanwijzingen over de ontbrekende stappen. Hier: model change

Het model is veranderd door het geluk dichter bij het verwachte model te zijn. Het model dat de AI probeert te bereiken is

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

En de ketting om daar te komen is geworden:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

De O vertegenwoordig verboden ruimtes ...

Dus drukt hij rechts, dan weer opnieuw, dan (rechts of boven, afhankelijk van waar de 4 heeft gemaakt), gaat dan verder met het voltooien van de ketting totdat het:

Chain completed

Dus nu zijn het model en de keten terug naar:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Tweede wijzer, het heeft pech gehad en de hoofdplaats is ingenomen. Het zal waarschijnlijk mislukken, maar het kan het nog steeds bereiken:

Enter image description here

Hier is het model en de ketting:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Wanneer het de 128 bereikt krijgt het een hele rij is weer opgedaan:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



Ik raakte geïnteresseerd in het idee van een AI voor deze game met geen hardcoded intelligentie (d.w.z. geen heuristieken, scorefuncties enz.). De AI zou dat moeten doen "weten" alleen de spelregels, en "erachter te komen" het spel spelen. Dit staat in schril contrast met de meeste AI's (zoals die in deze thread), waarbij het spel in wezen brute kracht wordt gestuurd door een scorende functie die het menselijke begrip van het spel vertegenwoordigt.

AI-algoritme

Ik vond een eenvoudig maar verrassend goed spelalgoritme: om de volgende zet voor een bepaald bord te bepalen, speelt de AI het spel in het geheugen af ​​met behulp van willekeurige bewegingen tot het spel voorbij is. Dit wordt verschillende keren gedaan terwijl de eindscore wordt bijgehouden. Dan is de gemiddelde eindscore per startbeweging berekend. De startbeweging met de hoogste gemiddelde eindscore wordt gekozen als de volgende zet.

Met slechts 100 runs (d.w.z. in geheugenspelletjes) per zet behaalt de AI de 8048-tegel 80% van de keren en de 4096-tegel 50% van de keren. Met 10000 runs krijgt de 2048 tile 100%, 70% voor 4096 tile en ongeveer 1% voor de 8192 tile.

Zie het in actie

De best behaalde score wordt hier getoond:

best score

Een interessant feit over dit algoritme is dat hoewel de random-play-spellen niet verwonderlijk slecht zijn, het kiezen van de beste (of minst slechte) zet leidt tot een zeer goed spel: een typisch AI-spel kan 70000 punten bereiken en de laatste 3000 zetten, maar de willekeurige spellen in het geheugen van elke willekeurige positie leveren gemiddeld 340 extra punten op in ongeveer 40 extra zetten voordat je sterft. (U kunt dit zelf zien door de AI uit te voeren en de debug-console te openen.)

Deze grafiek illustreert dit punt: de blauwe lijn toont de bordscore na elke zet. De rode lijn toont de algoritmen het beste random-run eindscore van die positie. In wezen trekken de rode waarden de blauwe waarden naar boven toe, omdat ze de beste schatting zijn van het algoritme. Het is interessant om te zien dat de rode lijn op elk punt net een klein stukje boven de blauwe lijn ligt, maar de blauwe lijn blijft steeds groter worden.

scoring graph

Ik vind het nogal verrassend dat het algoritme niet echt goed spel hoeft te voorzien om de zetten te kiezen die het produceren.

Later zoeken vond ik dat dit algoritme geclassificeerd kon worden als een Pure Monte Carlo Tree Search algoritme.

Implementatie en links

Eerst heb ik een JavaScript-versie gemaakt die dat kan zijn hier in actie gezien. Deze versie kan 100's runs uitvoeren in een goede tijd. Open de console voor extra info. (bron)

Later, om wat meer te spelen, gebruikte ik @nneonneo een sterk geoptimaliseerde infrastructuur en implementeerde ik mijn versie in C ++. Deze versie biedt ruimte voor maximaal 100000 runs per zet en zelfs 1000000 als je het geduld hebt. Bouwinstructie verstrekt. Het draait in de console en heeft ook een afstandsbediening om de webversie af te spelen. (bron)

resultaten

Verrassend is dat het verhogen van het aantal runs het spel niet drastisch verbetert. Er lijkt een limiet te zijn aan deze strategie op ongeveer 80000 punten met de 4096 tegel en alle kleinere, heel dicht bij het bereiken van de 8192-tegel. Het verhogen van het aantal runs van 100 tot 100000 verhoogt de kansen om deze score te bereiken (van 5% tot 40%) maar niet door te breken.

Het runnen van 10000 runs met een tijdelijke toename tot 1000000 nabij kritieke posities slaagde er in deze barrière te doorbreken minder dan 1% van de keren behaalt een max score van 129892 en de 8192 tegel.

verbeteringen

Na het implementeren van dit algoritme heb ik veel verbeteringen geprobeerd, waaronder het gebruik van de min- of max-scores of een combinatie van min, max en avg. Ik heb ook geprobeerd de diepte te gebruiken: in plaats van K-runs per zet uit te proberen, probeerde ik K-zetten per zet lijst van een bepaalde lengte ("omhoog, omhoog, links" bijvoorbeeld) en het selecteren van de eerste zet van de best scorende verplaatsingslijst.

Later heb ik een scorestructuur geïmplementeerd die rekening hield met de voorwaardelijke kans om een ​​zet te kunnen spelen na een bepaalde zetlijst.

Geen van deze ideeën toonde echter enig reëel voordeel ten opzichte van het eenvoudige eerste idee. Ik heb de code voor deze ideeën achtergelaten in de C ++ -code.

Ik heb een "Deep Search" -mechanisme toegevoegd waardoor het run-nummer tijdelijk is verhoogd naar 1000000 wanneer een van de runs per ongeluk de eerstvolgende hoogste tegel heeft bereikt. Dit bood een tijdverbetering.

Ik zou graag willen weten of iemand andere verbeterideeën heeft die de domeinonafhankelijkheid van de AI handhaven.

2048 Varianten en klonen

Gewoon voor de lol, ik heb het ook implementeerde de AI als een bookmarklet, aansluiten op de besturing van het spel. Hierdoor kan de AI werken met het originele spel en veel van zijn varianten.

Dit is mogelijk vanwege de domeinonafhankelijke aard van de AI. Sommige van de varianten zijn behoorlijk verschillend, zoals de zeshoekige kloon.


114
2018-05-25 09:25



Ik kopieer hier de inhoud van a plaatsen op mijn blog


De oplossing die ik voorstel is heel eenvoudig en gemakkelijk te implementeren. Hoewel, het heeft de score van 131040 bereikt. Verschillende benchmarks van de prestaties van het algoritme worden gepresenteerd.

Score

Algoritme

Heuristisch scoringsalgoritme

De aanname waarop mijn algoritme is gebaseerd, is vrij eenvoudig: als u een hogere score wilt behalen, moet het bord zo netjes mogelijk worden gehouden. In het bijzonder wordt de optimale opstelling gegeven door een lineaire en monotoon afnemende volgorde van de tegeldata. Deze intuïtie geeft je ook de bovengrens voor een tegelwaarde: s waarbij n het aantal tegels op het bord is.

(Er is een mogelijkheid om de 131072-tegel te bereiken als de 4-tegels willekeurig wordt gegenereerd in plaats van de 2-tegels wanneer nodig)

Twee mogelijke manieren om het bord te organiseren, worden getoond in de volgende afbeeldingen:

enter image description here

Om de wijding van de tegels af te dwingen in een monotoon afnemende volgorde, wordt de score si berekend als de som van de gelineariseerde waarden op de kaart vermenigvuldigd met de waarden van een geometrische reeks met de gemeenschappelijke verhouding r <1.

s

s

Meerdere lineaire paden kunnen tegelijkertijd worden geëvalueerd, de uiteindelijke score is de maximale score van een willekeurig pad.

Beslisregel

De geïmplementeerde beslissingsregel is niet helemaal slim, de code in Python wordt hier weergegeven:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Een implementatie van de minmax of de Expectiminimax zal het algoritme zeker verbeteren. Uiteraard een meer geavanceerde beslissingsregel zal het algoritme vertragen en het zal enige tijd kosten om te worden geïmplementeerd. Ik zal in de nabije toekomst een minimax-implementatie proberen. (blijf kijken)

criterium

  • T1 - 121 tests - 8 verschillende paden - r = 0.125
  • T2 - 122 tests - 8-verschillende paden - r = 0.25
  • T3 - 132 tests - 8 verschillende paden - r = 0,5
  • T4 - 211 testen - 2 verschillende paden - r = 0.125
  • T5 - 274 tests - 2 verschillende paden - r = 0.25
  • T6 - 211 testen - 2 verschillende paden - r = 0.5

enter image description here enter image description here enter image description here enter image description here

In het geval van T2 genereren vier tests in tien de 4096 tegel met een gemiddelde score van s 42000

Code

De code is te vinden op GiHub op de volgende link: https://github.com/Nicola17/term2048-AI Het is gebaseerd op term2048 en het is geschreven in Python. Ik zal zo snel mogelijk een efficiëntere versie in C ++ implementeren.


88
2018-03-26 22:13



Mijn poging gebruikt expectimax zoals andere oplossingen hierboven, maar zonder bitboards. De oplossing van Nneonneo kan 10 miljoen bewegingen controleren, ongeveer een diepte van 4 met 6 tegels over en 4 zetten mogelijk (2 * 6 * 4)4. In mijn geval duurt deze diepte veel te lang om te verkennen, ik pas de diepte van expectimax-zoekopdrachten aan op basis van het aantal vrije tegels dat nog over is:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

De scores van de borden worden berekend met de gewogen som van het kwadraat van het aantal vrije stenen en het puntproduct van het 2D-raster met dit:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

welke krachten om afdalingen in een soort slang afdalen vanaf de tegel linksboven.

Code hieronder of jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Ik denk dat ik een algoritme heb gevonden dat redelijk goed werkt, omdat ik vaak scores bereik boven 10000, mijn persoonlijk record is rond de 16000. Mijn oplossing is er niet op gericht om de grootste aantallen in een hoek te houden, maar om deze op de bovenste rij te houden.

Zie de onderstaande code:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

25
2018-03-12 18:57



Ik ben de auteur van een 2048-controller die beter scoort dan elk ander programma dat in deze thread wordt genoemd. Een efficiënte implementatie van de controller is beschikbaar op github. In een afzonderlijke repo er is ook de code die wordt gebruikt voor het trainen van de statusevaluatiefunctie van de controller. De trainingsmethode wordt beschreven in de papier.

De controller gebruikt expectimax search met een statusevaluatiefunctie die van de grond af is geleerd (zonder menselijke 2048-expertise) door een variant van temporeel verschil leren (een versterkingstechniek). De functie-waardefunctie gebruikt een n-tuple netwerk, wat in feite een gewogen lineaire functie is van patronen die op het bord worden waargenomen. Het ging om meer dan 1 miljard gewichten, in totaal.

Prestatie

Op 1 zetten / s: 609.104 (100 games gemiddeld)

Op 10 zetten / s: 589.355 (Gemiddeld 300 spellen)

Op 3-laags (ca. 1500 zetten / s): 511.759 (1000 games gemiddeld)

De tegelstatistieken voor 10 zetten / s zijn als volgt:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(De laatste regel betekent dat de tegels op hetzelfde moment op het bord staan).

Voor 3-laags:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Ik heb echter nooit waargenomen dat de tegel 65536 werd verkregen.


25
2017-12-21 10:49



Er is al een AI-implementatie voor deze game: hier. Fragment uit README:

Het algoritme is een iteratief dieptediepte eerste alfa-bèta-zoekactie. De evaluatiefunctie probeert de rijen en kolommen monotoon te houden (alle verlagen of verhogen) terwijl het aantal tegels op het raster wordt geminimaliseerd.

Er is ook een discussie over Y Combinator over dit algoritme dat misschien nuttig is.


21
2018-03-13 09:16



Algoritme

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

evaluatie

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Evaluatiedetails

128 (Constant)

Dit is een constante, gebruikt als een basislijn en voor andere toepassingen zoals testen.

+ (Number of Spaces x 128)

Meer spaties maken de staat flexibeler, we vermenigvuldigen zich met 128 (wat de mediaan is) omdat een raster gevuld met 128 vlakken een optimale onmogelijke toestand is.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Hier evalueren we gezichten die de mogelijkheid hebben om samen te voegen, door ze achteraf te evalueren, wordt tegel 2 van waarde 2048, terwijl tegel 2048 wordt geëvalueerd 2.

+ Sum of other faces { log(face) x 4 }

Hier moeten we nog steeds controleren op gestapelde waarden, maar op een mindere manier worden de flexibiliteitsparameters niet onderbroken, dus we hebben de som van {x in [4,44]}.

+ (Number of possible next moves x 256)

Een staat is flexibeler als deze meer vrijheid heeft voor mogelijke overgangen.

+ (Number of aligned values x 2)

Dit is een vereenvoudigde controle van de mogelijkheid om samenvoegingen in die staat te hebben, zonder een vooruitblik te maken.

Opmerking: de constanten kunnen worden aangepast ..


20
2018-03-12 20:15