Pruning in PV nodes

[syzygy]

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

Where did I write "everybody does it so it must be good"? The top engines are doing it. They do it for a reason.

What, EXACTLY, is the difference from your statement "the top engines are doing it, they do it for a reason."

Did you see the word "tested"? It was there and it is still there.

Congratulations, you have just refuted LMR.

How did MY statement refute LMR?

LMR makes it harder for other moves to replace the PV move. I can't make this clearer so I won't try to.

[Rebel]

Just because the "crowd" does it, doesn't make it right. MIGHT be, but NOT for THAT reason... If I run across a technical argument that is convincing, I might think differently. But I am definitely not a "lemming".

It's not the "crowd" that does it, it is the group of engines that are 100s of Elo stronger than the rest. This is not an argument based on lemmings but an argument based on objective measurement.

Maybe you do not understand why it works, but that does not change the fact that it works.

And what is the proof that it DOES work?

How about having a look at any rating list and let reality sink in?

How about thinking for a bit and then letting THAT sink in. At one point all the top programs were using Fruit's history stuff. No longer. If we thought like you seem to think, we'd STILL be doing that. A chess program is the sum of a BUNCH of different parts. Nothing says that a few of those parts are not sub-optimal, it is the sum that is getting measured.

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

I don't believe ANYTHING at the moment.

I remember our discussion about LMR around 2007, you said the same.

[Henk]

Having tested a lot of the PV node stuff in Stockfish, I can say that I 100% agree with Bob here!

A LOT of PV node dependant things have been removed, after careful testing. I can't even begin to count them.

The only PV node dependant stuff that is PROVEN to work in Stockfish is:
1/ skip Null search at PV nodes. That one is quite logical, because we should never fail high at a PV node, except for those artificial ones due to aspiration windows. The elo gain of this optimization is quite small, but measurable.
2/ IID reduction formula depends on PV-ness. PV nodes are reduces less than non PV nodes. The elo gain of this optimization is quite small, but measurable.

Even the LMR reduction depending on PV-ness is UNPROVEN. We cannot remove it because we need to retune perfectly the formula after that, and even then we would get an uncommitable 0 elo patch.

There are still lots of PV conditions, and the reason they cannot be removed is that our testing methodology does not allow it. The only way to commit a patch is if it is a clear elo gain, and unless it gains 2-3 elo, it's likely to fail in testing. Because PV nodes are few, and fewer as depth increases, tests removing PV node crap typically pass the SPRT with elo0=-1.5 elo1=4.5 at short TC, and fail the SPRT with elo0=0 elo1=6, because the elo gain is too small and decreases with depth (as PV nodes become scarce). This has misled Marco (and many others) to believe that these PV node conditions are inherently scalable, and now they are "sacred cows" of Stockfish, along with verification search, most of the endgame code, the broken unstoppable passer logic, etc.

Advice to anyone writing an engine: it's not because Stockfish does it that it's right. Testing is the only metric. Besides, some things work in some engines and not in others. Example: singular extension does not work for me, reducing cut nodes more than other nodes does not work either, etc. But these things really do work in SF.

Singular extensions and multi-cut pruning didn't give noticeable improvement to my chess program. But my testing is still worthless. Multi-cut pruning may give deep search but play did not improve. Might still be that conservative multi-cut pruning gives a few extra elo.

My singular extension implementation looked more like a specialized pv extension.

[bob]

Null-move at PV nodes wastes a little time, nothing else. Not a big elo win or lose. I q-search futility prune EVERYWHERE, but I do NOT use SEE() < 0. I use the delta value because even a losing capture can STILL leave us above alpha... Always have done this everywhere. Tossing it out on PV nodes hurts my code. Why would this be different? If you are capturing something and it is too small to get back to alpha, why search it? You can add a special rule for capturing the last piece to get the pawn-can-run score, without turning it off.


.

I am missing something. In q-search, assuming you are not in check, don't you accept the stand pat (do nothing) score? How can a losing capture then get higher than the stand pat score? I am confused why you would search losing SEE move if the stand pat score would end up being higher. What am I missing?

Simple. Say you are at a zero score. You consider the move RxN, your last piece, opponent's last piece. There is a remote chance RxN turns this game into an instant win if you have an unstoppable passed pawn. But that is not so common.

What I described was this: the current score is -3.0, alpha is 0.1 The only captures I consider searching are those where I win material, enough to get the score back up to alpha. Capturing a pawn at -3.0 is not going to pull the score back up to 0.1. No point in trying it, even though it actually wins a pawn. I've done this since Cray Blitz days, and since I use the variable "delta" in the code, someone liked the idea and started calling this "delta pruning". It is really just a little bit more sophisticated version of only searching captures with SEE >= 0.

So SEE >= 0 is not good enough to include the move. I do not search SEE < 0 in the q-search period. If my writing was not clear, that should explain that better.

But as I mentioned, SEE < 0 is risky because in some positions, that still brings the score back above alpha (as when a pawn can't be caught after removing opponent's last piece.) I just choose to ignore that case as very rare, to prune all of the other similar cases where it would just be a waste of time to search them..

[bob]

Just because the "crowd" does it, doesn't make it right. MIGHT be, but NOT for THAT reason... If I run across a technical argument that is convincing, I might think differently. But I am definitely not a "lemming".

It's not the "crowd" that does it, it is the group of engines that are 100s of Elo stronger than the rest. This is not an argument based on lemmings but an argument based on objective measurement.

Maybe you do not understand why it works, but that does not change the fact that it works.

And what is the proof that it DOES work?

How about having a look at any rating list and let reality sink in?

How about thinking for a bit and then letting THAT sink in. At one point all the top programs were using Fruit's history stuff. No longer. If we thought like you seem to think, we'd STILL be doing that. A chess program is the sum of a BUNCH of different parts. Nothing says that a few of those parts are not sub-optimal, it is the sum that is getting measured.

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

I don't believe ANYTHING at the moment.

I remember our discussion about LMR around 2007, you said the same.

Correct. What Fruit was doing was NOT working. I posted a cluster run using Fruit as the target. With and without history counters. ZERO elo difference. Reductions work, but using history counters (# that failed high, # that did not) to make the reduction decision certainly did not...

[bob]

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

Where did I write "everybody does it so it must be good"? The top engines are doing it. They do it for a reason.

What, EXACTLY, is the difference from your statement "the top engines are doing it, they do it for a reason."

Did you see the word "tested"? It was there and it is still there.

I have not, to date, seen ANYONE post any test results to compare reducing differently in PV nodes to not reducing differently in any nodes. Not one time. I have seen statements (in this thread) where it has NOT been tested in stockfish, it is just there.

Congratulations, you have just refuted LMR.

How did MY statement refute LMR?

LMR makes it harder for other moves to replace the PV move. I can't make this clearer so I won't try to.

How? If you LMR on the PV as well? Using that reasoning would not a check extension make it harder for any other move to replace the PV move? Even thought it TOO is applied to all nodes equally? I don't see any way you CAN make that any clearer. Because I do not believe it to be true and to date, no testing reported by anybody has shown it to be true. If you apply LMR equally EVERYWHERE, the PV is not given any advantage over any of the other moves.

[gladius]

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

Where did I write "everybody does it so it must be good"? The top engines are doing it. They do it for a reason.

What, EXACTLY, is the difference from your statement "the top engines are doing it, they do it for a reason."

Did you see the word "tested"? It was there and it is still there.

I have not, to date, seen ANYONE post any test results to compare reducing differently in PV nodes to not reducing differently in any nodes. Not one time. I have seen statements (in this thread) where it has NOT been tested in stockfish, it is just there.

I didn't post the test results - but I did state that handling LMR differently in PV nodes was an ELO gain for SF. Of course, this could be because of how it's tuned, and I'm sure there exists a better tuning that doesn't do anything different in PV/nonPV, but finding that is not so easy . IIRC, Lucas tried a version retuned with CLOP, and it failed.

On the other hand, all the other stuff that hadn't been tested (futility, razoring, probcut), I did the dumbest test possible, and just removed the PVNode restrictions at the same time, and it seems there is not much value there. So, hopefully a little elo boost to come from removing those restrictions properly.

[syzygy]

Congratulations, you have just refuted LMR.

How did MY statement refute LMR?

LMR makes it harder for other moves to replace the PV move. I can't make this clearer so I won't try to.

How? If you LMR on the PV as well?[/quote]
Especially if you do it on the PV, since a move replacing a PV move will have to be a sibling of the PV move.

Using that reasoning would not a check extension make it harder for any other move to replace the PV move?

No. The check extension will be applied independently of whether a move is the first move at a PV node or a later move.

With LMR you are searching the first move to say depth 20 and a later move will not replace it unless it gives a better score already at depth 19 (or lower). If there are tactics at depth 20, you won't see it. The move that just happens to be good at low depth will tend to stay at the front. (You could counterargue: that first move is more likely to be refuted because you are searching it with more precision. But the same applies when you don't apply reductions to PV nodes that you do apply to non-PV nodes. It is analogous.)

If you apply LMR equally EVERYWHERE, the PV is not given any advantage over any of the other moves.

It certainly does, and the situation is completely analogous to the one you are complaining about. That it may not hurt but may actually be good is another issue.

[Rebel]

Just because the "crowd" does it, doesn't make it right. MIGHT be, but NOT for THAT reason... If I run across a technical argument that is convincing, I might think differently. But I am definitely not a "lemming".

It's not the "crowd" that does it, it is the group of engines that are 100s of Elo stronger than the rest. This is not an argument based on lemmings but an argument based on objective measurement.

Maybe you do not understand why it works, but that does not change the fact that it works.

And what is the proof that it DOES work?

How about having a look at any rating list and let reality sink in?

How about thinking for a bit and then letting THAT sink in. At one point all the top programs were using Fruit's history stuff. No longer. If we thought like you seem to think, we'd STILL be doing that. A chess program is the sum of a BUNCH of different parts. Nothing says that a few of those parts are not sub-optimal, it is the sum that is getting measured.

So you actually believe this wasn't tested by the developers of Stockfish, Houdini, Komodo (despite numerous reports over the last years to the contrary, including some in this thread)?

I don't believe ANYTHING at the moment.

I remember our discussion about LMR around 2007, you said the same.

Correct. What Fruit was doing was NOT working. I posted a cluster run using Fruit as the target. With and without history counters. ZERO elo difference. Reductions work, but using history counters (# that failed high, # that did not) to make the reduction decision certainly did not...

It's not about the history counters, you questioned the whole concept of LMR. I even encouraged you not to give up. Besides, talking about Fruit it does use separate node types:

Code: Select all

search_full.cpp

static const int NodeAll = -1;
static const int NodePV  =  0;
static const int NodeCut = +1;

It's already in the first Fruit version 1.0 and that was early 2004, go figure.

[syzygy]

If you apply LMR equally EVERYWHERE, the PV is not given any advantage over any of the other moves.

It certainly does, and the situation is completely analogous to the one you are complaining about. That it may not hurt but may actually be good is another issue.

To quote yourself:

(of course, finding a new PV has to stumble over the reduced search depth problem before it can fail high)

In my words:

LMR makes it harder for other moves to replace the PV move.

Do we really need to discuss the obvious?