What is the Ideal Output for Understanding a Chess Engine?

[rfadden]

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

For the task I'm working on right now I'm favoring Bob's suggestion... this one that we are mentioning. I'll count MakeMove and then we can look at that and compare it to the old "node count" technique in the program that I'm patching.

[Chan Rasjid]

Muller wrote:-

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.

If we give an nps, it is either done because every other chess programmer Joe prints it or we want to let others compare the search speed of a program with that of others. The nps is useful as long as when we are asked to count horses, we don't count donkeys as Bob says.

It is not difficult to know when not to count a makemove(). My program only counts valid moves or nodes. Even the problem of PVS researching the same subspace should not be a problem as a particular chess program can cover only a certain nodes per time, within a reasonable limit, that depends on its implementation. The nps would still be a good indication if it is a fast or slow searcher. If we want to be strictly rigorous, we cannot talk.

Rasjid

[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

For the task I'm working on right now I'm favoring Bob's suggestion... this one that we are mentioning. I'll count MakeMove and then we can look at that and compare it to the old "node count" technique in the program that I'm patching.

Just remember that there are programs that do MakeMove() on moves that never get searched. As I mentioned, a program using ETC would make each move and do a hash probe to discover which of the moves is most likely to produce a cutoff. Other uses might be to make the moves and then use the resulting evaluations to order things. None of those are really nodes.

I personally have always just incremented a counter at the front of Search() and Quiesce() which does the job nicely.

Since they are only entered on a position I plan on searching further, they are perfect examples of "nodes".

[Guetti]

What is ETC?
There are also programs that make/undomove pseudolegal moves.

[hgm]

I personally have always just incremented a counter at the front of Search() and Quiesce() which does the job nicely.

I do that too, in Joker. But that leaves two problems:

1) If a position that is logically part of the search tree is found as a DepthOK hit in the hash table, should I count it as a node or not?

2) If I do IID, so that the same nodes are encountered several times (with different DepthLeft), do they count as a single nodes, or as often as I visit them? One might argue the earlier IID iterations are not part of the search. And how about the node from which I do the IID? If I count all nodes deeper in the tree as nodes in every iteration, wouldn't it be logical to count the root of that IID search multiple times as well?

In Joker my Search() routime looks like

Code: Select all

Search()
{
    MoveGen();
    while(move = NextMove())
    {
        UpdateHashKey(move);
        if(Repeat()) score = DRAW; else
        if(HasProbe() == OKHIT) score = hash->score; else
        {
            MakeMove(move);
            score = -Search();
            UnMake();
        }
        RestoreHashKey();
        ALPHA_BETA_STUFF
    }
}

So if a move that would cause the node it leads to to be a repeat or hash hit with sufficient depth and OK bounds, there is no MakeMove, and no call to Search(). Does this mean my reported node count and nps are too low compared to what they really are?

[Chan Rasjid]

What is ETC?

Enhanced Transposition Cutoff. The idea is to probe the hash tables for the whole move list for a beta-cutoff (beta < infi) before any move is searched. If a move gives a cutoff, then there is no need to do any search.

Fabien of Fruit once mentioned he could not make it work beneficially.

Rasjid

[bob]

I personally have always just incremented a counter at the front of Search() and Quiesce() which does the job nicely.

I do that too, in Joker. But that leaves two problems:

1) If a position that is logically part of the search tree is found as a DepthOK hit in the hash table, should I count it as a node or not?

Yes. Here is why I believe that is correct. when you count a node, you are not counting the _effort_ expended at _that_ node. You are counting the effort from the previous node required to reach this node. If you do more work here and search some moves, those new nodes will represent additional effort.

Perhaps a simpler way is that in a graph, you have nodes and arcs. I'm counting the arcs, which is what actually transitions me from node A to node B.
And when you think of it in that way, it doesn't matter whether a node instantly returns due to a repetition, a hash hit, or does a full or abbreviated search to return a real result...

2) If I do IID, so that the same nodes are encountered several times (with different DepthLeft), do they count as a single nodes, or as often as I visit them? One might argue the earlier IID iterations are not part of the search. And how about the node from which I do the IID? If I count all nodes deeper in the tree as nodes in every iteration, wouldn't it be logical to count the root of that IID search multiple times as well?

A node is still a node. If you search it twice, as with IID, or even with normal iterative deepening, it represents a node. Even though it has been searched previously to a different (or even the same) depth.

In Joker my Search() routime looks like

Code: Select all

Search()
{
    MoveGen();
    while(move = NextMove())
    {
        UpdateHashKey(move);
        if(Repeat()) score = DRAW; else
        if(HasProbe() == OKHIT) score = hash->score; else
        {
            MakeMove(move);
            score = -Search();
            UnMake();
        }
        RestoreHashKey();
        ALPHA_BETA_STUFF
    }
}

So if a move that would cause the node it leads to to be a repeat or hash hit with sufficient depth and OK bounds, there is no MakeMove, and no call to Search(). Does this mean my reported node count and nps are too low compared to what they really are?

I think they are perfectly compatible with what almost everyone else does. Count the nodes, or count the arcs. Nodes are better represented by entry in Search(), the arcs are better represented by MakeMove(). Both will be close enough to each other to be considered equal...

[bob]

What is ETC?

Enhanced Transposition Cutoff. The idea is to probe the hash tables for the whole move list for a beta-cutoff (beta < infi) before any move is searched. If a move gives a cutoff, then there is no need to do any search.

Fabien of Fruit once mentioned he could not make it work beneficially.

Rasjid

I tried it two ways. quick and dirty was to just make/unmake, but that updates way more stuff than needed. You only need the updated hash signature. This was way too slow and badly hurt performance. The second way was a special-purpose MakeMoveETC() which only updated the hash signature to save time. I never got any significant results. Looping over all the moves has a cost, which has to be offset by better cutoffs. It never panned out for me.

[wgarvin]

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

This makes sense. If some nodes can be explored very cheaply, using hash hits or whatever, then that should be reflected in a higher nodes-per-second---not a lower node count.

Even if a node is cheap to explore, it should still be counted.

[rfadden]

Ok so I finished my Rybka 1.0 Beta Patches, and the code is counting the number of calls to Make_Move in Rybka. The results are very interesting (for me anyway).

Also I tracked down and got rid of all (depth - 2), and I also changed the output so the program sends the stats for all ply, including the low ply numbers.

I also stopped the clipping of PV at the spot where the display string is calculated.

I've been looking at the speed and I've been comparing this to other programs.

On my Athlon XP 2400+ I'm seeing (roughly) a NPS of 750,000. That's a 2 GHz Athlon XP.

Here's something really rough... I'm noticing that Rybka 1.0 is searching something between 1.2 and 1.8 times faster than Fruit 2.3.1.

The thing that really strikes me as I run a few engine matches is that Rybka 1.0 depth and node display seems to have the same look and feel as Fruit when you remove the obfuscation.

I wonder if that was the whole point of the obfuscation. Here was a program about to take the lead from Fruit. The way it searches, the way it goes deeper, fast, looks like Fruit... uh oh, that might look too close to Fruit so maybe the output should be munged to make it look like it's Diep (vast knowledge, slow searcher).

Um, one self imposed warning here (for me)... the human mind can pick up on subtle similarities and our thinking can also influence what we see. I have often wondered if Rybka used Fruit's search techniques (open source to Fruit 2.1) and then had it's own fast bitboard with unique smart/fast Eval... Well I'm starting to see this in the runs now, and so as I say, perhaps this is me seeing a bit of what I expect to see...

My patches are in a little file that I could paste here. This is just a text listing of the addresses and values to change, with the old values, and a freely available patch program applies the patch to create a new .exe.

The patch changes about 72 bytes and that includes changing an identifier string that indicates that the binary has been patched.

Fun stuf...

I'm thinking of posting the text output of the program. I'm waiting before I post the patch. Over on the Rybka forum I was wondering if Vas would post that he objects to this. I'll give it more time...