Why do engines lack mate solving?

[Ras]

I remember the 80s when the 8 bit Mephistos were capable of dedicated mate solving, along with the interesting feature of looking for alternative solution moves. That seems to have dropped out of fashion somehow. Why?

It can't be that it's hard to implement. For the CT800, it took me a weekend to add this (including looking for alternate key moves), and most of the work was to integrate it seamlessly into the user interface, which is always somewhat difficult with an embedded system.

Is multi-variant analysis actually sufficient? Do modern engines reliably detect the shortest mating paths despite possible pruning?

[yurikvelo]

Because it hurts ELO

It can't be that it's hard to implement.

it is implemented
http://talkchess.com/forum/viewtopic.php?t=61419

Do modern engines reliably detect the shortest mating paths despite possible pruning?

no, it hurts ELO

[Jhoravi]

Because Mate solving is Brute Force. It hurts depth.

[yurikvelo]

That seems to have dropped out of fashion somehow. Why?

For simple tasks, such as 7-men or less positions - exact and immediate DTM score is available for free (TB7 Lomonosov)

For hard tasks, such as 8+ positions 1980s approach do not work, solution is far beyond brute force techniques (except for very short DTMs).

Best of what is available nowdays is Matefinder (Stockfish fork) with Syzygy-6 tables - dedicated DTM-solving tool.

Probably better or faster result can be achieved with Nalimov 6-men tablebases, but they are very impractical (1TB+ size) and lack support by SF.

[kgburcham]

just an example

[D] 4k2r/p1q1np1p/1p2p1p1/2p1P1B1/6Q1/2P5/PP4PP/3R2K1 w k -


8 processor(s) found, POPCNT available
NUMA configuration with 1 node(s), offset 0
Nalimov 6 men EGTB available - 999 MB cache
Engine: Houdini 4 Pro x64 (8192 MB)
by Robert Houdart

22/66 0:29 +30.25 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Qd6+ Kc8 5.Bxe7 Kb7 6.Qd7+ Ka6 7.a4 c4 8.Qc6 f5 9.exf6 h5 10.f7 h4 11.Qxe6 Kb7 12.Qe4+ Kc7 13.Qe5+ Kb7 14.Qxh8 (910.638.271) 30796 TB:2
23/66 0:30 +M24 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 c4 4.Qd6+ Kc8 5.Bxe7 Kb7 6.Qd7+ Ka6 7.Qc6 f5 8.exf6 g5 9.Qxc4+ Kb7 10.Qe4+ Kc7 11.f7 g4 12.Qe5+ Kc6 13.Qxh8 Kb7 14.f8Q (936.149.071) 30776 TB:2
24/66 0:31 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 c4 4.Qd6+ Kc8 5.Bxe7 Kb7 6.Qd7+ Ka6 7.Qc6 f5 8.exf6 g5 9.f7 g4 10.Qxc4+ Kb7 11.Qe4+ Ka6 12.Qc6 g3 13.f8Q gxh2+ 14.Kxh2 (954.587.127) 30788 TB:2
25/66 0:31 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 c4 4.Qd6+ Kc8 5.Bxe7 Kb7 6.Qd7+ Ka6 7.Qc6 f5 8.exf6 g5 9.f7 g4 10.Qxc4+ Kb7 11.Qe4+ Ka6 12.Qc6 g3 13.f8Q gxh2+ 14.Kxh2 (977.971.149) 30821 TB:2
26/66 0:39 +M17 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Rg8 4.Qb7 Re8 5.Qb8+ Kd7 6.Qd6+ Kc8 7.Bxe7 Rxe7 8.Qxe7 g5 9.Qxf7 g4 10.Qxe6+ Kc7 11.Qd5 h6 12.e6 b5 13.e7 g3 14.e8Q (1.237.739.396) 31252 TB:3
27/66 0:41 +M17 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Rg8 4.Qb7 Re8 5.Qb8+ Kd7 6.Qd6+ Kc8 7.Bxe7 Rxe7 8.Qxe7 g5 9.Qxf7 g4 10.Qxe6+ Kc7 11.Qd5 h6 12.e6 b5 13.e7 g3 14.e8Q (1.312.914.138) 31389 TB:3
28/66 0:53 +M15 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Re8 4.Qd6+ Kc8 5.Bxe7 Rxe7 6.Qxe7 g5 7.Qxf7 g4 8.Qxe6+ Kc7 9.Qd5 h6 10.e6 b5 11.e7 g3 12.e8Q gxh2+ 13.Kxh2 Kb6 14.Qdd8+ (1.710.378.134) 31942 TB:3


Engine: Stockfish 170916 64 BMI2 (8192 MB)
by T. Romstad, M. Costalba, J. Kiiski, G.
Found 172 tablebases.

37/52 0:07 +70.64++ 1.Qa4+ (164.236.084) 21816 TB:115
37/52 0:07 +74.73++ 1.Qa4+ (166.600.840) 21829 TB:115
37/52 0:07 +79.87++ 1.Qa4+ (167.141.856) 21837 TB:115
37/52 0:07 +86.30++ 1.Qa4+ (167.445.673) 21836 TB:115
37/52 0:07 +94.37++ 1.Qa4+ (167.659.978) 21842 TB:115
37/52 0:07 +104.47++ 1.Qa4+ (167.853.667) 21844 TB:115
37/52 0:07 +117.11++ 1.Qa4+ (168.121.379) 21850 TB:115
37/52 0:09 +M20 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 h5 7.Qxb6+ Kc8 8.Qxc5+ Kb7 9.Bxe7 Rxe7 10.Qxe7+ Kc6 11.Qd6+ Kb7 12.Qd7+ Kb8 13.Qxf7 h4 14.Qxe6 (201.894.165) 22169 TB:576
38/52 0:09 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (207.422.524) 22200 TB:605
39/52 0:10 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (225.282.164) 22212 TB:745
40/52 0:10 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (239.885.710) 22221 TB:813
41/52 0:11 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (248.810.334) 22209 TB:932
42/52 0:12 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (270.750.064) 22198 TB:1.149
43/52 0:13 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (303.795.942) 22186 TB:1.987
44/52 0:19 +M19 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 g5 5.Qb7 Re8 6.Qxa7 b5 7.Qxc5 h5 8.Qd6+ Kc8 9.Bxe7 Rxe7 10.Qxe7 g4 11.Qxf7 g3 12.Qxe6+ Kb7 13.Qd7+ Ka6 14.Qd6+ (436.467.132) 22346 TB:4.371
45/52 1:06 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.561.282.163) 23407 TB:6.336
46/52 1:07 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.587.896.202) 23410 TB:6.383
47/52 1:09 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.634.566.967) 23389 TB:6.574
48/52 1:10 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.658.414.305) 23375 TB:6.580
49/52 1:15 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.755.633.150) 23336 TB:6.795
50/52 1:18 +M18 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 h6 4.Bf6 Rg8 5.Qb7 Re8 6.Qb8+ Kd7 7.Qd6+ Kc8 8.Bxe7 Rxe7 9.Qxe7 a5 10.Qxf7 a4 11.Qxe6+ Kb7 12.Qd7+ Ka6 13.Qxa4+ Kb7 14.e6 (1.829.080.679) 23345 TB:6.824
51/52 2:46 +M16 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Rg8 4.c4 Re8 5.Qd6+ Kc8 6.Bxe7 Rxe7 7.Qxe7 a5 8.Qxf7 a4 9.Qxe6+ Kb7 10.Qd7+ Ka6 11.Qxa4+ Kb7 12.e6 b5 13.Qxb5+ Ka7 14.e7 (3.992.123.926) 23944 TB:7.406
52/52 2:50 +M16 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Rg8 4.c4 Re8 5.Qd6+ Kc8 6.Bxe7 Rxe7 7.Qxe7 a5 8.Qxf7 a4 9.Qxe6+ Kb7 10.Qd7+ Ka6 11.Qxa4+ Kb7 12.e6 b5 13.Qxb5+ Ka7 14.e7 (4.090.382.549) 23948 TB:7.440
53/52 3:04 +M15 1.Qa4+ Qc6 2.Rd8+ Kxd8 3.Qxc6 Re8 4.Qd6+ Kc8 5.Bxe7 Rxe7 6.Qxe7 g5 7.Qxf7 g4 8.Qxe6+ Kc7 9.Qd6+ Kc8 10.Qc6+ Kd8 11.Qb7 g3 12.e6 gxh2+ 13.Kxh2 Ke8 14.Qd7+ (4.432.597.444) 23979 TB:7.575

[Ras]

As for the ELO impact, of course I didn't imply just putting it into the usual search, but into a special mode that is just alpha-beta-minimax along with using the hash tables for positions/branches that are not mate for either side. So, avoiding any kind of pruning since this might overlook key moves within the given mating depth.

Or is it just that usual chess puzzles are given with "mate in 2-8", and that pruning and stuff will not kick in at that depth anyway? Because PC programs easily have 20 plies search depth and prune only on the last few plies so that "mate in 8" is more or less within the brute force base horizon?

In that case, a multivariant analysis of course would solve the problem even when considering possible alternative key moves.

[syzygy]

Because PC programs easily have 20 plies search depth and prune only on the last few plies so that "mate in 8" is more or less within the brute force base horizon?

They prune/reduce considerably more than that.

Shortest-mate finding and strongest play do not go together very well. The top engines have gone for strongest play; otherwise they would not have been top engines. For shortest-mate finding other programs are probably better.

A UCI engine has little reason to offer both possibilities in one. It is also not clear how to achieve that from a GUI point of view, although I guess a check button option could be provided that lets the engine switch between two entirely different search algorithms.

[Milos]

Shortest-mate finding and strongest play do not go together very well. The top engines have gone for strongest play; otherwise they would not have been top engines. For shortest-mate finding other programs are probably better.

A UCI engine has little reason to offer both possibilities in one. It is also not clear how to achieve that from a GUI point of view, although I guess a check button option could be provided that lets the engine switch between two entirely different search algorithms.

Why it is hard, you just merge regular SF and SF-mate-finder, you use conventional SF until you reach some high score like 10+ then you just switch to SF-mate-finder. There is no way that would hurt any Elo even if you test without GUI adjudication.

[Ras]

They prune/reduce considerably more than that.

OK, didn't know that since I'm working with a middle-class engine. I failed to get the top-class working with 192kB RAM in total.

Shortest-mate finding and strongest play do not go together very well.

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.

It is also not clear how to achieve that from a GUI point of view, although I guess a check button option could be provided

Yeah, that was my hook point, too, that there just might be no UCI/Winboard protocol switch that would even offer the engine the possibility to change its algorithm. Which in itself poses the question why not.

[jplchess]

Chest does mate solving. In terms of efficiency it will hurt because it is time consuming and thus the rating goes down with Stockfish, for example.

I have asked that question before on this forum.
Jonathan Lee