Naraku è un programma di scacchi che iniziai nel lontano 2009, e che portai avanti per circa 2 anni come progetto hobbistico per imparare il C, che all’epoca ritenevo potesse essere una buona aggiunta alle mie skill per il lavoro di ingegnere chimico. È basato su vari algoritmi che all’epoca apparivano freeware o pubblici (in parte anche sul controverso programma freeware Ippolit). La sua forza di gioco è stimata intorno ai 2700-2750 elo su un normale notebook moderno. Non ho più i sorgenti del programma da tempo, ma posso riassumere qui le caratteristiche principali:
- Come la stragrande maggioranza dei motori, è caratterizzato da algoritmo Negamax (variante del Minimax), con potatura alfa-beta.
- Utilizza diverse euristiche di taglio, quali per esempio Null move pruning, Late move reduction, aspiration windows, futility, e history pruning.
- Nelle ultime versioni implementai l’uso di bitboard, seppure in maniera parziale e probabilmente con qualche bug.
- Nelle prime versioni utilizzava una valutazione della posizione a tre step (opening, mid, endgame), ridotta poi a due visto che risultava più debole di una versione a due fasi.
- La funzione di valutazione consisteva nel calcolo dei pezzi materiali, tabelle PST, mobilità, king safety, oltre a numerosi termini posizionali (bishop pair, pedoni passati e protetti, torre su settima traversa ecc ecc) e tabelle dei principali finali integrate.
- Il programma disponeva della possibilità di ridurre la forza di gioco fino a circa 1000 elo, attraverso modifiche dei pesi, poisoning degli stessi, disattivazione di alcune funzioni.
Per il tuning dei pesi della funzione di valutazione avevo sviluppato un mio tool apposito che convergeva i pesi tramite un algoritmo di tipo evolutivo, che chiamai ironicamente Highlander (“ne resterà soltanto uno”).
Highlander, l’algoritmo di tuning
A grandi linee l’algoritmo funzionava in questo modo: faceva scontrare decine di varianti di Naraku i cui pesi venivano fatti variare in maniera casuale secondo metodo Montecarlo e per un certo intervallo limite dipendente dal peso (pesi con valori maggiori venivano fatti variare in un intorno più largo), rispetto a quelli del programma “padre”, che ugualmente partecipava allo scontro. Al termine di un grande numero di partite a tempi ultra brevi, il programma che risultava aver ottenuto il punteggio maggiore, passava alla generazione successiva. Tutti gli altri venivano eliminati (da qui il nome di Highlander). Il programma sopravvissuto generava quindi nuove decine di “figli”, attraverso nuove mutazioni casuali dei termini della funzione di valutazione, in un intorno via via più stretto. Era un algoritmo abbastanza veloce a convergere, rispetto a testare termine per termine con migliaia di partite (grande guadagno in termini di elo in poco tempo), anche se soffriva di alcuni svantaggi, il peggiore dei quali era la tendenza a convergere su dei minimi locali subottimali, che in parte ero riuscito a contrastare variando in modo casuale, alcuni dei pesi e ricominciando il round di test.
Oggi è superato da metodi enormemente più efficienti (Texel’s tuning per esempio), ma ho continuato ad utilizzarlo saltuariamente anche nel mio lavoro di ingegnere chimico in quanto adattabile facilmente anche ad altri ambiti e recentemente sono riuscito ad estenderlo un po’ aggiungendo maggiori possibilità di mutazione tra le varie versioni del programma.
Il nome del programma, Naraku, per chi se lo stesse chiedendo, è tratto dal villain principale del manga Inuyasha di Rumiko Takahashi, serie che in gioventù avevo molto apprezzato. Nel manga Naraku era noto per diventare più forte attraverso continue ricombinazioni e lo sviluppo di nuove emanazioni di se stesso, che ironicamente è proprio quello che succedeva al programma quando applicavo l’algoritmo Highlander.
Di seguito una partita di esempio di Naraku, contro Gnuchess 6.21, 20 secondi per mossa.