quiescent vs non-quiescent node counting
Robert Hyatt
Here's an interesting question. Suppose we are doing a search to depth=3.
When counting nodes in Crafty, at the top of Search() I increment nodes, and
at the top of Quiesce() I increment qnodes. This might well be misleading
for the following reason: at depth=1, which is at level three in the tree,
we make a move, and then call Quiesce since depth goes to zero. Quiesce will
increment qnodes, even if *no* capture moves are tried.
My question is this. How does everyone else count nodes. One idea might be
to move the increment into the main loop inside search, so that when a non-
quiescent move is made, the non-quiescent nodes are incremented.
My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
quiesce so it searches *no* nodes, there will still be a significant number
of q-nodes reported due to the way they are counted. Everyone ought to reach
an agreement to either (a) count 'em like I do, (b) count 'em like I proposed
above as an alternative, or (c) some other approach that we can all agree
produces good numbers. Any suggestions or comments? It seems that if Quiesce
finds *no* capture moves to try, qnodes should be zero? Or not?
Bob
Robert Hyatt
One other issue I just encountered when playing with the idea I previously
described. When searching a null-move, since no MakeMove() is needed, I did
not increment the nodes searched. NPS dropped significantly since so many null
moves are searched. What I'm currently using is to increment the node counters
just before calling Search() now. This has the effect of giving the same count
as before, but the moves searched at depth=1 now result in non-q-nodes, which
seems more logical.
More comments?
Peter W. Gillgasch
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> Here's an interesting question. Suppose we are doing a search to depth=3.
> When counting nodes in Crafty, at the top of Search() I increment nodes, and
> at the top of Quiesce() I increment qnodes. This might well be misleading
> for the following reason: at depth=1, which is at level three in the tree,
> we make a move, and then call Quiesce since depth goes to zero. Quiesce will
> increment qnodes, even if *no* capture moves are tried.
>
> My question is this. How does everyone else count nodes. One idea might be
> to move the increment into the main loop inside search, so that when a non-
> quiescent move is made, the non-quiescent nodes are incremented.
What I did in DarkThought was this: If a move passes all barriers of
being included into the qsearch (non futile capture or a check under
certain circumstances and strictly legal) I increased the node count.
All strictly legal moves in search region A (full width) are counted as
well. By moving that node_count++ line a little I could make it "twice
as fast" but that is nonsensical of course.
All this stuff happened before the xref lookup of course.
> My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
> quiesce so it searches *no* nodes, there will still be a significant number
> of q-nodes reported due to the way they are counted. Everyone ought to reach
> an agreement to either (a) count 'em like I do,
Actually I believed that we should get a "standard definition" of "what
is a node" for quite a long time but now after thinking about it for a
couple of years I think that this is practically impossible - forward
pruning decisions, illegal move detection etc. are playing into this.
You can probably not even ask for a clean definition how a specific
program counts nodes. Some guys will not give you an answer on that,
especially the commercial guys 8^)
> (b) count 'em like I proposed
> above as an alternative, or (c) some other approach that we can all agree
> produces good numbers. Any suggestions or comments? It seems that if Quiesce
> finds *no* capture moves to try, qnodes should be zero? Or not?
If your Quiesce() calls eval as alternative to making a move then I
think you should count the node no matter what (this is what I did).
All you have to ensure is that when you go from region A to region B
that your code does not increment the count in your region A code, calls
the region B code and and increments the count again for the same
position.
-- Peter
Peter W. Gillgasch
Ed Schröder
I see everbody is using their own definition of counting nodes.
REBEL does nodes++ every time the evaluation routine is called.
As simple as possible.
- Ed Schroder -
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>Here's an interesting question. Suppose we are doing a search to depth=3.
>When counting nodes in Crafty, at the top of Search() I increment nodes, and
>at the top of Quiesce() I increment qnodes. This might well be misleading
>for the following reason: at depth=1, which is at level three in the tree,
>we make a move, and then call Quiesce since depth goes to zero. Quiesce will
>increment qnodes, even if *no* capture moves are tried.
>
>My question is this. How does everyone else count nodes. One idea might be
>to move the increment into the main loop inside search, so that when a non-
>quiescent move is made, the non-quiescent nodes are incremented.
>
>My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
>quiesce so it searches *no* nodes, there will still be a significant number
>of q-nodes reported due to the way they are counted. Everyone ought to reach
>an agreement to either (a) count 'em like I do, (b) count 'em like I proposed
>above as an alternative, or (c) some other approach that we can all agree
>produces good numbers. Any suggestions or comments? It seems that if Quiesce
>finds *no* capture moves to try, qnodes should be zero? Or not?
>
>Bob
Martin Borriss
In article <4r84or$t...@news.xs4all.nl>, "Ed Schröder" <10065...@compuserve.com> writes:
> I see everbody is using their own definition of counting nodes.
>
> REBEL does nodes++ every time the evaluation routine is called.
>
Me too. The nodes are not incremented if the position can be evaluated lazy, so
I count only full or 'half-full' evaluations.
Martin
P.S.: The other day I lost a blitz match against MChess. Pretty depressing,
perhaps I should downgrade my computer again.
Peter W. Gillgasch
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> One other issue I just encountered when playing with the idea I previously
> described. When searching a null-move, since no MakeMove() is needed, I
> did not increment the nodes searched.
Why not ? It is called null *MOVE*. The position is different, the e.p.
state is different (well, sometimes), probably your hashkey is different
as well.
I did count it. Was faster :)
> NPS dropped significantly since so many null moves are searched.
Obvious.
> What I'm currently using is to increment the node counters just before
> calling Search() now. This has the effect of giving the same count as
> before, but the moves searched at depth=1 now result in non-q-nodes, which
> seems more logical.
>
> More comments?
Didn't do that. As I said I counted "below" the move. Since I had some
logic that told me if this is a qsearch node or not I could increment a
seperate qsearch count for the search statistics. So I had one counter
that included all nodes that were searched (*and* belong to the current
part of the tree) and another one that counted only qsearch nodes.
-- Peter
Robert Hyatt
Peter W. Gillgasch (gil...@ilk.com) wrote:
: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
:
: > Here's an interesting question. Suppose we are doing a search to depth=3.
: > When counting nodes in Crafty, at the top of Search() I increment nodes, and
: > at the top of Quiesce() I increment qnodes. This might well be misleading
: > for the following reason: at depth=1, which is at level three in the tree,
: > we make a move, and then call Quiesce since depth goes to zero. Quiesce will
: > increment qnodes, even if *no* capture moves are tried.
: >
: > My question is this. How does everyone else count nodes. One idea might be
: > to move the increment into the main loop inside search, so that when a non-
: > quiescent move is made, the non-quiescent nodes are incremented.
: What I did in DarkThought was this: If a move passes all barriers of
: being included into the qsearch (non futile capture or a check under
: certain circumstances and strictly legal) I increased the node count.
: All strictly legal moves in search region A (full width) are counted as
: well. By moving that node_count++ line a little I could make it "twice
: as fast" but that is nonsensical of course.
:
: All this stuff happened before the xref lookup of course.
: > My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
: > quiesce so it searches *no* nodes, there will still be a significant number
: > of q-nodes reported due to the way they are counted. Everyone ought to reach
: > an agreement to either (a) count 'em like I do,
: Actually I believed that we should get a "standard definition" of "what
: is a node" for quite a long time but now after thinking about it for a
: couple of years I think that this is practically impossible - forward
: pruning decisions, illegal move detection etc. are playing into this.
:
: You can probably not even ask for a clean definition how a specific
: program counts nodes. Some guys will not give you an answer on that,
: especially the commercial guys 8^)
: > (b) count 'em like I proposed
: > above as an alternative, or (c) some other approach that we can all agree
: > produces good numbers. Any suggestions or comments? It seems that if Quiesce
: > finds *no* capture moves to try, qnodes should be zero? Or not?
: If your Quiesce() calls eval as alternative to making a move then I
: think you should count the node no matter what (this is what I did).
:
: All you have to ensure is that when you go from region A to region B
: that your code does not increment the count in your region A code, calls
: the region B code and and increments the count again for the same
: position.
:
: -- Peter
Now I need Ed to jump in here so we can compare apples to apples. It appears to
me that if we count nodes as you suggest (Peter), which is exactly how I've been
counting them forever I think, then we reach an impossible condition when trying
to match Ed's numbers. A simple example.
Suppose our branching factor is 4, and we do a 4 ply search, and the move order
happens to be backward so we have to search every path with no alpha/beta cutoffs.
That will produce the following counts (4 at ply=1, 16 at ply=2, 64 at ply=3, and
256 at ply=4. However, counting as we are at present, we get 1 at ply=1, 4 at
ply=2, 16 at ply=3 and 64 at ply=4, for a total of 64+16+4+1=85 nodes. The
interesting thing is that we also get at *least* 64 quiescent nodes as well,
because for each node at ply=4 we will call quiesce and get one node at ply=5
as well, even if it's not expanded. This means that the total quiescent nodes
is always going to be reasonably close to the non-quiescent node count due to
simple math. I'm trying to compare with ed's 20-30% here.
I suppose it gets even worse if you use futility cutoffs at depth=1, as you do
get to avoid a quiesce call in those cases. Maybe it's hopeless to compare?
Robert Hyatt
Ed Schröder (10065...@compuserve.com) wrote:
: I see everbody is using their own definition of counting nodes.
:
: REBEL does nodes++ every time the evaluation routine is called.
: As simple as possible.
:
: - Ed Schroder -
:
Not so simple to me. :)
A couple of questions, any of which you can elect not to answer of course.
1. I assume you call Evaluate() at every node, both internal and q-search?
2. If so, then when depth > 0 you increment nodes, when it's <= 0 you increment
q-nodes?
If so, read my previous post on this thread and help me understand where we
are on different wavelengths. :)
Bob
:
:
: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
: >Here's an interesting question. Suppose we are doing a search to depth=3.
: >When counting nodes in Crafty, at the top of Search() I increment nodes, and
: >at the top of Quiesce() I increment qnodes. This might well be misleading
: >for the following reason: at depth=1, which is at level three in the tree,
: >we make a move, and then call Quiesce since depth goes to zero. Quiesce will
: >increment qnodes, even if *no* capture moves are tried.
: >
: >My question is this. How does everyone else count nodes. One idea might be
: >to move the increment into the main loop inside search, so that when a non-
: >quiescent move is made, the non-quiescent nodes are incremented.
: >
: >My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
: >quiesce so it searches *no* nodes, there will still be a significant number
: >of q-nodes reported due to the way they are counted. Everyone ought to reach
: >an agreement to either (a) count 'em like I do, (b) count 'em like I proposed
: >above as an alternative, or (c) some other approach that we can all agree
: >produces good numbers. Any suggestions or comments? It seems that if Quiesce
: >finds *no* capture moves to try, qnodes should be zero? Or not?
: >
: >Bob
:
:
Ed Schroder
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>Ed Schröder (10065...@compuserve.com) wrote:
>: I see everbody is using their own definition of counting nodes.
>:
>: REBEL does nodes++ every time the evaluation routine is called.
>:
>: As simple as possible.
>:
>: - Ed Schroder -
>:
>
>Not so simple to me. :)
>
>A couple of questions, any of which you can elect not to answer of course.
>
>1. I assume you call Evaluate() at every node, both internal and q-search?
>
>2. If so, then when depth > 0 you increment nodes, when it's <= 0 you increment
>q-nodes?
>
>If so, read my previous post on this thread and help me understand where we
>are on different wavelengths. :)
>
>Bob
REBEL does
in the MAIN search: nodes++
in the Q-search: nodes++ q_nodes++
before the evaluation routine is called.
To me you can't compare Crafty's nodes to Rebel.
You could however make a test version of Crafty which counts as Rebel.
Especially your q_nodes are interesting because of our previous
q_search discussions.
- Ed Schroder -
MANOHARARAJAH VALAVAN
In article <4r7dd7$l...@juniper.cis.uab.edu>,
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>Here's an interesting question. Suppose we are doing a search to depth=3.
>When counting nodes in Crafty, at the top of Search() I increment nodes, and
>at the top of Quiesce() I increment qnodes. This might well be misleading
>for the following reason: at depth=1, which is at level three in the tree,
>we make a move, and then call Quiesce since depth goes to zero. Quiesce will
>increment qnodes, even if *no* capture moves are tried.
>
>My question is this. How does everyone else count nodes. One idea might be
>to move the increment into the main loop inside search, so that when a non-
>quiescent move is made, the non-quiescent nodes are incremented.
I do it in the following way: in the loop that does make(), call to
alpha-beta() and unmake(), i add the increment for nodes. This is also done
for quiesce search. Thus one can get a good idea of the part of the search
that did the expansion. Gnu chess also does in this fashion.
When counting at the beginning of alpha-beta() or quiesce(), there will be
a problem for the quiesce node count. the Quiesce node count will be
artificially blown up - since many of the quiesce nodes are just used for
evaluation purposes. They never really expand out to handle capture sequences.
>
>My concern is simply this: If, in crafty, I do a 5 ply search, and "break"
>quiesce so it searches *no* nodes, there will still be a significant number
>of q-nodes reported due to the way they are counted. Everyone ought to reach
>an agreement to either (a) count 'em like I do, (b) count 'em like I proposed
>above as an alternative, or (c) some other approach that we can all agree
>produces good numbers. Any suggestions or comments? It seems that if Quiesce
>finds *no* capture moves to try, qnodes should be zero? Or not?
>
>Bob
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Peter W. Gillgasch
Ed Schröder <10065...@compuserve.com> wrote:
> I see everbody is using their own definition of counting nodes.
True. What do you think is a definition that
(a) makes sense
(b) is straightforward to implement in any program
(c) is well formulated enough that there is little case
of doubt on the "how" and "when" even is special cases
just for the sake of having numbers that can be compared ?
> REBEL does nodes++ every time the evaluation routine is called.
>
> As simple as possible.
Simple yes. Nodes per second ? Not neccessarily ;) Too many questions
are unanswerd (note that I don't ask them):
- is eval called inside the full width region
- is eval called in all positions, even in "get out of check" positions
- is eval called for deciding on extensions
- is eval by-passed if the fast evaluation falls out of the alpha beta
window
- is eval called to detect illegal positions
etc.
Note that this thread is not about "is program X faster than
Rebel/Crafty..." but about having a metric that can be compared among
different chess program architectures for the purpose of comparing tree
sizes and qsearch / full width ratios.
-- Peter
Peter W. Gillgasch
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> Peter W. Gillgasch (gil...@ilk.com) wrote:
> : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
[ big snip ]
> Now I need Ed to jump in here so we can compare apples to apples. It
> appears to me that if we count nodes as you suggest (Peter), which is
> exactly how I've been counting them forever I think, then we reach an
> impossible condition when trying to match Ed's numbers.
Agreed. Note that I didn't really want to suggest that metric since it
is not practical for all purposes, it is just the metric used in
DarkThought. I believe that it is the most meaningful metric though
since it does not reward a huge fanout by generating and executing tons
of moves that are not searched anyway.
>A simple example. Suppose our branching factor is 4, and we do a 4 ply
>search, and the move order happens to be backward so we have to search
>every path with no alpha/beta cutoffs. That will produce the following
>counts (4 at ply=1, 16 at ply=2, 64 at ply=3, and 256 at ply=4.
>However, counting as we are at present, we get 1 at ply=1, 4 at ply=2,
>16 at ply=3 and 64 at ply=4, for a total of 64+16+4+1=85 nodes. The
>interesting thing is that we also get at *least* 64 quiescent nodes as
>well, because for each node at ply=4 we will call quiesce and get one
>node at ply=5 as well, even if it's not expanded. This means that the
>total quiescent nodes is always going to be reasonably close to the
>non-quiescent node count due to simple math. I'm trying to compare
>with ed's 20-30% here.
Agreed. With the definition you are using in Crafty and I used in
DarkThought 20-30% seems impossible.
> I suppose it gets even worse if you use futility cutoffs at depth=1, as you do
> get to avoid a quiesce call in those cases.
I do that pruning *above* the move. Makes the tree much smaller since I
am using the mvv-lva method, so that moves are not counted (I don't
want to say that it is superior to SEE ordering, with much smaller I
mean that it is much smaller than expanding the node just to return
right away since it was futile).
> Maybe it's hopeless to compare?
Maybe. I had this CHEAT_NODES switch in DarkThought that used a more
naive implementation of node counting (for all practical purposes it
increased the node count after a move was executed) that did not take
the qsearch filtering into account (mainly to minimize the ratio of make
move operations over nodes searched to improve on the quality of the
legality and forward pruning filters - minimizing this is important
if your make_move() is expensive).
I suggest that we don't ask for a canonical definition of how to count
nodes. A good explanation how someone else counts them seems sufficient
to me since you can then compare notes if you count them as they do. But
as I said a good explanation tells too much about the structure of the
code for some commercial engines.
If Ed is willing to explain what he does (not neccessarily exactly but
if he explains it in such a way that our numbers are in 90-95% of the
cases the same) then you could try that. I think the main problem is
"what is Ed's definition of a qsearch node" for that experiment, right?
Another interesting question regarding Ed's definition is when he calls
eval(). In DarkThought I implemented Hans Berliner's recapture extension
idea which basically leads to an eval() call everytime you see a capture
in search region A (and *many* of the moves are captures). This gives
rise to another point. If you extend on recaptures then your full width
/ qsearch ratio gets better since a lot of captures are "moved up" into
the search region A and search region B has less captures to try due to
lack of material... So this question is really openening a can of
worms...
I feel that explaining all this things is too much to ask since Ed could
post the Rebel search engine source code as well 8^)
Maybe the two of you should work out some metric that let's you compare
your SEE efficiency in the qsearch or something. I feel that this is
what you are interested in Bob ?
-- Peter
Robert Hyatt
Ed Schroder (rebc...@xs4all.nl) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
: >Ed Schröder (10065...@compuserve.com) wrote:
: >: I see everbody is using their own definition of counting nodes.
: >: REBEL does nodes++ every time the evaluation routine is called.
: >:
: >: As simple as possible.
: >:
: >:
: >
: >Not so simple to me. :)
: >
: >A couple of questions, any of which you can elect not to answer of course.
: >
: >1. I assume you call Evaluate() at every node, both internal and q-search?
: >
: >2. If so, then when depth > 0 you increment nodes, when it's <= 0 you increment
: >q-nodes?
: >
: >If so, read my previous post on this thread and help me understand where we
: >are on different wavelengths. :)
: >
: >Bob
:
:
:
: REBEL does
: in the MAIN search: nodes++
: in the Q-search: nodes++ q_nodes++
:
: To me you can't compare Crafty's nodes to Rebel.
:
: You could however make a test version of Crafty which counts as Rebel.
:
: Especially your q_nodes are interesting because of our previous
: q_search discussions.
:
: - Ed Schroder -
:
Let me make sure I understand and I can then do this. nodes = *total* nodes
searched, q-nodes = only calls to quiesce() ??
For example, in crafty, where I report nodes=500,000, q-nodes=2,000,000,
it would now say nodes=2,500,000, q-nodes=2,000,000?
Bob
Robert Hyatt
I don't use the HiTech approach, although I've had a recapture extension
since 1983 when Ken and I first talked about doing it. The HiTech approach
appears (to me) to be too restrictive, and also becomes complicated when
the root of the tree itself is a recapture. I can tell you more if you are
interested, or you can scan search.c in Crafty's source to see what I do.
It's been working well for a long time, and doesn't seem to blow the tree
out too badly...
:
: I feel that explaining all this things is too much to ask since Ed could
: post the Rebel search engine source code as well 8^)
:
: Maybe the two of you should work out some metric that let's you compare
: your SEE efficiency in the qsearch or something. I feel that this is
: what you are interested in Bob ?
:
: -- Peter
:
No. I don't think it's an issue of using SEE to weed out captures. I think
it's much more than that. I can cull losers (as I do) or swaps (as I used to
do after the first couple of plies), but that's not enough. The thing that
I see ripping the q-search up is two queens go on a picnic, and you see a
long series of Qxp Qxp Qxn Qxb Qxp Qxp ..... all of which are safe captures,
but none of which will ever be actually played in the game.
Ed Schroder
>: REBEL does
>: in the MAIN search: nodes++
>: in the Q-search: nodes++ q_nodes++
>: before the evaluation routine is called.
>:
>: To me you can't compare Crafty's nodes to Rebel.
>:
>: You could however make a test version of Crafty which counts as Rebel.
>:
>: Especially your q_nodes are interesting because of our previous
>: q_search discussions.
>:
>: - Ed Schroder -
>Let me make sure I understand and I can then do this. nodes = *total* nodes
>searched, q-nodes = only calls to quiesce() ??
>
>For example, in crafty, where I report nodes=500,000, q-nodes=2,000,000,
>it would now say nodes=2,500,000, q-nodes=2,000,000?
>
>Bob
Yes.
nodes = all nodes searched, including q-search.
q_nodes = only q-search nodes.
- Ed -
Joe Stella
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>[...]
>My question is this. How does everyone else count nodes.
>[...]
In my program, I have three counters. I do:
1) Nodes++; at the top of search()
2) Q_nodes++; at the top of Quies()
3) leaf++; when search() calls quies()
then
total_nodes = Nodes + Q_nodes - leaf;
Joe Stella
Ed Schroder
You have a point Peter with your posting.
Since there are hundreds of chess programs or maybe we already have
crossed the 1000 in the meantime (In Holland I estimate we have 60-70
chess programmers) it's very unlikely that we will ever be able to find a
good, simple and reliable formula on node counts.
Everybody has his own type of Tree_Search with their own tricks or
inventions. Others are using Null Move etc. etc.
I have chosen to count every time the evaluation routine is called for
the following reasons:
- The approach is simple.
- I can see if q_search is within a reasonable / acceptable margins.
- Since the evaluation routine is the most time consuming part of Rebel,
it looks an interesting counter for me.
However nobody has told me if there is an "official rule" for counting
nodes, and reading these postings we all have started trying to find
one (right?)
Looking at all the different colors of chess programs I wonder if we will
succeed, but we can try of course.
Your questions...
- is eval called inside the full width region
Yes, always including in Q-search.
- is eval called in all positions, even in "get out of check" positions
All "illegal (generated) moves" are immediately killed, so no evaluation.
- is eval called for deciding on extensions
Nope.
- is eval by-passed if the fast evaluation falls out of the alpha beta
window
Not understood.
- is eval called to detect illegal positions
Only for a castling move. Strange huh...
- Ed Schroder -
Original posting...
gil...@ilk.de (Peter W. Gillgasch) wrote:
>Ed Schröder <10065...@compuserve.com> wrote:
>
>> I see everbody is using their own definition of counting nodes.
>
Robert Hyatt
Ed Schroder (rebc...@xs4all.nl) wrote:
: You have a point Peter with your posting.
Think he's asking about a classic "lazy evaluation." When you call
Evaluate() and the material score is way below alpha, if you are sure
your Evaluate() procedure can't produce a number large enough to bring
the score up to alpha, you can avoid doing the evaluation completely.
Lazy evaluation is the idea of first trying the parts of the eval that
bring the score up the quickest, and when it becomes obvious that you can't
get the score up to alpha, there's no need to try those parts that will
reduce the eval since you are already below an acceptable lower bound.
Bob
Peter W. Gillgasch
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> Peter W. Gillgasch (gil...@ilk.de) wrote:
> : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> :
> : > Peter W. Gillgasch (gil...@ilk.com) wrote:
> : > : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
[ snips are getting big tonite ]
> : Another interesting question regarding Ed's definition is when he calls
> : eval(). In DarkThought I implemented Hans Berliner's recapture extension
> : idea which basically leads to an eval() call everytime you see a capture
> : in search region A (and *many* of the moves are captures). This gives
> : rise to another point. If you extend on recaptures then your full width
> : / qsearch ratio gets better since a lot of captures are "moved up" into
> : the search region A and search region B has less captures to try due to
> : lack of material... So this question is really openening a can of
> : worms...
>
> I don't use the HiTech approach, although I've had a recapture extension
> since 1983 when Ken and I first talked about doing it. The HiTech approach
> appears (to me) to be too restrictive, and also becomes complicated when
> the root of the tree itself is a recapture. I can tell you more if you are
> interested, or you can scan search.c in Crafty's source to see what I do.
> It's been working well for a long time, and doesn't seem to blow the tree
> out too badly...
From what I remember the last time I checked (about 4 months ago or
something) your code looked restrictive to me ;-) I *think* you checked
captures happening on the same square in sequence which looks too
"static" to me. I had never any problems with the Hitech idea and
certainly not with recaptures at the root node (at least the beast never
exploded due to *this*). What I did was the following (this is how I
understood Hans and he never corrected me):
You remember the last result of a *search* that didn't fail high or low
(that is you don't change that before you do a re-search from the root
node otherwise your re-search will be completely different from the
original search and anything can happen since different extensions are
triggered). You center a window around that value (I used 1/4 of a pawn
in both directions). Now everytime you see a capture in the tree you
call eval with alpha/beta set to *that* window. If the result of eval is
within that interval you do an extension. What if you don't have a
search result yet? You simply center the recapture window around your
static evaluation.
The gain is of course that positional considerations are taken into
account as well (did *I* say something about positional considerations ?
8^) and a couple of plies can happen between the original capture and
the recapture. I verified that using the tree tracer and most of the
extensions looked pretty clever. I was very satisfied with that
technique and in case you didn't try it in Crafty you should consider
it.
Did you and Ken implement it in a different way ? What are the
complications at the root ? Did I overlook something silly ?
[ snip ]
> : Maybe the two of you should work out some metric that let's you compare
> : your SEE efficiency in the qsearch or something. I feel that this is
> : what you are interested in Bob ?
>
> No. I don't think it's an issue of using SEE to weed out captures. I think
> it's much more than that. I can cull losers (as I do) or swaps (as I used to
> do after the first couple of plies), but that's not enough. The thing that
> I see ripping the q-search up is two queens go on a picnic, and you see a
> long series of Qxp Qxp Qxn Qxb Qxp Qxp ..... all of which are safe captures,
> but none of which will ever be actually played in the game.
Hm. Don't see any way to get rid of that... But you are right, if Ed is
doing only 20-30% of his work in the qsearch it is certainly more than
that. Pretty impressive ratio.
-- Peter
Peter W. Gillgasch
Ed Schroder <rebc...@xs4all.nl> wrote:
> You have a point Peter with your posting.
>
> Since there are hundreds of chess programs or maybe we already have
> crossed the 1000 in the meantime (In Holland I estimate we have 60-70
> chess programmers) it's very unlikely that we will ever be able to find a
> good, simple and reliable formula on node counts.
>
> Everybody has his own type of Tree_Search with their own tricks or
> inventions. Others are using Null Move etc. etc.
I agree. There are just too many tricks you can do that distort the
results and abandoning these may be too much work for the purpose of
comparision alone - and since the program is not the same if you abandon
your tricks it doesn't make sense either.
Probably the best one can do about that is listening to programmers that
are willing to share their definition and if it is too different try to
"simulate" it if possible.
> I have chosen to count every time the evaluation routine is called for
> the following reasons:
> - The approach is simple.
> - I can see if q_search is within a reasonable / acceptable margins.
> - Since the evaluation routine is the most time consuming part of Rebel,
> it looks an interesting counter for me.
Makes sense. I didn't understand your metric in the first place but
after reading your further explanations I did. Thanks.
> However nobody has told me if there is an "official rule" for counting
> nodes, and reading these postings we all have started trying to find
> one (right?)
>
> Looking at all the different colors of chess programs I wonder if we will
> succeed, but we can try of course.
>
> Your questions...
Thanks for answering them. I didn't really want to ask them since I felt
that they go too much into details & "secrets" but your answers are
pretty interesting.
> - is eval called inside the full width region
> Yes, always including in Q-search.
>
> - is eval called in all positions, even in "get out of check" positions
> All "illegal (generated) moves" are immediately killed, so no evaluation.
>
> - is eval called for deciding on extensions
> Nope.
I am a bit surprised about this one.
> - is eval by-passed if the fast evaluation falls out of the alpha beta
> window
> Not understood.
What I was referring to is the well known trick that if you have a fast
evaluation that is maintained in an incremental fashion (during
make_move) that you impose an upper limit of the additional stuff you
evaluate (with the help of eval()). Now if your fast score plus that
upper limit is below alpha or your fast score minus that upper limit is
above beta you could simply skip eval() since the result will not
contribute to the result of the search. It depends of course on what you
are doing with the score but if you are only interested in a certain
range it can save a lot of time although it may be somewhat risky...
> - is eval called to detect illegal positions
> Only for a castling move. Strange huh...
Not really. Castling is a strange move, so it deserves strange handling
:)
-- Peter
Ed Schröder
I have tried "lazy evaluation", it's ok for quiet positions, but a
disaster for positions with BIG positional values involved (king safety,
passed pawns etc.) resulting in very bad moves! (at least by me) and
especially when you use "lazy evaluation" also in Q-search (very
dangerous!)
I use now what I call "risky evaluation", see my answer to Bob below.
- Ed Schroder -
Rebel does something similar as "lazy evaluation", although it is based
on different principals. I call it "risky evaluation" since there
are many risks on it. Through the years I invested month's of my time in
it with eventually good results. How it works I can't remember <smile>.
To stay on our subject, Rebel does also nodes++ in "risky evaluation".
I guess that tricks like "lazy evaluation", "risky evaluation" (anybody
else?) makes it almost impossible to make a standard rule for node
counting.
Mission Impossible?
- Ed Schroder -
gil...@ilk.de (Peter W. Gillgasch) wrote:
Ed Schröder
Rebel does something similar as "lazy evaluation", although it is based
on different principals. I call it "risky evaluation" since there
are many risks on it. Through the years I invested month's of my time in
it with eventually good results. How it works I can't remember <smile>.
To stay on our subject, Rebel does also nodes++ in "risky evaluation".
I guess that tricks like "lazy evaluation", "risky evaluation" (anybody
else?) makes it almost impossible to make a standard rule for node
counting.
Mission Impossible?
- Ed Schroder -
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>Ed Schroder (rebc...@xs4all.nl) wrote:
>: You have a point Peter with your posting.
>:
>: Since there are hundreds of chess programs or maybe we already have
>: crossed the 1000 in the meantime (In Holland I estimate we have 60-70
>: chess programmers) it's very unlikely that we will ever be able to find a
>: good, simple and reliable formula on node counts.
>:
>: Everybody has his own type of Tree_Search with their own tricks or
>: inventions. Others are using Null Move etc. etc.
>:
>: I have chosen to count every time the evaluation routine is called for
>: the following reasons:
>: - The approach is simple.
>: - I can see if q_search is within a reasonable / acceptable margins.
>: - Since the evaluation routine is the most time consuming part of Rebel,
>: it looks an interesting counter for me.
>:
>: However nobody has told me if there is an "official rule" for counting
>: nodes, and reading these postings we all have started trying to find
>: one (right?)
>:
>: Looking at all the different colors of chess programs I wonder if we will
>: succeed, but we can try of course.
>:
>: Your questions...
>: - is eval called inside the full width region
>: Yes, always including in Q-search.
>:
>: - is eval called in all positions, even in "get out of check" positions
>: All "illegal (generated) moves" are immediately killed, so no evaluation.
>:
>: - is eval called for deciding on extensions
>: Nope.
>:
>: - is eval by-passed if the fast evaluation falls out of the alpha beta
>: window
>: Not understood.
>:
Robert Hyatt
Joe Stella (jo...@ultranet.com) wrote:
:
Why "-leaf"? That seems to be something counted it "Nodes++;" If I were
counting "leaf" nodes, I'd probably increment when Quiesce() doesn't find
any capture to try.
In any case, it seems that total_nodes=Nodes+Q_nodes should be the total?
Robert Hyatt
: > : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
: > :
: > : > Peter W. Gillgasch (gil...@ilk.com) wrote:
: > : > : Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
:
:
: > : eval(). In DarkThought I implemented Hans Berliner's recapture extension
: > : idea which basically leads to an eval() call everytime you see a capture
: > : in search region A (and *many* of the moves are captures). This gives
: > : rise to another point. If you extend on recaptures then your full width
: > : / qsearch ratio gets better since a lot of captures are "moved up" into
: > : the search region A and search region B has less captures to try due to
: > : lack of material... So this question is really openening a can of
: > : worms...
: >
: > I don't use the HiTech approach, although I've had a recapture extension
: > since 1983 when Ken and I first talked about doing it. The HiTech approach
: > appears (to me) to be too restrictive, and also becomes complicated when
: > the root of the tree itself is a recapture. I can tell you more if you are
: > interested, or you can scan search.c in Crafty's source to see what I do.
: > It's been working well for a long time, and doesn't seem to blow the tree
: > out too badly...
:
: something) your code looked restrictive to me ;-) I *think* you checked
: captures happening on the same square in sequence which looks too
: "static" to me. I had never any problems with the Hitech idea and
: certainly not with recaptures at the root node (at least the beast never
: exploded due to *this*). What I did was the following (this is how I
: understood Hans and he never corrected me):
:
: You remember the last result of a *search* that didn't fail high or low
: (that is you don't change that before you do a re-search from the root
: node otherwise your re-search will be completely different from the
: original search and anything can happen since different extensions are
: triggered). You center a window around that value (I used 1/4 of a pawn
: call eval with alpha/beta set to *that* window. If the result of eval is
: within that interval you do an extension. What if you don't have a
: search result yet? You simply center the recapture window around your
: static evaluation.
:
: The gain is of course that positional considerations are taken into
: account as well (did *I* say something about positional considerations ?
: 8^) and a couple of plies can happen between the original capture and
: the recapture. I verified that using the tree tracer and most of the
: extensions looked pretty clever. I was very satisfied with that
: technique and in case you didn't try it in Crafty you should consider
: it.
:
: Did you and Ken implement it in a different way ? What are the
: complications at the root ? Did I overlook something silly ?
Ken started using fractional extensions when he worked on this. In his case,
a capture simply incremented the depth by .5 plies, so that a capture/recap
would extend one whole ply. He didn't like it, although it help Win At Chess
as I recall.
The problem(s) I have with calling Evaluate() are: (1) I don't call
Evaluate() when depth > 0. It's expensive, and and (2) calling Evaluate()
can produce positional scores with a range of several pawns. This can fool
Search() into thinking there's a recapture when there's none. (3) When
you fail high (or low), but use the *old* search value, it would seem to me
(from my testing) that this both (a) triggers recapture extensions when there
was none and (b) fails to do so when they were. Suppose you just searched to
depth=9 and got a score of +1.000, but when you start 10, you fail low because
you find the pawn you were winning was a mirage. All scores will be near 0,
which would screw this up.
I tried the Berliner approach, but used the instantataneous material value as
the trigger, and didn't like it. The extension is useful to prevent a simple
move like BxN from becoming a horizon move that hides something bad, because I
have to take a ply to do the recapture. The liklihood of this happening with
"BxN over here", followed a couple of plies of moves, followed by a BxN over
there that looks like a recapture by the HiTech definition. I haven't found
any cases where this circumstance behaves like a horizon effect problem. I
simply say two successive captures of the same valued piece is a capture/
recapture and extends one ply...
:
: [ snip ]
:
: > : Maybe the two of you should work out some metric that let's you compare
: > : your SEE efficiency in the qsearch or something. I feel that this is
: > : what you are interested in Bob ?
: >
: > No. I don't think it's an issue of using SEE to weed out captures. I think
: > it's much more than that. I can cull losers (as I do) or swaps (as I used to
: > do after the first couple of plies), but that's not enough. The thing that
: > I see ripping the q-search up is two queens go on a picnic, and you see a
: > long series of Qxp Qxp Qxn Qxb Qxp Qxp ..... all of which are safe captures,
: > but none of which will ever be actually played in the game.
:
: Hm. Don't see any way to get rid of that... But you are right, if Ed is
:
Chris Whittington
But, one of my nodes is worth forty-two of your nodes.
Only joking :)
Chris Whittington
Joe Stella
>Joe Stella (jo...@ultranet.com) wrote:
>:
>: In my program, I have three counters. I do:
>:
>: 1) Nodes++; at the top of search()
>: 2) Q_nodes++; at the top of Quies()
>: 3) leaf++; when search() calls quies()
>:
>: then
>: total_nodes = Nodes + Q_nodes - leaf;
>:
>:
>: Joe Stella
>:
>:
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>Why "-leaf"? That seems to be something counted it "Nodes++;" If I were
>counting "leaf" nodes, I'd probably increment when Quiesce() doesn't find
>any capture to try.
>In any case, it seems that total_nodes=Nodes+Q_nodes should be the total?
The reason for "-leaf" is because leaf nodes get counted twice. I do
Nodes++ at the top of search(), then I find out that I have exceeded
the horizon depth so I proceed to call quies() to get the final score.
Quies then does Q_nodes++, but a move has not been made so the same
position gets counted twice (once in Nodes++ and once in Q_nodes++).
"Leaf" is actually a useful number, because it tells me how many times
quies() gets called. If I divide Q_nodes/leaf I get the average size
of the q_search tree per position.
Joe Stella
Peter W. Gillgasch
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
[ snipped description of Berliner's recapture definition ]
> Ken started using fractional extensions when he worked on this. In his
> case, a capture simply incremented the depth by .5 plies, so that a
> capture/recap would extend one whole ply. He didn't like it, although it
> help Win At Chess as I recall.
>
> The problem(s) I have with calling Evaluate() are: (1) I don't call
> Evaluate() when depth > 0.
You could. If you get a real score from that "exceptional" call to
eval() then store it in the xref. If you get just the fast evaluation it
is not expensive and in the next iteration your eval will return the
value from the xref (hopefully).
> It's expensive, and and (2) calling Evaluate() can produce positional
> scores with a range of several pawns. This can fool Search() into
> thinking there's a recapture when there's none.
Did it only directly after a capture or a promotion (by peeking at the
last move). So by definition it is a recapture then (since this
definition was choosen deliberately with having positional compensation
in mind).
> (3) When you fail high (or low), but use the *old* search value, it would
> seem to me (from my testing) that this both (a) triggers recapture
> extensions when there was none and (b) fails to do so when they were.
Hm. Interesting. Let's discuss that.
When we search to depth n we have the recapture window set to
[L(n-1), R(n-1)]
Now the n-ply search gets underway and all captures that yield an
evaluation within [L(n-1), R(n-1)] get extended.
Now let's go to the n+1 search. We set the recapture window to
[L(n), R(n)]
Assuming that the recapture window has not changed very much then the
moves we see in the n-ply part of the tree get extended as before.
What happens if the recapture window has changed drastically - that
means that the n-ply search returned with result that is significantly
different to the result of the n-1 ply search ?
Different moves get extensions now. But is this really a problem ? The
move can fall into one of the following classes:
(a) moves that were extended by the n-1 ply search but not by the
n ply search.
(b) moves that are extended by the n ply search but not by the n-1
ply search.
Nodes of category (a) should not be a major problem since we search now
one ply deeper - that is for practical purposes the same as triggering
the extension.
Nodes of category (b) should be no problem at all since by default we
assume that a deeper search does not have a negative impact on the
quality of the move selection process.
But you are right, I see a problem with category (a) moves. In the case
that you had some extensions along a line that is below a category (a)
move the following will happen in the case that none of the extensions
are triggered during the n ply search (assuming that moves 2, 4, 5 and 6
have been extended, note that it is obvious that 2 moves cannot be
extended in sequence if you look at material alone):
move sequence | plies to go in n-1 search | plies to go in n search
1 n - 1 n
2 X n - 2 n - 1
3 n - 2 n - 2
4 X n - 3 n - 3
5 X n - 3 n - 4
6 X n - 3 n - 5
7 n - 3 n - 6
Interesting. But now that I think about it the xref will handle that
since for all practical purposes we can assume that the extended results
of the n-1 ply search are not replaced by the unextended n ply search
results. Probably the whole idea wouldn't work if the xref didn't help
out. What do you think ?
> Suppose you just searched to depth=9 and got a score of +1.000, but when
> you start 10, you fail low because you find the pawn you were winning was
> a mirage. All scores will be near 0, which would screw this up.
I don't think that this is a major problem. Ok we get some additional
extensions in that case during the re-search. Question is would we have
seen that the win of material was a mirage without having the extension
in the first place ? The additional extensions during the re-search are
then of course triggered in the wrong part of the tree since your
hypothesis that you win a pawn has vanished into thin air. But since you
cannot know that in advance... It is only a heuristic.
> I tried the Berliner approach, but used the instantataneous material value
> as the trigger, and didn't like it.
I tried that as well and didn't like too much altough it was better than
having only check extensions. Basically it was too restrictive for me.
> The extension is useful to prevent a simple move like BxN from becoming a
> horizon move that hides something bad, because I have to take a ply to do
> the recapture. The liklihood of this happening with "BxN over here",
> followed a couple of plies of moves, followed by a BxN over there that
> looks like a recapture by the HiTech definition. I haven't found any
> cases where this circumstance behaves like a horizon effect problem. I
> simply say two successive captures of the same valued piece is a capture/
> recapture and extends one ply...
But doesn't that lead to extensions in the "proof" parts of the tree as
well? What I like about the Hitech idea is that it restricts the
extensions only to that parts of the tree that seems to contain a
possible pv while your idea extends even lines that are completely
loopsided if the description above is really complete (?).
-- Peter
D Kirkland
I just increase my node count after every call to makemove.
This seems pretty simple to me...?
Yes, this will count nodes that are not legal, but so what!
They are still nodes visited by the search.
I am not yet using nullmoves, so this part is not a problem.
Seeing that a nullmove is a skipped turn, it would seem that
it should not be counted. But, as it is scored and can have
a cutoff (much like any other move), I think that it should
be counted as a node...
It seems to me that the basic idea of a node is when a move
is made. Is this wrong?
Yes, I understand that nullmoves and such can be kind of a
grey area. But with nullmoves, as they are treated pretty
much like other moves, they should be counted, no?
dan