Counting nodes correctly

[JimmyRustles]

Hi,

I've looked through the other posts about counting nodes and the consensus seems to be that you should do it after each make move in your alpha beta/qsearch.

The problem I've found in my code is that I'm inconsistent whether nodes get counted when the move is pruned.

My move loop in alphabeta looks like this:

Code: Select all

for (each move) {

    if (history pruning conditions) {
        continue;
    }
    
    if (SEE pruning conditions) {
        continue;
    }
    
    makeMove(move);
    nodesSearched++;
    
    if (futility pruning conditions) {
        unmakeMove(move);
        continue;
    }
    
    score = -alphaBeta(...);
    
    unmakeMove(move);
    
    // rest of move loop
    
}

As you can see, if a move gets SEE pruned or history pruned, it won't get counted as a node, but if it gets futility pruned, it does get counted as a node.

The reason I have to check futility pruning after making the move is because I can only see if a move gives check after making the move.

It seems that nodes shouldn't get counted if they're pruned, so should I be adding nodesSearched-- when the futility pruning condition holds?

[xr_a_y]

At top of your recursive Pvs or alphabeta routine you probably have

If depth <=0 then qsearch()

You can count nodes++ just after this.

In qsearch, you can do it at top of routine.

This way, you are counting all visited nodes.

Of course you can also count, legal move make, or anything else but what I described is what most engine does. Better to do the same as other do have a comparison point on this subject.

[hgm]

You cannot meaningfully compare node counts between different engines anyway. It depends too much on design details like this.

[JimmyRustles]

At top of your recursive Pvs or alphabeta routine you probably have

If depth <=0 then qsearch()

You can count nodes++ just after this.

In qsearch, you can do it at top of routine.

This way, you are counting all visited nodes.

Of course you can also count, legal move make, or anything else but what I described is what most engine does. Better to do the same as other do have a comparison point on this subject.

Thanks, this makes sense. I just changed to this method (increasing the nodes after the timeout code so nodes that time out and aren't searched aren't counted) and my search speed went from 711knps to 915knps. I always knew Raven was slow but maybe it's not quite as slow as I thought. Thanks!

You cannot meaningfully compare node counts between different engines anyway. It depends too much on design details like this.

I'm aware of this and that engines have different ways of counting nodes. Still, it'll be nice to have my search speed be accurate when it compare it against changed to the engine which might affect speed.

[hgm]

But if your MakeMove() is seriously time consuming, not counting the futility-pruned nodes would make you believe you could improve the speed of your engine by reducing the amount of futility pruning. Which I doubt would be the right thing to do for improving the engine.

I would expect node count to be most valuable when it most accurately counts the time-using actions in your engine. I doubt whether calling a routine to increase the node count and immediately return after that would qualify as such an action, compared to a MakeMove() / UnMake().

[jonkr]

Slow Chess counts nodes something like this, not futility pruned, but in a way that counts some pruned nodes. Actual node count should be like 25% less in midgame/opening. I kept adding more and more pruning and I often do tactical analysis of all the moves in a position before calling DoMove (this includes the check function which tests before making the move too.) So initially I felt for speed comparison to older versions and other engines I should count some of the pruned nodes, but in Dev I removed that so it actually gives the slower count/nps, might as well embrace the engine name and just feels more consistent.

Having a benchmark command to run through some positions and test changes for speed and compare it to what you expect could be helpful. Unfortunately I get so much speed variation even from changes that definitely don't matter I have trouble making comparisons doing that (I think has been some threads here about the variation.) But were a couple times I caught some major things like when I accidentally left some debug code enabled after a test.

[Joost Buijs]

At top of your recursive Pvs or alphabeta routine you probably have

If depth <=0 then qsearch()

You can count nodes++ just after this.

In qsearch, you can do it at top of routine.

This way, you are counting all visited nodes.

Of course you can also count, legal move make, or anything else but what I described is what most engine does. Better to do the same as other do have a comparison point on this subject.

Personally I find it cleaner to count nodes in move-make, only in this way you are counting distinct nodes. Of course it depends upon the definition of a node.

When you count nodes at each entry of the search the counts are highly exaggerated, at each research, IID, LMR research, PV research etc. you will artificially increase your node count, and make it very dependent upon how the search is organized. But again, it depends upon your definition of a node.

[hgm]

If you do IID / LMR / PVS re-searches, you would still have to redo the move generation, and it makes some sense to count that. For this reason I never do the re-searches, but instead let the node self-deepen or open the window. So that it can keep the move list and any sorting it has already done on it.

[Joost Buijs]

If you do IID / LMR / PVS re-searches, you would still have to redo the move generation, and it makes some sense to count that. For this reason I never do the re-searches, but instead let the node self-deepen or open the window. So that it can keep the move list and any sorting it has already done on it.

It depends upon how your search is organized. You don't have to redo the move generation for a research, I store most of the information for a node (including the move-list) in an array indexed by thread-number and ply. When I do a move-make I set flags 'evaluated = false' and 'generated = false', when I enter the search I check these flags and act upon them accordingly. Sorting the moves is also done once, the TT-move is treated separately.

I also tried a scheme where I sorted locally by first making a copy of the move-list, but the difference is negligible. There are many roads leading to Rome.

In fact it is a little bit more complicated because I also do staged move-generation, but it's just a matter of keeping track of everything.

[hgm]

Sure, that would work. One could argue whether one really leaves a node, when you keep so much information specific to the node from one visit to the next.

I did consider using the move stack in the same way as I collect the PV (a stack version of the tri-angular array method). Where each 'element' then is an entire move list + associated data, rather than a single move. I never tried that, though.