Milady, by Yves Lejeail
Milady is a Winboard chess engine written in visual basic .net 2003 language. Further explanations on features, copyright, installation, configuration are given in the readme file.
History :
I started the programme in 2004, December. From December 2004 to April 2005, it had just Min-Max Algorithm, and
worked with his own interface. Then I decided to try the Alpha-Beta pruning algorithm, so I completely re-wrote the engine,
which is now dependent on the Winboard GUI. The versions do not follow a strict rule since I'm not a professionnal programmer ;=).
Version features :
v1.0
In December 2005, the programme has the following features :
Alpha-Beta pruning, with Principal Variation Search
Iterative deepening and aspiration window
Quiescence Search
KillerMove and History Heuristic
Futility pruning at frontier nodes, Extended Futility at pre-frontier nodes, Limited Razoring at pre-pre-frontier nodes
Works in Arena, Winboard, or console mode
Own Opening Book in text format (created manually with Fruit 2.1 , Crafty 19.2, and Prodeo 1.1 analyses)
Can load FEN positions for Mate or Combination tests, performs perf t tests
has several personalities from the most famous chess players (Fisher, Petrossian, Tarrasch,...)
v1.1
In January 2006 :
removed a huge bug in the Alpha-Beta search : the Alpha and Beta parameters were passed by ref and thus modified
during the search. Now the parameters are transmitted recursively by val, and the algorithm can efficiently fail high
or fail low.
removed an other huge bug, this time in Quiescence node sorting and pruning. The programme was pruning good
captures and keeping some bad ones ! The search was very unstable. A bug I have created myself by awkwardness
have improved the speed by profiling using the simple but efficient Nprof programme, helping to find the bottlenecks.
Most of the code have been rewritten (using move_from and move_to features anywhere, removing all the Math.int
and Math.Abs calculations which are very time consuming, simplifying the redundent code, removing the MovePiece
and CapturePiece functions,...)
has several personalities from the most famous chess players (Fisher, Petrossian, Tarrasch,...)
v1.11
In February 2006 :
change move sorting mechanism: now the moves are sorted just during the search (normal and QS), so that the pruning should avoid sorting in
some cases
avoid the capture/recapture and promotions for the killer-moves. This require a deep change in the code (tab_best_move, tab_actuelle_variante,
...) to detect capture/recapture. Still need to remove the winning captures :=)
v1.2
In February 2006 :
change move sorting mechanism: fully avoid the captures in KillerMoves
added bonus for promotions and castling in the move ordering
fixed a bug in the castling right transmission from an iteration to the following (moves being retrieved from a list at depth 1)
removed pruning in Quiescence which causes some blinding effects
avoid to pass the board through subs and functions (board was already a global table!)
v1.5
In March 2006 :
a big improvement here since there are now a MakeMove and UnMakeMove functions, which are both using structures
to describe the move. NPS is a little bit better, since I get rid of the copy of arrays position=> tmp and tmp=> position
to do and undo a move !
v1.6
In March 2006 :
few improvements : the attack tables code has been simplified. The evaluation of the passed pawn should be better
especially when it involves future promotion
History Heuristic completely rewritten. It is now a table (64,64,15) , 15 being the maximum depth of the alpha_beta search,
The table is filled when a Value>best_score, and an other time when a beta cut-off occurs (I found it improves move ordering a lot)
Killer Moves are completely removed
v1.7
In March 2006:
removed all pruning stuff both in Alpha_Beta and in Quiescence search.
Also created a special move for Quiescence (no EP and no castling needed) , as well as a specific
sorting for this kind of move (of course there is no more EP in quiescent generation)
cleaned things in Alpha_Beta and Quiescence. Some tables are power of 2 in order to speed up processor table index acces
v1.72
In April 2006:
bug corrected in the move generation (introduced in v1.71);
the move structures are abandoned, since some integers are sufficiant to MakeMove and UnMakeMove;
evaluation completely rewritten, and now has some cut-offs when the score is very low compared to Alpha, or very far from zero (there
is no need to make a full eval in this case);
time control rewritten, now calculated with the branching factor;
Some code cleaning in all the programme.
v1.80
In May 2006:
Now Milady can build book from pgn files (if well formated like with pgntrim5 with a constant number of moves/line). Present book was made with top players games (presently rated>2700) when they were rated >2500, since 2000 up to 2005. The book is coded using Dictionarybase class, a hashtable which can be strongly typed (with int64 in Milady case);
using the Dictionarybase, Milady can now recognize each position during the search, even during the Alpha-Beta search. The 3 reps can be then detected, and it seems
to work according to game tests. Seems that Milady will have soon a TranspositionTable feature !
Some cleaning of the code modifying local and global variables declarations;
v1.81
In June 2006:
Removing a bug introduced recently (not recognizing the Queen promotion of the opponent!)
Better move ordering due to the add of History Heuristic for the case of beta cut-off when the move is not a capture (a kind of generalized killerMove)
v1.82
In June 2006:
Little rewriting of some subs and functions, in order to have more speed (use of smaller variables, using bytes instead of integers when possible, using return
features...). i.e. Code cleaning, in the move generators, check detection, attack tables,...
v1.85
In June 2006:
Further rewriting of some subs and functions, in order to have more speed (use of smaller variables, using bytes instead of integers when possible, using return
features...). Also, the Struc_Pion function called previously by Eval() is now inside Eval(), dicreasing the function call overhead. Now the NPS increase in some
case, at even depth, up to 100000 in middle game.
v1.86
In July 2006:
Further rewriting of some subs and functions, in order to have more speed (use of smaller variables, using bytes instead of integers when possible, using return
features...). Also, a small improvement in move ordering due to better PV recognition.
The en-passant moves are now taken into account in the book moves, so I hope it will reduce the number of book bugs ;=)
v2.0
In September 2006:
Implementation of Late Move Reduction, seems to work. Some explanations, when we are at a all nodes (i.e. we didn't had cut-of for the first moves),
there is no need to look at full depth for the remaining moves (so they are searched at reduced depth ,d-2, except we are in check, it is a checking move, it is a capture,...)
The list of exceptions could be improved. This is very good, seems to give a +100 elo or like that. In the same time, it is necessary to have an extension when the king of the side to move is in check (i.e. we avoid to enter in quiescence). The branching factor seems to be highly reduced without too much drawbacks.
Now, the maximum depth of search can be increased automatically by the engine (thanks to Redim Preserve feature). Previously the search was limited to depth 16
for Alpha_Beta, and 20 for Quiescence.
Still some bugs in the book (to do)
v2.1
In October 2006:
An integer called Tactic is propagated through the search. If the last 2 previous plies are not considered as tactical,
and the side to move is not in check, then if remaining depth is <= 0 then call Quiescence. Also if there is no tactic at all
the line can be reduce inside LMR. This could be improved by taking into account other moves than castling or
prise
v2.15
In December 2006:
Thanks to Leo Dijksman, a bug is discovered in the result claim not following the winboard protocol !!!.
Increasing the Castle value so that the engine want to castle as soon as possible
v2.21
In September 2007:
Winboard protocol rewritten completely thanks to Olivier and Lars (more stable now though not perfect)
Eval completely rewritten (passed pawn recognized, more elaborate King Safety added)
LMR search simplified (only reduce depth of non capture, non promotion, non passed-pawns,and non threatening moves)
Castle bug removed thanks to Dany (introduced from 2.15!)
v2.22
In September 2007:
Seearch bug removed thanks to Dany (introduced from 2.15!). In the Alpha-Beta
subroutine, I add a Return Beta (instead of exit for) when best_score>Beta, and also
return Alpha_Beta = Alpha (instead of Alpha_Beta=Best_Score) when all the moves
where searched
Still lot of remaining bugs to hunt :-)
v2.25 (not released)
In December 2007:
LMR speed-up for the PV-nodes, when there aresome good moves already found, it seems nice
to allow LMR to speed-up the search. The price is to reduce some good moves, too far in the move list
v2.30
In December 2007:
The depth of reduction is increased in LMR, in some conditions.There are still place for improvements in LMR
v2.40
In October 2008:
Removed the "depth improvements in LMR"
Playing Strength of Milady 1.0:
Milady is not a strong chess engine, since it can only look at ~20000 n/s, and it has usually a branching factor near 10 (!),
unless the line is really forced, so the branching factor decrease to 6. In a 10 minute game, it looks up to depth 5-6 on
a Athlon XP-M 1800 Mhz. The level is approximately between 1400-1800 elo (european, add 200 for US elo) from
all the tests I have done so far in Arena GUI.
Planed improvements :
There is clearly a problem with the branching factors which means I should improve the move ordering. Also,
I should add null move forward pruning or something like that. The evaluation function does not take sufficiently
into account the development of the pieces; that is something not easy to handle.
Acknowledgments :
Links :
Bruce Moreland chess programming tips
Winboard forum (winboard, programming, tournaments,...)