algorithm - Qual è l'algoritmo ottimale per il gioco 2048?




logic artificial-intelligence (10)

Copio qui il contenuto di un post 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.

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: 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:

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.

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 una regola decisionale più sofisticata 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

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

Codice

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

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 casuale con un valore di 2 o 4 . Il gioco termina quando tutte le caselle sono piene e non ci sono mosse in grado di unire le tessere o 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?


Ho sviluppato un AI 2048 utilizzando l' ottimizzazione expectimax , invece della ricerca minimax utilizzata dall'algoritmo di @ ovolve. L'IA esegue semplicemente la massimizzazione su tutte le mosse possibili, seguita dall'aspettativa su tutti i possibili spawn delle tessere (ponderata dalla probabilità delle tessere, cioè 10% per un 4 e 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 rende la visione 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 la tessera 8192 almeno una volta in ogni corsa!

Ecco lo screenshot della corsa migliore:

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 blocchi 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 una tabella di trasposizione ), quando raggiunge un limite di profondità predefinito o quando raggiunge uno stato di bordo altamente improbabile (ad es. È stato raggiunto ottenendo 6 tessere "4" in fila dalla posizione di partenza). 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 viene utilizzato per calcolare il punteggio della tavola, 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 utilizzando una strategia di "meta-ottimizzazione" (utilizzando un algoritmo chiamato CMA-ES ), in cui 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 .


Mi sono interessato all'idea di un'intelligenza artificiale per questo gioco senza intelligenza hard-coded (cioè senza euristica, funzioni di punteggio ecc.). L'IA dovrebbe "conoscere" solo le regole del gioco e "capire" 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 il gioco in memoria usando mosse casuali fino a che il gioco non è finito. Questo viene fatto più volte mentre si tiene traccia del punteggio del gioco finale. Quindi viene calcolato il punteggio finale medio per mossa iniziale . La mossa iniziale con il punteggio finale medio più alto viene scelta come mossa successiva.

Con solo 100 corse (vale a dire nei giochi di memoria) per mossa, l'IA raggiunge 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:

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 il miglior punteggio di fine corsa a random dell'algoritmo 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ù.

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 algoritmo di ricerca dell'albero di Monte Carlo puro .

Implementazione e collegamenti

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

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. ( source )

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 esecuzioni da 100 a 100000 aumentano le probabilità di raggiungere questo limite di punteggio (dal 5% al ​​40%) ma non di 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 di K per mossa, ho provato K mosse per ogni lista di mosse di una determinata lunghezza ("su, su, a 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 bookmarklet , agganciata 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.


Sono l'autore del programma AI che altri hanno menzionato in questo thread. Puoi vedere l'IA in action o leggere la source .

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.

Dato che il gioco è uno spazio di stato discreto, informazioni perfette, giochi a turni come scacchi e dama, ho usato gli stessi metodi che hanno dimostrato di funzionare su quei giochi, ovvero la search minimax con potatura alfa-beta . Dato che ci sono già molte informazioni su questo algoritmo, parlerò solo delle due principali euristiche che uso nella 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à.

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 di Hacker News ha dato un'interessante formalizzazione di questa idea in termini di teoria dei grafi.

Ecco uno screenshot di una griglia perfettamente liscia, grazie a questa eccellente parodia forchetta .

Piastrelle gratis

E infine, c'è una penalità per avere troppe tessere libere, poiché 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.

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


EDIT: 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:

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:

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

Gli O rappresentano 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:

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:

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

Ho scritto un risolutore 2048 in Haskell, principalmente perché sto imparando questa lingua in questo momento.

La mia implementazione del gioco differisce leggermente dal gioco reale, in quanto una nuova tessera è sempre un '2' (anziché il 90% 2 e il 10% 4). E che la nuova tessera non è casuale, ma sempre la prima disponibile in alto a sinistra. Questa variante è nota anche come Det 2048 .

Di conseguenza, questo risolutore è deterministico.

Ho usato un algoritmo esaustivo che favorisce le tessere vuote. Esegue abbastanza velocemente per profondità 1-4, ma in profondità 5 diventa piuttosto lento a circa 1 secondo per mossa.

Di seguito è riportato il codice che implementa l'algoritmo di risoluzione. La griglia è rappresentata come una serie di 16 numeri interi. E il punteggio viene fatto semplicemente contando il numero di caselle vuote.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Penso che abbia abbastanza successo per la sua semplicità. Il risultato che raggiunge quando inizia con una griglia vuota e la risoluzione in profondità 5 è:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Il codice sorgente può essere trovato qui: https://github.com/popovitsj/2048-haskell


Questa non è una risposta diretta alla domanda di OP, questo è più delle cose (esperimenti) che ho provato finora per risolvere lo stesso problema e ho ottenuto alcuni risultati e ho alcune osservazioni che voglio condividere, sono curioso di sapere se possiamo ulteriori approfondimenti da questo.

Ho appena provato la mia implementazione minimax con potatura alfa-beta con taglio di profondità dell'albero di ricerca a 3 e 5. Stavo cercando di risolvere lo stesso problema per una griglia 4x4 come assegnazione di progetto per il corso EDX ColumbiaX: CSMM.101x Artificial Intelligence ( AI) .

Ho applicato una combinazione convessa (provato diversi pesi euristici) di una coppia di funzioni di valutazione euristiche, principalmente dall'intuito e da quelle discusse sopra:

  1. Monotonicità
  2. Spazio disponibile libero

Nel mio caso, il giocatore del computer è completamente casuale, ma ho sempre assunto le impostazioni del contraddittorio e ho implementato l'agente del giocatore AI come massimo giocatore.

Ho una griglia 4x4 per giocare.

Osservazione:

Se assegno troppi pesi alla prima funzione euristica o alla seconda funzione euristica, in entrambi i casi i punteggi ottenuti dal giocatore di IA sono bassi. Ho giocato con molte assegnazioni di peso possibili alle funzioni euristiche e ho preso una combinazione convessa, ma molto raramente il giocatore AI è in grado di segnare 2048. La maggior parte delle volte si ferma a 1024 o 512.

Ho anche provato l'euristica dell'angolo, ma per qualche motivo rende i risultati peggiori, qualche intuizione perché?

Inoltre, ho cercato di aumentare il limite di profondità della ricerca da 3 a 5 (non posso aumentarlo di più poiché la ricerca di quello spazio supera il tempo consentito anche con la potatura) e ho aggiunto un'altra euristica che guarda i valori delle tessere adiacenti e dà più punti se sono in grado di unire, ma ancora non riesco a ottenere il 2048.

Penso che sarà meglio usare Expectimax invece di minimax, ma comunque voglio risolvere questo problema solo con minimax e ottenere punteggi alti come 2048 o 4096. Non sono sicuro che mi manchi qualcosa.

Sotto l'animazione vengono visualizzati gli ultimi passaggi del gioco svolto dall'agente AI con il riproduttore di computer:

Qualsiasi approfondimento sarà davvero molto utile, grazie in anticipo. (Questo è il link del mio post sul blog per l'articolo: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )

L'animazione seguente mostra gli ultimi passaggi del gioco in cui l'agente del giocatore AI può ottenere 2048 punteggi, questa volta aggiungendo anche il valore assoluto euristico:

Le seguenti figure mostrano l' albero del gioco esplorato dall'agente del giocatore dell'AI assumendo il computer come avversario per un solo passaggio:


Questo algoritmo non è ottimale per vincere il gioco, ma è abbastanza ottimale in termini di prestazioni e quantità di codice necessario:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

Molte altre risposte utilizzano l'intelligenza artificiale con una ricerca computazionalmente onerosa su possibili futuri, euristica, apprendimento e così via. Questi sono impressionanti e probabilmente la strada giusta, ma vorrei dare un'altra idea.

Modella il tipo di strategia che usano i buoni giocatori del gioco.

Per esempio:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Leggi i quadrati nell'ordine mostrato sopra fino a quando il valore dei quadrati successivi è maggiore di quello attuale. Questo presenta il problema di provare a unire un'altra tessera dello stesso valore in questo quadrato.

Per risolvere questo problema, ci sono due modi per muoversi che non vengono lasciati o peggio e esaminare entrambe le possibilità può rivelare immediatamente più problemi, questo forma un elenco di dipendenze, ogni problema che richiede un altro problema da risolvere per primo. Penso di avere questa catena o in alcuni casi un albero di dipendenze internamente al momento di decidere la mia prossima mossa, in particolare quando bloccato.

La piastrella deve fondersi con il vicino ma è troppo piccola: unisci un altro vicino con questo.

Piastrella più grande nel modo: aumenta il valore di una tessera circostante più piccola.

eccetera...

L'intero approccio sarà probabilmente più complicato di questo, ma non molto più complicato. Potrebbe essere questo meccanico sentire privo di punteggi, pesi, neuroni e ricerche approfondite di possibilità. L'albero delle possibilità deve anche essere abbastanza grande da richiedere qualsiasi ramificazione.


Sono l'autore di un controller 2048 che ottiene punteggi migliori di qualsiasi altro programma menzionato in questo thread. Un'efficace implementazione del controller è disponibile su github.com/aszczepanski/2048 . In un repository separato c'è anche il codice utilizzato per addestrare la funzione di valutazione dello stato del controllore. Il metodo di allenamento è descritto nel paper .

Il controllore utilizza la ricerca expectimax con una funzione di valutazione dello stato appresa da zero (senza esperienza 2048 umana) con una variante dell'apprendimento della differenza temporale (una tecnica di apprendimento di rinforzo). La funzione valore di stato utilizza una rete n-tupla , che è fondamentalmente una funzione lineare ponderata di schemi osservati sulla scheda. Ha coinvolto oltre 1 miliardo di pesi , in totale.

Prestazione

A 1 mosse: 609104 (media di 100 giochi)

A 10 mosse: 589355 (media di 300 partite)

A 3 veli (circa 1500 mosse / s): 511759 (media di 1000 giochi)

Le statistiche delle tessere per 10 mosse / s sono le seguenti:

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

(L'ultima linea significa avere le tessere date allo stesso tempo sul tabellone).

Per 3 veli:

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

Tuttavia, non l'ho mai osservato ottenendo il tile 65536.





2048