Le origini
Nello sviluppo di un programma di scacchi, perlomeno quelli basati su una funzione di valutazione scritta a mano, una delle attività più impegnative è l’ottimizzazione dei pesi della funzione. Per questi tipi di motori, la valutazione di una posizione è determinata da una combinazione di diversi termini: materiale, mobilità, struttura pedonale, sicurezza del re, attività dei pezzi e numerosi altri elementi strategici e posizionali. A ciascun termine sono associati uno o più coefficienti numerici, i cosiddetti pesi, che ne determinavano l’importanza relativa.
La qualità complessiva della funzione di valutazione di un motore scacchistico che utilizza una funzione hand-crafted, dipende in larga misura dall’equilibrio tra questi parametri. Un peso troppo elevato può portare il motore a sopravvalutare un determinato aspetto della posizione, mentre un valore troppo basso rischia di renderlo praticamente irrilevante. Inoltre, i diversi termini non sono necessariamente indipendenti: modificare il peso di un parametro può alterare l’efficacia di altri, rendendo difficile individuare manualmente la combinazione ottimale.
All’epoca in cui sviluppavo il mio primo motore, Naraku, uno degli approcci più immediati consisteva nel modificare progressivamente i singoli parametri, verificando ogni volta il risultato attraverso numerose partite. Si trattava però di un procedimento lungo e poco efficiente, soprattutto quando il numero di pesi da ottimizzare diventava significativo. Ogni modifica richiedeva un nuovo ciclo di test e, una volta individuato un valore apparentemente migliore, era necessario ripetere il procedimento sugli altri parametri, eventualmente tornando sui precedenti per correggere gli effetti delle modifiche successive.
Decisi quindi di sviluppare un tool autonomo che automatizzasse buona parte di questo processo. L’idea che mi venne in mente era relativamente semplice: anziché ottimizzare un parametro alla volta, avrei fatto competere contemporaneamente numerose versioni di Naraku, ciascuna caratterizzata da una diversa combinazione di pesi, lasciando che fossero i risultati delle partite a determinare quale configurazione meritasse di sopravvivere.
Chiamai questo algoritmo, Highlander, dal motto «Ne resterà soltanto uno», tratto dal celebre film dal nome omonimo e interpretato da Sean Connery e Christopher Lambert.
Dal punto di vista della classificazione informatica, Highlander appartiene alla famiglia degli algoritmi evolutivi e, più precisamente, può essere descritto come una strategia evolutiva (1+λ), basata esclusivamente su mutazione e selezione elitista. Questa distinzione è importante: a differenza di un algoritmo genetico classico, che è generalmente più complesso, Highlander non utilizza una popolazione di individui che si riproducono combinando le proprie caratteristiche attraverso crossover. Il processo evolutivo parte da un unico individuo, che genera una serie di varianti mediante mutazioni casuali.
Il principio di funzionamento
Per comprendere il funzionamento di Highlander è utile introdurre brevemente la notazione tipica delle strategie evolutive.
Nella forma (1+λ), il numero 1 rappresenta il singolo individuo di partenza, mentre λ indica il numero di discendenti generati a ogni generazione. Il simbolo «+» indica che, durante la selezione, il genitore compete direttamente con i propri discendenti: il migliore tra tutti diventa il genitore della generazione successiva.
Nel caso di Highlander, l’individuo era semplicemente una determinata versione di Naraku, identificata dalla configurazione dei pesi della sua funzione di valutazione.
L’algoritmo parte da una versione iniziale del programma, che chiamerò padre. Questa rappresenta la configurazione di riferimento e partecipa direttamente alla competizione, insieme a decine di varianti generate automaticamente.
Ogni variante, o figlio, viene ottenuta modificando casualmente uno o più pesi della funzione di valutazione. Le perturbazioni sono generate in maniera stocastica e hanno un’ampiezza variabile in funzione del valore del parametro interessato: in generale, i pesi numericamente più elevati possono subire variazioni più ampie, mentre quelli più piccoli sono modificati all’interno di intervalli più contenuti. Questo accorgimento consente di esplorare lo spazio dei parametri in modo proporzionato alla scala dei valori utilizzati dalla funzione di valutazione, evitando di applicare indiscriminatamente la stessa ampiezza di mutazione a coefficienti molto differenti tra loro.
Una volta generate le varianti, inizia la fase di selezione. Tutte le versioni del programma, compreso il padre, sono messe a confronto attraverso un grande numero di partite giocate a tempi estremamente rapidi. Lo scopo non è tanto ottenere una misura assoluta della forza di gioco di ciascuna variante, quanto stabilire quale configurazione dei pesi produce i risultati migliori rispetto alle altre.
Al termine della competizione viene selezionato un unico superstite: il programma che ha ottenuto il punteggio complessivo più elevato. Tutti gli altri sono eliminati.
Da qui il nome Highlander.
È proprio questo meccanismo a caratterizzare la strategia evolutiva (1+λ): il genitore non viene sostituito automaticamente, ma deve dimostrare di essere inferiore ad almeno uno dei discendenti. Se nessuno dei figli ottiene un risultato migliore, è il programma padre stesso a sopravvivere e a generare la generazione successiva.
Il processo evolutivo
Il programma superstite diventa così il nuovo padre e costituisce il punto di partenza per la generazione successiva.
A partire dai suoi pesi sono nuovamente generate decine di varianti, attraverso nuove mutazioni casuali. Il procedimento viene quindi ripetuto: generazione dei discendenti, competizione, selezione del migliore ed eliminazione di tutti gli altri.
Un aspetto importante dell’algoritmo è la progressiva riduzione dell’ampiezza delle mutazioni.
Nelle prime generazioni, infatti, i pesi possono essere modificati all’interno di intervalli relativamente ampi. L’obiettivo è esplorare una porzione sufficientemente estesa dello spazio delle soluzioni, individuando configurazioni potenzialmente migliori anche se sensibilmente differenti da quella iniziale. Man mano che il processo prosegue, gli intervalli di mutazione sono progressivamente ristretti. Le nuove varianti diventavano quindi sempre più simili al programma padre e le modifiche tendevano a concentrarsi su piccole correzioni dei parametri.
In questo modo Highlander alterna due comportamenti complementari: una prima fase orientata all’esplorazione dello spazio delle soluzioni e una fase successiva maggiormente dedicata alla ricerca di un ottimo locale nelle vicinanze della configurazione migliore individuata fino a quel momento. Il processo viene ripetuto per numerose generazioni, fino a quando le variazioni dei pesi non producono più miglioramenti significativi nei risultati dei test. L’algoritmo è giunto a convergenza.
Dal punto di vista matematico, il meccanismo di selezione può essere rappresentato in maniera relativamente semplice. Indicando con P il programma padre e con C₁, C₂, …, Cλ i suoi λ discendenti, il nuovo padre della generazione successiva è il candidato che ha ottenuto la prestazione migliore:
dove F rappresenta la funzione di merito, determinata empiricamente attraverso i risultati delle partite.
Si tratta quindi di una selezione elitista: la soluzione migliore non viene mai scartata a favore di una peggiore. Questa proprietà garantisce che il risultato osservato non peggiori da una generazione all’altra, almeno in termini di punteggio misurato durante la selezione. Naturalmente, come vedremo, la variabilità statistica delle partite impone alcune considerazioni.
Vantaggi e limiti
Rispetto all’ottimizzazione manuale o alla modifica sequenziale dei singoli parametri, Highlander presenta alcuni vantaggi interessanti.
Il primo è la possibilità di valutare contemporaneamente numerose combinazioni di pesi. Invece di concentrarsi su un singolo coefficiente, l’algoritmo può modificare più termini della funzione di valutazione e misurare direttamente l’effetto complessivo delle variazioni sulla forza di gioco.
Questo approccio è particolarmente utile quando i parametri presentano interazioni reciproche. Un peso, infatti, può risultare poco efficace se considerato isolatamente, ma diventare vantaggioso in presenza di determinati valori degli altri coefficienti. Valutare l’intera configurazione consente quindi di prendere in considerazione anche queste dipendenze, senza doverle necessariamente modellare esplicitamente.
Un secondo vantaggio è la relativa semplicità di implementazione. Non è necessario conoscere la forma analitica della funzione da ottimizzare, calcolarne le derivate o disporre di informazioni preliminari sulle relazioni tra i parametri. E’ sufficiente poter generare una nuova versione del programma e misurarne le prestazioni attraverso una serie di partite.
L’algoritmo, ha inoltre una buona velocità di convergenza, permettendo di ottenere miglioramenti apprezzabili della funzione di valutazione in tempi relativamente contenuti.
Fin qui, i vantaggi. Non mancano, tuttavia, alcuni limiti.
Il problema principale di questo tipo di algoritmi è la tendenza a convergere verso massimi locali, ovvero configurazioni apparentemente ottimali che non corrispondono necessariamente alla migliore soluzione disponibile nell’intero spazio dei parametri.
Una volta individuata una configurazione particolarmente competitiva, le successive generazioni tendono a esplorare una regione sempre più ristretta nelle sue vicinanze. Se il processo è iniziato nella regione sbagliata, diventa difficile allontanarsene. L’algoritmo convergerà verso una soluzione sub-ottimale.
Per contrastare questo problema ho adottato una strategia piuttosto semplice: modificare occasionalmente, in maniera casuale, alcuni dei pesi della configurazione migliore e avviare un nuovo ciclo di test. In sostanza, anziché proseguire la ricerca intorno all’ultimo superstite, l’idea è di perturbare deliberatamente la soluzione. Ho utilizzato questo sistema come punto di partenza per un’ulteriore evoluzione.
Questo accorgimento non garantisce di evitare i massimi locali, ma aumenta la possibilità di esplorare configurazioni differenti e, talvolta, di individuare soluzioni migliori.
Un ulteriore limite, come purtroppo mi accorsi presto, è rappresentato dalla natura statistica della selezione. Le partite a tempi molto rapidi consentono infatti di accumulare velocemente un numero elevato di risultati, ma introducono inevitabilmente una certa variabilità. Una variante può prevalere non soltanto per la qualità effettiva dei suoi pesi, ma anche per una combinazione favorevole di posizioni, aperture o risultati casuali. Per questo motivo è importante disporre di un numero sufficientemente elevato di partite: una popolazione troppo piccola di test può portare a selezionare una variante fortunata anziché realmente più forte.
Dal punto di vista statistico, il punteggio ottenuto in una serie limitata di partite è infatti soltanto una stima della reale forza relativa del programma. Tuttavia, l’utilizzo di Highlander, piuttosto che testare singolarmente ogni peso per un numero comunque notevole di partite, mi ha consentito di ridurre il numero di partite necessarie di diversi ordini di grandezza.
Il confronto con i metodi di tuning moderni
Esistono metodi di ottimizzazione decisamente più sofisticati e, in molti casi, più efficienti per il tuning automatico delle funzioni di valutazione degli engine scacchistici.
Un esempio particolarmente interessante è il Texel’s Tuning Method, proposto da Peter Österlund e utilizzato nel motore Texel.
A differenza di Highlander, che seleziona le configurazioni dei parametri in base ai risultati ottenuti direttamente nelle competizioni tra diverse versioni del programma, Texel’s Tuning utilizza una raccolta di partite per ricavare un insieme di posizioni e confrontare le valutazioni del motore con gli esiti effettivi delle partite.
Il procedimento si basa sulla regressione logistica e sulla minimizzazione di una funzione di errore che mette in relazione la valutazione delle posizioni con la probabilità del relativo risultato. L’ottimizzazione può essere effettuata simultaneamente su un numero molto elevato di parametri, utilizzando tecniche numeriche di ricerca locale e metodi di ottimizzazione più avanzati.
Questo approccio presenta vantaggi notevoli: consente di sfruttare milioni di posizioni ricavate dalle partite già giocate, riduce la necessità di organizzare continuamente tornei tra nuove varianti e permette di ottimizzare numerosi coefficienti in modo strutturato.
Con gli strumenti disponibili oggi, e soprattutto per funzioni di valutazione tradizionali caratterizzate da numerosi parametri, tecniche come Texel’s Tuning rappresentano generalmente una soluzione molto più efficace e sistematica.
Oltre gli scacchi
Nonostante lo avessi concepito specificamente per Naraku, senza avere idea, allora, di cosa fosse un algoritmo evolutivo, Highlander aveva una caratteristica che mi aveva colpito fin dalle prime sperimentazioni: la sua struttura era ed è estremamente generica.
L’algoritmo non richiede infatti alcuna conoscenza specifica del problema da ottimizzare. Gli unici requisiti sono la possibilità di generare varianti di una soluzione iniziale, modificandone alcuni parametri, e la disponibilità di un criterio quantitativo per misurarne le prestazioni. In termini più generali, è sufficiente disporre di una funzione obiettivo, anche complessa o non facilmente derivabile, alla quale sottoporre ogni candidato.
Questa caratteristica mi ha portato a riutilizzare Highlander occasionalmente anche nel mio lavoro di ingegnere chimico, adattandolo a problemi di ottimizzazione differenti da quelli per cui era stato originariamente sviluppato.
In ambito ingegneristico, infatti, capita frequentemente di dover individuare una combinazione ottimale di parametri senza disporre di una relazione analitica semplice tra le variabili di ingresso e il risultato finale. In determinate circostanze, la funzione obiettivo può essere rappresentata da una funzione da regredire, da un modello numerico, o da una procedura di calcolo relativamente complessa.
In questi casi, una strategia evolutiva può risultare interessante proprio perché non necessita di conoscere la struttura matematica interna del problema: deve semplicemente generare nuove configurazioni e confrontarne i risultati.
Recentemente sono tornato a lavorare su Highlander per utilizzarlo nel nuovo motore di scacchi che ho iniziato a sviluppare, Musashi, cercando di migliorarlo ulteriormente.