typo
as an aside
https://expositor.dev/pvs#when
Typically, zero-window pruning is not attempted for the first successor of
a node because the first successor is expected to meet or exceed alpha, in
which case the full-window search will have to be evaluated anyway. Since
the zero-window search is expected to be useless, implementations simply
begin the full-window search right away.
More correctly, the first successor meets or exceeds alpha in PV and Cut nodes
with perfect ordering, but not in All nodes. **It’d be reasonable, then,
to attempt zero-window pruning for every successor of an expected-All node
(including the first), but as far as I’m aware, no one has tried this.**
(We might expect it to be fairly useless since there shouldn’t be many
All nodes in the search tree from the root if move ordering is accurate
– they’d only appear in zero-window trees, as we’ll see below.)
If the first successor of an expected-PV node fails to meet alpha, the next
successor is predicted to meet or raise alpha instead. Then the zero-window
search of the second successor is expected to be useless (just as the
zero-window search of the first successor was expected to be useless),
**which suggests an implementation oughtn’t attempt zero-window pruning yet
but instead simply begin the full-window search right away (and so on until
a successor meets alpha). As far as I’m aware, no one has tried this.**
This is an incorrect guess only when the expected-PV node is ultimately
found to be an All node. (The reasoning for attempting zero-window pruning
after the first successor fails low might be, “we tried the only reasonable
successor and failed, so this position probably isn’t viable”).
typo
is anyone aware of someone trying either of the two bolded things?
ciekce
is the second one referring to not doing PVS zero-window searches until alpha is
raised?
typo
ye
ciekce
that is referred to as "CPW PVS"
typo
what
really
ciekce
because it was what the PVS example on CPW used to do
typo
huh
ciekce
it is drastically worse in practice than just doing them after the first move
typo
i wonder why
ciekce
I couldn't concretely tell you tbh
typo
i wonder what CPW does specifically
ciekce
it was a terrible noob trap
typo
i’ve never seen the source
ciekce
https://www.chessprogramming.org/index.php?title=Principal_Variation_Search&diff=26969&oldid=26237
typo
oh that should be bSearchPv = false if score >= alpha (not score > alpha)
and one’d do this only in expected-PV nodes
ciekce
what would this look like
ciekce
I would expect it to be terrible in an established engine because the rest of
the search is built around doing it the conventional way
typo
it’s still possible that it fares worse
typo
for... reasons (perhaps it’s better to search twice – once to populate history
tables and transposition entries, the second to properly search)
what about the first bolded thing?
ciekce
well an expected allnode isn't an expected pv node
so its children (including the first) aren't either
so !pv pruning already happens in most (all?) engines
typo
it’s taking me a bit to work out what you mean
ciekce
it could be that I misinterpreted you
can you elaborate on the bolded bit
typo
if i’m understanding correctly
by !pv you’re referring to the zero-window search flag
not whether it’s an expected-PV node or not
ciekce
Yes
Well
they're the same thing?
typo
well, no
but also yes
typo
https://expositor.dev/pvs#example
```
P−V
┏━━━━━━━━━━━━━━━━━━━━━┛────┬──────────┬─────┐
F Z Z Z
P−V Skp Skp Skp
┌───────────────┗━━━┓───────────┐
F *Z+F Z
Cut P−V Skp
│ ┏━━━━━┛─────┐
F F Z
All P−V Skp
┌─┴─┐ ┌───┬───┃───┬───┐
F Z F Z Z+F Z Z
Cut Skp P−V Skp P−V Skp Skp
```
at the node marked with *, zero-window pruning is attempted in most engines
merely b/c it isn’t the first successor
in that search, the zero-window flag will be true
despite the fact that * is an expected-PV node (if we believe its predecessor is
PV node but move ordering is fallible)
however, the node will be re-searched with a full-window and in that search the
zero-window flag will be false
ciekce
is the zero-window search an expected pv node?
typo
what does that mean
ciekce
well that particular move has two children
one is an expected cutnode (and has full-window flag, PvNode, set to false)
typo
expected-Cut in which search?
ciekce
and because that node failed low, and thus raised alpha in the parent, it is
re-searched, and that child is an expected pv node (and has PvNode set to true)
typo
in the search tree of the root (the full-window tree) the left child is an
expected-PV node
but in the zero-window search tree for * (attempting to prove that * will fail
low, so that it can be pruned) the left child is an expected-Cut node
ciekce
Indeed
I am confused where the disconnect is
we seem to be saying the same thing
typo
well an expected allnode isn't an expected pv node
so its children (including the first) aren't either
so !pv pruning already happens in most (all?) engines
the point you are making is that, although the search tree of the root (the
full-window search) can have All nodes, it will never have an expected-All
node
typo
which... i have to think about for a moment, but i believe it holds, if one’s
expectation policy is
• successors of expected-Cut are expected-All
• successors of expected-All are expected-Cut
• successors of expected-PV are expected-PV until alpha is met or exceeded
(and expected-Cut thereafter)
and given the fact that, as a theoretical matter, a Cut node (Cut node in fact,
not expected-Cut) for which zero-window pruning is attempted will always be
pruned
typo
i suppose my thinking was, you may have an expected-Cut node that you attempt
to zero-window prune but (due to search instability / hysteresis) does not
actually get pruned!
but it’s still an expected-Cut node
and so you’d predict its children are expected-All nodes
(and then it’s not true that the search tree of the root doesn’t have any
expected-All nodes)
typo
am i making sense here?
ciekce
I'm slightly lost by this
a Cut node (Cut node in fact, not expected-Cut) for which zero-window pruning
is attempted will always be pruned
typo
if there is not search instability, then a node whose score (true score) is less
than alpha will provably be pruned by a zero-window search
ciekce
Are we thinking of completely different things with "zero-window pruning"
typo
https://expositor.dev/pvs#description
The term “principal variation search” is something of a misnomer because
PVS is not a distinct search algorithm but α/β minimax with an additional
pruning rule:
> Before searching a successor, attempt to prove that the search will fail
> low (return a value beneath alpha), and if successful, skip the successor.
The proof that the full-window search will fail low takes the form of a
zero-window search, which has the property of failing low exactly when the
full-window search will fail low. That is, −ret(Z) < α implies −ret(F) < α.
ciekce
are you talking about the PVS zero-window search to prove that a move cannot
raise alpha?
AHA
yes, we are talking at complete cross purposes
I do not think of that as a pruning technique at all
by "zero-window pruning" I had in mind pruning techniques that are only applied
in nodes with zero windows
e.g. rfp, nmp
typo
a pruning rule in the same way that α/β is a pruning rule ^^'
admittedly, these two are very different than all the other pruning rules
(er, the others are pruning heuristics i suppose?)
ciekce
well yes, of course
but you would never see a regular here refer to it as such
ciekce
to the point that I don't register it as one
ciekce
re: the edit - yeah, "pruning" stuff would generally just refer to heuristics I
feel
well
mainly because there's so little sound stuff
just a/b (and pvs) and mdp
mate distance pruning
typo
i suppose my thinking was, you may have an expected-Cut node...
perhaps this makes sense now
but i’m not completely confident in my conclusion
typo
maybe a way to describe your model – for the search tree of the root to never
have an expected-All node – in which case the zero-window flag and expected-PV
flags collapse
typo
is that the expectation method is not
• successors of expected-Cut are expected-All
• successors of expected-All are expected-Cut
• successors of expected-PV are expected-PV until alpha is met or exceeded
(and expected-Cut thereafter)
but instead
• successors of expected-Cut are expected-All
• successors of expected-All are expected-Cut
• successors of expected-PV nodes are expected-PV until alpha is met or exceeed
(and expected-Cut thereafter) unless a zero-window search fails (in which case
the successor is expected-PV)
typo
this way, expected-Cut nodes are always actually pruned by a successful
zero-window search (and we never see their expected-All node sucessors!)
or are revised into being expected-PV
ciekce
I think that is what I meant as well?
typo
okay, this makes sense!
typo
that’s actually an interesting question
how often does a zero-window proof not succeed but the node actually turn out
to be a Cut node?
i’ll have to gather some stats sometime
typo
ugh this means i have more writing to do
typo
since now i want to add a section on what i figured out
typo
documenting that in PVS, “how you predict a node” is more complicated
than what i present on the page about α/β pruning
toanth
for most engines here, the first child of an expected pv node is an expected pv
node, all other children are expected cut nodes (and are therefore searched
with a zero window).
If a move would actually raise alpha (so the child wasn't a cut node), then it's
re-searched. The first re-search is still done with a zero window, but without
lmr. If that also gives you a score > alpha, you re-search it as a pv node,
with the full window.
typo
yeah, i was aware, but i omitted the reduced-search / nonreduced-search split to
focus on PVS itself
typo
in other words, https://expositor.dev/alpha-beta#predicting is not what people
actually do in PVS
it’s instead “a successor of an expected-PV node is expected-PV until alpha is
met or exceeed (and expected-Cut thereafter, unless a zero-window search fails,
in which case the expectation is revised and the successor expected-PV)”
typo
actually, it’s not even that
typo
you guess the second sucessor is expected-Cut even if the first successor failed
low!
typo
which means you have very strong belief in your move ordering and are sorta
doing this:
If you strongly believe your move ordering is perfect and the first successor
fails to raise alpha (meaning it was a Cut node), then you should consider
yourself an expected-All node instead of an expected-PV node.