PROG: odd/even score alternance
Remi Coulom
One phenomenon I observed in my chess program when I wrote its first
positionnal evaluation is the odd/even score alternance that occurs.
This especially visible in the opening. Depending on who is on the move
when the leaf nodes are evaluated, the score is different. This can
be observed with Crafty for instance :
(some lines of search output stripped)
Crafty v11.19
White(1): noise 0
noise level set to 0.
White(1): go
clearing transposition table
clearing pawn hash tables
time limit 51.42
depth time score variation (1)
1-> 0.00 0.000 Nf3
2-> 0.00 -0.174 Nf3 Nc6
3-> 0.00 0.000 Nf3 Nc6 Nc3
4-> 0.00 -0.174 Nf3 Nc6 Nc3 Nf6
5-> 1.00 -0.036 e3 Nc6 Bc4 Nf6 Nc3
6-> 2.00 -0.174 e3 e6 Nc3 Nc6 Bc4 Bc5 <HT>
7-> 8.00 0.000 Nf3 d6 Nc3 Nf6 d3 Be6 Bf4
8-> 15.00 -0.068 Nf3 Nf6 e3 e6 Be2 Bd6 o-o o-o
9-> 34.00 0.106 Nf3 Nf6 e3 e6 Be2 Bd6 o-o o-o Nc3
I think that this phenomenon can cause problems if search extensions
and the quiescence search make that leaf nodes are not all evaluated
at the same depth. To solve this problem, I added a factor in the
evaluation function that gave a bonus to the player on the move. By
setting this bonus to 1/2 of the score alternance observed, This gave
the following result for The Crazy Bishop :
00:00:00,00 0 ------ Depth = 1
[...]
00:00:00,06 12 +7 1. d4
00:00:00,06 24 ------ Depth = 2
00:00:00,06 48 +7 1. d4 Nf6
00:00:00,06 86 ------ Depth = 3
00:00:00,06 172 +7 1. d4 Nf6 2. Bf4
00:00:00,06 433 ------ Depth = 4
00:00:00,11 800 +7 1. d4 Nf6 2. Bf4 d5
00:00:00,17 1443 ------ Depth = 5
00:00:00,22 2925 +7 1. d4 Nf6 2. Bf4 d5 3. Nf3
00:00:00,39 5225 ------ Depth = 6
00:00:00,72 10975 +7 1. d4 Nf6 2. Bf4 d5 3. Nf3 Bf5
00:00:01,21 20635 ------ Depth = 7
00:00:03,13 56303 +6 1. d4 d5 2. Bf4 Bf5 3. e3 Nf6 4. Bb5+
00:00:06,54 116694 +7 1. e3
00:00:06,81 121733 +7 1. e3 Nf6 2. d4 d5
00:00:09,56 173314 ------ Depth = 8
Thus removing the annoying alternance. I wonder if this is a really
good idea. It sounds sensible to me but I am not sure it improves
a lot of things. In particular, I wonder if it is good in the middlegame
and in endings. I am going to run a long match between different
versions of TCB to test this idea. My feeling is that it will tend to
favor lines where the evaluation at the leaves of the tree are made
in quiet positions for the side on the move. This sounds sensible also,
but may not work in case of Zugzwang or forced move.
Any opinion ?
Remi
Dan Homan
I'm very new to chess programming (less than 6 months) and my program is
still pretty primitive (e.g. no hash tables, search extensions, etc...),
but I have noticed a similar problem with my program. On odd and even
ply depths it returns quite different scores (a large enough difference
to occasionally cause annoying researches) in certain positions. This
might be the result of a complicated exhange in process or something
else.
As a temporary fix, I've tried to get a better score for the center of
the alpha-beta window than simply using the score from the previous
iteration. I do this by (before the start of the next iteration)
searching one ply from the position at the end of the PV from the previous
iteration. This search is very quick because it is only 30 positions on
average, and seems to return a more accurate score to start the next
iteration.
So far this idea has worked very well in my program. I'm getting
many fewer fail-low results, and in some positions this translates
into searching 40% fewer nodes to get the same result as before.
It isn't perfect and does cause an occasional fail-low or fail-high
that I was not getting before, but on balance it is an improvement for
my program. I'm even thinking of using this idea as a way of
detecting nasty surprises one ply deeper than my search goes - perhaps
to extend the amount of time my program has allotted for that move.
Once I've implemented proper search extensions to handle tactical
combinations better, this approach will probably be unnecessary, but
I was surprised by how much of an improvement I got from 10 minutes
of programming.
---------------------------------------------------------------------
Dan Homan d...@vlbi.astro.brandeis.edu
Physics Department d...@quasar.astro.brandeis.edu
Brandeis University ho...@binah.cc.brandeis.edu
---------------------------------------------------------------------
Robert Hyatt
Remi Coulom (Remi....@ensimag.imag.fr) wrote:
: One phenomenon I observed in my chess program when I wrote its first
: Crafty v11.19
: Any opinion ?
: Remi
Tried it a long time ago. Will try it again. Others have tried other
ideas. For example Tony Scherzer only did odd-ply searches in "BeBe" to
eliminate the even ply stuff and also go for the usually more aggressive
style of odd-ply searches (since the program always gets one extra move
except when there are extensions.)
This is one thing that doomed the mtd(f) tests I ran a couple of weeks
ago, and I'd made a note to try to fudge positional scores with something
like this, although it is not clear exactly how much to fudge, since
sometimes the last PV move is a "developing move" which gets a bigger
bonus than when the last move is a "retreating move."
Robert Hyatt
Dan Homan (d...@vlbi.astro.brandeis.edu) wrote:
: I'm very new to chess programming (less than 6 months) and my program is
: still pretty primitive (e.g. no hash tables, search extensions, etc...),
: but I have noticed a similar problem with my program. On odd and even
: ply depths it returns quite different scores (a large enough difference
: to occasionally cause annoying researches) in certain positions. This
: might be the result of a complicated exhange in process or something
: else.
: As a temporary fix, I've tried to get a better score for the center of
: the alpha-beta window than simply using the score from the previous
: iteration. I do this by (before the start of the next iteration)
: searching one ply from the position at the end of the PV from the previous
: iteration. This search is very quick because it is only 30 positions on
: average, and seems to return a more accurate score to start the next
: iteration.
Richard Greenblatt used this idea in MacHack... but for a different
reason. He found that if you did this to depth=2, and only used the
score if it was worse, it would cure some "horizon effect" deficiencies
in the search. I played with it in the 70's as well. Using it to
"center" the score is a novel use for an old idea, however... and is
certainly worth trying.
: So far this idea has worked very well in my program. I'm getting
: many fewer fail-low results, and in some positions this translates
: into searching 40% fewer nodes to get the same result as before.
: It isn't perfect and does cause an occasional fail-low or fail-high
: that I was not getting before, but on balance it is an improvement for
: my program. I'm even thinking of using this idea as a way of
: detecting nasty surprises one ply deeper than my search goes - perhaps
: to extend the amount of time my program has allotted for that move.
: Once I've implemented proper search extensions to handle tactical
: combinations better, this approach will probably be unnecessary, but
: I was surprised by how much of an improvement I got from 10 minutes
: of programming.
I think you'll find that assumption wrong. Extensions won't stop the
odd/even problem, but they may change the offset from time to time.
IE generally an odd ply search after an even ply search will raise the
score, since the root to move side gets one extra move. With extensions,
this isn't quite a "given" any longer. As a result, your idea might not
work, but only because of incomplete search information when you do your
very shallow search on the end. But don't expect the extensions to get
rid of the even/odd problem... remember your example with Crafty above.
It has lots of extensions and still flip/flops as you saw...
: ---------------------------------------------------------------------
Dan Kirkland
In article <5n6p1d$7...@juniper.cis.uab.edu>,
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>Dan Homan (d...@vlbi.astro.brandeis.edu) wrote:
>
>: I'm very new to chess programming (less than 6 months) and my program is
>: still pretty primitive (e.g. no hash tables, search extensions, etc...),
>: but I have noticed a similar problem with my program. On odd and even
>: ply depths it returns quite different scores (a large enough difference
>: to occasionally cause annoying researches) in certain positions. This
>: might be the result of a complicated exhange in process or something
>: else.
>
>: As a temporary fix, I've tried to get a better score for the center of
>: the alpha-beta window than simply using the score from the previous
>: iteration. I do this by (before the start of the next iteration)
>: searching one ply from the position at the end of the PV from the previous
>: iteration. This search is very quick because it is only 30 positions on
>: average, and seems to return a more accurate score to start the next
>: iteration.
How is this better than just starting the next iteration with
the current PV? Am I missing something here?
I also don't have any hash tables in my program (not enough memory).
I just use the moves from my current PV as the first moves for each
ply in the next iteration.
I also tried keeping a killer list that only had moves from previous
PVs, then using this to reorder PV moves at the next iteration.
Another idea I have yet to try...
Keeping the PV from the first move along with keeping the last PV.
Then if the PV keeps swapping from even to odd ply, I have both
the PVs I need to reorder the moves for a fast search...
>Richard Greenblatt used this idea in MacHack... but for a different
>reason. He found that if you did this to depth=2, and only used the
>score if it was worse, it would cure some "horizon effect" deficiencies
>in the search. I played with it in the 70's as well. Using it to
>"center" the score is a novel use for an old idea, however... and is
>certainly worth trying.
dan
Robert Hyatt
Dan Kirkland (kirk...@ee.utah.edu) wrote:
: In article <5n6p1d$7...@juniper.cis.uab.edu>,
: hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
: >Dan Homan (d...@vlbi.astro.brandeis.edu) wrote:
: >
: >: I'm very new to chess programming (less than 6 months) and my program is
: >: still pretty primitive (e.g. no hash tables, search extensions, etc...),
: >: but I have noticed a similar problem with my program. On odd and even
: >: ply depths it returns quite different scores (a large enough difference
: >: to occasionally cause annoying researches) in certain positions. This
: >: might be the result of a complicated exhange in process or something
: >: else.
: >
: >: As a temporary fix, I've tried to get a better score for the center of
: >: the alpha-beta window than simply using the score from the previous
: >: iteration. I do this by (before the start of the next iteration)
: >: searching one ply from the position at the end of the PV from the previous
: >: iteration. This search is very quick because it is only 30 positions on
: >: average, and seems to return a more accurate score to start the next
: >: iteration.
: How is this better than just starting the next iteration with
: the current PV? Am I missing something here?
Perhaps. This simply adds one more move to the end of the PV, which
will "adjust" the score for one more move as well. The point being
that if the last search was an odd-ply search, we'd expect the even-
ply search to have a lower score since "min" gets to move one more time
than it did on the odd-ply search while max gets the same number of moves.
Adding this extra move will drop the score to something closer to what
the next search will return.
this might work well if you see scores that swing significantly from
iteration to iteration...
: I also don't have any hash tables in my program (not enough memory).