Scaccomatto 2008
Se date un'occhiata alle pagine 8 e 10 ecco quello che è successo a Torino qualche mese fa... tra l'altro in qualche foto mi si intravede!
Scaccomatto08
Le migliori canzoni di Bobby Solo
17 ore fa
Visualizzazione post con etichetta Computer chess. Mostra tutti i post
Visualizzazione post con etichetta Computer chess. Mostra tutti i post
lunedì 25 maggio 2009
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:
- La sicurezza del re
- La correlazione di materiale
- 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:
- 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)
- I pedoni passati vengono premiati in funzione della distanza dalla casa di promozione e dal fatto che siano o meno protetti
- 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
- Per i cavalli, gli alfieri e le torri vengono calcolate diverse mobilità pesate, nel computo totale, con diversi parametri
- 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.
- 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!
martedì 25 dicembre 2007
mercoledì 22 agosto 2007
How to test a chess engine?
[Update: you can find a new version of this post on www.mizarchessengine.com ]
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
mercoledì 27 giugno 2007
Writing a chess engine 5: moves generation (part 1)
You have chosen a board representation: now it's time to write the move generation function, maybe the most difficult task and main source of bugs (with makemove function); obviously the way to generate moves is different according to the board representation you have chosen. For us a move is legal when, after you play it, your king isn't in check. So a "legal moves generator" generates only legal moves; a "pseudo legal moves generator" generates all moves available. Why? Speed! To control if a move is a legal move is a "time consuming" task; so it is a good idea to delay this control until the move is played effectively. A pseudo legal moves generator generates moves as fast is possible, later in "make move function" we control if a move is a legal one; if it is legal we go ahead, if it isn't legal we must "undo" the move and try another move. We will write a pseudo legal moves generator. So why i'm talking about a legal moves generator? Because there are situation in which is more simple to write a legal generator! If your king is in check you can only: It is more simple and more fast to write a legal "check escaping"moves generator and not to make legality test in "makemove" instead using the pseudo-legal generator and to have a lot of "failed legality test" and "undo". Strong chess engines have at least two kind of moves generator: I suggest to write first a pseudo-legal moves generator and to debug it; then when your chess engine is finished and "bug free" you can improve it writing a "check evasion generator". You'll be able to use pseudo-legal moves generator to debug the legal one and you'll know that if there is a bug, it is coming from legal generator. We know that a chess programs consider chess moves as a game tree. In theory, they examine all moves, then all counter-moves to those moves, then all moves countering them, and so on, where each individual move by one player is called a "ply". This evaluation continues until it reaches a final "leaf" position which is evaluated. We will talk later about search, but now you must know only that it is possible (indeed it is favorable) that a chess engines doesn't examine all moves to find a good one. To help a chess engine to do this it is very, very important to ordering them in some way; from the most dangerous to the less dangerous. In the early day of "Computer Chess" computers were not so powerful to generate and search all moves at every ply; so old chess engines used a "selective generator" that generated only some moves to search. Today this kind of moves generator are used by shogi engine or by go engine. Today we have the power to generate and search all moves: but as you know there is the possibility that a chess engines doesn't examine all moves to find a good one. It is a waste of time to generate all moves just to find out that the first one is the only that we need. There are various strategies about how many moves a (pseudo-legal) moves generator can generate. We can distinguish: To write an all-moves is simpler than to write a "capture / no capture". To write a "capture / no capture" is simpler than to write an incremental generator. You must pay attention that according to your board representation, writing a "capture / no capture" or an incremental can be useless. For array-based board i think that an all moves is a good choice, for bitboard based "capture/no capture" is a best choice (it is more simple to generate only capture move or non capture). I think incremental is an optimum, but i never used this kind of generator (Fruit uses this). The only way is to test every generator and to chose the best (you can think that it is obvious, but believe me a lot of people don't do test)! I suggest to write a simple all-moves pseudo legal generator and a capture only pseudo legal generator (useful in quiescence search, we will talk about quiescence later): Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website! (to be continued...)
We can distinguish two kind of move generator:
mercoledì 4 aprile 2007
Writing a chess engine 4: To write a F.E.N. parser
Now you have choosen a way to store in memory a chess position, but you need a way to test it! You'll need a way to insert simply a chess position in your engine too: you need a FEN parser!
What does FEN means? FEN is "Forsyth-Edwards Notation"; it is a standard for describing chess positions using the ASCII character set. A single FEN record uses one text line of variable length composed of six datafields. A text file composed exclusively of FEN data records should have a file namewith the suffix ".fen".
Why we need FEN? Having a standard position notation is particularly important for chessprogrammers as it allows them to share position databases. For example, there exist standard position notation databases with many of the classical benchmark tests for chess playing programs, and by using a common position notation format many hours of tedious data entry can be saved. I think it is useful write a parser that transform a FEN string into an intermediate chess position data structure, then you can map this data struct into your own data struct: in this way if you change you data struct you haven't to change this code. An example of data struct can be:
typedef struct {
char piece[64]; /*pezzo*/
char col[64]; /*colore*/
char side; /*tratto*/
unsigned char castle; /*arrocco*/
char enp; /*en passant*/
char ply; /*ply*/
char nm; /*numero mosse*/
}FEN_POSITION;
char piece[64]; /*pezzo*/
char col[64]; /*colore*/
char side; /*tratto*/
unsigned char castle; /*arrocco*/
char enp; /*en passant*/
char ply; /*ply*/
char nm; /*numero mosse*/
}FEN_POSITION;
A FEN string has six fields. Each field is composed only of non-blankprinting ASCII characters. Adjacent fields are separated by a single ASCIIspace character. This is the FEN string of starting position:
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Data Field 1: Piece placement data
The first field represents the placement of the pieces on the board. The board contents are specified starting with the eighth rank and ending with the firstrank. For each rank, the squares are specified from file a to file h. Whitepieces are identified by uppercase SAN piece letters ("PNBRQK") and blackpieces are identified by lowercase SAN piece letters ("pnbrqk"). Empty squares are represented by the digits one through eight; the digit used represents thecount of contiguous empty squares along a rank. A solidus character "/" is used to separate data of adjacent ranks.
Data Field 2: Active color
The second field represents the active color. A lower case "w" is used ifWhite is to move; a lower case "b" is used if Black is the active player.
Data Field 3: Castling availability
The third field represents castling availability. This indicates potentialfuture castling that may of may not be possible at the moment due to blockingpieces or enemy attacks. If there is no castling availability for either side,the single character symbol "-" is used. Otherwise, a combination of from oneto four characters are present. If White has kingside castling availability,the uppercase letter "K" appears. If White has queenside castlingavailability, the uppercase letter "Q" appears. If Black has kingside castlingavailability, the lowercase letter "k" appears. If Black has queensidecastling availability, then the lowercase letter "q" appears. Those letterswhich appear will be ordered first uppercase before lowercase and secondkingside before queenside. There is no white space between the letters.
Data Field 4: En passant target square
The fourth field is the en passant target square. If there is no en passanttarget square then the single character symbol "-" appears. If there is an enpassant target square then is represented by a lowercase file characterimmediately followed by a rank digit. Obviously, the rank digit will be "3"following a white pawn double advance (Black is the active color) or else bethe digit "6" after a black pawn double advance (White being the active color).An en passant target square is given if and only if the last move was a pawnadvance of two squares. Therefore, an en passant target square field may havea square name even if there is no pawn of the opposing side that mayimmediately execute the en passant capture.
Data Field 5: Halfmove clock
The fifth field is a nonnegative integer representing the halfmove clock. Thisnumber is the count of halfmoves (or ply) since the last pawn advance orcapturing move. This value is used for the fifty move draw rule.
Data Field 6: Fullmove number
The sixth and last field is a positive integer that gives the fullmove number.This will have the value "1" for the first move of a game for both White andBlack. It is incremented by one immediately after each move by Black.
This code transforms a fen string filling FEN_POSITION struct.
(to be continued: moves generator)
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
venerdì 2 marzo 2007
Computer chess e Wikipedia
Mi hanno detto di avere visto il mio nome su Wikipedia; pensavo ad uno scherzo, invece è vero: sono su wikipedia! Qualche anno fa mi venne l'idea di scrivere un programma che giocasse a scacchi, cercando su Internet scoprii che vi era una numerosa comunità di appassionati in Italia e nel mondo. Scrissi il mio primo programma, di nome Gargamella, ed ebbi così l'opportunità di partecipare a competizioni nazionali e conoscere molte persone. Oggi il mio ultimo programma si chiama Mizar, è gratuito e fornito di sorgenti.
Di tanto in tanto vorrei postare qui articoli sulla computer chess, principalmente vorrei fare qualcosa per coloro che vogliono scrivere un proprio programma, ma prima di tutto devo ristrutturare il sito di Mizar.
sabato 3 febbraio 2007
Writing a chess engine 3: board representations
[Update: you can find a new version of this post on mizarchessengine.com ]
[...]
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
To be continued (next FEN notation)
[...]
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
venerdì 2 febbraio 2007
Writing a chess engine 2: chess engine's anatomy
[Update: you can find a new version of this post on mizarchessengine.com ]
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
giovedì 1 febbraio 2007
Writing a chess engine 1: to choose a programming language
Some people mail me to ask how to write a chess engine. So i thought to write some columns to help them. From today i'm going to write a short description about writing a simple chess engine. First of all: English isn't my first language, so if you find mistakes, please sorry and mail me: i'll fix them.
In this column we'll talking about which is the best programming language to write a chess engine. The answer is simple: "The one you know best!". There are engines written in C++, C, Java, Delphi/Pascal, Visual Basic, Assembly...
Mizar is written in C.
From the web you can download a lot of source code and a lot of free compilers or IDE.
About C/C++ i suggest:
Code::Block it is a good IDE and works with a lot of free compiler
Open Watcom is the free release of the old good compiler (work with Code Block)
Digital Mars is a free compiler (work with Code Block)
MinGW it is a "GCC for Windows"
Visual C++ Express 2005 is fast, is free, i think it is the best
Update: now you can download Visual Studio 2008 Express
After that i suggest to use program like CVS to implement revision control.
Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website
To be continued... (next chess engine anatomy)
Iscriviti a:
Post (Atom)
