L'algoritmo fondamentale è, nella sua forma più semplice, qualcosa come Negamax - Wikipedia. In parole povere, è così:
- Computa tutte le mosse legali nella posizione corrente.
- Guarda tutte le mosse possibili. Disegna un albero dove la radice è la posizione attuale, e ogni possibile mossa è un ramo che porta ad un altro nodo - queste sono le possibili posizioni successive.
- Prova ogni possibile mossa - immagina di fare quella mossa e calcola la nuova posizione. Ora torna al passo 1 e continua ad espandere l'albero.
Si noterà che questo ci permette di guardare ogni possibile partita di scacchi, ma ci vorrà praticamente un'eternità. Quindi, dobbiamo modificare il passo 1 limitando la profondità ad un certo numero di mosse, D:
- Computa tutte le mosse legali nella posizione corrente. MA se abbiamo già raggiunto la profondità D nell'albero, valuta la posizione corrente. Registra il risultato nell'albero.
Ora sorvolerò sulla parte critica dato che è spiegato bene altrove: ad ogni livello dell'albero prima dei nodi "foglia" terminali di profondità D, guardiamo tutte le valutazioni nella posizione successiva. Assumiamo che chiunque sia il suo turno farà la migliore mossa possibile per lui, quindi registriamo quel punteggio di valutazione (e la migliore mossa da giocare) e lo propaghiamo indietro (ricorsivamente) attraverso l'albero fino alla radice. Il risultato finale di questo è che abbiamo immaginato che in ogni possibile posizione, il giocatore da muovere faccia la migliore mossa possibile (supponendo che possa vedere avanti fino alle valutazioni alla profondità D). La migliore mossa possibile nella posizione originale della radice è la mossa che faresti tu, assumendo che il tuo avversario faccia le migliori mosse possibili. L'algoritmo Negamax è un modo ricorsivo super-elegante per implementare questo algoritmo in poche righe di codice.
Per valutare una posizione e assegnarle un punteggio: si può semplicemente calcolare la quantità di materiale per ogni lato, e assegnare, ad esempio, +4 se il bianco è avanti di un cavallo e un pedone. Si possono anche calcolare i fattori posizionali (sicurezza del re, posizionamento dei pezzi minori, struttura dei pedoni, ecc.) e aggiungerli al punteggio.
Ci sono tonnellate di perfezionamenti all'algoritmo base di Negamax. Il principale è la ricerca alfa-beta, che aiuta ad eliminare i rami dell'albero di gioco che non hanno alcuna utilità. Altri come la ricerca di quiescenza aiutano ad evitare l'"effetto orizzonte", dove un computer fa mosse che sembrano ottime fino alla profondità D ma poi perde una regina, diciamo, alla profondità D+1 (senza una soluzione per l'effetto orizzonte, i computer spesso iniziano ad impazzire dando via pezzi poiché pensano che il gioco finisca alla profondità D). Nella ricerca di quiescenza, l'albero viene esteso quando una posizione è piena di mosse critiche come controlli e catture di re.
Infine, ci sono tonnellate di trucchi per la velocità (hashtables per ricordare le posizioni viste in precedenza; bitboard per un calcolo follemente efficiente delle mosse legali - roba davvero bella e sorprendente qui, con tavole rappresentate usando schemi binari con 1 bit per ciascuna delle 64 caselle, che funziona bene con i moderni processori a 64 bit!; tabelle di endgame che hanno finali per 5 o 6 pezzi completamente precompilati, tabelle di apertura con le migliori mosse selezionate dalla pratica dei grandi maestri, etc etc.)
Se sei un programmatore, è divertente codificare 1) il generatore di mosse legali, e 2) l'algoritmo Negamax, con una semplice funzione di valutazione. Questo è tutto ciò di cui hai bisogno per fare un motore di scacchi di base!
Modifica: AlphaZero è arrivato dopo che ho originariamente risposto a questa domanda. La ricerca ad albero di Monte Carlo e la configurazione di apprendimento di rinforzo profondo è diversa da quella che ho descritto sopra e merita una risposta separata su Quora, anche se le basi della ricerca ad albero sono ancora importanti. Raccomanderei di imparare prima la ricerca tradizionale Negamax/alpha-beta e poi di imparare AlphaZero.