Domanda Qual è l'algoritmo ottimale per il gioco 2048?


Di recente mi sono imbattuto nel gioco 2048. Unisci tessere simili spostandole in una delle quattro direzioni per creare tessere "più grandi". Dopo ogni mossa, una nuova tessera appare in una posizione vuota a caso con un valore di entrambi 2 o 4. Il gioco termina quando tutte le caselle sono piene e non ci sono mosse che possono unire tessere, oppure si crea una tessera con un valore di 2048.

Uno, ho bisogno di seguire una strategia ben definita per raggiungere l'obiettivo. Quindi, ho pensato di scrivere un programma per questo.

Il mio attuale algoritmo:

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
}

Quello che sto facendo è in qualsiasi momento, cercherò di unire le tessere con i valori 2 e 4, cioè, cerco di avere 2 e 4 tessere, il minimo possibile. Se provassi in questo modo, tutte le altre tessere si unirebbero automaticamente e la strategia sembrerebbe buona.

Ma, quando utilizzo effettivamente questo algoritmo, ottengo solo circa 4000 punti prima che il gioco termini. Il punteggio massimo di AFAIK è leggermente superiore a 20.000 punti, molto più grande del mio punteggio attuale. C'è un algoritmo migliore di quello sopra?


1753
2018-03-12 05:37


origine


risposte:


Ho sviluppato un AI 2048 usando expectimax ottimizzazione, invece della ricerca minimax utilizzata dall'algoritmo di @ ovolve. L'IA esegue semplicemente la massimizzazione su tutte le mosse possibili, seguita dall'aspettativa su tutte le possibili spawn delle tessere (ponderate dalla probabilità delle tessere, cioè il 10% per un 4 e il 90% per un 2). Per quanto ne so, non è possibile sfoltire l'ottimizzazione di expectimax (eccetto per rimuovere rami che sono estremamente improbabili), e quindi l'algoritmo utilizzato è una ricerca di forza bruta attentamente ottimizzata.

Prestazione

L'IA nella sua configurazione predefinita (profondità massima di ricerca di 8) impiega da 10 a 200 ms per eseguire una mossa, a seconda della complessità della posizione della scheda. Nei test, l'IA raggiunge una velocità di movimento media di 5-10 mosse al secondo nel corso di un'intera partita. Se la profondità di ricerca è limitata a 6 mosse, l'IA può facilmente eseguire 20+ mosse al secondo, il che lo rende per alcuni osservazione interessante.

Per valutare le prestazioni del punteggio dell'IA, ho eseguito l'intelligenza artificiale 100 volte (collegato al browser game tramite telecomando). Per ogni tessera, qui ci sono le proporzioni dei giochi in cui quella tessera è stata raggiunta almeno una volta:

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

Il punteggio minimo su tutte le corse era 124024; il punteggio massimo raggiunto è stato 794076. Il punteggio medio è 387222. L'IA non ha mai mancato di ottenere la tessera 2048 (quindi non ha mai perso la partita nemmeno una volta in 100 partite); in effetti, ha raggiunto il 8192 tessere almeno una volta in ogni corsa!

Ecco lo screenshot della corsa migliore:

32768 tile, score 794076

Questo gioco ha richiesto 27830 mosse su 96 minuti o una media di 4,8 mosse al secondo.

Implementazione

Il mio approccio codifica l'intera scheda (16 voci) come un singolo intero a 64 bit (dove le tessere sono i nybbles, cioè i pezzi a 4 bit). Su una macchina a 64 bit, ciò consente di far passare l'intera scheda in un unico registro macchina.

Le operazioni di spostamento dei bit vengono utilizzate per estrarre singole righe e colonne. Una singola riga o colonna è una quantità di 16 bit, quindi una tabella di dimensioni 65536 può codificare trasformazioni che operano su una singola riga o colonna. Ad esempio, le mosse sono implementate come 4 ricerche in una "tabella degli effetti di movimento" precalcolata che descrive come ogni mossa interessa una singola riga o colonna (ad esempio, la tabella "sposta a destra" contiene la voce "1122 -> 0023" che descrive come riga [2,2,4,4] diventa la riga [0,0,4,8] quando viene spostata a destra).

Anche il punteggio viene eseguito utilizzando la ricerca tabella. Le tabelle contengono punteggi euristici calcolati su tutte le righe / colonne possibili e il punteggio risultante per una scheda è semplicemente la somma dei valori della tabella in ogni riga e colonna.

Questa rappresentazione della scheda, insieme all'approccio alla ricerca di tabelle per il movimento e il punteggio, consente all'IA di cercare un enorme numero di stati di gioco in un breve periodo di tempo (oltre 10.000.000 stati di gioco al secondo su un nucleo del mio laptop di metà 2011).

La ricerca expectimax è codificata come una ricerca ricorsiva che alterna fasi "di aspettativa" (testando tutte le possibili posizioni e valori di spawn delle mattonelle e ponderando i loro punteggi ottimizzati per la probabilità di ogni possibilità), e le fasi di "massimizzazione" (testando tutte le mosse possibili e selezionando quello con il miglior punteggio). La ricerca ad albero termina quando vede una posizione precedentemente vista (usando a tavolo di trasposizione), quando raggiunge un limite di profondità predefinito o quando raggiunge uno stato di bordo altamente improbabile (ad esempio è stato raggiunto ottenendo 6 "4" tessere di fila dalla posizione iniziale). La profondità di ricerca tipica è di 4-8 mosse.

Euristico

Diverse euristiche sono utilizzate per indirizzare l'algoritmo di ottimizzazione verso posizioni favorevoli. La scelta precisa di euristica ha un enorme effetto sulle prestazioni dell'algoritmo. Le varie euristiche sono ponderate e combinate in un punteggio posizionale, che determina come "buona" una determinata posizione della scheda. La ricerca di ottimizzazione mirerà quindi a massimizzare il punteggio medio di tutte le possibili posizioni di bordo. Il punteggio effettivo, come mostrato dal gioco, è non utilizzato per calcolare il punteggio della scheda, poiché è troppo pesantemente ponderato a favore della fusione delle tessere (quando la fusione ritardata potrebbe produrre un grande beneficio).

Inizialmente, ho usato due euristiche molto semplici, concedendo "bonus" per i quadrati aperti e per avere grandi valori sul bordo. Queste euristiche hanno funzionato abbastanza bene, raggiungendo frequentemente il 16384 ma senza arrivare a 32768.

Petr Morávek (@xificurk) ha preso la mia intelligenza artificiale e ha aggiunto due nuove euristiche. La prima euristica era una penalità per avere righe e colonne non monotone che aumentavano man mano che i ranghi aumentavano, assicurando che le file non monotone di piccoli numeri non influenzassero fortemente il punteggio, ma le file non monotone di grandi numeri danneggiavano sostanzialmente il punteggio. La seconda euristica ha contato il numero di potenziali unioni (valori uguali adiacenti) oltre agli spazi aperti. Queste due euristiche servivano a spingere l'algoritmo verso schede monotone (che sono più facili da unire), e verso posizioni di bordo con un sacco di fusioni (incoraggiandolo ad allineare le unioni dove possibile per un effetto maggiore).

Inoltre, Petr ha anche ottimizzato i pesi euristici usando una strategia di "meta-ottimizzazione" (usando un algoritmo chiamato CMA-ES), dove i pesi stessi sono stati adeguati per ottenere il punteggio medio più alto possibile.

L'effetto di questi cambiamenti è estremamente significativo. L'algoritmo è passato dal realizzare la tessera 16384 a circa il 13% delle volte per raggiungerlo oltre il 90% delle volte e l'algoritmo ha iniziato a raggiungere 32768 su 1/3 del tempo (mentre la vecchia euristica non ha mai prodotto una tessera 32768) .

Credo che ci sia ancora spazio per miglioramenti sull'euristica. Questo algoritmo sicuramente non è ancora "ottimale", ma mi sembra che si stia avvicinando molto.


Che l'IA raggiunga la tessera 32768 in oltre un terzo dei suoi giochi è un traguardo enorme; Sarò sorpreso di sentire se alcuni giocatori umani hanno raggiunto 32768 nel gioco ufficiale (cioè senza usare strumenti come i salvataggi o annullare). Penso che la piastrella 65536 sia a portata di mano!

Puoi provare l'intelligenza artificiale per te stesso. Il codice è disponibile all'indirizzo https://github.com/nneonneo/2048-ai.


1130
2018-03-19 07:22



Sono l'autore del programma AI che altri hanno menzionato in questo thread. Puoi vedere l'IA in azione o leggi il fonte.

Attualmente, il programma raggiunge una percentuale di guadagno del 90% in esecuzione in javascript nel browser del mio computer portatile dato circa 100 millisecondi di tempo di riflessione per mossa, quindi mentre non perfetto (ancora!) Si comporta abbastanza bene.

Poiché il gioco è uno spazio discreto, informazioni perfette, giochi a turni come scacchi e dama, ho usato gli stessi metodi che hanno dimostrato di funzionare su quei giochi, vale a dire Minimax  ricerca con potatura alfa-beta. Dato che ci sono già molte informazioni su questo algoritmo, parlerò solo delle due principali euristiche che uso nel funzione di valutazione statica e che formalizzano molte delle intuizioni che altre persone hanno espresso qui.

Monotonicità

Questa euristica cerca di garantire che i valori delle tessere aumentino o diminuiscano sia lungo le direzioni sinistra / destra che su / giù. Solo questa euristica coglie l'intuizione che molti altri hanno menzionato, che le tessere di valore più alto dovrebbero essere raggruppate in un angolo. Normalmente impedirà alle tessere con valori più piccoli di rimanere orfani e manterrà la tavola molto organizzata, con tessere più piccole che si sovrappongono e si riempiono nelle tessere più grandi.

Ecco uno screenshot di una griglia perfettamente monotona. L'ho ottenuto eseguendo l'algoritmo con la funzione eval impostata per ignorare l'altra euristica e considerare solo la monotonicità.

A perfectly monotonic 2048 board

levigatezza

L'euristica di cui sopra tende a creare strutture in cui le tessere adiacenti stanno diminuendo di valore, ma ovviamente per unire, le tessere adiacenti devono avere lo stesso valore. Pertanto, l'euristica scorrevolezza misura solo la differenza di valore tra le tessere vicine, cercando di minimizzare questo conteggio.

Un commentatore su Hacker News ha dato un'interessante formalizzazione di questa idea in termini di teoria dei grafi.

Ecco uno screenshot di una griglia perfettamente liscia, per gentile concessione di questa eccellente parodia della forcella.

A perfectly smooth 2048 board

Piastrelle gratis

E infine, c'è una penalità per avere troppe tessere libere, dal momento che le opzioni possono esaurirsi rapidamente quando il tabellone di gioco diventa troppo angusto.

E questo è tutto! La ricerca attraverso lo spazio di gioco mentre si ottimizzano questi criteri produce prestazioni straordinariamente buone. Un vantaggio nell'usare un approccio generalizzato come questo piuttosto che una strategia di spostamento esplicitamente codificata è che l'algoritmo può spesso trovare soluzioni interessanti e inaspettate. Se lo guardi correre, spesso fa mosse sorprendenti ma efficaci, come cambiare improvvisamente a quale muro o angolo si sta costruendo.

Modificare:

Ecco una dimostrazione della potenza di questo approccio. Ho stappato i valori della tessera (quindi ha continuato ad andare dopo aver raggiunto il 2048) ed ecco il risultato migliore dopo otto prove.

4096

Sì, questo è un 4096 a fianco di un 2048. =) Ciò significa che ha ottenuto l'elusiva tessera 2048 per tre volte sullo stesso tabellone.


1224
2018-03-13 20:04



MODIFICARE: Questo è un algoritmo ingenuo, che modella il processo di pensiero cosciente umano, e ottiene risultati molto deboli rispetto all'IA che ricerca tutte le possibilità dal momento che guarda solo una tessera avanti. È stato inviato all'inizio della timeline di risposta.

Ho perfezionato l'algoritmo e battuto il gioco! Potrebbe fallire a causa della semplice sfortuna verso la fine (sei obbligato a scendere, cosa che non dovresti mai fare, e una tessera appare dove dovrebbe essere la tua più alta. Cerca semplicemente di mantenere la riga superiore piena, quindi spostarti a sinistra non rompere il modello), ma fondamentalmente si finisce per avere una parte fissa e una parte mobile con cui giocare. Questo è il tuo obiettivo:

Ready to finish

Questo è il modello che ho scelto di default.

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

L'angolo scelto è arbitrario, praticamente non premi mai un tasto (la mossa proibita), e se lo fai, premi di nuovo il contrario e prova a ripararlo. Per le tessere future il modello si aspetta sempre che la successiva tessera casuale sia un 2 e compaia sul lato opposto al modello corrente (mentre la prima riga è incompleta, nell'angolo in basso a destra, una volta completata la prima riga, in basso a sinistra angolo).

Ecco l'algoritmo. Circa l'80% vince (sembra che sia sempre possibile vincere con più tecniche "professionali" di intelligenza artificiale, non sono sicuro di questo, però).

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

Alcune indicazioni sui passaggi mancanti. Qui: model change

Il modello è cambiato a causa della fortuna di essere più vicino al modello previsto. Il modello che l'IA sta cercando di ottenere è

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

E la catena per arrivarci è diventata:

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

Il O rappresentare spazi proibiti ...

Quindi premerà a destra, poi di nuovo a destra, quindi (a destra o in alto a seconda di dove è stato creato il 4) quindi procederà a completare la catena finché non ottiene:

Chain completed

Quindi ora il modello e la catena sono tornati a:

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

Secondo puntatore, ha avuto sfortuna e il suo punto principale è stato preso. È probabile che fallirà, ma può ancora realizzarlo:

Enter image description here

Qui il modello e la catena sono:

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

Quando riesce a raggiungere il 128 guadagna un'intera riga si guadagna di nuovo:

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

119
2018-03-12 16:05



Mi sono interessato all'idea di un'intelligenza artificiale per questo gioco che contiene nessuna intelligenza hard-coded (non ci sono euristiche, funzioni di punteggio ecc.). L'intelligenza artificiale dovrebbe "conoscere" solo le regole del gioco, e "risolvere" il gioco. Ciò è in contrasto con la maggior parte delle IA (come quelle di questa discussione) in cui il gioco è essenzialmente una forza bruta guidata da una funzione di punteggio che rappresenta la comprensione umana del gioco.

Algoritmo AI

Ho trovato un algoritmo di gioco semplice ma sorprendentemente buono: per determinare la prossima mossa per una determinata tavola, l'IA gioca in memoria usando mosse casuali fino a quando il gioco è finito. Questo viene fatto più volte mentre si tiene traccia del punteggio del gioco finale. Quindi il punteggio finale medio per mossa iniziale è calcolato. La mossa iniziale con il punteggio finale medio più alto viene scelta come mossa successiva.

Con solo 100 esecuzioni (vale a dire in giochi di memoria) per mossa, l'IA ottiene la tessera 2048 l'80% delle volte e la tessera 4096 il 50% delle volte. L'utilizzo di 10000 esecuzioni consente di ottenere il tile 2048 al 100%, il 70% al 4096 e l'1% al tile 8192.

Guardalo in azione

Il miglior punteggio raggiunto è mostrato qui:

best score

Un dato interessante su questo algoritmo è che mentre i giochi a caso non sono sorprendenti, scegliere la mossa migliore (o meno cattiva) porta ad una partita molto buona: un tipico gioco AI può raggiungere 70000 punti e le ultime 3000 mosse, tuttavia i giochi casuali in memoria di qualsiasi posizione danno una media di 340 punti aggiuntivi in ​​circa 40 mosse extra prima di morire. (Puoi vederlo da solo eseguendo l'intelligenza artificiale e aprendo la console di debug.)

Questo grafico illustra questo punto: la linea blu mostra il punteggio di bordo dopo ogni mossa. La linea rossa mostra l'algoritmo migliore punteggio di fine partita a caso da quella posizione. In sostanza, i valori rossi stanno "tirando" verso l'alto i valori blu verso di loro, poiché sono la migliore ipotesi da parte dell'algoritmo. È interessante notare che la linea rossa è appena un po 'sopra la linea blu in ogni punto, eppure la linea blu continua ad aumentare sempre di più.

scoring graph

Trovo abbastanza sorprendente che l'algoritmo non abbia bisogno di prevedere effettivamente un buon gioco per scegliere le mosse che lo producono.

Cercando in seguito ho scoperto che questo algoritmo potrebbe essere classificato come un Ricerca dell'albero di Monte Carlo pura algoritmo.

Implementazione e collegamenti

Per prima cosa ho creato una versione JavaScript che può essere visto in azione qui. Questa versione può eseguire centinaia di esecuzioni in tempi decenti. Apri la console per ulteriori informazioni. (fonte)

Successivamente, per giocare ancora un po ', ho utilizzato l'infrastruttura altamente ottimizzata @nneonneo e ho implementato la mia versione in C ++. Questa versione consente fino a 100000 corse per mossa e anche 1000000 se si ha la pazienza. Istruzioni di costruzione fornite. Funziona nella console e ha anche un telecomando per riprodurre la versione web. (fonte)

risultati

Sorprendentemente, aumentare il numero di corse non migliora drasticamente il gioco. Sembra esserci un limite a questa strategia a circa 80000 punti con la tessera 4096 e tutti i più piccoli, molto vicino al raggiungimento della tessera 8192. Aumentando il numero di corse da 100 a 100000 aumenta il probabilità di raggiungere questo limite di punteggio (dal 5% al ​​40%) ma senza superarlo.

Esecuzione di 10000 esecuzioni con un aumento temporaneo a 1000000 in prossimità di posizioni critiche riuscite a superare questa barriera meno dell'1% dei tempi ottenendo un punteggio massimo di 129892 e 8192 tessere.

miglioramenti

Dopo aver implementato questo algoritmo ho provato molti miglioramenti tra cui l'utilizzo dei punteggi min o max, o una combinazione di min, max e avg. Ho anche provato ad usare la profondità: invece di provare le corse K per mossa, ho provato K mosse per mossa elenco di una determinata lunghezza ("su, su, sinistra" per esempio) e selezionando la prima mossa dell'elenco di mosse con punteggio migliore.

Successivamente ho implementato un albero di punteggio che teneva conto della probabilità condizionata di essere in grado di giocare una mossa dopo una determinata lista di mosse.

Tuttavia, nessuna di queste idee ha mostrato alcun reale vantaggio rispetto alla semplice prima idea. Ho lasciato il codice per queste idee commentate nel codice C ++.

Ho aggiunto un meccanismo di "Deep Search" che ha aumentato temporaneamente il numero di esecuzione a 1000000 quando una delle esecuzioni è riuscita a raggiungere accidentalmente la tessera più alta successiva. Questo ha offerto un miglioramento nel tempo.

Sarei interessato a sapere se qualcuno ha altre idee di miglioramento che mantengono l'indipendenza dal dominio dell'IA.

2048 Varianti e cloni

Solo per divertimento, ho anche implementato l'intelligenza artificiale come un bookmarklet, agganciarsi ai controlli del gioco. Ciò consente all'IA di lavorare con il gioco originale e molte delle sue varianti.

Ciò è possibile a causa della natura indipendente dal dominio dell'IA. Alcune varianti sono abbastanza distinte, come il clone esagonale.


114
2018-05-25 09:25



Copio qui il contenuto di a pubblicare sul mio blog


La soluzione che propongo è molto semplice e facile da implementare. Anche se ha raggiunto il punteggio di 131040. Vengono presentati diversi parametri di riferimento delle prestazioni dell'algoritmo.

Score

Algoritmo

Algoritmo di punteggio euristico

L'assunto su cui si basa il mio algoritmo è piuttosto semplice: se si desidera ottenere un punteggio più alto, la scheda deve essere mantenuta il più pulita possibile. In particolare, l'impostazione ottimale è data da un ordine decrescente lineare e monotono dei valori della tessera. Questa intuizione ti darà anche il limite superiore per un valore di tile: s dove n è il numero di tessere sul tabellone.

(C'è la possibilità di raggiungere la tessera 131072 se il quadratino a 4 viene generato casualmente invece del 2-piastrino quando necessario)

Due possibili modi di organizzare la tavola sono mostrati nelle seguenti immagini:

enter image description here

Per far rispettare l'ordinamento delle tessere in ordine decrescente monotono, il punteggio è calcolato come la somma dei valori linearizzati sul tabellone moltiplicati per i valori di una sequenza geometrica con rapporto comune r <1.

s

s

Diversi percorsi lineari possono essere valutati contemporaneamente, il punteggio finale sarà il punteggio massimo di qualsiasi percorso.

Regola decisionale

La regola decisionale implementata non è abbastanza intelligente, il codice in Python è presentato qui:

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

Un'implementazione di minmax o Expectiminimax migliorerà sicuramente l'algoritmo. Ovviamente un altro una sofisticata regola decisionale rallenterà l'algoritmo e richiederà un po 'di tempo per essere implementato. Proverò un'implementazione minimax nel prossimo futuro. (rimanete sintonizzati)

segno di riferimento

  • T1 - 121 test - 8 percorsi diversi - r = 0,125
  • T2 - 122 test - 8 percorsi diversi - r = 0,25
  • T3 - 132 test - 8 diversi percorsi - r = 0,5
  • T4 - 211 test - 2 percorsi diversi - r = 0,125
  • T5 - 274 test - 2 percorsi diversi - r = 0,25
  • T6 - 211 test - 2 percorsi diversi - r = 0,5

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

Nel caso di T2, quattro test su dieci generano la piastrella 4096 con un punteggio medio di s 42000

Codice

Il codice può essere trovato su GiHub al seguente link: https://github.com/Nicola17/term2048-AI È basato su term2048 ed è scritto in Python. Implementerò una versione più efficiente in C ++ il prima possibile.


88
2018-03-26 22:13



Il mio tentativo usa expectimax come altre soluzioni sopra, ma senza bitboard. La soluzione di Nneonneo può controllare 10 milioni di mosse che è approssimativamente una profondità di 4 con 6 tessere a sinistra e 4 mosse possibili (2 * 6 * 4)4. Nel mio caso, questa profondità richiede troppo tempo per essere esplorata, aggiusto la profondità della ricerca expectimax in base al numero di tessere libere lasciate:

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

I punteggi delle schede sono calcolati con la somma ponderata del quadrato del numero di tessere libere e del prodotto punto della griglia 2D con questo:

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

che costringe ad organizzare le tessere in modo discendente in una sorta di serpente dalla tacca in alto a sinistra.

Codice di seguito o 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



Penso di aver trovato un algoritmo che funziona abbastanza bene, dato che spesso raggiungo i punteggi sopra i 10000, il mio record personale è intorno ai 16000. La mia soluzione non mira a tenere i numeri più grandi in un angolo, ma a mantenerli nella prima fila.

Si prega di consultare il codice qui sotto:

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