giovedì 25 dicembre 2008

Natale 2008

Buon Natale!
Merry Christmas!

Read More...

venerdì 19 dicembre 2008

Post-It dicembrino



Trovare un po' di tempo per scrivere un post sulle tue peripezie Torinesi.

Tacere sulla vicenda di quando mi è caduta la chiave magnetica dell'albergo sotto il tavolo di due Gran Maestri che giocavano a Scacchi ripresi dalle telecamere Rai.

Tacere anche su come sei riuscita a recuperarla.

Sentita l'altra sera, un po' scurrile, ma ottima metafora della vita:
tre topi, in un locale, stanno facendo l'happy hour; due ubriachi e uno sobrio
topo ubriaco 1:"A me il mio Padrone... hic!... mi fa una pippa: mi mette il formaggio nella gabbietta... hic!... e io levo il formaggio, me lo mangio e gli tiro la gabbietta addosso! hic!"
topo ubriaco 2:"Ma smettila...hic!...A me il mio Padrone mi fa...hic!... due pippe: mi mette il veleno per topi davanti casa...hic!... io lo raccolgo, chiamo degli amici per organizzare un festino e...hic!... lo sniffiamo alla faccia sua!"
topo sobrio:"Si va bene, siete fortissimi, ma ora andiamo che vi riaccompagno a casa: tra mezz'ora devo incularmi il gatto!"

Evitare di scrivere qualcosa sul caso di Eluana Englaro. Diritto alla vita, diritto alla morte? Esiste una risposta 'corretta'? Non credo. L'unica cosa seria e non strumentale che si dovrebbe fare è legiferare immediatamente sul testamento biologico.

io: "[...] diceva che non riusciva a sfondare non perchè non avesse talento, ma perchè non era raccomandato, così non riuscendo a sfondare qui se ne andò in America dove si aprì uno studio tutto suo, ho saputo che un uragano glielo ha spazzato via e la linea dell'alta tensione che passava lì vicino ha innescato un incendio in cui ha perso tutto"
amico: "insomma Dio gli ha detto: non è cosa tua!"

Sii serio con te stesso: evita di fare propositi per il prossimo anno, tanto sai già che non ne realizzerai nemmeno uno e quello che riuscirai a fare saranno cose assolutamente imprevedibili!

Programmare un viaggio con immersione a Lourdes, però: dopo che la bettola in cui vivevi è stata ristrutturata, il fatto che si sia rotta la colonna degli scarichi fognari inondando di liquami l'appartamento venti minuti prima di ritraslocarvi nuovamente è un segno che non devo sottovalutare.

Evitare di ridere ancora a questa scena: il tuo arrivo a Torino non è stato da meno!

Uscito dalla spirale della pasta fritta, uscito dalla spirale del Bailey's entrato in quella della cioccolata calda con pandoro!

Il nuovo Ricordi è un casino: troppe cose in troppo poco spazio.

Ho letto che fare troppo sesso provoca l'infarto. Sono contento: camperò cent'anni!

Pensare alla frase culto di quest'anno; in pole-position: "Ricordati che il viola è il nuovo nero!"

Read More...

martedì 2 dicembre 2008

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!

Read More...

Related Posts with Thumbnails