PVS, window, and mate

[dragontamer5788]

What if White to play. First move of the supposed deep mate sequence for White is a quiet move (for instance a pawn push to reduce King mobility). Best answer for black is in fact a shorter mate or a dramatic material gain that White is not viewing because it starts by a queen sac.

I like giving names to these positions.

* Starting position: P. Lets assume a "pruned" search only searches the first 6 moves (#1 through #6) per position. The reality is that 36 moves are available per ply however.

* AIs always consider the first move-chain first. Lets say at 10-ply, position P.1.1.1.1.1.1.1.1.1.1 (that is: White plays move#1, followed by Black plays move#1... for 10 ply) results in a "deep mate" where White wins. I'll call this position P(1^10) for short.

* Black apparently finds a shorter-mate at P.1.1.1.1.1.7.1.2 (Black wins). (At 5th ply, Black leaves the principal variation and starts to search move#7 instead, which eventually results in Black-wins position). P(1^5).7.1.2 for short.

Remember: White is pruning only to the first 6 moves in the assumption. So white will never consider move#7 at any ply. Black "doesn't prune", so move#7 at P(1^5) is certainly a consideration: resulting in the position P(1^5).7.

Does the above notation describe what you are worried about adequately? I'm just trying to assign names to your hypothetical positions, so that we can speed up the discussion.

It feels to me that if White want to be sure of its supposed mate, pruning shall be switch off.

If you wanted to be "sure" of anything, you wouldn't be pruning in the first place! The idea of pruning is that you're willing to draw conclusions from only a subset of the analysis.

White, across the 10-ply, only has to consider a search tree of size ~60 Million. Black, searching the whole 36-moves per ply, will instead have a search tree of size 3.6 Quadrillion. White can perform its 10-ply analysis in a incredibly small fraction of the time it takes for Black to consider all the moves.

But consider how the "deep mate" found in P(1^10) looks like to white's PVS search. P(1^10) is black to move (can't move, so checkmate). White, at P(1^9) sees that position as +infinity. Black, at P(1^8), sees the position as -infinity, which fails-low.

Since -infinity fails low, White's AI is going to search P(1^8).2, P(1^8).3, P(1^8).4... etc. etc. The only way "checkmate" gets passed up through the P(1^8) position is if all moves under consideration (move#1 through move#6, assuming heavy pruning) all result in checkmate.

Then again, when the "checkmate" is returned to P(1^6) (two ply up higher), the checkmate has to survive through another fail-low check across the positions P(1^6).2, P(1^6).3, P(1^6).4.

Even with deep pruning, I am unsure of how White's "deep mate" gets passed all the way up to the eval(P) level.

[fabianVDW]

What if White to play. First move of the supposed deep mate sequence for White is a quiet move (for instance a pawn push to reduce King mobility). Best answer for black is in fact a shorter mate or a dramatic material gain that White is not viewing because it starts by a queen sac.

It feels to me that if White want to be sure of its supposed mate, pruning shall be switch off.

I feel lost...

Pruning does not have to be switched off in order to prove for white that there is a mating sequence.

Consider this search tree. Whites "supposed" mating sequence is (from Dragontamers notation) P.1.1.1... and white also has (even shorter) mating sequence also for all other moves P.1.2 - P.1.34. Move P.1.35 will lead into a mating sequence for Black(White getting mated). Suppose move P.1.35 is one of the least considerable, like a queen sac. If I understand you correctly, your worries are that white will not find move P.1.35 because of deep pruning.

White start searching.
It searches the move P.1
Black now searches P.1.1 and finds the mate score. Now the alpha for Black in this position is a negative mate score. Alpha will continue to be -Mate for all other moves P.1.2 - P.1.34. For move P.1.35, a lot of LMR is planned, because it is a negative capture, its history score will supposedly be very bad, and it is the last move to be considered. The reduced search does not find Blacks mating sequence, but also does not find a forced mate by white( as is requirement). Now this search score will be > alpha, because alpha is still -Mate Score. Thus it will be researched with full depth (no LMR) and Black will find the mating sequence or atleast a sequence in which it will not be mated( We know by definition that there is a sequence for black that will not result into getting mated. And most of the pruning methods [like futility pruning for example] will not skip moves when not proven that there is a non mating line). In anyway, it is now proven for white, that there is indeed not a forced mate for white. Proving the forced mate for black if white plays move P.1 is a another story since probaply futility pruning etc. will truncate that search tree. But a proven mate is definitly proven!

[xr_a_y]

Ok for lmr, but what about SEE of supposed bad cap?

[Sven]

What if White to play. First move of the supposed deep mate sequence for White is a quiet move (for instance a pawn push to reduce King mobility). Best answer for black is in fact a shorter mate or a dramatic material gain that White is not viewing because it starts by a queen sac.

That is a valid example for missing a forced mate. But the key point was the opposite: how would it be possible to see a forced mate when in fact there is none?

[fabianVDW]

Ok for lmr, but what about SEE of supposed bad cap?

The same priniciple applies there. As long as you dont SEE-Prune moves when you don't have a non mating line, there is no way that Whites supposed mating sequence will be propagated up to the root.

What if White to play. First move of the supposed deep mate sequence for White is a quiet move (for instance a pawn push to reduce King mobility). Best answer for black is in fact a shorter mate or a dramatic material gain that White is not viewing because it starts by a queen sac.

That is a valid example for missing a forced mate. But the key point was the opposite: how would it be possible to see a forced mate when in fact there is none?

Sven is right, missing a mate is easy with pruning techniques (which does not really matter as long as the found line is still winning). But a mate sequence is definite.

[Pio]

I think I already started a similar discussion some months ago ... anyway

I'm struggling to fix something inside Minic. Here's the thing : when doing a window search you gradually increase alpha and/or beta until the return score fits in the given interval. When an engine discover a deep mate, let's say at depth >30 !, the fully open (or even semi-open) window search needed to "validate" the mate is extremely slow and moreover to ensure mate is indeed one, some pruning shall be switch off ... There is no way a half open window search without lmr and see forward pruning is going to finish some days ...

So I'm looking for a way to handle deep mate better. What are your advice ?

Hi, the only thing I can think of is that your transposition table overwrite some PV nodes. If you have a couple of slots in each bucket and always prioritise PV nodes in your replacement scheme and do not have any bugs I do not think it is possible to have your behaviour. Maybe you miss the stand pat score in your quiescence search somewhere.

/Pio

[xr_a_y]

Interresting point. For now i use 2 slots per bucket. One being always replace, the other replace by depth. You are suggesting a pv only slot. I ll try that asap.

[hgm]

It should not be possible to prune or reduce moves when the alternative is being checkmated. Such moves would score way above alpha, no matter how unfavorable you would estimate their outcome based on SEE and such. And the only way to refute such alternative moves would be through an even faster forced mate. As long as this is not found yet, the alternative move would become PV.

[xr_a_y]

It should not be possible to prune or reduce moves when the alternative is being checkmated.

This is also my feeling. But this requiere that even not being currently in check, if alpha and/or beta bound is a mating/ed score then hard pruning shall be switch off.

[fabianVDW]

It should not be possible to prune or reduce moves when the alternative is being checkmated.

This is also my feeling. But this requiere that even not being currently in check, if alpha and/or beta bound is a mating/ed score then hard pruning shall be switch off.

Only alpha should be enough. This is what most engines and SF do, anyway IIRC