GnuChess: un giocatore sequenziale di scacchi
2.4 La scelta della mossa
2.4.2 L’analisi delle continuazioni
2.4.2.3 La scelta della migliore continuazione
L’analisi delle continuazioni del gioco a partire dalla posizione corrente prevede la visita dell’albero di gioco associato e la valutazione dei nodi incontrati su esso.
In GnuChess queste operazioni sono condotte secondo l’euristica di approfondimento iterativo (cfr. 1.3.3.1): la visita dell’albero viene ripetuta più volte, ma ad ogni iterazione la profondità del sottoalbero esplorato viene aumentata di una unità.
La prima visita è condotta fino al primo livello dell’albero; il processo iterativo termina quando è raggiunta la massima profondità di ricerca
(MaxSearchDepth) oppure è scaduto il tempo massimo di ricerca (ResponseTime+ExtraTime). Ad ogni iterazione viene prodotta una nuova valutazione numerica (score) della posizione alla radice e la continuazione principale (PrVar) che ha determinato questo valore.
GnuChess considera affidabile una valutazione che differisce di poco da quelle ottenute nelle iterazioni precedenti. Per misurare il grado di stabilità delle valutazioni ne viene calcolata una media pesata (Zscore(i-1)) con la quale confrontare la valutazione corrente (scorei). Essa è definita così:
Zscorei= 0 se i = 0 Zscore( i - 1)+ scorei 2 se i > 0
dove i è il numero di iterazioni (coincide con la profondità di esplorazione dell’albero).
In GnuChess l’algoritmo di valutazione della posizione corrente scaturisce dalla combinazione del metodo
aspiration-search (cfr. 1.3.2.1) con l’algoritmo di ricerca su alberi di gioco denominato falphabeta (cfr. 1.3.2.2).
2.4.2.3.1 Aspiration-search
La tecnica aspiration-search permette di realizzare la ricerca alpha-beta con una
finestra (alpha,beta) iniziale più stringente della finestra canonica (-∞,+∞) migliorando così l’efficienza della visita.
Non è tuttavia da escludere la possibilità che la ricerca non abbia successo perché il valore della radice (valore minimax) non è contenuto nella finestra iniziale; in tal caso la ricerca deve essere reiterata con una finestra che contiene sicuramente il valore minimax. Quest’ultima sarà della forma (score,+∞) se la prima ricerca ha prodotto un fallimento superiore, mentre sarà (-∞,score) se il fallimento è stato inferiore (score è il valore ritornato dalla prima ricerca). La caratteristica fondamentale del metodo aspiration-search è la determinazione della finestra iniziale. In GnuChess essa è
aggiornata ad ogni iterazione del metodo di approfondimento iterativo sulla base dei valori associati alla radice nelle iterazioni precedenti. In particolare, se alpha e beta sono gli estremi di tale finestra essi sono determinati come in Tab. 2.3:
iterazione alpha beta
i=1 scoreroot-90 scoreroot+90
i>1 if (Zscorei<scorei) Zscorei-Awndw-zwndwi else scorei-Awndw-zwndwi scorei+Bwndw
Tab. 2.3 Determinazione della finestra (alpha, beta)
Nella prima iterazione non si ha alcuna stima del valore minimax della radice e quindi il programma esegue una valutazione statica (scoreroot) della posizione corrente (è la
stessa valutazione statica che sarà operata sui nodi foglia dell’albero di gioco durante la
Questa stima non è sicuramente affidabile perché non tiene nessun conto delle
continuazioni del gioco, ma è soddisfacente se usata come centro di una finestra αβ.
Nelle iterazioni successive, invece, il centro della finestra è fissato dal valore minimax ricavato dall’ultima ricerca. Awndw e Bwndw sono valori costanti che definiscono
l’estensione inferiore e superiore della finestra a partire dal suo centro. Si noti una certa asimmetria nella determinazione dei due estremi. GnuChess sembra infatti intenzionato a voler limitare al minimo la possibilità di un fallimento inferiore. In questo caso, infatti, il tempo massimo di ricerca viene incrementato di 10 volte il tempo inizialmente fissato; ciò non avviene nel caso di fallimento superiore. La ragione di questa scelta è che un fallimento inferiore sta ad indicare una situazione per il giocatore che ha la mossa decisamente peggiore di quanto era stato stimato e quindi deve essere prevista un’analisi molto più in profondità di tutte le possibili continuazioni. Il termine zwndwi tende appunto ad estendere inferiormente la finestra di una quantità
proporzionale alla distanza rispetto al valore 0 delle valutazioni sin qui ottenute10:
zwndwi= 20 + Zscorei 12
Fig. 2.4 mostra schematicamente l’implementazione dei metodi di
approfondimento iterativo e di aspiration-search in GnuChess.
int iterative_deepening(position *p,int MaxSearchDepth) { int score,scoreroot,alpha,beta,zscore,zwndw; scoreroot=scoreposition(p); init_z(&zscore,&zwndw); init_window(&alpha,&beta,scoreroot);
for (d=1;d<MaxSearchDepth && !timeout();d++) { score=falphabeta(p,alpha,beta,d); if (score<alpha) score=falphabeta(p,-9000,score,d); else if (score>beta) score=falphabeta(p,score,9000,d); update_z(&zscore,&zwndw,score); update_window(&alpha,&beta,zscore,zwndw ,score) } return (score);
}
Fig. 2.4 Approfondimento iterativo e aspiration-search in GnuChess
2.4.2.3.2 L’algoritmo di ricerca:
falphabeta
Falphabeta è l’algoritmo di base usato da GnuChess per calcolare il valore minimax della radice dell’albero di gioco.
La sua particolarità è che, fissata la finestra iniziale (alpha,beta), esso determina un limite superiore più stringente (rispetto ai valori alpha o beta) per il valore corretto qualora la ricerca determini un fallimento. Questa informazione è utile perché rende più efficiente la ripetizione della ricerca stabilita da aspiration-search. In Fig. 2.5 è descritta la versione dell’algoritmo falphabeta in GnuChess.
#define mate 9999 #define stalemate -9998
int falphabeta (position *p,int alpha,int beta,int depth) { position *p; int quiet,nmoves,score,best,i; score=evaluate(p,&quiet); if ((score==mate) || (score==stalemate)) /* stato finale */ return (score);
if (!quiet) /* se la posizione è turbolenta*/ extend_depth(&depth); /* la profondità di ricerca aumenta */
if (depth==0)
return (score);
nmoves=movelist(p,&successor);
best=-12000; /* il valore minimax di un nodo è certamente maggiore di -12000 */
if (best>alpha) alpha=best;
for (i=1;(i<=nmoves) && (best<beta);i++;successor++) { makemove(successor); score=-falphabeta(successor,-beta,-alpha,depth-1) undomove(successor); if (score>best) { best=score; if (best>alpha) alpha=best; } } return (best); )
Fig. 2.5 Algoritmo falphabeta in GnuChess
L’ordine di visita dell’albero di gioco è a scandaglio.
Un aspetto interessante di questa visita è che la funzione di valutazione è applicata anche ai nodi interni. La valutazione statica di un nodo, oltre che restituire una stima del suo valore minimax, determina informazioni di carattere generale sullo stato del gioco che saranno utilizzate da alcune delle euristiche
implementate nella ricerca.
2.4.2.3.3 Euristiche per migliorare la
ricerca
GnuChess completa l’algoritmo falphabeta con un certo numero di metodi finalizzati a
migliorare l’affidabilità e l’efficienza della ricerca.
2.4.2.3.3.1 L’estensione della
profondità di visita: la ricerca
quiescente
Il programma implementa un criterio di estensione della profondità nominale di ricerca. La motivazione del metodo è di ottenere una valutazione più affidabile delle posizioni turbolente (instabili) analizzandone continuazioni più lunghe. L’analisi di turbolenza di una posizione utilizza informazioni dedotte al momento dell’esecuzione della mossa che ha portato alla posizione (MakeMove) e durante la valutazione statica di quest’ultima. In questa analisi
GnuChess distingue fra posizioni interne e terminali nell’albero di gioco.
Sia N una posizione posta al livello Ply in una ricerca di profondità nominale Sd. Si supponga in generale che la ricerca nel sottoalbero di N sia già stata estesa e sia D (D≥Sd-Ply) la sua profondità. Sia inoltre S la valutazione statica di N e (α, β) la finestra corrente.
N è instabile se è non terminale e: • il re è in scacco e Ply=D-1 (si intende dare all’avversario un’altra possibilità di scacco)
• c’è una minaccia di promozione da parte dell’avversario
• vi è stata una ricattura nella mossa precedente e α ≤ S ≤β.
Se N è una posizione terminale (Ply≥D), essa è considerata instabile quando: • S ≥α e il re è in scacco
• S ≥α e l’avversario minaccia una promozione
• S ≥α, Ply=Sd+1 e almeno due pezzi del giocatore che ha la mossa sono inchiodati
• S ≤β e l’avversario minaccia lo scacco matto.
In tutti questi casi la profondità del sottoalbero di N viene estesa di una unità divenendo D+1.
Le posizioni terminali per cui non sono verificate le precedenti condizioni di stabilità sono considerate comunque instabili. La ricerca quiescente riguarda però soltanto una porzione del loro sottoalbero: quella in cui i nodi sono generati da mosse di cattura o di promozione.
La ricerca quiescente non può
comunque estendersi di più di 11 mosse oltre la profondità nominale Sd
dell’albero di gioco.