definition of a node

[AndrewShort]

If you have a legal move only generator:

Code: Select all

  ExecuteMove();
  node_count++;

If you don't:

Code: Select all

  ExecuteMove();
  if (LegalPosition())
    node_count++;

I get a performance hit when I count that way, simply because that leads to higher number of times the node count is incremented. Here's why: If you count at the top of search/qsearch, it ignores hash hits (so your nps goes down in high hashing positions). But if you count after a legal MakeMove(), it counts all legal moves made to the board, whether or not there will be a hash hit (so your nps goes up with high hash hits). In one of my test puzzles, the former method yielded 20 million nodes, while the latter method yielded 120 millions nodes (it was a high hash hit position, King Rook vs King, no egtb) and took a lot longer, because it executed the increment line 100 million more times. I think the difference was something like 142 seconds (former) vs. 160 seconds (latter)... Although my node count variable is an unsigned 64 bit integer, which perhaps is inefficient, perhaps I should use an unsigned 32 bit int instead...

[bob]

If you have a legal move only generator:

Code: Select all

  ExecuteMove();
  node_count++;

If you don't:

Code: Select all

  ExecuteMove();
  if (LegalPosition())
    node_count++;

I get a performance hit when I count that way, simply because that leads to higher number of times the node count is incremented. Here's why: If you count at the top of search/qsearch, it ignores hash hits (so your nps goes down in high hashing positions). But if you count after a legal MakeMove(), it counts all legal moves made to the board, whether or not there will be a hash hit (so your nps goes up with high hash hits). In one of my test puzzles, the former method yielded 20 million nodes, while the latter method yielded 120 millions nodes (it was a high hash hit position, King Rook vs King, no egtb) and took a lot longer, because it executed the increment line 100 million more times. I think the difference was something like 142 seconds (former) vs. 160 seconds (latter)... Although my node count variable is an unsigned 64 bit integer, which perhaps is inefficient, perhaps I should use an unsigned 32 bit int instead...

How is that the case?

My search looks like this:

Search() {
nodes_searched++;
repetition / 50 move check
hash probe
egtb probe
null-move search
while (n=NextMove()) {
Make
call search/quiesce
Unmake
}
}

You guys are coming up with some bizarre implementations of a normal negamax search.

I don't see how the mentioned change would change NPS enough to measure. Most positions are perfectly legal anyway unless you start off in a wild tactical position with a forced mate... And if you generate legal moves to escape check, the number of illegal moves is very small, and whether you count them or not is just "noise" to the overall number... Nobody cares whether you search 100,234,567 nodes on an N-ply search for position P or you only searched 100,000,000 nodes. Most care about the 100M vs 600M type differences, and this is not going to come anywhere near that kind of error margin.

[AndrewShort]

my search doesn't look like that, simply because I need to go back and clean it up. As I've added features, it's gotten a little messy. This thread and your responses have inspired me to clean it up, so thanks. I'm sure I'll get at least a 4% gain as someone else reported...

[sje]

My search looks like this:

Search() {
nodes_searched++;
repetition / 50 move check
hash probe
egtb probe
null-move search
while (n=NextMove()) {
Make
call search/quiesce
Unmake
}
}

Change:
repetition / 50 move check
To:
repetition / 50 move check / insufficient mating material check

I agree with Bob; simply incrementing a 64 bit counter should have next to no effect on timing statistics. Well, unless you happen to be using an 8 bit machine.

To get a good idea of the actual cost of incrementing the node count, try running two versions with one version having the incrementation commented out.

[hgm]

Well, unless you happen to be using an 8 bit machine.

Not even then: only once every 256 times you have to touch anything but the lowest 8 bits.

[AndrewShort]

In my present screwy way of doing search, the difference between counting nodes and not counting nodes is usually unnoticeable. My point was that for positions where you get high number of hash hits, the difference can be quite noticeable, if you measure the difference between including hash hits as nodes or not, since in my particular example, it means executing an increment (VB: nodes=nodes+1) literally 100 million more times than otherwise.

Isn't it true that running a VB statement nodes=nodes+1 100 million times is not free? In my case if I count differently (simply move where I count, which effectively counts less), it saved something like 20 seconds in time...

[bob]

In my present screwy way of doing search, the difference between counting nodes and not counting nodes is usually unnoticeable. My point was that for positions where you get high number of hash hits, the difference can be quite noticeable, if you measure the difference between including hash hits as nodes or not, since in my particular example, it means executing an increment (VB: nodes=nodes+1) literally 100 million more times than otherwise.

Isn't it true that running a VB statement nodes=nodes+1 100 million times is not free? In my case if I count differently (simply move where I count, which effectively counts less), it saved something like 20 seconds in time...

If that is all you do, it would have a cost. But with modern super-scalar out-of-order execution CPUs, those instructions get interlaced with other instructions and the cost very well might be zero or very close to it...

[AndrewShort]

not in front of my pc now, but I think I'm incrementing like this:

ulNodes = CULng(ulNodes + 1)

That might be my problem... I think vb complains without the casting ...,but if I let it cast implicitly it might be faster? I'll have to try..as you can tell I'm not a "real" dev type..

[sje]

First, some of us don't use any Microsoft development tools at all, let alone Visual Basic. So it's quite possible that VB is inserting some kind of extra run time code for conversion, overflow checking, or exception processing and nobody here can help.

The best way to determine incremental execution cost is to write a pair of simple timing loops; one with a 64 bit increment and one with TWO 64 bit increments of separate variables. Run both and do a little linear algebra and you'll get exact numbers.