What is the Ideal Output for Understanding a Chess Engine?

[bob]

I would always suggest sticking with the traditional definition of "node" unless your name happens to be Donald Knuth, Claude Shannon, etc... Then one might have the "reputation" necessary to re-define an accepted term.

If a definition becomes vague, it becomes useless.

I think this ignores the true problem: some programs might not terminate the tree at a boundary between two nodes, according to the accepted definition. So they do fractional nodes. (E.g. the MakeMove to it, but not the MoveGen, or the HashProbe, but not the MakeMove.)

How would you define nps for such a program?

To come back to the original question, "What is the most useful output for understanding a Chess program", I would say that the number of nodes searched (by whatever definition) comes very, very low on the list indeed. Statistics about the number of cutoffs on 1st, 2nd and later moves, hash hit percentage, PV per ply depth (to judge extensions) and such seems orders of magnitude more useful.

The traditional definition of "node" has no "fractional" description. A node is what is produced when a move is executed during tree traversal. If you make/unmake to (say) order moves at a ply, those are not nodes. Because the search does not pass through them.

So I don't see how the concept of 'fractional node' can exist and be compatible with the classic AI definition of "node".

[bob]

I would always suggest sticking with the traditional definition of "node" unless your name happens to be Donald Knuth, Claude Shannon, etc... Then one might have the "reputation" necessary to re-define an accepted term.

If a definition becomes vague, it becomes useless.

I think this ignores the true problem: some programs might not terminate the tree at a boundary between two nodes, according to the accepted definition. So they do fractional nodes. (E.g. the MakeMove to it, but not the MoveGen, or the HashProbe, but not the MakeMove.)

How would you define nps for such a program?

To come back to the original question, "What is the most useful output for understanding a Chess program", I would say that the number of nodes searched (by whatever definition) comes very, very low on the list indeed. Statistics about the number of cutoffs on 1st, 2nd and later moves, hash hit percentage, PV per ply depth (to judge extensions) and such seems orders of magnitude more useful.

I think that the number of nodes is simply the number of times that you call MakeMove

Uri

With a restriction, that you have to actually traverse the node with the search. For example, the ETC algorithm can make/unmake every move at a ply to determine which one to try first. Those do _not_ count. As they are not traversed, just analyzed to determine which is the best to try first. Most would not use make/unmake to do that test, but the idea is the same. A "node" is what is produced when you take a node, and execute a move on it, leading to a new position where you may repeat the same process again...

[hgm]

So I don't see how the concept of 'fractional node' can exist and be compatible with the classic AI definition of "node".

That still leaves the problem that some engines do nothing in a node but a single hash probe, while other engines might always do a complete move generation, SEE every move and sort on it, and then do 40 hash probes...

To count both these actions as a single node, doesn't make the concept of node very meaningful.

[sje]

Upon taking another look at my code, it appears that Symbolic's A/B searcher also counts null move execute/retract calls as well.

The code really isn't that bad. There are three routines for trying moves: TryNull(), TryMove(), and TryMoveNSS(). The last is the same as TryMove() except that it doesn't try a speculative search; i.e., an A/B search with a zero width window.

Each of the try move routes does the execute/retract, and in between it calls Gate() after making sure that the tried move is legal (or a null). The actual node count incrementation occurs in Gate().

In turn, Gate() decides which node processor to activate (if needed). There are different processors for the root, for full width, for captures or checks, etc. Sometimes no processor is needed, e.g., a tablebase hit. The idea is that all code that would be common to a node processor is factored out and moved to Gate().

[michiguel]

I would always suggest sticking with the traditional definition of "node" unless your name happens to be Donald Knuth, Claude Shannon, etc... Then one might have the "reputation" necessary to re-define an accepted term.

If a definition becomes vague, it becomes useless.

I think this ignores the true problem: some programs might not terminate the tree at a boundary between two nodes, according to the accepted definition. So they do fractional nodes. (E.g. the MakeMove to it, but not the MoveGen, or the HashProbe, but not the MakeMove.)

How would you define nps for such a program?

To come back to the original question, "What is the most useful output for understanding a Chess program", I would say that the number of nodes searched (by whatever definition) comes very, very low on the list indeed. Statistics about the number of cutoffs on 1st, 2nd and later moves, hash hit percentage, PV per ply depth (to judge extensions) and such seems orders of magnitude more useful.

I think that the number of nodes is simply the number of times that you call MakeMove

Uri

With a restriction, that you have to actually traverse the node with the search. For example, the ETC algorithm can make/unmake every move at a ply to determine which one to try first. Those do _not_ count. As they are not traversed, just analyzed to determine which is the best to try first. Most would not use make/unmake to do that test, but the idea is the same. A "node" is what is produced when you take a node, and execute a move on it, leading to a new position where you may repeat the same process again...

"Node" seems to be an abstract concept within the framework of a given algorithm, but when you go into practice it may be blurred. If you make a move and hit the hashtable, that counts as a node despite you do very little in the new position. What if I calculate only the new hash signature before updating the board and I hit the table? I am doing basically the same thing, but according to your definition it does not count. You may that the move was not made but someone can that the move was made with a "lazy make move" optimization.

Also, what is the definition of "making the move"? update the board? what is the board? board[64]? all the attack tables? the hash signature?
What if I change the structure of the board during search?

I do not count illegal positions visited as nodes but... why if I do? why if I do not have "checkmate" but internally I capture the king, which worths the highest score? Then I have to count those as nodes because I am traversing the tree. In that scheme, a checkmate is a "pruning", and if I decide to check illegal pseudo-moves I must count them as nodes! (they are not "illegal" anymore, they just lose in the next ply). I other words, counting non-legal makemove()'s may depend on the definition of "game termination".

It is possible to define a node when you write in a paper the alpha-beta algorithm, but I do not think it is possible to do it with accuracy when an application is written. There are too many definitions of other factors that will alter what a node is.

Miguel

[sje]

Code: Select all

thePosition.ExecuteMove(theMove); // Does all internal data structure updates
if (thePosition.IsLegal())
{
  GlobalNodeCount++;
  // Various processing
  theScore = thePosition.Evaluate();  // May recurse
}
else
  theScore = ScoreBusted;
thePosition.RetractMove();

[michiguel]

Code: Select all

thePosition.ExecuteMove(theMove); // Does all internal data structure updates
if (thePosition.IsLegal())
{
  GlobalNodeCount++;
  // Various processing
  theScore = thePosition.Evaluate();  // May recurse
}
else
  theScore = ScoreBusted;
thePosition.RetractMove();

That is actually what I do. Well, almost. I do GlobalNodeCount++; inside Makemove and if the move is not legal I do GlobalNodeCount--. I do not think I can claim that's THE way to do it.

Miguel

[bob]

I would always suggest sticking with the traditional definition of "node" unless your name happens to be Donald Knuth, Claude Shannon, etc... Then one might have the "reputation" necessary to re-define an accepted term.

If a definition becomes vague, it becomes useless.

I think this ignores the true problem: some programs might not terminate the tree at a boundary between two nodes, according to the accepted definition. So they do fractional nodes. (E.g. the MakeMove to it, but not the MoveGen, or the HashProbe, but not the MakeMove.)

How would you define nps for such a program?

To come back to the original question, "What is the most useful output for understanding a Chess program", I would say that the number of nodes searched (by whatever definition) comes very, very low on the list indeed. Statistics about the number of cutoffs on 1st, 2nd and later moves, hash hit percentage, PV per ply depth (to judge extensions) and such seems orders of magnitude more useful.

I think that the number of nodes is simply the number of times that you call MakeMove

Uri

With a restriction, that you have to actually traverse the node with the search. For example, the ETC algorithm can make/unmake every move at a ply to determine which one to try first. Those do _not_ count. As they are not traversed, just analyzed to determine which is the best to try first. Most would not use make/unmake to do that test, but the idea is the same. A "node" is what is produced when you take a node, and execute a move on it, leading to a new position where you may repeat the same process again...

"Node" seems to be an abstract concept within the framework of a given algorithm, but when you go into practice it may be blurred. If you make a move and hit the hashtable, that counts as a node despite you do very little in the new position. What if I calculate only the new hash signature before updating the board and I hit the table? I am doing basically the same thing, but according to your definition it does not count. You may that the move was not made but someone can that the move was made with a "lazy make move" optimization.

Also, what is the definition of "making the move"? update the board? what is the board? board[64]? all the attack tables? the hash signature?
What if I change the structure of the board during search?

I do not count illegal positions visited as nodes but... why if I do? why if I do not have "checkmate" but internally I capture the king, which worths the highest score? Then I have to count those as nodes because I am traversing the tree. In that scheme, a checkmate is a "pruning", and if I decide to check illegal pseudo-moves I must count them as nodes! (they are not "illegal" anymore, they just lose in the next ply). I other words, counting non-legal makemove()'s may depend on the definition of "game termination".

It is possible to define a node when you write in a paper the alpha-beta algorithm, but I do not think it is possible to do it with accuracy when an application is written. There are too many definitions of other factors that will alter what a node is.

Miguel

A couple of comments:

First, a node is not very abstract in its usage in AI. In the game of chess specifically, a node is what you get when you advance the search from one position to another by making a move, and then recursively doing this within depth/time/space constraints. So if the search starts at node(x), and does something so that it now finds itself at node (x+1) everyone would probably agree that node (x+1) is actually a "node" since the search is now ready to apply a move to that position which will then take us to another position (node).

Secondly, there is a bit of vagueness if you ignore the search itself, because one can make/unmake moves whenever you want. I do this to print the PV when a new best move is backed up to the root. Do I count those make/unmake positions as "nodes"? No, because the search is not traversing them. At the root, before I start the initial search, I make/unmake each root move to get an initial evaluation. Do I count those as nodes? No. More recent versions of crafty actually call quiesce after making each root move. I count those as they are traversed by the search in a normal way.

Finally, whether or not one counts illegal nodes should be immaterial unless the number is extremely high. If you worry about counting/not-counting less than 1% of the nodes, that is not going to effect anything. What will make the count useless is when it is off by a larger factor. Say 10 as in the case being discussed, as that makes the number completely meaningless.

"nodes" don't mean a lot between programs anyway, other than to give some measure of how much effort a program expends in dealing with one, which give a measure of whether the program is simple (large node count) or very complex (smaller node count). How useful that is is debatable, but it clearly does provide _some_ information. Particularly if program A's node count is pretty close to program B's. You can either assume that one author is far better than the other at writing code, or else the complexity of the two programs are pretty similar. That latter assumption then lets you use the node count to draw other conclusions about what the program is doing as a result...

[bob]

So I don't see how the concept of 'fractional node' can exist and be compatible with the classic AI definition of "node".

That still leaves the problem that some engines do nothing in a node but a single hash probe, while other engines might always do a complete move generation, SEE every move and sort on it, and then do 40 hash probes...

To count both these actions as a single node, doesn't make the concept of node very meaningful.

That's OK. It is not what is done in a node that is important. It is what is done to actually reach the node in the first place. Leaf nodes are different than the rest because we go no deeper. But we did a lot of work to actually get to that leaf node and that's why we count it. And once we get there we do enough work to determine that there are no more useful captures, which is even more work. But we really aren't trying to estimate the work done in a node, rather the work done to actually reach a node in the first place, which is a somewhat different thing.

If we go deeper from a node, that produces new nodes, which accounts for the effort in the current node required to reach those new nodes...

[bob]

Upon taking another look at my code, it appears that Symbolic's A/B searcher also counts null move execute/retract calls as well.

The code really isn't that bad. There are three routines for trying moves: TryNull(), TryMove(), and TryMoveNSS(). The last is the same as TryMove() except that it doesn't try a speculative search; i.e., an A/B search with a zero width window.

Each of the try move routes does the execute/retract, and in between it calls Gate() after making sure that the tried move is legal (or a null). The actual node count incrementation occurs in Gate().

In turn, Gate() decides which node processor to activate (if needed). There are different processors for the root, for full width, for captures or checks, etc. Sometimes no processor is needed, e.g., a tablebase hit. The idea is that all code that would be common to a node processor is factored out and moved to Gate().

I don't see anything wrong with counting them in fact. The new node is different, since the side to move has changed. You might argue "but it takes far less effort to reach that node than reaching a normal node." To which I would respond "what about trying the hash move before generating any moves at all? that takes far less effort, yet produces no less valid new nodes than the null-move search does."