PVS, window, and mate

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
dragontamer5788
Posts: 96
Joined: Thu Jun 06, 2019 6:05 pm
Full name: Percival Tiglao

Re: PVS, window, and mate

Post by dragontamer5788 » Wed Aug 21, 2019 6:41 pm

xr_a_y wrote:
Wed Aug 21, 2019 6:10 pm
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
Posts: 60
Joined: Fri Mar 15, 2019 7:46 pm
Location: Germany
Full name: Fabian von der Warth

Re: PVS, window, and mate

Post by fabianVDW » Wed Aug 21, 2019 7:12 pm

xr_a_y wrote:
Wed Aug 21, 2019 6:10 pm
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!
Author of FabChess: https://github.com/fabianvdW/FabChess
A UCI compliant chess engine written in Rust.
FabChessWiki: https://github.com/fabianvdW/FabChess/wiki
fabianvonderwarth@gmail.com

User avatar
xr_a_y
Posts: 707
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: PVS, window, and mate

Post by xr_a_y » Thu Aug 22, 2019 5:05 am

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

Sven
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: PVS, window, and mate

Post by Sven » Thu Aug 22, 2019 11:47 am

xr_a_y wrote:
Wed Aug 21, 2019 6:10 pm
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 Schüle (engine author: Jumbo, KnockOut, Surprise)

fabianVDW
Posts: 60
Joined: Fri Mar 15, 2019 7:46 pm
Location: Germany
Full name: Fabian von der Warth

Re: PVS, window, and mate

Post by fabianVDW » Thu Aug 22, 2019 3:59 pm

xr_a_y wrote:
Thu Aug 22, 2019 5:05 am
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.
Sven wrote:
Thu Aug 22, 2019 11:47 am
xr_a_y wrote:
Wed Aug 21, 2019 6:10 pm
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.
Author of FabChess: https://github.com/fabianvdW/FabChess
A UCI compliant chess engine written in Rust.
FabChessWiki: https://github.com/fabianvdW/FabChess/wiki
fabianvonderwarth@gmail.com

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: PVS, window, and mate

Post by Pio » Thu Aug 22, 2019 8:22 pm

xr_a_y wrote:
Tue Aug 20, 2019 3:18 pm
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

User avatar
xr_a_y
Posts: 707
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: PVS, window, and mate

Post by xr_a_y » Fri Aug 23, 2019 8:39 am

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.

User avatar
hgm
Posts: 23526
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: PVS, window, and mate

Post by hgm » Fri Aug 23, 2019 1:46 pm

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.

User avatar
xr_a_y
Posts: 707
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: PVS, window, and mate

Post by xr_a_y » Fri Aug 23, 2019 3:45 pm

hgm wrote:
Fri Aug 23, 2019 1:46 pm
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
Posts: 60
Joined: Fri Mar 15, 2019 7:46 pm
Location: Germany
Full name: Fabian von der Warth

Re: PVS, window, and mate

Post by fabianVDW » Fri Aug 23, 2019 5:00 pm

xr_a_y wrote:
Fri Aug 23, 2019 3:45 pm
hgm wrote:
Fri Aug 23, 2019 1:46 pm
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
Author of FabChess: https://github.com/fabianvdW/FabChess
A UCI compliant chess engine written in Rust.
FabChessWiki: https://github.com/fabianvdW/FabChess/wiki
fabianvonderwarth@gmail.com

Post Reply