Nodes and NPS

[Pedro Castro]

I have doubts like I should count the number of nodes. I have seen some programs that they add 1 node every time that they enters in the serach and also 1 node every time that they enters in the qsearch, me, I up to now in my program I had also this way.

In the last version, I have changed the system, count the nodes after the function makemove (), as much in the search as in the qsearch, the result is that now my program has half of nps, before approximately 1.000.000, now approximately 500.000, I was always missed that big it was my nps, more considering that my move generator is based on a board of 64 elements, without using mailbox, 0x88, bitboard, etc (firstchess).

Even, among the programs pointers there is a lot of difference, 400.000 for shredder, 1.000.000 for Fritz or without speaking of Rybka that doesn't arrive at the 100.000 in my system (maybe Rybka no count nodes in qsearch)

So I suppose that it is complicated to unify approaches. But which the most correct form that you think?

[H.G.Muller]

Count the number of evaluations, or the number of times you run the move generator. Nodes that you visit without doing anything are not really visited.

When I count for timing purposes, I count the number of times the IID loop is run. That correlates quite well with execution time.

It all depends what you want to use the count for. If it is just to gauge your own speed compared to earlier versions that count in the same way, it does not matter much.

[YvesLejeail]

I agree with H.G suggestion . I think the "perft" way to count nodes is very nice, since it could be seen as a reference, and to obtain it in the Alpha-Beta algorithm, just count one node at the place you call the Quiescence (though you don't call it in a perft test, hope you understand what I mean). This way you obtain the normal nodes generated (the leaf nodes)...
But there could be other "definitions", since inside the Quiescence, each nodes takes time to evaluate. Counting also the nodes when you call the eval
in the Quiescence search will be an other definition, doubling the nodes, as you said.
Personnally I count Alpha_Beta and Quiescent nodes in different counters,
I don't think there is a norm, except maybe the generated leaf nodes suggested by H.G. ...
Yves

[Sven Schüle]

Nodes that you visit without doing anything are not really visited.

Hi,

a node which you visit is a node that should always count in my opinion. You never do "nothing" at a node. Either the position is illegal, or it is a final position, or you detect a trivial draw, or you skip the subtree by hash table lookup, or you do whatever can be done to avoid expanding the subtree.

In all of these cases your program knows at least a very tiny little bit about the node, and that's why each node should count. For me this includes to count qsearch nodes, too. Counting eval calls only, or IID calls, or leaves of the full search produces different numbers which should also be called differently.

It all depends what you want to use the count for. If it is just to gauge your own speed compared to earlier versions that count in the same way, it does not matter much.

I can fully support this. I think many people probably use their NPS numbers to judge about their code changes and compare subsequent versions of their own engine ("if I apply this and that pruning I save 2% nodes but my NPS drops by 4%"). So NPS may be a very personal thing.

Nevertheless NPS comparison between different engines is done sometimes, and I think it may be helpful to have a kind of standard here, although NPS does not stand alone. Other numbers like percentage of QS nodes, branching factor or hash table hit rate will probably be used together with NPS for "serious" comparison of engines.

Sven

Edit: And not to forget the ELO