searching: nodes per second

[G. Hensel]

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?

[Bill Rogers]

I think that you got it right. Only the moves that are actually made are counted.
Bill

[hgm]

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.

[CThinker]

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?

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).

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...

[G. Hensel]

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.

[G. Hensel]

Sorry, I meant to reply to Lance P.

[CThinker]

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 Thinker, for example, Search nodes are far more expensive than QSearch nodes.

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.

[frankp]

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.

[diep]

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?

Most commercial authors just toy something with their nps.

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

[sje]

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:

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