| |
Main
Date: 09 Aug 2007 21:38:42
From: Macchess
Subject: Difference between node and leaf in tree
|
Dear all,
What is considered a node, and what is considered a leaf in AB search?
Common sense would be that all but the last level where the evaluation
is taking place is considered a node. And the last level, when you do
not search any deeper, is a leaf.
So when to calculcate NPS, you end much less than when calculating leafs.
Secondly, when calculating Quiescence search, is each position reached
considered a node?
We have some open source programs where we can verify in the code. How
is Schredder, Hiarcs, Fritz etc doing this calculation.
Thanks,
|
|
| |
Date: 10 Aug 2007 01:10:02
From: David Richerby
Subject: Re: Difference between node and leaf in tree
|
Macchess <[email protected] > wrote:
> What is considered a node, and what is considered a leaf in AB
> search?
Everything in the tree is a node. A node that has no children is a
leaf.
> So when to calculcate NPS, you end much less than when calculating
> leafs.
>
> Secondly, when calculating Quiescence search, is each position
> reached considered a node?
>
> We have some open source programs where we can verify in the code.
> How is Schredder, Hiarcs, Fritz etc doing this calculation.
Who cares? Nodes per second isn't a good way to measure engines'
performance relative to each other. Some engines will look at a lot
of nodes relatively superficially; others will spend a long time on
each node but make sure they consider only the important nodes.
Dave.
--
David Richerby Aluminium Tree (TM): it's like a tree
www.chiark.greenend.org.uk/~davidr/ that's really light!
|
| | |
Date: 11 Aug 2007 08:54:09
From: Macchess
Subject: Re: Difference between node and leaf in tree
|
David Richerby a �crit :
> Everything in the tree is a node. A node that has no children is a
> leaf.
Does this mean that if you do not generate any moves from a position, it
is not counted as a node? And as long as you generate moves, even in PV
only, it is counted as a node?
> Who cares? Nodes per second isn't a good way to measure engines'
> performance relative to each other.
Well I do. I tend to believe that each level deeper gives you an
additional 30-40 elo, at least at sub-1800 levels. I have a highly
unoptimized move generator, and I would like to compare that if I switch
to e.g. bitboards to gain some additional speed, how much in nodes this
represent. I have at this moment about 10000-30000 NPS (not calculating
leafs). I have the figures on the same machines for other programs. So
I wonder if optimizing would be worth trying or if I should re-design.
The NPS is a good measure on how good my optimization is compared to
e.g. crafty.
Secondly, I run the same program on Core 2 duo with GCC, Core 2 extreme
with VC8 and Pentium III-1Ghz with BCB. So being able to extrapolate
is always helpful.
Best regards,
Yves
|
| | | |
Date: 11 Aug 2007 11:43:48
From: David Richerby
Subject: Re: Difference between node and leaf in tree
|
Macchess <[email protected] > wrote:
> David Richerby a �crit :
>> Everything in the tree is a node. A node that has no children is a
>> leaf.
>
> Does this mean that if you do not generate any moves from a
> position, it is not counted as a node? And as long as you generate
> moves, even in PV only, it is counted as a node?
If you don't generate moves from a position, it's a leaf. Leaves are
in the tree. Everything that is in the tree is a node.
>> Who cares? Nodes per second isn't a good way to measure engines'
>> performance relative to each other.
>
> Well I do. I tend to believe that each level deeper gives you an
> additional 30-40 elo, at least at sub-1800 levels.
The move generator probably isn't all that significant. Evaluation is
likely to be taking up much more time.
> I have a highly unoptimized move generator, and I would like to
> compare that if I switch to e.g. bitboards to gain some additional
> speed, how much in nodes this represent.
Fair enough. That's a legitimate use for NPS. But it doesn't really
matter what you count as a node, as long as you're consistent.
> I have at this moment about 10000-30000 NPS (not calculating leafs).
> I have the figures on the same machines for other programs. So I
> wonder if optimizing would be worth trying or if I should re-design.
> The NPS is a good measure on how good my optimization is compared to
> e.g. crafty.
No it isn't. The NPS is only a reasonable measure of how good your
optimization is compared to previous versions of you program. For
example, take your copy of Crafty and change it so that the evaluation
function just returns material. Suddenly, you'll see that crafty is
doing many, many more nodes per second and playing worse. NPS is
meaningless between different engines.
Even between versions of the same engine, it doesn't mean all that
much. For example, adding a transposition table will *decrease* the
NPS (because it takes time to look things up in the TT) but will
increase the performance of the engine (because it decreases
repetition in the search).
For a long time, now, computer chess programmers have been focussing
on pruning as a way to make chess engines go faster, not on increasing
NPS. Of course, because many people think NPS is significant, they
presumably count absolutely everything as a node, to make the number
as big as possible.
> Secondly, I run the same program on Core 2 duo with GCC, Core 2
> extreme with VC8 and Pentium III-1Ghz with BCB. So being able to
> extrapolate is always helpful.
Sure. But, again, it doesn't matter what you count as a node for
these purposes, as long as you're consistent.
Dave.
--
David Richerby Disposable Sumerian Chair (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a chair that's really old but
you never have to clean it!
|
| | | | |
Date: 11 Aug 2007 18:44:39
From: Kenneth Sloan
Subject: Re: Difference between node and leaf in tree
|
Some people like to count "Nodes Expanded", rather than "Nodes
Created". This sometimes depend on how their node expansion works.
"Nodes Evaluated" is yet another choice - neither the same as "Nodes
Expanded" nor "Nodes Created".
And some count them all...
Before comparing "nps" across programs, be sure what it stands for.
--
Kenneth Sloan [email protected]
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/
|
| | |
Date: 09 Aug 2007 23:23:59
From: JohnnyT
Subject: Re: Difference between node and leaf in tree
|
David Richerby wrote:
> Who cares? Nodes per second isn't a good way to measure engines'
> performance relative to each other. Some engines will look at a lot
> of nodes relatively superficially; others will spend a long time on
> each node but make sure they consider only the important nodes.
It does provide one interesting metric. Not in program to program
comparison, but in general hardware to hardware comparison.
It is helpful to see how a program scales on various hardware platforms.
And while it is not at all clear what the ELO - KNPS relationship is,
even within a given program, it is a fairly strongly held belief that
more KNPS == more ELO strength. Especially, at faster clock speeds, and
possibly more importantly, and standard analysis speeds. The better the
answer the quicker the time, the better.
Similarly priced machines can have significant differences in KNPS
because of a large variety of issues. If this is generally important
to you, this is a useful figure.
Penis Measurement has ALWAYS been important.
|
| | | |
Date: 10 Aug 2007 12:01:45
From: David Richerby
Subject: Re: Difference between node and leaf in tree
|
JohnnyT <[email protected] > wrote:
> David Richerby wrote:
>> Who cares? Nodes per second isn't a good way to measure engines'
>> performance relative to each other. Some engines will look at a lot
>> of nodes relatively superficially; others will spend a long time on
>> each node but make sure they consider only the important nodes.
>
> It is helpful to see how a program scales on various hardware
> platforms.
Yes, it's useful for that, which I should probably have mentioned as
an aside.
Dave.
--
David Richerby Miniature Book (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ romantic novel but you can hold in it
your hand!
|
|
