Qui ho raccolto i motori scacchistici che ho creato per diletto. Per chi non ha mai avuto a che fare con questa particolare tipologia di programmi, si tratta di software in grado di analizzare una posizione sulla scacchiera e individuare le mosse più promettenti, valutandone le possibili conseguenze. A differenza di un giocatore umano, un motore scacchistico esplora sistematicamente un gran numero di varianti e utilizza algoritmi e funzioni di valutazione per scegliere la continuazione che ritiene migliore. I motori non sono generalmente programmi completi dotati di una propria interfaccia grafica: vengono caricati all’interno di apposite interfacce, come Arena, che si occupano di mostrare la scacchiera, gestire le partite e comunicare con il motore attraverso protocolli standard, come UCI. In questo modo è possibile utilizzare, confrontare e far giocare tra loro motori diversi, anche se sviluppati da autori differenti.
Indice:
Naraku 1.4
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, 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.
Musashi 1.01
Musashi è il nuovo programma che ho iniziato a sviluppare da qualche mese. È sviluppato completamente in VB.NET (NET 8.0), nativamente a 64 bit. Anch’esso utilizza l’interfaccia UCI. Il nome deriva dal famoso samurai Musashi Miyamoto.
Dai primi test, in base ai test nelle condizioni della mia rating list, ha una forza stimata di circa 2560 Elo, al momento è quindi più debole di Naraku di circa 100-120 elo. Almeno 70-80 elo sono dovuti alla maggiore lentezza del Visual Basic rispetto al C, sui cui si può fare ben poco. Il resto a funzionalità che in Musashi devo ancora implementare. Come obiettivo mi sono dato il voler raggiungere e superare la forza del vecchio programma, restando però in Visual Basic.
Queste le caratteristiche attuali del programma:
- Anche questo è un classico motore con potatura alfa-beta, PVS, internal iterative deepening, funzione di valutazione hand crafted (no NNUE), numerose euristiche di taglio, quiescience search e transposition table.
- Rappresentazione della scacchiera bitboard based con magic bitboards per la generazione di mosse di alfiere e torre e zobrist hashing.
- Ordinamento delle mosse tramite MVV-LVA, killer moves, history heuristic, con SEE per le potatura catture svantaggiose.
- Funzione di valutazione che al momento ha questi termini principali: Calcolo statico dei pezzi, tabelle PST per mediogioco e finali, mobilità dedicata per ogni pezzo, king safety con pawn storm e shelter, bishop pair, knight e bishop outpost, pedoni passati, candidati, appesi, doppiati, isolati e protetti, torre a supporto di pedone passato e torre su colonna aperta e su settima traversa, material imbalance, per il momento alcune euristiche semplificate per la gestione dei finali.
- Funzione di valutazione ottimizzata tramite una evoluzione dell’algoritmo Highlander, che ora è un algoritmo evolutivo più completo. In futuro potrei passare al Texel’s tuning o ad altro (chiaramente se la licenza del Texel tuning dovesse essere compatibile con un programma freeware a codice chiuso).
- Single core, per il momento.
Alcuni chiarimenti:
Perché VB.NET e non altri linguaggi molto più performanti?
Ho scelto di utilizzare VB.NET invece di altri linguaggi di programmazione molto più diffusi e veloci, sia perché Visual Basic è un linguaggio che ho sempre apprezzato molto, ma anche perché lo utilizzo quotidianamente per lavoro. E anche perché non esistono molti programmi di scacchi realizzati in Visual Basic. L’obbiettivo d’altronde non è realizzare un programma da 3700 elo in Visual Basic che vada a sfidare Stockfish, ma vedere fin dove riesco ad arrivare.
Utilizza NNUE?
No, per una mia precisa scelta ho voluto realizzare un programma “vecchio stampo”, con funzione di valutazione sviluppata a mano. È più divertente, e credo che continuerò su questa strada anche in futuro.
Perché a codice chiuso e non su Github?
Preferisco tenerlo closed source per il momento, come fatto per tutti gli altri programmi sul sito, principalmente perché è un progetto personale che preferisco portare avanti nel tempo libero, senza vincoli del dover spiegare il perché di alcune scelte, dover portare avanti un canale github e perché mi darebbe fastidio vedere qualcuno molto più bravo di me in VB.NET, fare un fork del programma e ottenere un motore 500 elo più forte.
È un derivato/clone di Stockfish/Reckless/Ethereal o qualche altro programma?
No, il codice è scritto completamente in VB.NET da zero e utilizza le tecniche che ho descritto sopra, nelle loro definizione più classiche, con (sicuramente) diversi bug e mancate ottimizzazioni. Posso fornire a chi vuole, parte del codice sorgente via email per verifica. Chiaramente motori come Stockfish, Ethereal, Fruit, così come tanti altri, sono fonti di ispirazione, il che non vuol dire che il codice sia copiato. Allego un paio di screenshots di esempio del codice di Musashi:
Utilizza AI?
Nella scrittura del programma principale no, ma sto utilizzando AI nella ricerca e risoluzione di bug, oltre che nell’implementazione dell’algoritmo di tuning. Ritengo AI un ottimo strumento, quando è utilizzato nella ricerca e correzione di bug e d’altronde, ormai è integrata ovunque (in Visual Studio è attiva di default). Di seguito un esempio di codice in VB.NET tratto dalla definizione della Lazy evaluation, in cui ho corretto uno dei tanti bug scovati da AI.
È Naraku riscritto in Visual Basic?
No, anche se alcune tecniche di ricerca e valutazione sono molto simili (essendo standard di ogni motore moderno), i due programmi sono profondamente differenti e lo si può vedere direttamente dalla valutazione delle posizioni. Per esempio, anche se più lento di 2-3 volte, Musashi utilizza, grazie a tecniche più moderne, un pruning molto più aggressivo rispetto a Naraku, il che gli consente di raggiungere, e a volte, superare, la stessa profondità raggiunta da Naraku ricercando appena un terzo dei nodi.
Downloads
Musashi è scaricabile cliccando su questo link: Musashi 1.01.
Qui trovate il changelog in formato txt. Changelog.txt.
Vecchia versione: Musashi 1.0.
Richiede le .NET 8.0. Testato funzionante su Windows 7, Windows 10 e 11, gira perfettamente sotto Arena, cutechess, Scid vs PC, Littleblitzer.
Alcune immagini di esempio:
