Utilizzo dell'intelligenza artificiale per risolvere il gioco 2048 (codice JAVA)

• 7 aprile 2014
• Vasilis Vryniotis
• . 6 commenti

Ormai la maggior parte di voi ha ascoltato / suonato il 2048 gioco di Gabriele Cirulli. È un gioco da tavolo semplice ma molto avvincente che richiede di combinare i numeri delle celle per raggiungere il numero 2048. Come previsto, la difficoltà del gioco aumenta quando più celle vengono riempite con valori elevati. Personalmente, anche se ho trascorso un bel po 'di tempo a giocare, non sono mai stato in grado di raggiungere il 2048. Quindi la cosa naturale da fare è cercare di sviluppare un risolutore di intelligenza artificiale in JAVA per battere il gioco del 2048. 🙂

In questo articolo parlerò brevemente del mio approccio per la costruzione del Risolutore di Intelligenza Artificiale del Gioco 2048, descriverò l'euristica che ho usato e fornirò il codice completo che è scritto in JAVA. Il codice è open source con licenza GPL v3 e puoi scaricarlo da Github.

Sviluppare il gioco 2048 in JAVA

Il gioco originale è scritto in JavaScript, quindi ho dovuto riscriverlo da zero in JAVA. L'idea principale del gioco è che hai una griglia 4 × 4 con valori Integer, che sono tutti potenze di 2. Le celle con valore zero sono considerate vuote. In ogni momento del gioco puoi spostare i valori verso 4 direzioni su, giù, destra o sinistra. Quando si esegue uno spostamento, tutti i valori della griglia si muovono in quella direzione e si fermano quando raggiungono i bordi della griglia o quando raggiungono un'altra cella con valore diverso da zero. Se quella cella precedente ha lo stesso valore, le due celle vengono unite in una cella con doppio valore. Alla fine di ogni mossa viene aggiunto un valore casuale nel tabellone in una delle celle vuote e il suo valore è 2 con 0.9 probabilità o 4 con 0.1 probabilità. Il gioco termina quando il giocatore riesce a creare una cella con valore 2048 (vittoria) o quando non ci sono altre mosse da fare (perdere).

Nell'implementazione originale del gioco, l'algoritmo move-merge è un po 'complicato perché tiene conto di tutte le direzioni. Una buona semplificazione dell'algoritmo può essere eseguita se fissiamo la direzione verso la quale possiamo combinare i pezzi e ruotare la tavola di conseguenza per eseguire la mossa. Maurizio van der Schee ha recentemente scritto un articolo a riguardo che credo valga la pena di verificare.

Tutte le lezioni sono documentate con commenti Javadoc. Di seguito forniamo una descrizione di alto livello dell'architettura dell'implementazione:

1. Classe del consiglio di amministrazione

La classe del tabellone contiene il codice principale del gioco, che è responsabile dello spostamento dei pezzi, del calcolo del punteggio, della convalida se il gioco è terminato ecc.

2. ActionStatus e Direction Enum

ActionStatus e Direction sono 2 enumerazioni essenziali che memorizzano il risultato di una mossa e la sua direzione di conseguenza.

3. Classe ConsoleGame

ConsoleGame è la classe principale che ci consente di giocare e testare l'accuratezza del Risolutore AI.

4. Classe AIsolver

L'AIsolver è la classe primaria del modulo di Intelligenza Artificiale che è responsabile della valutazione della mossa migliore successiva data una particolare Tavola.

Tecniche di intelligenza artificiale: potatura Minimax vs Alpha-beta

Sono stati pubblicati diversi approcci per risolvere automaticamente questo gioco. Il più notevole è quello sviluppato da Matteo Overlan. Per risolvere il problema ho provato due approcci diversi, usando l'algoritmo Minimax e la potatura Alpha-beta.

Algoritmo di Minimax

I Minimax è un algoritmo ricorsivo che può essere utilizzato per risolvere giochi a somma zero per due giocatori. In ogni stato del gioco associamo un valore. L'algoritmo Minimax cerca nello spazio dei possibili stati di gioco creando un albero che viene espanso fino a raggiungere una particolare profondità predefinita. Una volta raggiunti quegli stati foglia, i loro valori vengono utilizzati per stimare quelli dei nodi intermedi.

L'idea interessante di questo algoritmo è che ogni livello rappresenta il turno di uno dei due giocatori. Per vincere, ogni giocatore deve selezionare la mossa che minimizza la vincita massima dell'avversario. Ecco una bella presentazione video dell'algoritmo minimax:

[Contenuto incorporato]

Di seguito puoi vedere lo pseudocodice dell'algoritmo Minimax:

function minimax (nodo, profondità, giocatore che massimizza)
    if profondità = 0 or nodo è un nodo terminale
        ritorno il valore euristico del nodo
    if maximizingPlayer bestValue: = -∞
        per ciascuno figlio del nodo val: = minimax (child, depth - 1, FALSE)) bestValue: = max (bestValue, val);
        ritorno miglior valore
    altro
        bestValue: = + ∞
        per ciascuno figlio del nodo val: = minimax (figlio, profondità - 1, TRUE)) bestValue: = min (bestValue, val);
        ritorno miglior valore
(* Chiamata iniziale per massimizzare il giocatore *)
minimax (origine, profondità, VERO)

Potatura alfa-beta

I Algoritmo di potatura alfa-beta è un'espansione di minimax, che riduce fortemente (pota) il numero di nodi che dobbiamo valutare / espandere. Per raggiungere questo obiettivo, l'algoritmo stima due valori l'alfa e la beta. Se in un dato nodo la beta è inferiore all'alfa, allora il resto dei sottotitoli può essere eliminato. Ecco una bella presentazione video dell'algoritmo alphabeta:

[Contenuto incorporato]

Di seguito puoi vedere lo pseudocodice dell'algoritmo di potatura Alpha-beta:

function alphabeta (nodo, profondità, α, β, maximizingPlayer)
    if profondità = 0 or nodo è un nodo terminale
        ritorno il valore euristico del nodo
    if massimizzando il giocatore
        per ciascuno figlio del nodo α: = max (α, alfabeta (figlio, profondità - 1, α, β, FALSE))
            if ≤ α
                rompere (* β interruzione *)
        ritorno α
    altro
        per ciascuno figlio del nodo β: = min (β, alfabeta (figlio, profondità - 1, α, β, TRUE))
            if ≤ α
                rompere (* α limite *)
        ritorno β
(* Chiamata iniziale *)
alphabeta (origine, profondità, -∞, + ∞, TRUE)

Come viene utilizzata l'IA per risolvere il Gioco 2048?

Al fine di utilizzare gli algoritmi di cui sopra, dobbiamo prima identificare i due giocatori. Il primo giocatore è la persona che gioca. Il secondo giocatore è il computer che inserisce casualmente i valori nelle celle del tabellone. Ovviamente il primo giocatore cerca di massimizzare il suo punteggio e raggiungere la fusione del 2048. D'altra parte il computer nel gioco originale non è specificamente programmato per bloccare l'utente selezionando la mossa peggiore possibile per lui, ma piuttosto inserisce casualmente i valori nelle celle vuote.

Quindi perché utilizziamo tecniche di intelligenza artificiale che risolvono i giochi a somma zero e che assumono specificamente che entrambi i giocatori scelgano la mossa migliore per loro? La risposta è semplice; nonostante sia solo il primo giocatore a cercare di massimizzare il proprio punteggio, le scelte del computer possono bloccare i progressi e impedire all'utente di completare il gioco. Modellando il comportamento del computer come un giocatore non casuale ortografico, ci assicuriamo che la nostra scelta sia solida indipendentemente da ciò che il computer gioca.

La seconda parte importante è assegnare valori agli stati del gioco. Questo problema è relativamente semplice perché il gioco stesso ci dà un punteggio. Purtroppo cercare di massimizzare il punteggio da solo non è un buon approccio. Uno dei motivi è che la posizione dei valori e il numero di celle vuote sono molto importanti per vincere la partita. Ad esempio, se disperdiamo i grandi valori in celle remote, sarebbe davvero difficile per noi combinarli. Inoltre, se non abbiamo celle vuote disponibili, rischiamo di perdere il gioco in qualsiasi momento.

Per tutti i motivi di cui sopra, diverse euristiche è stato suggerito come la Monotiticità, la scorrevolezza e le Piastrelle libere del tabellone. L'idea principale non è quella di utilizzare il punteggio da solo per valutare ogni stato di gioco, ma piuttosto costruire un punteggio composito euristico che includa i punteggi sopra menzionati.

Infine, dovremmo notare che anche se ho sviluppato un'implementazione dell'algoritmo Minimax, il gran numero di stati possibili rende l'algoritmo molto lento e quindi è necessaria la potatura. Come risultato nell'implementazione di JAVA, utilizzo l'espansione dell'algoritmo di potatura Alpha-beta. Inoltre, a differenza di altre implementazioni, non poto aggressivamente le scelte del computer usando regole arbitrarie, ma invece le prendo in considerazione tutte al fine di trovare la migliore mossa possibile del giocatore.

Sviluppare una funzione di punteggio euristico

Per battere il gioco, ho provato diverse funzioni euristiche. Quello che ho trovato più utile è il seguente:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

La funzione sopra combina il punteggio effettivo della scheda, il numero di celle / tessere vuote e una metrica chiamata punteggio di raggruppamento di cui parleremo più avanti. Vediamo ogni componente in modo più dettagliato:

1. Punteggio effettivo: Per ovvie ragioni, quando calcoliamo il valore di una tavola dobbiamo tener conto del suo punteggio. Le schede con punteggi più alti sono generalmente preferite rispetto alle schede con punteggi più bassi.
2. Numero di celle vuote: Come accennato in precedenza, mantenere poche celle vuote è importante per garantire che non perderemo la partita nelle mosse successive. Gli stati di bordo con più celle vuote sono generalmente preferiti rispetto ad altri con meno. Sorge una domanda su come valuteremmo quelle celle vuote? Nella mia soluzione li appesantisco in base al logaritmo del punteggio effettivo. Ciò ha il seguente effetto: più basso è il punteggio, meno importante è avere molte celle vuote (questo perché all'inizio del gioco combinare le celle è abbastanza facile). Più alto è il punteggio, più importante è garantire che abbiamo celle vuote nel nostro gioco (questo perché alla fine del gioco è più probabile che perda a causa della mancanza di celle vuote.
3. Punteggio di cluster: Usiamo il punteggio del clustering che misura la dispersione dei valori della nostra board. Quando le celle con valori simili sono vicine, sono più facili da combinare, il che significa che è più difficile perdere la partita. In questo caso il punteggio del clustering ha un valore basso. Se i valori del tabellone sono sparsi, questo punteggio ottiene un valore molto grande. Questo punteggio viene sottratto dai due punteggi precedenti e agisce come una penalità che garantisce che saranno preferite le schede raggruppate.

Nell'ultima riga della funzione assicuriamo che il punteggio non sia negativo. Il punteggio dovrebbe essere rigorosamente positivo se il punteggio del board è positivo e zero solo quando il board del punteggio è zero. Le funzioni max e min sono costruite in modo da ottenere questo effetto.

Infine, dovremmo notare che quando il giocatore raggiunge uno stato di gioco terminale e non sono consentite più mosse, non usiamo il punteggio sopra per stimare il valore dello stato. Se la partita viene vinta assegniamo il valore intero più alto possibile, mentre in caso di perdita si assegna il valore non negativo più basso (0 o 1 con logica simile a quella del paragrafo precedente).

Ulteriori informazioni sul punteggio cluster

Come abbiamo detto prima, il punteggio del clustering misura quanto sono sparsi i valori del board e si comporta come una penalità. Ho costruito questo punteggio in modo tale da incorporare suggerimenti / regole da parte degli utenti che "padroneggiano" il gioco. La prima regola suggerita è che si tenta di mantenere vicine le celle con valori simili per combinarle più facilmente. La seconda regola è che le celle di alto valore dovrebbero essere vicine l'una all'altra e non apparire al centro del tabellone ma piuttosto ai lati o agli angoli.

Vediamo come viene stimato il punteggio del clustering. Per ogni cella della scheda stimiamo la somma delle differenze assolute rispetto ai suoi vicini (escluse le celle vuote) e prendiamo la differenza media. Il motivo per cui prendiamo le medie è di evitare di contare più di una volta l'effetto di due celle vicine. Il punteggio totale del clustering è la somma di tutte quelle medie.

Il punteggio cluster ha i seguenti attributi:

1. Ottiene un valore elevato quando i valori della scheda sono sparsi e un valore basso quando le celle con valori simili sono vicine tra loro.
2. Non sovrasta l'effetto di due cellule vicine.
3. Le celle ai margini o agli angoli hanno meno vicini e quindi punteggi più bassi. Di conseguenza, quando i valori alti sono posizionati vicino ai margini o agli angoli, hanno punteggi più piccoli e quindi la penalità è minore.

La precisione dell'algoritmo

Come previsto, l'accuratezza (ovvero la percentuale di giochi vinti) dell'algoritmo dipende fortemente dalla profondità di ricerca che utilizziamo. Maggiore è la profondità della ricerca, maggiore è la precisione e maggiore è il tempo necessario per l'esecuzione. Nei miei test, una ricerca con profondità 3 dura meno di 0.05 secondi ma dà il 20% di possibilità di vincere, una profondità di 5 dura circa 1 secondo ma dà il 40% di possibilità di vittoria e infine una profondità di 7 dura 27-28 secondi e dà circa il 70-80% di possibilità di vincere.

Espansioni future

Per quelli di voi che sono interessati a migliorare il codice qui ci sono alcune cose che puoi esaminare:

1. Migliora la velocità: Migliorare la velocità dell'algoritmo ti consentirà di utilizzare una profondità maggiore e quindi ottenere una migliore precisione.
2. Crea grafica: C'è una buona ragione per cui l'implementazione di Gabriele Cirulli è diventata così famosa. È bello da vedere! Non mi sono preoccupato di sviluppare una GUI, ma piuttosto di stampare i risultati su console, il che rende il gioco più difficile da seguire e da giocare. La creazione di una bella interfaccia grafica è un must.
3. Sintonizza l'euristica: Come accennato in precedenza, diversi utenti hanno suggerito euristiche diverse. Si può sperimentare il modo in cui vengono calcolati i punteggi, i pesi e le caratteristiche della tavola che vengono prese in considerazione. Il mio approccio alla misurazione del punteggio del cluster dovrebbe combinare altri suggerimenti come Monotonicity e Smoothness, ma c'è ancora spazio per miglioramenti.
4. Ottimizzazione della profondità: Si può anche provare a sintonizzare / regolare la profondità della ricerca in base allo stato del gioco. Inoltre puoi usare il Ricerca approfondita approfondita prima approfondita algoritmo che è noto per migliorare l'algoritmo di potatura alfa-beta.

Non dimenticare di scaricare il codice JAVA da Github ed esperimento. Spero vi sia piaciuto questo post! Se lo hai fatto, prenditi un momento per condividere l'articolo su Facebook e Twitter. 🙂