michiguel wrote:bob wrote:Uri Blass wrote:hgm wrote:bob wrote: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...