How do you count nodes?

[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?

[Mincho Georgiev]

I do it just like you at this stage. Count them all. Counting makemove could be wrong due to the fact that this move wouldn't raise a search at all if it gets pruned.

[hgm]

In micro-Max I count iterations of the IID loop. (And IID is done in every node, starting below QS level and deepening in steps of 1.)

In my other engines I count at the top of Search. But in Joker and Spartacus I probe the hash for a node before calling Search, so nodes that produce a hash hit will not be counted. In the loop over moves I call Search recursively only once for every move. But in cases of IID the loop over moves can be executed several times.

[mcostalba]

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

Glaurung counted at the top of the search, but this gives a number higher then reality for the reasons you well explained.

Currently we count inside do_move(), that is your makeMove(), as expected we have a lower node count but this is not a problem it was done so because SMP code got simplified given that is a bit tricky to count nodes when multiple threads are running.

Third way is an hybrid way that does not make a lot of sense to me. What we print in output as labeling of the number is "nodes searched" so that you'd are suppose changing position with a makeMove() to actually account for a new node, not just to generate the move.

I have to say that in SF all the pruning, including legality check, is done _before_ the do_move() call so that after a do_move() you are assured to always call also the next search() function.

[jhaglund]

How I like think of it is like a node in a computer network topology. Each branching computer would be a node as to each node in a tree making a pv line.

http://en.wikipedia.org/wiki/Node_(networking)

For me, only the computers turned on would be counted.
10 minutes later, a bunch of computers turn off, and new ones turn on, count whatever is on.

[Evert]

I count as one node every time I make a move, with one exception: I don't count nodes where the player who just moved is in check (which means the node is illegal).
In other words, I cound all nodes where I "do work". In the case of IID, that means I count "double", but I think this is correct, since I'm doing work in both cases.

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

[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 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()"?

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

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();
    }
}

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

[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?

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.