searching: nodes per second
Moderators: hgm, Rebel, chrisw
searching: nodes per second
I would like to know if there is a standard way of measuring nodes per second. For example, are transposition moves also considered? I would think that only moves that are actually searched (i.e. move is played, move generator called, etc.) are counted. And do all top programs (Fritz, Shredder, Junior, etc.) measure engine speed in the same manner?
-
- Posts: 3562
- Joined: Thu Mar 09, 2006 3:54 am
- Location: San Jose, California
Re: searching: nodes per second
I think that you got it right. Only the moves that are actually made are counted.
Bill
Bill
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: searching: nodes per second
Ther is no standard way, as not all engines work the same way. Some probe the transposition table before making a move, others after it. Most usual is counting calls to Search(), irrespective of what Search() then actually does. Some times it will generate moves, but often it will not, because null move or stand pat (or hash probe) will produce a cutoff. If a node does IID, should it count each iteraton as a node? In micro-Max I do that, as micro-Max also runs the move generator anew for each iteration.
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: searching: nodes per second
I think you should count nodes in a manner that makes sense to your own program. I am guessing that even in your program, there are different types of nodes - some one is more expensive than others. If that is the case, then your "nodes per second" is really "average nodes per second" (average of X types of nodes).G. Hensel wrote:I would like to know if there is a standard way of measuring nodes per second. For example, are transposition moves also considered? I would think that only moves that are actually searched (i.e. move is played, move generator called, etc.) are counted. And do all top programs (Fritz, Shredder, Junior, etc.) measure engine speed in the same manner?
What is the purpose of this NPS for you? If you want to know how fast your engine is, I suggest that you run a profiler. That way you will really know how fast each of your functions is, how many times they are executed, and which section of code takes the most time.
The only time that statistics become the same for engines is when they are all written in the same way, and that I think is counter to progress.
Cheers...
Re: searching: nodes per second
You've guessed right that I want to know how fast my engine (still in development, btw) does its search.
About the profiler, I may have done the hard way, as I wrote code to do just that, count # of calls for any given function and how much cumulative 'execution' time for that particular function (taking into account overhead of doing the actual measurement).
I'm not sure what you mean by different "type" of nodes. I see a node as a position in the search tree, where search goes from one node to the next, and then back using say, make_move() and take_back_move() functions. I would guess that not all positions (or nodes) that are transpositions end up being searched..
So I would like to know how fast my 'program' is doing a search, in comparison with other programs, to get an idea of how efficient is the code I've written (especially since I do not use the same data structures as most, i.e. 0x88 for storing a position).
I just find it hard to believe that a program (say Fritz) running on a PC with a single CPU can search 3 or 4 million positions per second, knowing what types of instructions are needed to generate moves, evaluate a position, etc. My guess is that they also include transpositions in the NPS value.
About the profiler, I may have done the hard way, as I wrote code to do just that, count # of calls for any given function and how much cumulative 'execution' time for that particular function (taking into account overhead of doing the actual measurement).
I'm not sure what you mean by different "type" of nodes. I see a node as a position in the search tree, where search goes from one node to the next, and then back using say, make_move() and take_back_move() functions. I would guess that not all positions (or nodes) that are transpositions end up being searched..
So I would like to know how fast my 'program' is doing a search, in comparison with other programs, to get an idea of how efficient is the code I've written (especially since I do not use the same data structures as most, i.e. 0x88 for storing a position).
I just find it hard to believe that a program (say Fritz) running on a PC with a single CPU can search 3 or 4 million positions per second, knowing what types of instructions are needed to generate moves, evaluate a position, etc. My guess is that they also include transpositions in the NPS value.
-
- Posts: 388
- Joined: Wed Mar 08, 2006 10:08 pm
Re: searching: nodes per second
In Thinker, for example, Search nodes are far more expensive than QSearch nodes.G. Hensel wrote:You've guessed right that I want to know how fast my engine (still in development, btw) does its search.
About the profiler, I may have done the hard way, as I wrote code to do just that, count # of calls for any given function and how much cumulative 'execution' time for that particular function (taking into account overhead of doing the actual measurement).
I'm not sure what you mean by different "type" of nodes. I see a node as a position in the search tree, where search goes from one node to the next, and then back using say, make_move() and take_back_move() functions. I would guess that not all positions (or nodes) that are transpositions end up being searched..
So I would like to know how fast my 'program' is doing a search, in comparison with other programs, to get an idea of how efficient is the code I've written (especially since I do not use the same data structures as most, i.e. 0x88 for storing a position).
I just find it hard to believe that a program (say Fritz) running on a PC with a single CPU can search 3 or 4 million positions per second, knowing what types of instructions are needed to generate moves, evaluate a position, etc. My guess is that they also include transpositions in the NPS value.
In a very short profile run, here is what I get:
- the Search function gets called 120445 times, and consumed 5.11% of the run-time
- the QS function gets called 33762437 times (280X the Search calls), and yet only consumed 3.23% of the run-time.
So, it matters what happens after you do a MakeMove(). If that is intended to make a recursive call to Search(), then that is an expensive node.
Another example is, if you decide to add checking moves in you QS, you might suddenly see a huge increase in your NPS, because now you get more QS nodes, and QS nodes are cheap. But that is really deceiving.
-
- Posts: 228
- Joined: Sun Mar 12, 2006 3:11 pm
Re: searching: nodes per second
I thought a node was a successor position in the search tree, irrespective of how you get a value for the new position and return from that node (other than abort). So transposition hits (returning a value for the position without searching the tree and making more nodes) would count in this scheme, for example.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: searching: nodes per second
Most commercial authors just toy something with their nps.G. Hensel wrote:I would like to know if there is a standard way of measuring nodes per second. For example, are transposition moves also considered? I would think that only moves that are actually searched (i.e. move is played, move generator called, etc.) are counted. And do all top programs (Fritz, Shredder, Junior, etc.) measure engine speed in the same manner?
Junior is known for also counting moves they futile skip. Tiger was known for just counting a part of what it actually searched. Fritz for years kept secret the nps it got, "as that was our biggest secret", to quote Frans.
Rybka decided to follow Fritz approach it seems and just shows some garbage number that has not even a close relation to its nps.
Zappa without evaluation function gets to 3.3 mln nps at an opteron 2.2Ghz in 64 bits, so Rybka will be close to that actually.
For diep currently showing its nps is easy, i just count what i search, but as i already detect repetitions early on, and illegal moves diep also detects early on, so i'm not so sure i count them (as i don't even search them).
So that would make diep's nps quite a tad higher, up to 50% in some positions when i would count it like Bob does.
Additionally is the fast searcher idea i've got. That searcher is at millions of nps a node, whereas diep is something like 200k nps at a core2 2.4Ghz (single core).
If i combine them together i do not actually know what to count to be honest. Internal i have 2 counts of course. I know the average goes to roughly 700k-900k nps then (single core). So i'm not sure which of the 2 npses to show or an average then.
Vincent
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: searching: nodes per second
Symbolic counts a node:
1) The move is generated (only legal moves are generated)
2) The move is executed and the position state is fully updated
3) Analysis
4) Subtree processing (charged to subtree nodes)
5) The move is retracted and the position state is fully restored
Without steps 3 and 4, the program has an early opening node frequency of about 3.2 MHz per thread on a 2.66 GHz Intel Xeon.
Here's the list of variables in Symbolic's position class that are fully valid at each node:
1) The move is generated (only legal moves are generated)
2) The move is executed and the position state is fully updated
3) Analysis
4) Subtree processing (charged to subtree nodes)
5) The move is retracted and the position state is fully restored
Without steps 3 and 4, the program has an early opening node frequency of about 3.2 MHz per thread on a 2.66 GHz Intel Xeon.
Here's the list of variables in Symbolic's position class that are fully valid at each node:
Code: Select all
Man manv[SqLen]; // 0: SqA1, 1: SqB1, ... 7: SqH1, ... 63: SqH8
Color good; // Active color
Color evil; // Passive color
ui cabs; // Castling bits (bit 0: WK, bit 1: WQ, bit 2: BK, bit 3: BQ)
Sq epsq; // En passant target square
ui hmvc; // Half move counter
ui fmvn; // Full move number
BB merge; // All men merged
BB sweep; // Sweeper men merged (bishops, rooks, queens)
BB locbm[ManRCLen]; // Locus by man
BB locbc[ColorRCLen]; // Locus by color
BB atkbc[ColorRCLen]; // Attacked by color
BB atkfs[SqLen]; // Attacks from a square
BB atkts[SqLen]; // Attacks to a square
ui mcbm[ManRCLen]; // Man count by man (up/dn)
ui mcbc[ColorRCLen]; // Man count by color (up/dn)
Sq ksbc[ColorRCLen]; // King squares by color (up/dn)
est rmbc[ColorRCLen]; // Raw material total by color (up/dn)
ui pdbc[ColorRCLen]; // Piece distribution signatures (up/dn)
hst aphs; // All position data HS (up/dn) (also saved in PPD)
hst pshs; // Pawn structure HS (up/dn)
hst mdhs; // Material distribution HS (up/dn)
BB pmbb; // Pinned man bitboard (PPD saved/restored)
BB fmbb; // Frozen man bitboard (PPD saved/restored)
bool inch; // In check status (PPD saved/restored)
PPDStack hist; // Preserved Position Data autosizing history stack