Transposition table pruning

[bob]

I see no reason to treat PV vs non-PV nodes any differently. That is a bad misconception. Why would you want to search the PV one way, and then search the other moves another way?

I suspect avoiding transposition table cutoffs in the PV became popular due to its use in Fruit. It doesn't make a lot of sense to me either.

I think that for an engine that is used for analysis is the way around: It does not make any sense to gain almost nothing in terms of search speed and lose the PV, which is a valuable piece of information. People are crazy about gaining 1 elo point and forget how a true chess player may use the engine.

Miguel

But Fruit also uses other PV-dependent techniques for example, different extensions in full nodes vs. zero-width nodes. I think the general idea is that you are going to cut most of those nodes anyway, so you cut the tree size a bit. If the search throws up anything really interesting that node will get re-searched with the full extensions. A bit like LMR but playing with the extensions. This is now done in quite a few strong programs.

I think those are important reasons, for me at least and Miguel's remarks are not technical, so not much dispute about that.

Another simple reason why PV- nodes and Non PV nodes are different; not that this is required per sé, but usually PV nodes will be searched by Aspiration window search, and Non PV nodes will be searched by a Null window search.

This is a little mixed up with respect to terminology.

normal alpha/beta would start with -infinity,+infinity as the bounds at the start of an iteration or search.

Aspiration search starts with a narrower window, usually centered about the previous score and with a width chosen by the author.

PVS searches the first move at any node where alpha != beta - 1 with a normal aspiration window, and then searches the remainder of the moves at that node with a null-window unless one fails high causing a re-search with the original non-null window.

PVS doesn't treat PV/ALL/CUT nodes any differently, from any perspective we might adjust, depth - reductions - pruning - extensions - etc.

Aspiration search is simply an attempt to make the overall tree size smaller, because on the first move we don't know what the score will look like, and the fully-open infinite window means no cutoffs will occur until the search establishes bounds as it goes down thru the tree below the first node. With aspiration search, we artificially narrow the initial window so that we can prune some branches even before we know the true score and/or bounds. But that is all it does. PVS is yet another optimization that produces the same result as minimax, or alpha/beta, but often (not always) with fewer nodes searched. Scores should not change. Just the time.

● The characteristics of these searches being -very?- different, this is more important than the other mentioned changes. It is not so much about treating the nodes differently, it is about the different types of search.

I don't see how the width of the window changes a thing. You _could_ search the PV with a null-window, and resolve the fail-highs normally, just as happens when you search the rest of the root moves with a null-window, and occasionally have to re-search one after a fail-high. This is not treating PV and non-PV moves differently, it is an optimization. On the first move there is no point searching with a null-window since you know the search will either fail high or low, requiring a re-search. On the rest of the moves (non-PV) you may or may not need to re-search, saving time.

● Aspiration window search under circumstances sometimes can be very costly compared to Null window search. But this is usually offset by much smaller number of PV nodes. You can afford other costly measures better in PV nodes.

What "costly measures" are you talking about when you say you can afford them in PV nodes, and imply you can't afford them in non-PV nodes? I'm missing that point completely.

● In my view all the other differences are just ways of making these two types of searches work together better.

That does not mean any of the different ways of handling PV nodes and Non PV nodes -in Stockfish or other programs- are all necessary, or even any of them, but it just makes sense that PV nodes will be more valuable, otherwise they would not be PV nodes. There is nothing mysterious about that, I'm not claiming having new insights here but it is also no 'misconception'. In my humble opinion

Eelco

Actually PV nodes are no more or less valuable than the rest of the moves. Alpha/Beta proves this quite clearly. The goal is to search _all_ of the moves, and find the best one. If you really treat PV and non-PV nodes differently, you make it _much_ harder for the non-PV nodes to become PV nodes. If you do that, why not just abort the search after the first move is completed and go on to the next iteration? Answer: Because we are not sure the first (so-called PV) move is the best move, we need to prove it. And proving it requires the same level of analysis as we applied to compute the PV score, otherwise we are comparing apples and oranges.

[jdart]

Actually PV nodes are no more or less valuable than the rest of the moves. Alpha/Beta proves this quite clearly. The goal is to search _all_ of the moves, and find the best one. If you really treat PV and non-PV nodes differently, you make it _much_ harder for the non-PV nodes to become PV nodes.

This is the conservative approach. But like most chess programming we are talking about heuristics. Many times, with good move ordering, the first move or the first few moves kill all the alternatives by a good margin. That is why LMR, futility and history pruning, etc. work effectively, and also why it may make sense to reduce extensions in non PV nodes. We allow these techniques to eliminate poor alternatives with a shallower search or even no search. There are always going to be cases where these heuristic assumptions fail but the idea is that you are going to get more depth faster with aggressive pruning, so you will get the "right" move eventually, maybe in a later iteration.

Empirically this seems to work because Fruit, Toga, Stockfish, etc. are strong programs. Would they be better with a more conservative approach? I don't know but I suspect not.

[bob]

Actually PV nodes are no more or less valuable than the rest of the moves. Alpha/Beta proves this quite clearly. The goal is to search _all_ of the moves, and find the best one. If you really treat PV and non-PV nodes differently, you make it _much_ harder for the non-PV nodes to become PV nodes.

This is the conservative approach. But like most chess programming we are talking about heuristics. Many times, with good move ordering, the first move or the first few moves kill all the alternatives by a good margin. That is why LMR, futility and history pruning, etc. work effectively, and also why it may make sense to reduce extensions in non PV nodes. We allow these techniques to eliminate poor alternatives with a shallower search or even no search. There are always going to be cases where these heuristic assumptions fail but the idea is that you are going to get more depth faster with aggressive pruning, so you will get the "right" move eventually, maybe in a later iteration.

Empirically this seems to work because Fruit, Toga, Stockfish, etc. are strong programs. Would they be better with a more conservative approach? I don't know but I suspect not.

Never know till the test is run. I've already tested the history counter stuff in these programs and their Elo slightly increases when it is removed from the LMR decision making. Just because something is present doesn't mean it is optimal at all.

[hgm]

I thought you already tested the effect of not doing hash cutoffs in PV nodes, and reported here that you could not detect any Elo difference because of this.

[bob]

I thought you already tested the effect of not doing hash cutoffs in PV nodes, and reported here that you could not detect any Elo difference because of this.

My recall was that I eliminated _exact_ cutoffs. Not upper/lower cutoffs. I may well be wrong. The exact cutoffs are the ones that tend to chop the PV off short. I interpreted this discussion as not allowing _any_ cutoffs on PV nodes, which is a bit different.