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 :
V3.10
In August 2012:
·
Added
extensions when entering in endings (pawn ending = 3plies, simple endinf = 1 ply);
·
Added
extension for a white pawn on 7th or a black pawn on 2nd
(1 ply). It is limited to endings (material remaining below Queen). Note that
the pawn promotion does not seem to work in the Quiescence
·
Added
a static pruning near the leaves (razoring, futility
pruning, extended futility pruning). Some rooms for improvement since it seems
to work for low depths
V3.02
In May 2012:
·
The
SEE was not really working so I moved back to Quiescence of 3.0;
·
Just
added a condition to reduce Tactic (i.e. extensions) if number of move is
greater than a threshold (corresponding to LMR)
V3.01
In April 2012:
·
Big
change! A SEE (Static Exchange Evaluation) procedure is applied in Quiescente move generation (for captures). If a piece make
a capture,
the move is evaluated by SEE which says if it is
advantageous or not. There is a big time saving with a pruning condition: if Value+SEE<Alpha+Pawn,
there is no chance that the move is interesting
since it can not raise the Value (static evaluation)
above alpha. It works well and is tactically much more
accurate but there are lot of improvements to do now.
NPS increases since there are less quiescent positions which are examined;
·
Killer
Moves re-introduced. Don’t know if it’s better;
·
Rules
for LMR are changed: it depends of the number of moves generated, but also if
the position is tactical or not
·
If
the remaining depth is equal to zero (or below in case of extensions), the
tactical moves are seen like the other moves. So that if a line is very
tactical,
this particularity will vanished smoothly with
lower depth. It seems to speed-up a little bit, with a few disadvantages. I
know there are some huge bugs in
the criteria to decide if a move (and then a whole
line) is tactical, but the programme seems to perform
worse if I try to remove them!
·
The
conditions to enter in Quiescence have been modified. There is a variable which
controles if a line is tactical, by adding fractional
numbers if a move is considered
as tactical.
v2.72
In October2010:
·
Same
as 2.71 with improved move ordering (hanging pieces), no eval
> Beta condition to enter in Nullmove, NullScore<Alpha-c1 for nullmove
threat condition, distance to pawn promotion re-activated for some endings
v2.71
In September 2010:
The versions before 2.71
and after 2.40 seem to be weaker than 2.40. So they have not be
released to the public. They have been thrown away, after monthes
of work.
The 2.71 is simply the 2.40
with two improvements :
·
Now
the Nullmove seem to work (not perfectly though)
v2.40
In October 2008:
·
Removed
the "depth improvements in LMR"
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.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.22
In September 2007:
·
Search
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.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.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.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.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)
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 ;=)
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.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.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.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.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.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 access
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.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.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.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.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.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,...)
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,...)