Qual è l’algoritmo ottimale per il gioco 2048?
Introduzione
2048 è un emozionante gioco di tile-shifting, dove ci muoviamo piastrelle in giro per combinarli, con l’obiettivo di valori sempre più grandi piastrelle.
In questo tutorial, stiamo andando a indagare un algoritmo per giocare 2048, uno che aiuterà a decidere le mosse migliori da fare ad ogni passo per ottenere il miglior punteggio.
Come giocare a 2048
Una partita di 2048 viene giocata su una scheda 4×4., Ogni posizione sul tabellone può essere vuota o può contenere una tessera, e ogni tessera avrà un numero su di esso.
Quando iniziamo, la scheda avrà due tessere in posizioni casuali, ognuna delle quali ha un “2” o un “4” su di essa – ognuna ha una probabilità indipendente del 10% di essere un “4”, o altrimenti a è un “2”.
Le mosse vengono eseguite spostando tutte le tessere verso un bordo: su, giù, sinistra o destra., In questo modo, tutte le tessere con lo stesso valore che sono adiacenti l’una all’altra e si muovono insieme si uniranno e finiranno con una nuova tessera uguale alla somma delle due precedenti:
Dopo aver fatto una mossa, una nuova tessera verrà posizionata sulla lavagna. Questo è posto in una posizione casuale, e sarà un “2” o un “4” nello stesso modo come le piastrelle iniziali – “2” 90% del tempo e “4” 10% del tempo.
Il gioco continua fino a quando non ci sono più mosse possibili.
In generale, l’obiettivo del gioco è raggiungere una singola tessera con un valore di “2048”., Tuttavia, il gioco non si ferma qui, e possiamo continuare a giocare, per quanto è possibile andare, puntando per la più grande tessera possibile. In teoria, questa è una tessera con il valore “131,072”.
Spiegazione del problema
Risolvere questo gioco è un problema interessante perché ha una componente casuale. È impossibile prevedere correttamente non solo dove verrà posizionata ogni nuova tessera, ma se sarà un “2” o un “4”.
In quanto tale, è impossibile avere un algoritmo che risolva correttamente il puzzle ogni volta., Il meglio che possiamo fare è determinare ciò che è probabile che sia la mossa migliore in ogni fase e giocare il gioco di probabilità.
In qualsiasi momento, ci sono solo quattro possibili mosse che possiamo fare. A volte, alcune di queste mosse non hanno alcun impatto sulla scacchiera e quindi non valgono la pena di fare – ad esempio, nella scheda sopra una mossa di “Down” non avrà alcun impatto poiché tutte le tessere sono già sul bordo inferiore.
La sfida è quindi determinare quale di queste quattro mosse sarà quella che avrà il miglior risultato a lungo termine.,
Il nostro algoritmo si basa sull’algoritmo Expectimax, che è a sua volta una variazione dell’algoritmo Minimax, ma dove i possibili percorsi attraverso il nostro albero sono ponderati dalla probabilità che accadano.
in sostanza, abbiamo trattare il gioco come un gioco per due giocatori:
- Lettore – il giocatore umano – può spostare la scheda in una delle quattro direzioni
- Lettore di Due computer giocatore può piazzare una tessera in un punto vuoto sul bordo
sulla Base di questo, siamo in grado di generare un albero di risultati di ogni mossa, ponderati per la probabilità di ogni mossa accadendo., Questo può quindi darci i dettagli necessari per determinare quale mossa umana è probabile che dia il miglior risultato.
3.1. Diagramma di flusso di Gameplay
Il flusso generale di come il gameplay funziona:
Possiamo vedere immediatamente l’casuale aspetto del gioco in “Aggiungi Casuale Tegola” del processo, sia il fatto che stiamo trovando casuale piazza per aggiungere la piastrella, e stiamo selezionando un valore casuale per la piastrella.
La nostra sfida è quindi decidere cosa fare nel passaggio “Determina la prossima mossa”. Questo è il nostro algoritmo per giocare il gioco.,
L’overflow generale di questo sembra ingannevolmente semplice:
Tutto quello che dobbiamo fare è simulare ciascuna delle possibili mosse, determinare quale dà il miglior risultato e quindi usarlo.
Quindi ora abbiamo ridotto il nostro algoritmo a simulare una determinata mossa e generare un punteggio per il risultato.
Questo è un processo in due parti. Il primo passaggio è quello di vedere se la mossa è ancora possibile, e se non, poi abortire presto con un punteggio di “0”., Se la mossa è possibile, passiamo all’algoritmo reale in cui determiniamo quanto è buona una mossa:
3.2. Determinare la prossima mossa
La parte fondamentale del nostro algoritmo finora è nella simulazione di una mossa, e la parte fondamentale di questo è il modo in cui generiamo un punteggio per ogni possibile mossa. Questo è dove il nostro algoritmo Expectimax entra in gioco.
Simuleremo ogni possibile mossa da entrambi i giocatori per diversi passaggi e vedremo quale di questi dà il miglior risultato. Per il giocatore umano, questo significa ciascuna delle mosse” su”,” giù”,” sinistra “e” destra”.,
Per il giocatore del computer, questo significa posizionare sia un “2” o un “4” in ogni possibile posizione vuota:
Questo algoritmo è ricorsivo, con ogni passo ricorsivo che si ferma solo se è una certa profondità dalla mossa effettiva nel gioco reale.,ulating un punteggio per il momento simulato il layout della scheda
- Simulare ogni possibile umana spostare
- Per ognuno di questi
- Recurse nuovamente dentro l’algoritmo
- Ritorno calcolato il punteggio da questo umano spostare
- Aggiungere il punteggio calcolato da questo computer, ponderati per la probabilità di questa mossa accadendo
Quando abbiamo finito questo, poi ci aggiungi tutte le calcolati i punteggi, e questo è il punteggio finale per il trasloco, vogliamo rendere il gioco attuale consiglio di amministrazione., Poiché lo facciamo quattro volte-una per ogni possibile mossa dal tabellone di gioco corrente-finiamo con quattro punteggi, e il più alto di questi è la mossa da fare.
3.3. Punteggio di una posizione di bordo
A questo punto, l’unica cosa che resta da fare è calcolare un punteggio per una tavola. Questo non è lo stesso punteggio come il gioco utilizza, ma ha bisogno di prendere in considerazione quanto è buona una posizione questo è quello di continuare a giocare da.
Ci sono un gran numero di modi in cui questo può essere ottenuto aggiungendo diversi fattori insieme a ponderazioni appropriate., Per esempio:
- Numero di posizioni vuote
- Numero di possibili unioni – cioè, il numero di volte che il numero è in due posizioni adiacenti
- Il valore più grande in qualsiasi posizione
- Somma di tutte le posizioni
- Monotonicità del consiglio – questo è il modo in cui il consiglio di amministrazione è strutturato, tale che i valori di posizione di aumentare in una sola direzione.
Pseudocodice
Ora che sappiamo come funzionerà l’algoritmo, che aspetto ha? Esploriamo alcuni pseudocodici che descrivono l’algoritmo in modo più dettagliato.,
Non siamo interessati al gioco effettivo del gioco, solo all’algoritmo per determinare le mosse, quindi iniziamo da lì:
Come prima, questo ci porta al punto in cui stiamo simulando ciascuna delle possibili mosse dal tabellone iniziale e restituendo quella che segna il miglior punteggio. Questo ci lascia con la necessità di generare punteggi per le tavole appena simulate.
Abbiamo aggiunto un limite di profondità in modo da poter interrompere l’elaborazione dopo un po’., Perché stiamo lavorando con un algoritmo ricorsivo, abbiamo bisogno di un modo per fermare, altrimenti eseguire potenzialmente per sempre:
Questo ci dà la nostra ricorsione, la simulazione di fuori di ogni possibile umana e computer muoversi per un certo numero di passi e decidere quale l’essere umano si muove dare il miglior risultato possibile.
L’unica cosa che rimane è quello di elaborare un punteggio finale per una determinata posizione di bordo. Non esiste un algoritmo perfetto per questo, e diversi fattori daranno risultati diversi.,
Ottimizzazione delle prestazioni
Finora abbiamo un algoritmo che tenterà di risolvere il gioco, ma non è così efficiente come potrebbe essere. A causa della natura casuale del gioco, è impossibile avere un risolutore perfettamente ottimizzato – ci sarà sempre un certo livello di ripetizione semplicemente a causa della natura del processo.
Possiamo almeno fare del nostro meglio per ridurre il lavoro che non abbiamo bisogno di fare però.,
Stiamo già facendo un po ‘ di ottimizzazione nell’algoritmo di cui sopra non elaborando mosse che non hanno alcun impatto sul gioco. Ci sono altri modi che possiamo ridurre il lavoro da fare, però, come il monitoraggio della probabilità cumulativa di mosse, e fermarsi quando che diventa troppo bassa. Questo ha il rischio di rimuovere la soluzione perfetta, ma se la probabilità è così bassa, allora quasi certamente non accadrà comunque.
Possiamo anche determinare dinamicamente il limite di profondità con cui lavorare., Il nostro pseudocodice sopra ha un limite hard-coded di 3, ma potremmo calcolarlo dinamicamente in base alla forma della tavola all’inizio dei nostri calcoli, ad esempio impostandolo sul numero di quadrati vuoti o sul numero di tessere distinte sulla tavola. Ciò significherebbe che attraversiamo meno mosse da schede che hanno meno possibilità di espansione.
Inoltre, poiché è possibile rivedere più volte le stesse posizioni della scheda, possiamo ricordarle e memorizzare nella cache il punteggio per quelle posizioni invece di ricalcolarle ogni volta., Potenzialmente possiamo generare ogni possibile posizione di bordo prima del tempo, ma ci sono un numero enorme di questi – 281,474,976,710,656 diverse possibili posizioni di bordo utilizzando piastrelle fino a 2048 – quindi questo probabilmente non è fattibile.
Tuttavia, l’ottimizzazione più importante che possiamo fare è regolare l’algoritmo per la generazione di punteggi di bordo. Questo funziona per decidere quanto è buono il consiglio per continuare a giocare e i fattori e le ponderazioni che usiamo per questo sono direttamente collegati a quanto bene il nostro algoritmo gioca.,
Conclusione
2048 è un gioco estremamente interessante per tentare di risolvere. Non esiste un modo perfetto per risolverlo, ma possiamo scrivere euristiche che cercheranno i migliori percorsi possibili attraverso il gioco.
Gli stessi principi generali funzionano per qualsiasi gioco a due giocatori-ad esempio, gli scacchi – in cui non è possibile prevedere ciò che l’altro giocatore farà con qualsiasi grado di certezza.
Perché non provare a scrivere un’implementazione di questo e vedere come funziona?