Pruning in PV nodes

[syzygy]

- LMR

Oops, this is obviously done in the PV, but with reduced reductions.

[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. Not enough information. Do you actually believe it was not tested by Fabien (history). By the way, NO I don't believe it was tested by Houdart. He simply copied Robolito, which was already written that way. We don't know what Komodo does so far as I know, since there is no source and I have not looked inside.

So back to the beginning. Robolito's search does it this way. How many just "lemming'ed along and did the same?" No idea. My comment was simply "until I see some sort of technical justification for treating PV differently from non-PV, I'm not interested in rewriting a lot of code unless I reach the point where I want to test the idea. On the surface, it sounds wrong. I consider all moves at the root to be equal, because I can find any of them to be the best move. Why make it harder to replace the first?

[bob]

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

100%, are you sure? Then how to explain that several PV-specific things have been PROVEN to work, as you just confirmed?

So which ones do not lose Elo if you enable them in the PV:
- razoring
- futility pruning
- null move
- probcut
- pruning at shallow depth
- LMR
- qsearch futility pruning
- qsearch pruning of negative SEE moves

How about doing this differently. Re-phrase... Which ones do not lose elo if you enable/disable them on the FIRST move at any node, not just on the left-hand edge of the tree.

I razor at PV nodes. I just ran a test and turning it off does NOT improve Elo. I am twiddling with my razoring code right now, in fact, and have tried a bunch of different things. Doing/not-doing at PV is not important.

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.

Now for a different angle. You have a best move. But there is a BETTER move later in the ply-1 move list. Do you REALLY want to make it harder to discover that by doing less effort on the remaining moves than you were willing to spend on the first move? What is the justification for that? We've seen those "blind positions" where stockfish simply will not change its mind at all, there were a couple of threads here within the last couple of weeks.

Give a good technical reason for omitting ANY of the above at a PV node and we can talk. The only ones I use are (a) I don't do null-move because it is not legal to have a null-move in the real PV; (b) IID, which is expensive. I want to order the first move as accurately as possible since that move represents most of the effort, thanks to alpha/beta. A program changes its best move about 1/6 of the time, which means 5/6 of the time the PV doesn't change. Doing IID on non-PV nodes that are going to remain non-PV is not worth the effort. Verified by testing when I added IID back in 1995. Haven't changed it since, although I test it with different changes on occasion.

My primary point was "just because xxx does it is NOT a good reason to do it." Fruit was best when it came out, yet it's history counter usage for reductions was pure nonsense. It worked EXACTLY as well without the history counters, I tested and posted those results here about a year or a little less after Fruit 2.1 was released.

[bob]

I find it hard to justify treating the first move differently from the rest of the moves...

I find it hard to argue against what all the top engines are doing, which is to treat PV and non-PV nodes differently.

That's not an argument. Fruit was a top engine, and applied LMR reductions solely based on the history counter values, not order or anything. Did that make it right? Does anybody do that today? (no).

Following that reasoning, nobody would be using LMR (none of the top engines are using any sort of reductions today and it is hard to argue against what they are doing...).

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

You're right, definitely it should be tested for each engine to determine — is it helps. For me disable reductions at PV node makes engine stronger (comparing to version with doing reductions at the same way as in non-pv nodes). Do you have another expirience with your engine?

So far I have not run any test on any search enhancement where it performs better by doing it differently for PV and non-PV nodes. May be perfectly reasonable to split things that way, but I have not been able to find any benefit. If you have a specific thing to try, feel free and if it is not horribly complex, I'll make the changes and run a few million games to test it carefully...

Stockfish does quite a lot of things differently in PV/non-PV nodes, and removing that distinction has been tested on the framework for quite a few of them.

Things that have been tested and found to help:
1. No null move in PV nodes
2. Less aggressive LMR in PV nodes
3. Different IID parameters

Things I don't remember if have been tested:
1. No futility in PV
2. No razoring in PV
3. No prob-cut in PV

1 and 3 (first group) I agree with. But I can offer technical reasons why they don't work well in the PV. a null move is not a legal move, so it can't be in the PV. Therefore why bother? If it fails high or if it returns a true score you could not keep it as best. Ergo don't do it except when it can only fail high or low.

for 3, IID is not cheap. The point is to get better move ordering. Since the PV nodes produce far larger trees than non-PV nodes, improving ordering there is beneficial. Since a program only changes its mind about 1/6 of the time when doing a new iteration, 5/6 of the time that first move represents the major part of the search space. Ordering is more important on a large tree. Trying to improve the ordering on what are already small trees (non-PV nodes) has a cost and a benefit. Cost is the expense of the iid search, benefit is reducing the size of the tree. Since it is already small, it is quite likely the cost of the iid search exceeds the tree size reduction. Hence it is a net loss. Not a huge one, but certainly measurable.

The rest I don't agree with. Not because I think they are dead wrong, but because I can see no technical justification. What is razoring? Dumping bad moves near the tips to avoid effort? Why doesn't that work on PV nodes just as well as non-PV nodes, *IF* you use reasonable rules regarding what can be razored vs what can not.

[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)?

Here's something I posted here last year or the year before, that was counter to "standard practice." At that point in time, the usual practice was to extend checks in the regular search by 1 ply, although some used 3/4. Another standard practice was "never reduce tactical moves which includes checks." I got interested in all of the extensions and reductions rules, and discovered a quick 15-20 Elo by (a) NOT extending checks that SEE says lose material and (b) reducing those same moves. Yet everyone was doing it at the time. So was it right or wrong? About all you can say here is "it was just the norm" even though it was actually incorrect.

I'm simply waiting for a rational explanation why one would reduce more/less on non-pv/pv moves. What makes PV moves special? Don't we hope to find a BETTER move every time we do another iteration? That's the only reason I can see. If we want to find a better move, it HAS to come from the pool of non-PV moves at the root. So why short-change the search on those and make it harder to see deep/clever tactics? That's my question. If there is a reason, I'd love to hear it and change my thinking...

Right now I consider this in that "always extend checks, never reduce them" school of thought that is a little detrimental to engine development.

[syzygy]

Right now I consider this in that "always extend checks, never reduce them" school of thought that is a little detrimental to engine development.

Why? It certainly wasn't the norm to treat PV and non-PV differently until some years ago.

Why did you stop extending all checks? Because you had a theoretical explanation that explained why it was better to not extend all checks? Or because you measured this to be better?

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.

If we want to find a better move, it HAS to come from the pool of non-PV moves at the root. So why short-change the search on those and make it harder to see deep/clever tactics?

Congratulations, you have just refuted LMR.

[JVMerlino]

Why did you stop extending all checks? Because you had a theoretical explanation that explained why it was better to not extend all checks? Or because you measured this to be better?

Apparently you didn't read what he wrote, as he was very clear that not only did he not stop extending ALL checks, he gave an ELO boost for what he DID decide to do (reduce checks that have SEE < 0).

But, honestly, it seems like you two are working two sides of a different argument.

jm

[bob]

Right now I consider this in that "always extend checks, never reduce them" school of thought that is a little detrimental to engine development.

Why? It certainly wasn't the norm to treat PV and non-PV differently until some years ago.

Why did you stop extending all checks? Because you had a theoretical explanation that explained why it was better to not extend all checks? Or because you measured this to be better?

Because I had a theoretical objection to doing so, and testing confirmed I was correct. Someone pointed out the old "patzer sees check, patzer plays check." I replaced "plays" with "extends" and thought "why would I extend moves that cause the tree to get larger, even though the checking move is unsafe?" That was, to me, a valid reason to test the idea. Same thing with all the other extensions that I no longer do (recapture, passed pawn pushes, etc). The only worthwhile extension I found with a few million cluster games was the check extension. And I found it to be significantly better if it is only treated in a special way if it is a safe check (not losing material).

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." and my paraphrased "everybody (that is strong) does it so it much be good" (parenthetical added as that was my intended implication". I was equating "everybody" with "the top engines" in this regard. That is NOT a convincing argument except to a lemming.

If we want to find a better move, it HAS to come from the pool of non-PV moves at the root. So why short-change the search on those and make it harder to see deep/clever tactics?

Congratulations, you have just refuted LMR.

How did MY statement refute LMR? I didn't say reduce NOTHING. I said 1/6 of the time a new iteration will find a new best move. From the set of NON_PV root moves, obviously. You can treat some of them differently based on noted characteristics. I reduce everywhere myself. I just try to not reduce moves that might turn out to be important later. And I twiddle with that "recognition" every now and then to see if there are even more recognizable moves to not reduce..

No need to report to hyperbole.



If I were guessing about all of this PV/non-PV stuff, I'd bet it traces back to a single program. Probably Rybka 3. From there to robolito. From robolito to everyone that is now using the idea. The "Hey, robolito is very strong, whatever it is doing must be right" is not so convincing. The combination of everything is certainly very strong. But that does NOT mean that every thing done in it is optimal, or even reasonable. Just like the fruit example I gave with history reductions.

[mjlef]

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?

[syzygy]

Why did you stop extending all checks? Because you had a theoretical explanation that explained why it was better to not extend all checks? Or because you measured this to be better?

Apparently you didn't read what he wrote, as he was very clear that not only did he not stop extending ALL checks, he gave an ELO boost for what he DID decide to do (reduce checks that have SEE < 0).

It was a rhetorical question. I actually do have the habit of reading.

Read the rest of my statement which again stresses my belief that it is not done in the top engine for folkloristic reasons.