Aspiration Rules...
Chris Pile
Can any of the chess-programming gurus shed light on the mystery
surrounding 'Aspiration Window' values?
I get wildly different results in my node count, and also overall move time,
simply by making small changes to the aspiration window. Is this normal?
At the moment I'm using a window of LAST_SCORE-75 and LAST_SCORE+75.
My pawn value is 100.
This seems to give very few fails, and therefore re-searches. However; I've a
feeling this value isn't optimal. I've tried 'half-a-pawn' but this seemed to
cause
quite a few re-searches.
Is there some magic formula for calculating the optimal aspiration value?
My program is currently using the NegaMax version of Alpha-Beta, with no
fancy 'tricks' other than a simple sort of the capture moves in the q-search.
Moves are played on traditional 10x12 byte-boards and the move generator
doesn't check for illegal moves, this is left to the 'make move' routine.
I'm getting 370-400 NPS on a 3-ply search (this is iterations of 'search' and
does
not include illegal moves) on a 4-MHz Z80... I think this is very poor. Anyone
know what a good NPS benchmark should be for such a CPU?
This is the first chess program I've written, so it's probably lots of rubbish
code
causing it to be so slow...
Thanks in advance,
Chris.
Robert Hyatt
: Hello All,
: Can any of the chess-programming gurus shed light on the mystery
: surrounding 'Aspiration Window' values?
: I get wildly different results in my node count, and also overall move time,
: simply by making small changes to the aspiration window. Is this normal?
: At the moment I'm using a window of LAST_SCORE-75 and LAST_SCORE+75.
: My pawn value is 100.
That is pretty pessimistic. Remember that you _want_ an occasional
fail, so that you know that your window is not _too wide_. You just
don't want to make it too narrow so that you continually fail outside
the 'big window' too frequently.
: This seems to give very few fails, and therefore re-searches. However; I've a
: feeling this value isn't optimal. I've tried 'half-a-pawn' but this seemed to
: cause
: quite a few re-searches.
: Is there some magic formula for calculating the optimal aspiration value?
yes.. it is called "empirical testing"... :) IE try several on a large set
of test positions. But one important thing to watch for is if your program
exhibits odd/even depth evaluation swings, your 'aspiration window' should
be adjusted accordingly to center it on what the expected eval for the
_next_ iteration will be, rather than on what the current iteration produced.
: My program is currently using the NegaMax version of Alpha-Beta, with no
: fancy 'tricks' other than a simple sort of the capture moves in the q-search.
: Moves are played on traditional 10x12 byte-boards and the move generator
: doesn't check for illegal moves, this is left to the 'make move' routine.
: I'm getting 370-400 NPS on a 3-ply search (this is iterations of 'search' and
: does
: not include illegal moves) on a 4-MHz Z80... I think this is very poor. Anyone
: know what a good NPS benchmark should be for such a CPU?
If you had asked me 20 years ago, I could have answered that. As I had
several in my office I was busy programming. But no idea now...
: This is the first chess program I've written, so it's probably lots of rubbish
: code
: causing it to be so slow...
: Thanks in advance,
: Chris.
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Rolf Tueschen
<79g9hf$dvf$1...@juniper.cis.uab.edu>:
>Chris Pile <pegasusE...@enterprise.net> wrote:
>: I'm getting 370-400 NPS on a 3-ply search (this is iterations of 'search' and
>: does
>: not include illegal moves) on a 4-MHz Z80... I think this is very poor. Anyone
>: know what a good NPS benchmark should be for such a CPU?
>If you had asked me 20 years ago, I could have answered that. As I had
>several in my office I was busy programming. But no idea now...
Now, anyone out there who still wants to tell me that this man is a
scientist? Har-de-har! This man ain't no scientist -- he's the proxy for
the actual hardware industry, nothing else.
Without the exact knowledge of history of our field we won't be able to
understand the present ballyhoo. As it was said often enough. In
principle things didn't change very much over the past two decades. It's
all hardware ballyhoo. Hyatt, ChessBase -- it's all the same. They try
to confuse the enduser as if he were in _need_ of higher hardware to be
able to become a better chessplayer. A cheat. And then comes that Hyatt
is spreading so much fascist shit here in that cc group. A scandal!
While the only knowledge-oriented chessprogram (on WIN95), CSTal, is
given away in Germany for some 14 US$$!!!
So far about honesty and profit-oriented cheats.
Robert Hyatt
: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in
: <79g9hf$dvf$1...@juniper.cis.uab.edu>:
:>Chris Pile <pegasusE...@enterprise.net> wrote:
:>: I'm getting 370-400 NPS on a 3-ply search (this is iterations of 'search' and
:>: does
:>: not include illegal moves) on a 4-MHz Z80... I think this is very poor. Anyone
:>: know what a good NPS benchmark should be for such a CPU?
:>If you had asked me 20 years ago, I could have answered that. As I had
:>several in my office I was busy programming. But no idea now...
: Now, anyone out there who still wants to tell me that this man is a
: scientist? Har-de-har! This man ain't no scientist -- he's the proxy for
: the actual hardware industry, nothing else.
Perhaps so, in your eyes. But since you always assume a physical position
where when you open your eyes, you only see your large intestines, I don't
see what 'your' vision of the world is useful for.
: Without the exact knowledge of history of our field we won't be able to
: understand the present ballyhoo. As it was said often enough. In
: principle things didn't change very much over the past two decades. It's
: all hardware ballyhoo. Hyatt, ChessBase -- it's all the same. They try
: to confuse the enduser as if he were in _need_ of higher hardware to be
: able to become a better chessplayer. A cheat. And then comes that Hyatt
: is spreading so much fascist shit here in that cc group. A scandal!
The above is _exactly_ what is expected when you take too much of any
laxative...
: While the only knowledge-oriented chessprogram (on WIN95), CSTal, is
: given away in Germany for some 14 US$$!!!
: So far about honesty and profit-oriented cheats.
so much for idiots..
:>--
Russ Garratt
and move ordering.
If you use bad move ordering, the NPS value goes up because there are
more fast calls to MakeMove() than to the (presumable much slower)
GenerateMoveList()
If you can generate moves in a sensible order *incrementally* rather
than all at once, you will see a huge performance boost because you'll
get a beta cutoff in many nodes without having to generate too many
moves.
The whole computer chess community is still in debate as to the best
method for move generation/ordering, you could look at the "history
algorithm" which has a very low cpu overhead to pick fairly well sorted
moves - but does require *all* the moves to be generated first - so
alternative methods are worth a look, especially on a slow cpu. (such as
hash table move, killer move, captures first etc)
One very bad method to always avoid is using the result of the static
evaluator to give scores to each move and then bubble sorting the list -
almost the worst possible and slowest way of move ordering - but this
algorithm originated in the days of the 8080/Z80 and you may have come
across it. This guarantees many unnecessary evaluations, which are
usually the slowest and most unreliable part of any chess program.
In many progs the "Is the king attacked" function is a big CPU hog,
partly because it is called in situations which don't warrant it, and
partly due to inefficient coding. Hand craft this one in assembler and
design it really well - its worth changing data structures elsewhere in
order to gain efficiency in this area.
Aspiration values calculated only at the root depend on how your
evaluator works - does it try to generate an "absolute" score in some
sense, or is the score "relative" to the root position, indicating
whether the position is getting better or worse for the computer? the
cutoff scheme is a little different in each case. Are you looking for
"best root move" or "and root move which improves your position" ? There
is no definitive answer to this "aspiration window" as it depends on
what is reasonable to achieve in a given position - which is the main
problem of such searching anyhow :-)
Hope this helps
Goodwill from Russ Garratt (Author of The Swindler - which is *still*
under development but beats me most games)
Chris Pile wrote:
>
> Hello All,
>
> Can any of the chess-programming gurus shed light on the mystery
> surrounding 'Aspiration Window' values?
>
> I get wildly different results in my node count, and also overall move time,
> simply by making small changes to the aspiration window. Is this normal?
>
> At the moment I'm using a window of LAST_SCORE-75 and LAST_SCORE+75.
> My pawn value is 100.
>
> This seems to give very few fails, and therefore re-searches. However; I've a
> feeling this value isn't optimal. I've tried 'half-a-pawn' but this seemed to
> cause
> quite a few re-searches.
>
> Is there some magic formula for calculating the optimal aspiration value?
>
> My program is currently using the NegaMax version of Alpha-Beta, with no
> fancy 'tricks' other than a simple sort of the capture moves in the q-search.
>
> Moves are played on traditional 10x12 byte-boards and the move generator
> doesn't check for illegal moves, this is left to the 'make move' routine.
>
> I'm getting 370-400 NPS on a 3-ply search (this is iterations of 'search' and
> does
> not include illegal moves) on a 4-MHz Z80... I think this is very poor. Anyone
> know what a good NPS benchmark should be for such a CPU?
>
Jakub Sipowicz
>
> NPS values are very sensitive to certain criteria eg size of hash table
> and move ordering.
As Chris is using Z80, he has not too much space (if any) for a hash
table. AFAIR Z80 can address (without some tricks eg., bank switching)
64KB only.
JS
--
Jakub Sipowicz
Institute of Computer Science,
Jagiellonian University, Krakow, Poland
mailto:sipo...@softlab.ii.uj.edu.pl
Steve Maughan
and
>does
>not include illegal moves) on a 4-MHz Z80... I think this is very poor.
Anyone
>know what a good NPS benchmark should be for such a CPU?
I'm going back a little (~1985) but on my Spectrum which is a 3.5 MHz Z80 (I
think?) the best programs were Colossus 4 and SuperChess 3.5 (Chris
Whittingtom). If my memory is correct Colossus searched ~170 node/sec while
SC3.5 searched ~120.
Steve Maughan
Russ Garratt
be many years back) that hardware tricks would be no problem. Using one
of the output ports to select memory banks in the upper 16K range would
give 256x16K memory for hash. Not much by todays standards but a huge
boost in performance over none at all.
Presumably the 8 bits written to the output port could be 8 bits from
the hashcode, latched into the upper 8 bits of a 22 bit memory address
register, the lower 14 bits from the low 14 z80 address lines on the
next cycle ... result is just read from memory above 0xc000 as normal
ram. Plenty of "spare" obsolete memory chips these days from 286/386/486
computers can be had for virtually nothing and could be used in such a
configuration. And the rest would be simple TTL logic gates, easy when
the RAM response time only needs to be 200ns or so ...would be very
cheap, and nice slow signals to watch on the scope makes debugging easy.
Chris Pile
I think I've basically got my 'Aspiration' search working, but I
fear that I might have problems with it.
The way I'm doing it at the moment is this:
alpha = -INF
beta = +INF
depth = 1
loop: save depth
save alpha
save beta
call search (returns score for the best root-move to depth
'depth')
restore beta
restore alpha
restore depth
if score <= alpha then set alpha to -INF and jump to loop
if score >= beta then set beta to +INF and jump to loop
alpha = score - window_size
beta = score + window_size
increase depth
if depth < max_depth the jump to loop
If I call search with no iterative deepening, just alpha=-INF, beta=+INF and
depth=4 (for example) then it sometimes returns a root-move that is different
from the aspiration version.
This is also true even when the aspiration version doesn't suffer from any
window
failures and searches, iteratively, to the same depth...
I can't believe this is normal??? Shouldn't they both return the same
root-move?
Thanks in advance,
Chris.
Robert Hyatt
: Many thanks to all that replied to me regarding this subject.
: Thanks in advance,
: Chris.
Hard to answer. When you "fail high" do you fiddle with the 'root move list'
in any way? When you say 'different move' does the score stay the same? IE
it is possible that thru transpositions, two different root moves produce
the same score/PV.
And to really test it, turn hashing off and you should get the same score/PV
either way, allowing for the issue of different first move so long as the
score doesn't change at all...
Chris Pile
Robert Hyatt wrote in message <79ssbg$2ee$1...@juniper.cis.uab.edu>...
>Hard to answer. When you "fail high" do you fiddle with the 'root move list'
>in any way? When you say 'different move' does the score stay the same? IE
>it is possible that thru transpositions, two different root moves produce
>the same score/PV.
My program is still *very* crude. It has no transposition/hashing features, nor
does
it store the entire PV; simply the 'best move at root'. This best move is
stored by
the main search routine, providing the move is a 'root-move'. No adjustment or
fiddling with the root move occurs in the aspiration routine.
>And to really test it, turn hashing off and you should get the same score/PV
>either way, allowing for the issue of different first move so long as the
>score doesn't change at all...
Well, I don't have the hashing worry. I've tested if the scores are the same
for any
different moves, and they are. I guess that if the move's score remains the
same as
any 'alternative' move then it's probably OK? I was a little worried that I
might have
made some blatantly obvious (to a seasoned chess programmer!) error in my
aspiration routine... Or, perhaps, have an even worse error deeper in my
program!
Thanks for the help,
Chris.
Robert Hyatt
: Robert Hyatt wrote in message <79ssbg$2ee$1...@juniper.cis.uab.edu>...
: Thanks for the help,
: Chris.
The issue is the 'score'. It shouldn't change. But you might find that
Nf3 Nf6 e4 and e4 Nf6 Nf3 produce the same score... but which gets
played first depends on move ordering... so long as the score is the
same, alpha/beta should always produce the same result...
But not necessarily the same move as you can see...