PVS, window, and mate

[xr_a_y]

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 ?

[jhellis3]

I can think of 3 things:

1. Mate distance pruning.

2 Shift alpha / beta on subsequent fail high/lows in order to keep the window somewhat reasonable.

3. In SF everything non-pv non-mainline is done 0 window, with the exception of if something else on the pv returns a value within the window it is searched full (window) width.

[xr_a_y]

I can think of 3 things:

1. Mate distance pruning.

2 Shift alpha / beta on subsequent fail high/lows in order to keep the window somewhat reasonable.

3. In SF everything non-pv non-mainline is done 0 window, with the exception of if something else on the pv returns a value within the window it is searched full (window) width.

Unless a bug is hiding somewhere those 3 things are already done in Minic.

[dragontamer5788]

Lets standardize upon a notation first. P is the root position. P.1 is the first child. P.1.20 is the 20th child of the 1st child of the Root. P.1.20.5.30.8 is 5-plys deep (8th move of the 30th move of the 5th move of the 20th move of the 1st move of the root position). Lets say position P is white-to-play. If white chooses the 0th move, then the new position is represented as position P.0.

With notation out of the way, lets say P.3.1.4.1.5 is a "Deep mate" with value +infinity (Black "to move" but black has no moves because it is a lost position). Has this move really proven that the overall search will require an exhaustive search? No, not at all. All you have proven is that Move#1 in position P.3.1.4 was the wrong move for Black to have made.

A properly working "aspiration window" is supposed to ignore these deep mates, under the assumption that Black had a better move available. P.3.1.4.1.5 is supposed to trigger Beta-cutoff! There's no way Black should be getting checkmated, because (under an aspiration window assumption) Black probably had a better sequence of moves available.

EDIT: I realize I'm talking about Alpha-Beta search, not PVS search. Still, I'm sure the concept is similar. Any "deep mate" should only resume the search from P.3.1.4. You should NOT be resetting the window at P unless you have proven that all moves available at P.3.1.4 results in a mate.

EDIT2: Upon reading up on PVS search more, I've come to the conclusion that you've perhaps made a mistake in your implementation. The PVS Search algorithm in Wikipedia (https://en.wikipedia.org/wiki/Principal ... ion_search), if it finds a "deep mate" at P.3.1.4.1.5, should restart the search at position P.3.1.4. You shouldn't be searching any deeper than 2 ply (unless the entire P.3.1.4 branch leads to checkmate: at which point the PVS search will back up to P.3 and try to prove that position instead).

[Sven]

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 ?

I assume you are talking about the following case: you search at root with nominal depth D and a normal aspiration window that has no mate scores as bounds; you are using fail-soft alpha-beta; the search uses all kinds of pruning to be fast; and you get a fail high because one root move returns a mate score with a mate distance higher than D, and this means a beta cutoff at root so you skip all remaining root moves. Now the next step is to repeat the root search with a "better" window.

If my assumption is right then why would you switch off pruning for the re-search? And why would you assume that searching one root move with pruning enabled could ever return a mate score that is false? Do you also prune when the king is in check? If you don't then your search should never return a forced mate when it actually is not forced. It may return a non-optimal mate score (i.e. there may, and will often, be a shorter path to mate). If pruning leads to selectivity at some node so that only a subset of all moves is searched (so no full alpha-beta) and all moves being searched lead to being mated then the node fails low and the parent fails high, but the parent does not propagate a mate score up the tree. Same for mating instead of being mated: if all moves from the subset lead to mating the opponent then that node fails high and the parent fails low but even here no mate score gets propagated up.

The only way I can see how wrong mate scores can survive up to the root is a bug ... One possible bug could be to propagate mate scores resulting from a null move search, that should be limited to "beta".

[xr_a_y]

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 ?

I assume you are talking about the following case: you search at root with nominal depth D and a normal aspiration window that has no mate scores as bounds; you are using fail-soft alpha-beta; the search uses all kinds of pruning to be fast; and you get a fail high because one root move returns a mate score with a mate distance higher than D, and this means a beta cutoff at root so you skip all remaining root moves. Now the next step is to repeat the root search with a "better" window.

If my assumption is right then why would you switch off pruning for the re-search? And why would you assume that searching one root move with pruning enabled could ever return a mate score that is false? Do you also prune when the king is in check? If you don't then your search should never return a forced mate when it actually is not forced. It may return a non-optimal mate score (i.e. there may, and will often, be a shorter path to mate). If pruning leads to selectivity at some node so that only a subset of all moves is searched (so no full alpha-beta) and all moves being searched lead to being mated then the node fails low and the parent fails high, but the parent does not propagate a mate score up the tree. Same for mating instead of being mated: if all moves from the subset lead to mating the opponent then that node fails high and the parent fails low but even here no mate score gets propagated up.

The only way I can see how wrong mate scores can survive up to the root is a bug ... One possible bug could be to propagate mate scores resulting from a null move search, that should be limited to "beta".

All your assumption are right. And null move is protected from returning mate score. For some days now I continue to prune even if beta at root is a mate score and this indeed allow for better mate detection.

Probably I need to control window size a little more, trying to raise alpha at root if beta is huge to speed the re searches a little bit.

And why would you assume that searching one root move with pruning enabled could ever return a mate score that is false?

Well, pruning is disabled when in check ... but there is a lot of moves that are pruned without being in check before that crucial moment and some of them may have been better for the side being mated.
I'm not good at creating positions but it feels possible to find one where white on move thinks it can mate in 10 but in fact black can mate in 6 after first white move but black mating line is full of crazy sacrifices that are maybe pruned by SEE (for both side).

[dragontamer5788]

EDIT: I don't think I know what I'm talking about anymore... lemme sit back and listen for a bit.

[Sven]

And why would you assume that searching one root move with pruning enabled could ever return a mate score that is false?

Well, pruning is disabled when in check ... but there is a lot of moves that are pruned without being in check before that crucial moment and some of them may have been better for the side being mated.

But such a node fails low so the parent node fails high, and the mate score will be ignored at higher levels in the tree. Also the pruning code itself should ensure (not only for null move pruning) that it does not fire in case of a mate score. I would go through all places in your search where pruning can be applied, and answer the question: at this point, how would it be possible that I return a "being mated" score without having searched all legal moves, unless that score is taken from the TT?

[dragontamer5788]

And why would you assume that searching one root move with pruning enabled could ever return a mate score that is false?

Well, pruning is disabled when in check ... but there is a lot of moves that are pruned without being in check before that crucial moment and some of them may have been better for the side being mated.

But such a node fails low so the parent node fails high, and the mate score will be ignored at higher levels in the tree. Also the pruning code itself should ensure (not only for null move pruning) that it does not fire in case of a mate score. I would go through all places in your search where pruning can be applied, and answer the question: at this point, how would it be possible that I return a "being mated" score without having searched all legal moves, unless that score is taken from the TT?

Even if pruning were applied, that only reduces the search width. If a particular position had 30 legal moves, but it were pruned down to 5 moves under consideration, the code should still exhaustively check all 5 moves before returning the (proposed) checkmate... even if it uses LMR / SEE to ignore the other 25-moves.

[xr_a_y]

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...