What is the Ideal Output for Understanding a Chess Engine?

[rfadden]

Thanks Bob, this info is very useful.

I just had an "oh my gosh" moment when i realized that I first started messing with one of your chess programs 30 years ago.

That's freaky man... From 20 to 50 and I'm still messing around with chess programs. You'ld think I would have learned something over these years.

So what I was trying to do is to patch Rybka to output a proper node count and I was trying to avoid doing it like Strelka because for that I would have to add funky patches in five routines (write over an instruction with a branch, then place that code at the new location, etc., and that's tedious. I was thinking of adding "instrumentation" at just one spot so I was looking for one thing to count. As you indicate I could pick on "make_move".

Keep in mind this patch to remove the Obfuscation in Rybka 1.0 beta is something I mentioned in the Rybka forum with Vas adding a few comments here and there, so this is an openly discussed thing. I documented the obfuscation and I was just taking a stab at giving a patch that anyone could apply to 1.0 beta to be able to see actual Depth, Nodes, and NPS. Changing the location of the Instrumentation is not that hard especially if I pick on one location in one subroutine...

It's all for fun.

Thanks

[Harald Johnsen]

For its cognitive search, Symbolic keeps the whole tree in memory and so the node count is simply the total number of nodes in the tree graph. A purist might consider this an undercount as a given node may be visited more than once for different reasons.

As Bob (iirc) said in the other thread, node count is about search space.
Your undercount is surely more accurate than anything else because in modern engines we search and re-search and re-search the same nodes a lot of times. Do we want to know the number of makemove() done or the number or unique positions seen ?
I think that counting makemove is too inacurate (to represent search space), it is from a time where the branching factor was high so the node count was a good approximation of the number of leaf positions.
With a branching factor of 2 this node count has nothing to do with the search space anymore.

Perhaps we could show the search space to the end user and keep the traditional node (makemove) count for the coder ?

HJ.

ps: of course we (usually) don't have this unique positions count because we still don't have the search tree in memory.

[bob]

Thanks Bob, this info is very useful.

I just had an "oh my gosh" moment when i realized that I first started messing with one of your chess programs 30 years ago.

That's freaky man... From 20 to 50 and I'm still messing around with chess programs. You'ld think I would have learned something over these years.

So what I was trying to do is to patch Rybka to output a proper node count and I was trying to avoid doing it like Strelka because for that I would have to add funky patches in five routines (write over an instruction with a branch, then place that code at the new location, etc., and that's tedious. I was thinking of adding "instrumentation" at just one spot so I was looking for one thing to count. As you indicate I could pick on "make_move".

Keep in mind this patch to remove the Obfuscation in Rybka 1.0 beta is something I mentioned in the Rybka forum with Vas adding a few comments here and there, so this is an openly discussed thing. I documented the obfuscation and I was just taking a stab at giving a patch that anyone could apply to 1.0 beta to be able to see actual Depth, Nodes, and NPS. Changing the location of the Instrumentation is not that hard especially if I pick on one location in one subroutine...

It's all for fun.

Thanks

That was the way we used to patch operating system code on the old IBM /370 - /370 and xerox sigma machines. Most components included a "patch area" (a block of unused memory) explicitly for this purpose so that new executables would not need to be created, since they were often unique to each specific computer system and configuration options used when the system was "generated" (who remembers the old "sysgen" days now?)

[bob]

For its cognitive search, Symbolic keeps the whole tree in memory and so the node count is simply the total number of nodes in the tree graph. A purist might consider this an undercount as a given node may be visited more than once for different reasons.

As Bob (iirc) said in the other thread, node count is about search space.
Your undercount is surely more accurate than anything else because in modern engines we search and re-search and re-search the same nodes a lot of times. Do we want to know the number of makemove() done or the number or unique positions seen ?
I think that counting makemove is too inacurate (to represent search space), it is from a time where the branching factor was high so the node count was a good approximation of the number of leaf positions.
With a branching factor of 2 this node count has nothing to do with the search space anymore.

Perhaps we could show the search space to the end user and keep the traditional node (makemove) count for the coder ?

HJ.

ps: of course we (usually) don't have this unique positions count because we still don't have the search tree in memory.

WIth depth-first searching (which includes alpha/beta) there is no way to count the actual search space covered, hence we count the actual search space visited which includes some duplication. But since the effort is also duplicated, it is a reasonable measure. There's no way to do this in depth-first unless you have a hash table large enough that no overwriting ever occurs. Then a hash match would mean "don't count this node, been here before"...

[mhull]

That was the way we used to patch operating system code on the old IBM /370 - /370 and xerox sigma machines. Most components included a "patch area" (a block of unused memory) explicitly for this purpose so that new executables would not need to be created, since they were often unique to each specific computer system and configuration options used when the system was "generated" (who remembers the old "sysgen" days now?)

I do.

IIRC, it's still done.

Incidentally, many people might be shocked to discover that the space shuttles utilize four redundant 370-on-a-board computers.

[bob]

That was the way we used to patch operating system code on the old IBM /370 - /370 and xerox sigma machines. Most components included a "patch area" (a block of unused memory) explicitly for this purpose so that new executables would not need to be created, since they were often unique to each specific computer system and configuration options used when the system was "generated" (who remembers the old "sysgen" days now?)

I do.

IIRC, it's still done.

Incidentally, many people might be shocked to discover that the space shuttles utilize four redundant 370-on-a-board computers.

I thought they were much more primitive than that. Last talk I heard by the shuttle designers showed that they were hauling a laptop on board to do the orbital position calculations so that the astronauts could know exactly where they are over the planet at any instant of time...

[mhull]

That was the way we used to patch operating system code on the old IBM /370 - /370 and xerox sigma machines. Most components included a "patch area" (a block of unused memory) explicitly for this purpose so that new executables would not need to be created, since they were often unique to each specific computer system and configuration options used when the system was "generated" (who remembers the old "sysgen" days now?)

I do.

IIRC, it's still done.

Incidentally, many people might be shocked to discover that the space shuttles utilize four redundant 370-on-a-board computers.

I thought they were much more primitive than that. Last talk I heard by the shuttle designers showed that they were hauling a laptop on board to do the orbital position calculations so that the astronauts could know exactly where they are over the planet at any instant of time...

Ok, it appears I was somewhat in error. The 370 complex was ground-based at the Johnson Space Center. Here are the computer details for the shuttle orbiter:

The Space Shuttle General Purpose Computer was one of five computers providing navigation and control processing functions aboard each Shuttle. Each computer consisted of a central processor (IBM's Advanced System/4 Pi) and an input/output processor.

http://www-03.ibm.com/ibm/history/exhib ... uttle.html

The name of the system is derived from the fact that the angular measure of a complete sphere (solid angle) is 4π steradians, while the angular measure of a complete circle is 360 degrees; hence System/4 Pi and System/360. This implies that System/4 Pi is a version of the IBM System/360 for the three-dimensional world of avionics.
http://en.wikipedia.org/wiki/System_4_Pi

[hgm]

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.

[Uri Blass]

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

[hgm]

But that would mean that programs that call MakeMove in vain (e.g. for nodes that are futility or hash pruned) would get a much higher nps than programs that skip Make/UnMake in such cases, making it look like they are faster, while they are in fact much slower. So nps according to this definition would still not be a very useful measure.