Un passo-passo guida per la compilazione di un semplice scacchi AI

da Lauri Hartikka

esploriamo alcuni concetti di base che ci aiuterà a creare un semplice scacchi AI:

sposta generazione
scheda di valutazione
minimax
alpha e beta di potatura.

Ad ogni passo, miglioreremo il nostro algoritmo con una di queste tecniche di programmazione degli scacchi testate nel tempo. Dimostrerò come ognuno influenza lo stile di gioco dell’algoritmo.

È possibile visualizzare l’algoritmo AI finale qui su GitHub.

Passo 1: Generazione di mosse e visualizzazione della tavola

Useremo gli scacchi.libreria js per la generazione di mosse e scacchiera.js per visualizzare la scheda. La libreria move generation implementa fondamentalmente tutte le regole degli scacchi. Sulla base di questo, possiamo calcolare tutte le mosse legali per un determinato stato del consiglio.

Visualizzazione della funzione di generazione dei movimenti. La posizione di partenza viene utilizzata come input e l’output è tutte le possibili mosse da quella posizione.

L’utilizzo di queste librerie ci aiuterà a concentrarci solo sul compito più interessante: creare l’algoritmo che trova la mossa migliore.

Inizieremo creando una funzione che restituisce solo una mossa casuale da tutte le mosse possibili:

Anche se questo algoritmo non è un giocatore di scacchi molto solido, è un buon punto di partenza, in quanto possiamo effettivamente giocare contro di esso:

Black riproduce mosse casuali. Riproducibile su https://jsfiddle.net/lhartikk/m14epfwb/4

Passo 2 : Valutazione della posizione

Ora proviamo a capire quale lato è più forte in una certa posizione. Il modo più semplice per raggiungere questo obiettivo è quello di contare la forza relativa dei pezzi sulla scacchiera utilizzando la seguente tabella:

Con la funzione di valutazione, siamo in grado di creare un algoritmo che sceglie la mossa che dà il massimo di valutazione:

L’unico miglioramento tangibile che il nostro algoritmo ora catturare un pezzo, se è possibile.

Il nero gioca con l’aiuto della semplice funzione di valutazione. Giocabile su https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Passo 3: Albero di ricerca utilizzando Minimax

Successivamente creeremo un albero di ricerca da cui l’algoritmo può scegliere la mossa migliore. Questo viene fatto utilizzando l’algoritmo Minimax.

In questo algoritmo, l’albero ricorsivo di tutte le possibili mosse viene esplorato a una data profondità e la posizione viene valutata alle “foglie” finali dell’albero.

Successivamente, restituiamo il valore più piccolo o il più grande del bambino al nodo genitore, a seconda che si tratti di un bianco o di un nero da spostare. (Cioè, cerchiamo di minimizzare o massimizzare il risultato ad ogni livello.)

Una visualizzazione dell’algoritmo minimax in una posizione artificiale. La mossa migliore per il bianco è b2-c3, perché possiamo garantire che possiamo arrivare a una posizione in cui la valutazione è -50

Con minimax in atto, il nostro algoritmo sta iniziando a capire alcune tattiche di base degli scacchi:

Minimax con livello di profondità 2. Giocabile su: https://jsfiddle.net/k96eoq0q/1/

L’efficacia dell’algoritmo minimax è fortemente basata sulla profondità di ricerca che possiamo raggiungere. Questo è qualcosa che miglioreremo nel passaggio successivo.

Punto 4: Potatura alfa-beta

La potatura alfa-beta è un metodo di ottimizzazione dell’algoritmo minimax che ci consente di ignorare alcuni rami nell’albero di ricerca. Questo ci aiuta a valutare l’albero di ricerca minimax molto più in profondità, mentre si utilizzano le stesse risorse.

La potatura alfa-beta si basa sulla situazione in cui possiamo interrompere la valutazione di una parte dell’albero di ricerca se troviamo una mossa che porta a una situazione peggiore di una mossa precedentemente scoperta.

La potatura alfa-beta non influenza il risultato dell’algoritmo minimax — lo rende solo più veloce.

L’algoritmo alfa-beta è anche più efficiente se ci capita di visitare prima quei percorsi che portano a buone mosse.

Le posizioni che non abbiamo bisogno di esplorare se viene utilizzata la potatura alfa-beta e l’albero viene visitato nell’ordine descritto.

Con alpha-beta, otteniamo una spinta significativa all’algoritmo minimax, come mostrato nel seguente esempio:

Il numero di posizioni che sono necessarie per valutare se vogliamo eseguire una ricerca con profondità di 4 e la posizione “root” è quella che viene mostrata.

Segui questo link per provare la versione migliorata alpha-beta dell’IA degli scacchi.

Passo 5: Funzione di valutazione migliorata

La funzione di valutazione iniziale è abbastanza ingenua in quanto contiamo solo il materiale che si trova sulla scheda. Per migliorare questo, aggiungiamo alla valutazione un fattore che tiene conto della posizione dei pezzi. Ad esempio, un cavaliere al centro del tabellone è migliore (perché ha più opzioni ed è quindi più attivo) di un cavaliere sul bordo del tabellone.

Useremo una versione leggermente modificata di tabelle quadrate che sono originariamente descritte nel chess-programming-wiki.

Il pezzo visualizzato-tabelle quadrate visualizzati. Possiamo diminuire o aumentare la valutazione, a seconda della posizione del pezzo.

Con il seguente miglioramento, iniziamo ad ottenere un algoritmo che gioca alcuni scacchi “decenti”, almeno dal punto di vista di un giocatore occasionale:

Valutazione migliorata e potatura alfa-beta con profondità di ricerca di 3. Giocabile su https://jsfiddle.net/q76uzxwe/1/

Conclusioni

La forza di un semplice algoritmo di gioco degli scacchi è che non commette errori stupidi. Detto questo, manca ancora la comprensione strategica.

Con i metodi che ho introdotto qui, siamo stati in grado di programmare un algoritmo di gioco degli scacchi che può giocare a scacchi di base. La “parte AI” (esclusa la generazione di movimenti) dell’algoritmo finale è di sole 200 righe di codice, il che significa che i concetti di base sono abbastanza semplici da implementare. È possibile controllare la versione finale è su GitHub.

Alcuni ulteriori miglioramenti che potremmo apportare all’algoritmo sarebbero ad esempio:

move-ordering
faster move generation
e end-game specific evaluation.

KGSAU