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?
How do you count nodes?
Moderators: hgm, Rebel, chrisw
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: How do you count nodes?
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How do you count nodes?
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.
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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: How do you count nodes?
Glaurung counted at the top of the search, but this gives a number higher then reality for the reasons you well explained.Edsel Apostol wrote: Which do you think is the correct one? How do you count nodes in your engine?
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.
Last edited by mcostalba on Sun Sep 04, 2011 2:10 pm, edited 2 times in total.
-
- Posts: 173
- Joined: Sun May 11, 2008 7:43 am
Re: How do you count nodes?
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.
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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: How do you count nodes?
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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: How do you count nodes?
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 wrote: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?
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: How do you count nodes?
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()"?bob wrote: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 wrote: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?
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();
}
}
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();
}
}
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();
}
}
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();
}
}
Edsel Apostol
https://github.com/ed-apostol/InvictusChess
https://github.com/ed-apostol/InvictusChess
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: How do you count nodes?
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.Edsel Apostol wrote: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?
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.
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: How do you count nodes?
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?Don wrote: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.Edsel Apostol wrote: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?
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.
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
https://github.com/ed-apostol/InvictusChess
https://github.com/ed-apostol/InvictusChess