How do you count nodes?

[Don]

I can't seem to find any standard on how to count nodes correctly. In our engine we count nodes at the top of the search function. The problem with this is that when you have a lot of search calls inside the search function itself without making a move (IID, Singular Extension, ProbCut, Nullmove Verification, Razoring Verification, etc) it will artificially bloat the node count. In my opinion this is not accurate.

There are other ways that I could think of. Next method of counting nodes is to count the number of makeMove calls. The problem with this is that there are engines like ours that prune moves before calling makeMove. So we have tried a move and prune it and it was not counted as nodes. This also seem not accurate in my opinion.

Another method is to count the number of moves tried inside the search move loop. This will include moves that are pruned before makeMove function is called. This seems to be accurate to me, but I'm not sure if this is the correct definition of a node. When we implement this on our engine, the NPS seems to double based on the starting position.

Which do you think is the correct one? How do you count nodes in your engine?

I actually count nodes encountered in the search. A node is a position. A move creates a new position or "node." So when you make a move you encounter a new node and you add it to the tally.

There is the terminology "nodes searched" which implies that you don't count a node unless a search springs from it. I don't subscribe to that definition as I don't think it's meaningful.

There is also the terminology "evaluations per second" which implies that you count how many static evaluation calls - presumably this would include lazy evaluation too. Komodo sometimes makes a move and does not evaluate it but I still count it as a node.

I like my definition because it's easy to explain and implement with no ambiguity so you can call it, "nodes encountered." I think it is a sensible definition. I wish all programs would standardize on something, regardless of what it is but that is not likely to happen.

Hi Don, how about a move pruned before making the move resulting to a new position? Do you consider it as a node? Is it required for the makeMove call in Komodo to consider a move a new node?

In Komodo the move has to actually be called via "make()" to be counted. However there is a good argument for counting those moves too. Sometimes you prune a move before making it by doing a significant amount of work up-front. Near leaf nodes we prune a lot of moves without making them, but before doing so we perform a significant amount of work and it almost seems unfair not to get to count it. It's semantics. You could say without exaggeration that the resulting node was "looked at" or "considered."

But if you do that, you could also count losing captures in the quies search and that doesn't quite seem right either - so I prefer to do the most straightforward thing and just count moves actually made.

I hope that all programs also implement the same method on counting nodes. I'm thinking to implement something like MTPS (moves tried per second). This is what Crafty is already doing if I am not mistaken. This seems to be the most accurate.

[Edsel Apostol]

I can't seem to find any standard on how to count nodes correctly. In our engine we count nodes at the top of the search function. The problem with this is that when you have a lot of search calls inside the search function itself without making a move (IID, Singular Extension, ProbCut, Nullmove Verification, Razoring Verification, etc) it will artificially bloat the node count. In my opinion this is not accurate.

There are other ways that I could think of. Next method of counting nodes is to count the number of makeMove calls. The problem with this is that there are engines like ours that prune moves before calling makeMove. So we have tried a move and prune it and it was not counted as nodes. This also seem not accurate in my opinion.

Another method is to count the number of moves tried inside the search move loop. This will include moves that are pruned before makeMove function is called. This seems to be accurate to me, but I'm not sure if this is the correct definition of a node. When we implement this on our engine, the NPS seems to double based on the starting position.

Which do you think is the correct one? How do you count nodes in your engine?

I actually count nodes encountered in the search. A node is a position. A move creates a new position or "node." So when you make a move you encounter a new node and you add it to the tally.

There is the terminology "nodes searched" which implies that you don't count a node unless a search springs from it. I don't subscribe to that definition as I don't think it's meaningful.

There is also the terminology "evaluations per second" which implies that you count how many static evaluation calls - presumably this would include lazy evaluation too. Komodo sometimes makes a move and does not evaluate it but I still count it as a node.

I like my definition because it's easy to explain and implement with no ambiguity so you can call it, "nodes encountered." I think it is a sensible definition. I wish all programs would standardize on something, regardless of what it is but that is not likely to happen.

Hi Don, how about a move pruned before making the move resulting to a new position? Do you consider it as a node? Is it required for the makeMove call in Komodo to consider a move a new node?

In Komodo the move has to actually be called via "make()" to be counted. However there is a good argument for counting those moves too. Sometimes you prune a move before making it by doing a significant amount of work up-front. Near leaf nodes we prune a lot of moves without making them, but before doing so we perform a significant amount of work and it almost seems unfair not to get to count it. It's semantics. You could say without exaggeration that the resulting node was "looked at" or "considered."

But if you do that, you could also count losing captures in the quies search and that doesn't quite seem right either - so I prefer to do the most straightforward thing and just count moves actually made.

I hope that all programs also implement the same method on counting nodes. I'm thinking to implement something like MTPS (moves tried per second). This is what Crafty is already doing if I am not mistaken. This seems to be the most accurate.

Thanks for the input Don. It seems you are doing it the same as SF. Might explain the low NPS. If we are going to implement the same with Hannibal, we are around the same NPS also.

I'm now curious as to how Critter is counting nodes . It seems to show a very high NPS. The engine that is counting makeMove calls only and is still very fast is Gull.

[rvida]

I'm now curious as to how Critter is counting nodes.

Incrementing the counter at the top of search() and qsearch() functions. Nodes where IID occurs are counted twice. Making a move but not recursing does not count.

[Don]

I'm now curious as to how Critter is counting nodes.

Incrementing the counter at the top of search() and qsearch() functions. Nodes where IID occurs are counted twice. Making a move but not recursing does not count.

Making a move and counting it as a new node should give higher node counts, not lower node counts as Edsel implies. If I make a move and not recurse, it still counts as a node.

There could be a difference for some programs based on how a search is structured. Socrates worked like this, leaving out most of the details:

int search( position p, move_t mv )

The very first thing that happened was that you created a new node by applying the specified move. That was more convenient for the parallel search and i think if I counted nodes at the top of the search it would be equivalent to counting when a move is made.

Some programs count end nodes only. The old programs had much larger branching factors and this didn't make much difference but nowadays that would reduce the counts significantly.

[Kempelen]

I have found an issue when not counting nodes at the top of the search.

Usually people put a time-control at the top of the search like:

Code: Select all

#define CONTROL 16383

search {

if (nodes & CONTROL) {
     see if time reached.....
}

...

if you increment the nodes variable at makemove, it could happen that if you do a prunning this check could not happen at that particular situation, so you will have to wait for the next 16383 iteration to do the time-check, an again, if that particular node is a prunning without visiting a real tree node, again the time check is not executed. Same in a row could happen...., more for aggresive prunning engines.

This could seen as no important, as 16383 node loop run quick fast, but it could be of importance in very fast games (and of course the value for CONTROL is important also)

I dont know if make-prunning-unmoke node counter people take this into account and how they deal with it, or if they consider this as no important.

[Don]

I do the same thing but I use a separate counter for that. Something like this:

if ( ++tics & TC_RESOLUTION_MASK ) {
time control stuff ....
}

I have found an issue when not counting nodes at the top of the search.

Usually people put a time-control at the top of the search like:

Code: Select all

#define CONTROL 16383

search {

if (nodes & CONTROL) {
     see if time reached.....
}

...

if you increment the nodes variable at makemove, it could happen that if you do a prunning this check could not happen at that particular situation, so you will have to wait for the next 16383 iteration to do the time-check, an again, if that particular node is a prunning without visiting a real tree node, again the time check is not executed. Same in a row could happen...., more for aggresive prunning engines.

This could seen as no important, as 16383 node loop run quick fast, but it could be of importance in very fast games (and of course the value for CONTROL is important also)

I dont know if make-prunning-unmoke node counter people take this into account and how they deal with it, or if they consider this as no important.

[Edsel Apostol]

I'm now curious as to how Critter is counting nodes.

Incrementing the counter at the top of search() and qsearch() functions. Nodes where IID occurs are counted twice. Making a move but not recursing does not count.

Making a move and counting it as a new node should give higher node counts, not lower node counts as Edsel implies. If I make a move and not recurse, it still counts as a node.

There could be a difference for some programs based on how a search is structured. Socrates worked like this, leaving out most of the details:

int search( position p, move_t mv )

The very first thing that happened was that you created a new node by applying the specified move. That was more convenient for the parallel search and i think if I counted nodes at the top of the search it would be equivalent to counting when a move is made.

Some programs count end nodes only. The old programs had much larger branching factors and this didn't make much difference but nowadays that would reduce the counts significantly.

There are I think two kinds of engine:

Type A: checks if the move is legal or gives check to the King before "makeMove", capability to prune moves before doing "makeMove"

Type B: checks for legality and if the move gives check after making the move, "makeMove' should be called before they could decide to prune, counts moves where the king can be captured

For Type A engines, counting nodes at the top of the search is faster than counting "makeMove" as there are some some calls to the search function inside the search function itself that counts the same node more than once (IID, Singular Extension, ProbCut, etc).

For Type B engines, counting "makeMove" seems faster compared to at the top of the search as it counts pruned moves (pruned moves is geater in number compared to internal search calls like IID, etc), it also counts moves that leaves the king to be captured

So we have:

1. Type A (count nodes at top of search)
2. Type A (count "makeMove")
3. Type B (count nodes at top of search)
4. Type B (count "makeMove")
5. Type A (count "makeMove" + pruned moves)

The one that will produce the fastest NPS in descending order:

5 - (I'm not aware of any engine doing this, though it basically counts the same moves as 4 below, just more accurate and faster)
4 - (method in Crafty)
3 and 1- (1 is the most common method: Hannibal, Critter, etc..)
2 - (method in Stockfish)

[Aleks Peshkov]

if you increment the nodes variable at makemove, it could happen that if you do a prunning this check could not happen...

From OOP point of view makemove() should accept only Position and Move objects. Counting nodes should be a Search object responsibility, as identical Positions with different node counts should be considered identical.

Conceptually it does not matter whether objects are actual objects or just a bunch of global functions and global data.

[bob]

I can't seem to find any standard on how to count nodes correctly. In our engine we count nodes at the top of the search function. The problem with this is that when you have a lot of search calls inside the search function itself without making a move (IID, Singular Extension, ProbCut, Nullmove Verification, Razoring Verification, etc) it will artificially bloat the node count. In my opinion this is not accurate.

There are other ways that I could think of. Next method of counting nodes is to count the number of makeMove calls. The problem with this is that there are engines like ours that prune moves before calling makeMove. So we have tried a move and prune it and it was not counted as nodes. This also seem not accurate in my opinion.

Another method is to count the number of moves tried inside the search move loop. This will include moves that are pruned before makeMove function is called. This seems to be accurate to me, but I'm not sure if this is the correct definition of a node. When we implement this on our engine, the NPS seems to double based on the starting position.

Which do you think is the correct one? How do you count nodes in your engine?

I count "MakeMoves()" today. I used to just increment a counter at the top of search or quiesce, but once you start to use forward pruning, that understates the effort. If you make a move, then use some sort of static (or dynamic) criteria to decide when a move should just be skipped, you have to unmake the move and then move on. That's a make/unmake which creates a brand new position that you choose to not search. In classic AI theory, making a move traverses an arc in the tree and leads to a new node. I decided to count those.

In our case, we already have checked the legality of the move, we already have determined if the move gives check, so we could already prune moves before even calling the makeMove() function. Can we consider the moves being pruned as a node even though we have not called "makeMove()"?

I am not sure there is a "correct" answer. For me, Make/Unmake/legality check (which is done after Make) is a significant amount of effort. And since a node is defined by following an arc from another node, and the arc is a result of updating the position P to P' by making a move, I chose to count the way I do to include the "overhead of making a move" and counting that as a node so that I get an accurate estimate of "what does it cost to search a single node?"

Even though Crafty just counts the MakeMoves() function calls as I've described in the second method, it basically falls on the third method where it counts all the moves being played inside the search move loop. This seems to be the most accurate. Though if we are going to use this way of counting in our engine, our NPS would be more or less doubled, helped by the fact that pruned moves doesn't need make/unmake (though we spent effort in checking legality and if the moves gives check without actually doing a makeMove).

I don't think it matters, every program is so different that comparing NPS, or total nodes searched, or anything else, is a misnomer at best. It'd be nice if for a given position, given depth (say no possible extensions available) that every program searches a tree of the same size. But that is what makes programs different...

Method 1 (We are currently doing this in Hannibal):

Code: Select all

int search(position, alpha, beta, depth) {
    nodes++;
    ...
    score = search(position, alpha, beta, depth/2); // IID, counts extra nodes even though the position is the same (same node)
    ...
    move loop { // already checks for legality and checking moves
        if (move_is_prunable) continue; // pruned moves not counted
        makeMove();
        score = -search(position, -beta, -alpha, depth-1);
        unmakeMove();
    }
}

Method 2 (what Stockfish is doing as Marco described, this gives the slowest NPS):

Code: Select all

int search(position, alpha, beta, depth) {
    ...
    move loop { // already checks for legality and checking moves
        if (move_is_prunable) continue; // pruned moves not counted
        makeMove();
        nodes++;
        score = -search(position, -beta, -alpha, depth-1);
        unmakeMove();
    }
}

Method 3 (This is the category where Crafty falls):

Code: Select all

int search(position, alpha, beta, depth) {
    ...
    move loop { // checks legality and if move gives check after doing the move
        makeMove();
        nodes++;
        if (move_is_prunable) { // pruned moves are already counted 
            unmakeMove();
            continue;
        }
        score = -search(position, -beta, -alpha, depth-1);
        unmakeMove();
    }
}

Method 4 (This method makes our NPS count double, basically the same as Method 2 except that we count pruned moves, almost basically the same as Method 3 (where all moves inside the move loop is counted) except that this one doesn't call make/unmake before pruning the move, this gives the fastest NPS):

Code: Select all

int search(position, alpha, beta, depth) {
    ...
    move loop { // already checks for legality and checking moves
        nodes++;
        if (move_is_prunable) continue; // pruned moves are already counted
        makeMove();
        score = -search(position, -beta, -alpha, depth-1);
        unmakeMove();
    }
}

[yoshiharu]

Usually people put a time-control at the top of the search like:

Code: Select all

#define CONTROL 16383

search {

if (nodes & CONTROL) {
     see if time reached.....
}

...

I have slightly different approach: I have a separate counter that I increase every time I increase node_count, then I do the following

Code: Select all

if ( separate_count>CONTROL) {
    separate_count=0;
    ... check time control ...
}

The price is having a(nother) global variable to take care of, but I didn't see any appreciable slowdown when I first introduced this.