Mizar goes to Turin - writing Mizar 4.0 part 1

english version soon

Nell'ambito della manifestazione "Scaccomatto 2008" la Società Scacchistica Torinese ospita la Chess Computer Cup 2008 a cui Mizar parteciperà. E' stata l'occasione per mettere di nuovo mano sul codice del programma, revisionandolo. Avevo già pronta una nuova versione, ma a causa del furto del portatile ho praticamente perso tutto e ho dovuto ricominciare da capo. Non tutto il male viene per nuocere, memore della passata esperienza ho potuto fare un'analisi preliminare del programma creandomi uno scheduling per il lavoro. Certo non sono ancora riuscito, come mi ha consigliato un amico, ad implementare il comando "gioca la mossa migliore" e nemmeno "gioca una mossa che faccia confondere il tuo avversario", ma ci sto lavorando! Ho iniziato, questa volta, dalla funzione di valutazione statica. Ho cercato di renderla più snella e veloce. Dal punto di vista teorico le aree che voglio coprire sono:

1. La sicurezza del re
2. La correlazione di materiale
3. la struttura pedonale

Nei precedenti programmi mi affidavo a delle euristiche che per numero e complessità rendevano il programma ingestibile e sospetto mal si coordinassero. Questa volta ho cercato di creare un modello semplificato e trovare degli indici facilmente calcolabili che mi diano una metrica approssimata per gli ambiti di conoscenza che voglio coprire. Ho cercato di rendere la funzione continua e progressiva. I pochi parametri saranno poi ottimizzati da un meccanismo di auto-ottimizzazione (autotuning) che sto mettendo a punto da qualche tempo. Ispirandomi al sistema di learning di Deep Thought ho raccolto un considerevole numero di posizioni di partite magistrali con relativa mossa migliore e/o da scartare. Per ogni posizione tengo traccia della valutazione che da il mio programma della mossa in questione, calcolando la distanza tra la questa e la prima (quella che poi verrà giocata); l'idea è quella di minimizzare tramite un algoritmo di gradient descent la funzione somma di queste distanze. Minore è l'indice, maggiore la corrispondenza con le mosse magistrali. Per evitare un problema di sovradattamento al campione (il programma diventa si bravo a risolvere le posizione, ma solo quelle!) sto usando un grosso numero di posizioni (oltre 6000) e tengo traccia delle varie iterazioni dell'algoritmo. Organizzando un torneo tra i vari programmi con differenti parametri sceglierò il migliore: il problema è ovviamente il numero di partite necessarie per avere risultati statisticamente validi (vedi il post How to test a chess engine). Mizar, all'interno della funzione di valutazione calcola:

1. Il materiale presente sulla scacchiera: con bonus per la coppia di Alfieri su caselle di colore opposto, correzioni al valore dei Cavalli e delle Torri ispirate all'articolo di Kaufman (ora nel team di Rybka) e dei bonus per evitare i "bad trades" (cavallo per tre pedoni)
2. I pedoni passati vengono premiati in funzione della distanza dalla casa di promozione e dal fatto che siano o meno protetti
3. I pedoni deboli (doppiati, isolati, arretrati) vengono penallizati progressivamente in funzione del fatto che siano solo una debolezza o siano anche bloccati e quindi attaccati
4. Per i cavalli, gli alfieri e le torri vengono calcolate diverse mobilità pesate, nel computo totale, con diversi parametri
5. Per ogni pezzo viene attribuito un valore funzione della sua posizione e della posizione dei due re. Invogliano così i pedoni centrali e le torri ad avanzare, i cavalli, gli alfiri e la regina a centralizzarsi. Viene poi calcolato un valore funzione della distanza tra il pezzo e i due re. Per i cavalli viene usata una tabella precalcolata, per Torri e Alfiere è usata la Distanza Manhattan, per Re e Regina la Distanza Chebyshev.
6. La sicurezza del Re è calcolata contando gli attacchi delle caselle attorno al Re.

Una funzione di questo tipo ha reso necessario l'uso di tabelle di attacco: grandi matrici in cui è memorizzato per ogni casella quale pezzo sta attaccando la casella in questione. Pe5r ottimizzare il tutto, considerando che in Mizar la funzione di valutazione è chiamata solo duramnte la quiescenza ho pensato bene di riscrivere il generatore di catture per sfruttare i dati presenti nelle tavole. Il debug del nuovo generatore e la parziale riscrittura di quello generale ha reso necessaria l'implementazione del nuovo comando divide che per ogni mossa alla radice ritorna il numero di nodi sottostanti. Insieme al perft, il divide si è rivelato un ottimo strumento di correzione. Sul sito (che verrà aggiornato dopo il torneo) troverete presto le posizione utilizzate e i valori calcolati, utili come riferimento. Ho scritto anche una piccola routine per il calcolo di numeri casuali con distanza di Hamming prefissata, attualmente funziona solo su Windows Xp o Vista dato che utilizza le nuove API crittografiche, Mizar ha infatti un nuovo set di numeri di Zobrist a 64 bit con distanza minima 24 e distanza minima 10 nella parte a 32 bit usata nella cache della funzione di valutazione. I risultati avuti usando la rand() della libreria C sono stati tragicomici e meriterebbero un post a parte. L'algoritmo di ottimizzazione è stato eseguito solo dopo avere implementato tutte le tecniche di pruning statico e dinamico di cui parlerò nel prossimo post. Torno a programmare!