Why do engines lack mate solving?

[chessmobile]

I know from experience that those mephisto units from late 80's and early 90's would fail to find the mate when one did exist on some occasions.

[hgm]

Agree. That is why I have put in a dedicated mate solver that only prunes based on alpha-beta and has no extensions. However, that would also be totally easy for PC based engines.

But even a full-width alpha-beta search is an extremely poor way to find mates. In Shogi finding the fastest mate (where checks are not counted,as while you check the opponent he must evade, and cannot advance his own mate plans) does actually provide Elo, as most games end in a race to checkmate the opponent. Engines there typically do use a mate finder, which is completely independent from their normal search and evaluation. Usually it is based on proof-number search. These searches often finds mate in 20 or 30 (counting the checks), inpositions where alpha-beta would probably not get beyond mate in 3.

The question of course is: when there code for finding mates and for playing a game is completely independent, why would you want it to be in the same .exe file? It would make as much sense as wanting Stockfish to also encrypt e-mails, plan routes for car avigation, or search for extraterrestrial intelligence...

[Ras]

But even a full-width alpha-beta search is an extremely poor way to find mates.

Well yes, I sort of have to agree. Usually, the analysis mode shows the mate earlier. For a classic 7-mover by Nimzowitsch, my analysis mode throws out the solution after 10s at depth 10 while my mate solver mode takes 42 minutes.

(FEN: q5k1/5p2/7Q/r2b1B2/8/8/r2R3K/8 w - - 0 1 )

But the issue is - it is not guaranteed in analysis mode. Because the task at hand is not to find mate, but to find mate within a given maximum of moves.

Or earlier, but that is trivial by doing an iterative search at ply depth 1, 3, 5, 7, ... to the maximum depth. However, this also implies that extensions are not the best idea because they might overlook a shorter mate that isn't in an extension path.

Usually it is based on proof-number search. These searches often finds mate in 20 or 30 (counting the checks), inpositions where alpha-beta would probably not get beyond mate in 3.

For real games, that makes sense. But not for problem search.

The question of course is: when there code for finding mates and for playing a game is completely independent, why would you want it to be in the same .exe file?

Because most of the code is the just reuse of existing pieces. Move generator, check verification, hash table use, potential SMP. Even the plain alpha-beta, for pre-sorting the moves at a shallow search depth. Everything is already there anyway.

For PC engines, pasting over a position is already there, too, e.g. via an FEN string. It can't be that hard to use UCI or so to tell the engine "with that position, what moves lead to mate-in-X, if any?". And to have the engine answer something useful in case the original position instead has a forced mate for the opponent.

[yurikvelo]

Because most of the code is the just reuse of existing pieces. Move generator, check verification, hash table use, potential SMP. Even the plain alpha-beta, for pre-sorting the moves at a shallow search depth. Everything is already there anyway.

Matefinder (Stockfish clone) does exactly what you say - reuse most of SF code + add specific DTM-minimizer code.

There is no reason to have SF and SF-Matefinder compiled in the same EXE file.
Switching engine in GUI is not less convenient than switching UCI option.

[hgm]

But the issue is - it is not guaranteed in analysis mode. Because the task at hand is not to find mate, but to find mate within a given maximum of moves.

It will always be advantageous to search first where you have better prospects of finding something. When the maximum number of moves is given, you would only have to tell it to the engine in termsof an aspiration window, and the engine's mate-distance pruning would prevent automatically that any of the extended (or less reduced) branches would extend beyond the given depth. I am used to problems where the number of moves is not given, however.

Being able to set the root aspiration would in general be a very useful option during analysis, not just for mating problems. I wonder why engines do not have that. I even consider defining a command for it in WB protocol.

Usually it is based on proof-number search. These searches often finds mate in 20 or 30 (counting the checks), inpositions where alpha-beta would probably not get beyond mate in 3.

For real games, that makes sense. But not for problem search.

Proof-number search does make sense, because its notion of 'evaluation' correlates very well with the prospects for achieving a mate: it will spend the effort where the losing side has the fewest oppotunities to escape. A normal evaluation would go by material, which is often in the wrong direction, as these problems tend to be constructed such that you have to sacrifice a lot of material. I noticed this when solvig mate problems with my engine HaChu, which does have special modes for solvig mating problems.

Because most of the code is the just reuse of existing pieces. Move generator, check verification, hash table use, potential SMP. Even the plain alpha-beta, for pre-sorting the moves at a shallow search depth. Everything is already there anyway.

But it is all very sub-optimal for the new purpose. The egine might use aslow board representation such as bitboard, gaining the overhead back in evaluation during games, while that evaluation now is not needed. It uses alpha-beta where proof-number search would do better. It is like building an airplane out of car parts.

For PC engines, pasting over a position is already there, too, e.g. via an FEN string. It can't be that hard to use UCI or so to tell the engine "with that position, what moves lead to mate-in-X, if any?". And to have the engine answer something useful in case the original position instead has a forced mate for the opponent.

These are completely trivial parts of an engine, normally copy-pasted from other engines, so sharing those in the same executable doesn'toffer any real savings. Of course it is possible to use UCI or WB options to tell an engine what to do. This is also how it works in HaChu. You just go to the engine settings dialog, where there is a combobox to set it for normal play or mate solving for white or for black.

It islike Yuri says, though: switching an engine from one mode to the other through the engine settings is just as much work for auser as switching from one engine to another. And the latter is much more flexible. You could change from Stockfish to Chest, rather than being convicted to some Stockfish-like replacement for a true mate solver.

[Ras]

It will always be advantageous to search first where you have better prospects of finding something.

I have been thinking about this, and my solution is to just change the perspective. Instead of seeing the resulting, reduced search tree for the 7 move puzzle by Nimzowitsch e.g. as a 5-mover extended by 2 moves, why not regarding it as a reduced 7-mover?

I'm only reducing the moves for the side to move, not for the side to be mated.

So what I'm doing now is:
- use depth 7 moves, but only consider check-giving moves for the side that shall mate.
- if that doesn't give a solution, use all moves in the root position, but only consider check-giving moves after that.
- move the limit for the check-giving further and further until it reaches 1 (last ply must deliver check).

The puzzle in question is particularly profiting because the whole solution is a sequence of checks; but also other puzzles enjoy a big speedup. Instead of 42 minutes, finding the mate now takes less than a second! On a Cortex-M4 with 168MHz and 96kB hashtables (in mate search mode).

Of course, the re-search still takes 42 minutes because everything must be tried out (minus only alpha-beta-cuts) to prove that there is no second solution.

A normal evaluation would go by material, which is often in the wrong direction, as these problems tend to be constructed such that you have to sacrifice a lot of material.

Yeah; I evaluate any position that is not mate with just 0 - with the idea being that this should enable a lot of fast alpha-beta-cutoffs (and it is easy to implement). Do you think that the basic idea is sound?

It is like building an airplane out of car parts.

Makes sense, thanks. So that point is now clear to me.

[hgm]

Yeah; I evaluate any position that is not mate with just 0 - with the idea being that this should enable a lot of fast alpha-beta-cutoffs (and it is easy to implement). Do you think that the basic idea is sound?

I'm not sure. You would like to bias it against pointless sacrifices, as without material it will be hard to checkmate. The normal end-game piece values seem irrelevant, though. It would be better to evaluate by mobility, or better yet, 'useful mobility'. E.g. count how many squares that can be used for giving checks by the attacking side are protected by each piece, and then preferentially go for those that hinder your efforts the most.

The point is that you want any sub-optimal defense to be punished as quickly as possible. I doubt it would take 42min to walk the minimal tree that you need to prove mate, for that problem. It likely takes solong because it is just randomly trying moves for the winning side in order to find the one that leads a quicker mate after the defender deviates.

It would be interesting to do a search that preferentially keeps hash entries with mate scores. And then aftery you find the solution, set the depth of all those entries to 0, so it cannot use them for cutoff, but that it can use the move. And then re-run the problem starting with that hash table to see how long it takes then.

[Ras]

Yes, these examples show the problem quite well. The mate is spotted, and with increasing depth, the mate distance decreases. The question then is when to be sure that the displayed mate is actually the sortest possible.

Especially with Stockfish, the problem becomes clear. The mate is possible in 15 moves, i.e. 30 plies. And then this:
37/52 0:09 +M20
...
53/52 3:04 +M15

Either I fail to understand the output, or Stockfish really needs more than 50 plies depth in order to reliably detect a mate in 15. Maybe because of the pruning that usually doesn't happen early in the search tree. So the high search depth is needed to move the M15 into the depth area with less aggressive pruning.

OK, but from the rest of the thread I got it that it wouldn't make sense to both up the engine with another option.

But still, mate in 15 is way more than my system could even hope to detect because its maximum recurson depth is limited to 20 plies anway. With just 28kB for the stack, there are technical barriers.

[Ras]

Do you, by chance, have some example position from back then? It's long since, but just maybe?

[Ras]

I'm not sure. You would like to bias it against pointless sacrifices, as without material it will be hard to checkmate.

With the difficulty being to discern pointless sacrifices from pointed ones.

I doubt it would take 42min to walk the minimal tree that you need to prove mate, for that problem.

Right; after the enhancement with the check-preferred reduced trees, it takes less than a second, even on the limited hardware.

What is taking so long, however, is the re-search for another solution move, which doesn't exist. In that case, it isn't about proving mate, but about proving the absence of mate.

It likely takes solong because it is just randomly trying moves for the winning side in order to find the one that leads a quicker mate after the defender deviates.

Not quite. I have always done a move-sorting so that check-giving moves are prioritised first, then captures with MVA-LVV, then moves that approach a piece to the enemy king.

It would be interesting to do a search that preferentially keeps hash entries with mate scores.

If a mate score is found, I'm returning anway. Either it is a refutation in some way (maybe even mate for the opponent), or it is already the solution PV. In both cases, there won't be a re-search of that branch.

For the overall re-searching potential double-solutions, the solution moves that would have lead to mate are blocked from the search at root level anyway, so their whole branches along with their mate score cannot be entered again.

Another reason why I'm storing only 0 results is that I always store them as "exact", even when they actually are not exact, but cutoffs. When just looking for mate, this is OK and increases the hit rate.

Plus of course that the hash tables only have a limited effect anyway, and then only in endgame-like puzzles. For the Nimzowitsch puzzle and before my change, the hash tables were worth 37% more total speed. With just 96kB, their effect is clearly limited.

However, there's still the pawn hash table that I don't use in mate search mode, worth another 24kB. With some creative pointer casting, I could put it to use, I'm just out of ideas. Actually a pity to have 24kB and ignore them.