Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old August 9th 07, 10:38 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jun 2007
Posts: 23
Default 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,
  #2   Report Post  
Old August 10th 07, 01:10 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default Difference between node and leaf in tree

Macchess 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!
  #3   Report Post  
Old August 10th 07, 07:23 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2007
Posts: 188
Default 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.
  #4   Report Post  
Old August 10th 07, 12:01 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default Difference between node and leaf in tree

JohnnyT 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!
  #5   Report Post  
Old August 11th 07, 09:54 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jun 2007
Posts: 23
Default 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


  #6   Report Post  
Old August 11th 07, 11:43 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default Difference between node and leaf in tree

Macchess 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!
  #7   Report Post  
Old August 12th 07, 12:44 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 1,305
Default 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
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/
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 01:42 PM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017