Scacchi e Intelligenza Artificiale

Scacchi e intelligenza artificiale

Introduzione

Scacchi e intelligenza artificiale costituiscono un incontro naturale: da un lato c’è un gioco antico, fatto di regole precise ma di enorme profondità strategica; dall’altro ci sono gli algoritmi, ossia procedure di calcolo capaci di esplorare una posizione e scegliere una mossa nel modo più efficace possibile.

A prima vista appare tutto semplice ma, in realtà, dietro ogni singola decisione sulla scacchiera si nasconde un problema gigantesco, poiché le combinazioni crescono in modo vertiginoso e, dopo poche mosse, diventano letteralmente miliardi di miliardi.

Per questo un motore scacchistico non può permettersi di analizzare tutto: deve selezionare le mosse, scartarle, restringere il campo. Insomma, deve «potare» i rami dell’albero delle varianti.

L’idea di rappresentare la partita come un albero è molto utile: i nodi corrispondono alle posizioni raggiunte dopo un certo numero di mosse, mentre gli archi indicano le mosse legali che conducono da una posizione alla successiva. Si tratta di una struttura elegante ma anche spietata, perché il numero dei rami cresce a una velocità impressionante.

Qui entra in gioco il lavoro pionieristico di Shannon, che individuò due strategie principali: una più diretta (la «Strategia A»), basata sulla forza bruta, e una più selettiva (la «strategia B»), fondata sulla valutazione euristica delle sole mosse più promettenti. A queste si può affiancare anche una terza direzione, quella delle valutazioni strategiche della posizione, che però in questo contesto non verrà descritta.

Il cuore del problema è capire come un algoritmo possa stabilire le linee di gioco che meritano attenzione. Un primo passo è «l’algoritmo Mini-Max», nato nella teoria dei giochi a somma zero tra due giocatori.

L’idea è molto semplice: ogni giocatore cerca di massimizzare il proprio risultato e, al tempo stesso, di minimizzare il massimo vantaggio che potrebbe ottenere l’avversario. Da qui il nome: minimizzare il massimo. In una formulazione più raffinata, si può assegnare a ciascuna posizione un valore posizionale, tenendo conto che il punto di vista di un giocatore è, per così dire, il riflesso negato di quello dell’altro.

Così ogni nodo della posizione iniziale riceve il valore della foglia corrispondente, con segno opposto, e “bontà” l’algoritmo sceglie la variante che presenta il modulo di più alto.

A rendere questo processo davvero efficiente interviene la «potatura Alpha-Beta», che consente di scartare i rami destinati a non influenzare il risultato finale. È un risparmio enorme di tempo e di risorse, e permette al motore di guardare più in profondità senza perdersi in analisi inutili.

In questo campo ebbe un ruolo importante anche Botvinnik, grande campione del mondo e maestro di generazioni di scacchisti, tra cui Karpov e Kasparov. Le sue idee contribuirono a modellare il modo in cui ancora oggi funzionano molte macchine scacchistiche: privilegiare il guadagno materiale più immediato rispetto alla sola ricerca dello scacco matto, costruire un repertorio di partite di grandi maestri come guida iniziale alla scelta delle mosse e analizzare non un solo albero alla volta, ma più sottoalberi in parallelo, cioè più linee strategiche contemporaneamente.

È anche questo che rende possibile passare da una strategia più grezza ad una più raffinata e selettiva.

Naturalmente, tutto comincia da una base molto concreta: una libreria capace di generare le mosse legali a partire dalla posizione iniziale dei pezzi, nel rispetto delle regole degli scacchi, compresi l'arrocco, la presa al passo e tutte le altre mosse speciali. A questa libreria se ne affianca di solito un’altra, destinata a mostrare graficamente la scacchiera sullo schermo.

È il punto di partenza indispensabile: prima si costruisce il motore che sa muovere correttamente i pezzi, anche in modo casuale, poi si introduce il criterio con cui valutare e scegliere la mossa migliore. Qui entra in scena la seconda fase del progetto: la funzione di valutazione della posizione.

Il motore deve capire, in termini numerici, quale delle due parti stia meglio, se il Bianco o il Nero. Il modo più immediato per farlo consiste nell’assegnare un punteggio ai pezzi: il pedone vale 1, il Cavallo e l’Alfiere 3, la Torre 5, la Donna 9 e il Re un valore enorme, praticamente infinito.

Moltiplicando questi punteggi, ad esempio per 10, si ottiene una scala più comoda: il pedone bianco vale 10, Cavallo e Alfiere 30, la Torre 50, la Donna 90, mentre al Re si assegna un valore molto più alto, come 900 o 1000. I pezzi neri ricevono valori opposti.

In questo modo la posizione può essere letta come un saldo complessivo, e l’algoritmo impara a distinguere le mosse che aumentano il vantaggio da quelle che lo riducono. Sul piano pratico, questo significa che il motore, quando può, cercherà di catturare pezzi avversari, sempre nel rispetto delle regole di movimento e delle mosse speciali, così da massimizzare la differenza di punteggio a proprio favore.

Se invece non esistono catture vantaggiose, allora verrà giocata una mossa casuale. È un punto di partenza semplice, ma già ricco di contenuto. E soprattutto permette di capire come, dietro il linguaggio apparentemente freddo degli algoritmi, ci sia in realtà una logica molto vicina al pensiero scacchistico umano: valutare, scegliere, sacrificare, attaccare, difendersi.

P.S. Il passo successivo consiste nel costruire un algoritmo che dia al motore la possibilità di "discernere" la mossa migliore, tra le tante mosse casuali e le varie catture. In questa fase emerge il concetto di "albero di ricerca" del gioco.

Gli scacchi: un gioco "a somma zero"

Un gioco si definisce "a somma zero" quando la somma algebrica dei "payoff", riguardo all'esito delle mosse scelte da un giocatore, risulta (dopo tali scelte) pari a 0. In pratica, tra due contendenti che giocano ad un gioco a somma zero, se uno di loro vince, l'altro ha perso.

Assegnando, ad esempio, valore 1 al risultato di vittoria, valore 0 ad un esito pari e -1 alla sconfitta, avremo che la somma relativa all'esito finale della partita dovrà essere 0: se un giocatore ha vinto coi pezzi bianchi, l'altro ha perso coi pezzi neri.

Gli scacchi sono un gioco a somma zero, ad "informazione perfetta" (i giocatori conoscono, in ogni istante, tutte le informazioni relative allo stato passato e presente del gioco), deterministico, sequenziale e non cooperativo.

Ai giochi a somma zero che si svolgono tra due contendenti è possibile applicare l'algoritmo di ricerca "Mini-Max", un modello matematico che consente di "minimizzare" (o "massimizzare") la massima perdita possibile (o il minimo guadagno possibile).

I due giocatori dovranno trovarsi in "interazione strategica" tra loro, vale a dire che gli esiti delle loro scelte (le mosse) si influenzeranno a vicenda per cui essi dovranno adottare una strategia tesa a massimizzare il loro payoff, tenendo conto degli opposti obiettivi.

L'algoritmo Mini-Max analizza ricorsivamente l'albero di ricerca, "risalendo" (ossia ripercorrendo a ritroso) l'albero a partire dalle "foglie" (i nodi terminali), in posizioni di "fine gioco", fino ai nodi "radice", corrispondenti alla posizione attuale dei giocatori.

Teoricamente è possibile, in un gioco deterministico ad informazione completa, pervenire ad un risultato finale ben definito ma nel caso degli scacchi, essendo elevato il numero di mosse, un approccio di tipo deterministico è impraticabile.

Dovremo quindi accontentarci di una valutazione approssimativa dei vari "stati" del sistema (ovvero delle varie posizioni dei pezzi sulla scacchiera), attribuendo loro un certo valore e cercando di giungere a quello stato associato al valore più grande. Ovviamente, si dovrà tenere conto degli opposti obiettivi: un giocatore cercherà di giungere ad uno stato che ha la valutazione maggiore mentre l'altro perseguirà l'opposto.

All'aumentare del numero di nodi terminali cresce la "complessità computazionale" dell'algoritmo, sia spaziale che temporale. Ecco perché, come vedremo, si utilizzano altri algoritmi, cosiddetti "euristici", come ad es. la "potatura Alfa-Beta", per ridurre il grado di complessità del modello Mini-Max.

P.S. Sull'argomento riguardante la complessità computazionale di un "algoritmo complicato" dedicherò un paragrafo a parte.

Cos'è un albero di ricerca

Un albero di ricerca è una struttura di dati, utilizzata per risolvere un certo problema, composta da vari "nodi" e vari "rami": i nodi rappresentano gli "stati" del problema (negli scacchi, tali stati corrispondono alle diverse posizioni dei pezzi sulla scacchiera) mentre i rami descrivono le "azioni" (sono, in pratica, le varie mosse effettuate dai 2 giocatori di scacchi) che consentono il passaggio da un nodo all'altro.

Un ramo permette il collegamento tra 2 nodi e un nodo può essere collegato a più nodi, secondo una relazione "gerarchica" tra di essi: a partire da un nodo "radice", che definisce lo stato iniziale del sistema, si diramano, tramite rami, altri nodi (due, nel caso di un albero binario) da cui si generano, attraverso un processo di "espansione", altri nodi e così via.

I nodi generati da un nodo "padre" (o nodo "genitore") si chiamano nodi "figli" (il nodo "radice" è il nodo padre di tutti gli altri nodi figli): una "foglia" è un nodo da cui non si dirama alcun figlio (non ci sono ulteriori espansioni) e l'insieme delle foglie determina la "frontiera" del sistema.

I differenti stati dell'albero definiscono lo "spazio degli stati", mentre un "cammino" è determinato dalla connessione di più nodi, tramite una serie di rami. È possibile che, in certi casi, uno stesso stato possa ripresentarsi più volte: in tali casi, possiamo già apportare un miglioramento all'algoritmo, ignorando gli stati duplicati.

Una struttura di ricerca di questo tipo può esserci di aiuto per l'algoritmo Mini-Max, derivato dal teorema di Von Neumann.

P.S. Per l'analisi parziale dell'albero di ricerca si utilizza la "strategia A" di Shannon, basata sull'esplorazione mediante "forza bruta": si valutano, in pratica, tutte le possibili mosse per ciascuna posizione, fino ad un certo "livello" (chiamato "orizzonte", da cui deriva la denominazione di "effetto orizzonte"). Il livello a cui ci si ferma dipende, ovviamente, dalla potenza elaborativa del computer adottato. Oggi si arriva ad esplorare alberi molto "profondi" nel tempo di pochi secondi.

L'algoritmo Mini-Max

Come abbiamo visto, il giocatore A (chiamato "giocatore Max"), a cui spetta la 1^{^} mossa, sceglierà, tra i vari stati con diverse valutazioni, quello associato alla valutazione più alta, mentre il giocatore B (chiamato "giocatore Min") farà l'opposto, ossia tenderà a scegliere lo stato che ha la valutazione più bassa per il giocatore A.

In situazioni di "conflitto" di questo tipo, il giocatore A considererà quello stato al quale il giocatore B ha assegnato la valutazione meno bassa possibile. In altre parole, il giocatore A cercherà di "minimizzare" il più possibile la valutazione, effettuata da B, di un certo stato (cioè di una data posizione). La stessa cosa farà B, quando toccherà a lui muovere.

Ciò vale non solo per la 1^{^} mossa ma per tutte le altre mosse a vari livelli di profondità, fino a pervenire ad un "livello orizzonte" prestabilito. A questo punto, in base alla funzione di valutazione (che si applica all'ultimo livello di profondità), si dovrà "tornare indietro", ripercorrendo a ritroso il "cammino" che conduce alla migliore valutazione (alla mossa migliore, in pratica) per il giocatore A.

A partire, quindi, dal livello orizzonte si sceglierà lo stato a valutazione più elevata, riguardo alla scelta del giocatore A, oppure quello con valutazione più bassa, riguardo alla scelta del giocatore B, e porteremo tale stato al livello superiore, ignorando tutti gli altri. Si continuerà, in questo modo, fino a raggiungere il livello 0 (il nodo "radice").

Non si tratta, dunque, di scegliere le valutazioni "intermedie" più alte ma quel percorso che ci consente di ottenere il migliore risultato, nell'ipotesi che il nostro avversario faccia la mossa migliore.

La complessità temporale dell'algoritmo Mini-Max (strategia di "tipo A") è esponenziale: O(b^{^}d), in cui b è il fattore di "branching" (la "ramificazione", ovvero il numero medio di "figli" per ciascun nodo) e d (depth) è la profondità dell'albero. La complessità spaziale, invece, è pari a O(b∙d).

P.S. Da notare che più l'albero di ricerca è profondo, più l'algoritmo sarà efficiente. Al contrario di ciò che si potrebbe pensare (e, cioè, che più profondo è l'albero e più difficile è la valutazione degli stati), quegli algoritmi in grado di analizzare nodi più in profondità (che girano su hardware più veloce) battono gli stessi algoritmi che girano su hardware più lento (in grado di analizzare meno nodi).

La "potatura" (o "pruning") Alpha-Beta

L'algoritmo Mini-Max esegue la ricerca completa di tutti i nodi dell'albero, anche se la maggior parte di questi non ha alcuna influenza sulla valutazione della mossa migliore da effettuare.

Si può prevedere, quindi, di "tagliare" quei rami che non influiscono sulla valutazione della radice (ossia della mossa che intendiamo effettuare), riducendo la complessità dell'algoritmo Mini-Max e migliorando le prestazioni (poiché i tempi di esplorazione dell'albero si riducono).

Per ciò che riguarda la complessità computazionale, nel caso peggiore (se non ci sono "potature") essa rimane la stessa del Mini-Max (cioè O(b^{^}d)) ma mediamente, per effetto dei "tagli", essa si riduce a O(sqrt(b^{^}d)), che rappresenta un vantaggio in termini di prestazioni.

Come si procede? All'inizio si persegue una strategia di espansione di tipo "depth-first" (ossia "prima in profondità"), fino al limite dell'orizzonte, in modo da valutare la migliore variante (quella che esprime la mossa da effettuare): si espandono per primi i "figli" di un nodo già espanso (si pensi all'algoritmo di implementazione di una "pila", in cui l'ultimo elemento entrante è il primo ad uscire), fino ad arrivare alle "foglie".

In seguito si utilizzano due variabili, dette "alpha" e "beta", che rappresentano la posizione migliore e la posizione peggiore. Si ha che, in particolare:

• "Alpha" è il minimo punteggio che il giocatore A (il giocatore a cui tocca la mossa) è in grado di raggiungere; inizialmente tale punteggio è -inf ma nei calcoli intermedi rappresenta la peggiore valutazione (cioè la mossa peggiore) per A;
• "Beta" è il massimo punteggio che B è in grado di ottenere; tale punteggio inizialmente è +inf ma nei calcoli intermedi rappresenta la migliore valutazione per B.

È come se, in pratica, ciascun nodo venisse "etichettato" con i valori di "alpha" e di "beta", i quali si aggiornano man mano che l'albero si espande. A questo punto, se si verifica, per un certo nodo, che alpha>beta (il valore di alpha è maggiore di quello di beta), la ricerca si ferma e l'algoritmo passerà ad analizzare un altro sottoalbero. Quel ramo (inclusi quelli che si trovano al di sotto) si può "tagliare".

La complessità computazionale: un'introduzione

Algoritmi di ricerca differenti possono essere eseguiti in tempi diversi, possiamo quindi assumere il "tempo di esecuzione" di un algoritmo come "parametro qualitativo" di riferimento dello stesso, al fine di confrontare i vari algoritmi tra loro e pervenire alla scelta di quello più "efficiente".

Naturalmente non calcoleremo il tempo di esecuzione in secondi, in quanto tale tempo è influenzato da fattori quali l'hardware di un PC, l'architettura del microprocessore, il compilatore, ecc., ma prenderemo in considerazione la "dimensione dei dati".

Cosa significa? In riferimento al "sorgente" di un algoritmo, quindi non all'eseguibile, per ciascuna classe di istruzioni stimeremo "l'ordine di grandezza" di tali istruzioni, tenendo sempre presente la loro dimensione.

Per quanto riguarda, ad esempio, le istruzioni elementari, come l'istruzione di assegnamento di una variabile o le operazioni aritmetiche (la somma, la differenza, ecc.), assegneremo a tali istruzioni un "costo unitario" (ad es., l'istruzione a=5 avrà costo 1). Nel caso di istruzioni non elementari (l'iterazione e la selezione, in particolare), si dovrà considerare la condizione più "sfavorevole", ossia quella in cui è coinvolto il maggior numero