LVA MVV with relative Pin

[Clemens Pruell]

First off, most of the time this LVA MVV method of ordering my capture
moves for Alphabeta works fine, because captures like B x R are usually
good moves.

But only recently my program (WHITE) had this position to play (FEN):

1r1qr1k1/5pbp/3p2p1/1B3b2/3PnN2/1QN5/PP3PPP/3R1K1R w - - 0 19


It needed 50 Seconds to find a somewhat 'playable' move (from my
engine's limited 8-ply point of view: Nfd5 - but strong engines can refute this) - which is a lot longer than usual.

Of course I'd like to know what makes this position so complicated (not
only for my program, also very strong and fast 5000-nps engines like
Stockfish, Houdini, Rybka or Deep Pharaon seem to have a hard time
with doing their 'usual' 20+ - ply searches. In addition to this they
can't tell me, whether White or Black is better, some say it's +0.70
from White's point of view, others say the opposite -0.70 etc. ...
Objectively ... well, I'm not an expert player (1800 rating), but
I'd say Black doesn't have enough compensation for the two lost
pawns ...)

Atm these are my three theories, why finding a best move
(or at least a reasonable score) for this position is so hard for the
programs (especially my own):

(1) 46 legal root moves. Maybe that's just too much and thus the tree
explodes automatically (?), no matter how I order the moves ?

(2) MVV LVA doesn't work properly here.
That B x R capture is likely to appear in thousands,
maybe millions of child nodes, as one of the first moves White will try,
thus instead of searching the best move first one of the worst moves
is searched first. And maybe that's the reason why the search takes so
long (?)
But what could be a workaround for this situation, when this
MVV LVA heuristic (which works so well most of the time) suddenly
performs worse than choosing the moves in random order ?
Are cases like this maybe worth the effort to keep incremental data
only for 'relative pins' (? Atm I do this only for 'real' pins) ?

(3) Maybe the position is so dynamic, that most hashmoves,
which are found from shallower iterations, will rarely be the best moves
at the subsequent iterations, and thus the whole node
(with the hashmove which didn't do the expected beta cutoff)
needs to be searched again ?
I'm generally wondering what can be done against this issue:
'Hashmove from previous iteration does not as many beta-cutoffs
as expected.'

Which of my amateurish theories is most likely the correct reason ?
This could help me a lot if only I knew at which parts of my program
I'll need to battle this issue. (Of course I'd like to keep on ordering
my moves with LVV MVA, because in most cases it helps a lot, ... except
here ...)

Thanks in advance for ANY tipps.

[Evert]

It needed 50 Seconds to find a somewhat 'playable' move (from my
engine's limited 8-ply point of view: Nfd5 - but strong engines can refute this) - which is a lot longer than usual.

That may not be too bad, in a somewhat complicated position.
Jazz switches to Qa4 at 6 ply and f3 at 14 ply, but always with a large positive score for white.

(1) 46 legal root moves. Maybe that's just too much and thus the tree
explodes automatically (?), no matter how I order the moves ?

Lots of possible moves will of course slow things down quite a bit. Maybe.

(2) MVV LVA doesn't work properly here.
That B x R capture is likely to appear in thousands,
maybe millions of child nodes, as one of the first moves White will try,
thus instead of searching the best move first one of the worst moves
is searched first. And maybe that's the reason why the search takes so
long (?)

I doubt it. After Bxe8 the first move tried would be Rxb3 and then a null-move will fail high and prune the rest of the tree. (Or am I missing something here? I only looked at the position briefly)

But what could be a workaround for this situation, when this
MVV LVA heuristic (which works so well most of the time) suddenly
performs worse than choosing the moves in random order ?
Are cases like this maybe worth the effort to keep incremental data
only for 'relative pins' (? Atm I do this only for 'real' pins) ?

Maybe, but the question is whether the extra work pays off on average. My guess is it doesn't, but you'd have to try to make sure.
An idea that might be interesting is to keep track of "bad captures" in the same way as you would keep track of killer moves, and then sort moves that have historically been bad at this search depth lower down in the list. In practice this may be dangerous though and it could hurt more than it helps.

(3) Maybe the position is so dynamic, that most hashmoves,
which are found from shallower iterations, will rarely be the best moves
at the subsequent iterations, and thus the whole node
(where the hashmove which didn't do the expected beta cutoff)
needs to be searched again ?
I'm generally wondering what can be done against this issue:
'Hashmove from previous iteration does not as many beta-cutoffs
as expected.'

That's easy to check: simply monitor how often a cut-off is caused by the first move or by a later move. That will tell you how your move ordering is doing.

[hgm]

IID protects you to a certain extent from tactically wrong moves. In HaQiKi D and Shokidoki, when I have to search 3-ply or more, I first do a 1-ply search. BxR with a soft-pinned B will then fail low (e.g. refuted by RxQ in the subsequent QS), and if there is a more modest capture later in the ranking, like QxP, that does produce a cutoff, the 3-ply search will start with this QxP (and hopefully reproduce the cutoff at 3 ply). This way, 'good captures' (according to SEE) that are obviously tactically bad (according to QS) will only waste the time of a 1-ply search, rather than a 3-or-more-ply search. This on average produced a positive effect.

I sometimes wonder if it wouldn't be better to do an open-window QS search on _all_ captures in nodes where you are gong to do a deep search, so that you can order them by QS score, rather than by SEE or victim.

[Ralph Stoesser]

I sometimes wonder if it wouldn't be better to do an open-window QS search on _all_ captures in nodes where you are gong to do a deep search, so that you can order them by QS score, rather than by SEE or victim.

I have tried it with Stockfish. Seems to not pay off in general. It might work better if one keeps track of the local quality of move ordering and does it only for subsequent iterations in case it turns out that the move ordering from previous iterations was substantial below-average.

[Clemens Pruell]

But what could be a workaround for this situation, when this
MVV LVA heuristic (which works so well most of the time) suddenly
performs worse than choosing the moves in random order ?
Are cases like this maybe worth the effort to keep incremental data
only for 'relative pins' (? Atm I do this only for 'real' pins) ?

Maybe, but the question is whether the extra work pays off on average. My guess is it doesn't, but you'd have to try to make sure.
An idea that might be interesting is to keep track of "bad captures" in the same way as you would keep track of killer moves, and then sort moves that have historically been bad at this search depth lower down in the list. In practice this may be dangerous though and it could hurt more than it helps.

Yes, that seems like a good idea!
Atm I keep track of 'historically bad' (but only 'quiet') moves
[in addition to the standard history counters], and when doing
move ordering it seems to give me better move ordering when I compare the move's success rate with its blunder rate (before deciding whether
it should be searched very soon or very late).
Maybe the same method will work for bad capture moves too.

Btw. I think I've also found the very reason why the search took so long:
My hashtable could only store 2 Mio. positions, but this root-node
produced 30 Mio. nodes ...
I got the same position analyzed more quickly (30 Sec. instead of 50 Sec) when I used a hashtable which could store 8 Mio. positions.
Of course this still means plenty of index collisions and situations, where
an arbitrary node (close to the leafs) will replace a more valuable hash
entry (close to the root), but ... well: at least it's better this way.

Thanks for your help again.
Also I'm not yet using any Null-Move or other forward pruning (too
complicated for an amateur like me...), I guess I'll need to get a lot
closer to that minimal Alpha Beta tree first.
20 Mio. explored nodes (like in this case) for 8-ply are still way too much
(even without any forward pruning).

One more thing:
I don't use Quiescence Search either (YET!), but instead I'll do a
simplified SEE for the very last piece which moved (right before the leaf
node). If there are also some other pieces 'en-pris' in that final position
(for which eval() is applied), eval() ignores this.
These other pieces were also en-pris 2 plies before that final leaf node, and thus the consequences of them, being captured, should have been evaluated (and produced a cutoff) before the current leaf node
(grand-sibling) even existed.
So if there really are some other (maybe even more valuable)
pieces en pris in the evaluated position, their loss was not tragedy
enough to cause a beta-cutoff in the parent node.
And thus I think eval() can ignore this detail.
Well, that's basically my excuse why I don't use a Quiescence Search yet.
(Truth is, of course, that Quiescence is way too complicated for me ... )

[Evert]

Yes, that seems like a good idea!
Atm I keep track of 'historically bad' (but only 'quiet') moves
[in addition to the standard history counters], and when doing
move ordering it seems to give me better move ordering when I compare the move's success rate with its blunder rate (before deciding whether
it should be searched very soon or very late).
Maybe the same method will work for bad capture moves too.

I'm actually experimenting with the reverse: bad captures (according to SEE) that end up causing a cut-off are stored as a special type of killer move. I don't have enough test games to say whether it really helps in practice of not though (I doubt it's an original idea, which means Bob Hyatt has probably tested it and can say whether it does anything).

Also I'm not yet using any Null-Move or other forward pruning (too
complicated for an amateur like me...),

Don't ignore it, it's not that hard! I'm hardly a professional.

I don't use Quiescence Search either (YET!), but instead I'll do a
simplified SEE for the very last piece which moved (right before the leaf
node). If there are also some other pieces 'en-pris' in that final position
(for which eval() is applied), eval() ignores this.
These other pieces were also en-pris 2 plies before that final leaf node, and thus the consequences of them, being captured, should have been evaluated (and produced a cutoff) before the current leaf node
(grand-sibling) even existed.
So if there really are some other (maybe even more valuable)
pieces en pris in the evaluated position, their loss was not tragedy
enough to cause a beta-cutoff in the parent node.
And thus I think eval() can ignore this detail.
Well, that's basically my excuse why I don't use a Quiescence Search yet.
(Truth is, of course, that Quiescence is way too complicated for me ... )

Again, it's not that hard - especially if you aready have a normal search working: the easiest way to do it is just ignore all non-captures, and return immediately if the static score is already above alpha (we can do no worse than that when we look at all possible captures). A more efficient way to do it is to use a specialised move generator that only produces captures, but you can manage without if you have to (certainly if you want to focus on getting things to work).

[micron]

QS is more fundamental than TT, history counters, move ordering by SEE, null-move, LMR... With disabled QS, my engine drops 400 Elo; that's more than the effect of disabling the TT.

As Evert said, QS is easy to write. It's a greatly simplified version of Search(), the only addition being a 'stand pat' evaluation before you generate and try capture moves.

Code: Select all

standPatScore = Evaluate( inBoard, alpha, beta );
if ( standPatScore >= beta ) return standPatScore;
if ( standPatScore > alpha ) alpha = standPatScore;
...
...try good captures and promotions
...

Robert P.

[Desperado]

Again, it's not that hard - especially if you aready have a normal search working: the easiest way to do it is just ignore all non-captures, and return immediately if the static score is already above alpha (we can do no worse than that when we look at all possible captures). A more efficient way to do it is to use a specialised move generator that only produces captures, but you can manage without if you have to (certainly if you want to focus on getting things to work).

i assume you didnt mean it like you wrote it ?!

if not you should fix it in your source.
only return immediatelly if staticValue >= beta, look at Robert Purves code snippet above.
(what you wrote is only valid for alpha == beta-1, so called nullWindows)

regards

[Evert]

i assume you didnt mean it like you wrote it ?!

if not you should fix it in your source.
only return immediatelly if staticValue >= beta, look at Robert Purves code snippet above.
(what you wrote is only valid for alpha == beta-1, so called nullWindows)
regards

Interesting. I didn't look at code, just quoted from memory. You're right, of course.
Funnily enough, I have static_score>=beta in Jazz, but static_score>alpha in Sjaak.

I wonder how much of a difference it makes in practice though. I guess I'll find out when I correct the problem in Sjaak and test it!