Mate in 2, not found

Discussion of chess software programming and technical issues.

Moderator: Ras

Carbec
Posts: 161
Joined: Thu Jan 20, 2022 9:42 am
Location: France
Full name: Philippe Chevalier

Mate in 2, not found

Post by Carbec »

Hi,
I found this position : [d]n1N3br/2p1Bpkr/1pP2R1b/pP3Pp1/P5P1/1P1p4/p2P4/K7 w - - 0 1 I was surprised that even strong programs don't find it.
It seems , at least for me, that its the Late Move Reduction that is the cause.

Any idea ?

Philippe
abulmo2
Posts: 462
Joined: Fri Dec 16, 2016 11:04 am
Location: France
Full name: Richard Delorme

Re: Mate in 2, not found

Post by abulmo2 »

In my programs dumb & amoeba, nullmove pruning is the culprit of preventing the search to find the mate at an acceptable depth. Other reduction heuristics like futility pruning, razoring, late move reduction and late move pruning play a role too, but not as much as nullmove.
Richard Delorme
laurietunnicliffe
Posts: 23
Joined: Wed Nov 17, 2021 1:19 am
Full name: Laurie Tunnicliffe

Re: Mate in 2, not found

Post by laurietunnicliffe »

Yep, null moves the problem in ltchess3
ernest
Posts: 2046
Joined: Wed Mar 08, 2006 8:30 pm

Re: Mate in 2, not found

Post by ernest »

Carbec wrote: Sat Nov 04, 2023 9:44 pm Hi,
I found this position : [d]n1N3br/2p1Bpkr/1pP2R1b/pP3Pp1/P5P1/1P1p4/p2P4/K7 w - - 0 1 Philippe
By the way, that position is not attainable in "normal" chess... :)
petero2
Posts: 723
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Mate in 2, not found

Post by petero2 »

ernest wrote: Sun Nov 05, 2023 5:46 am
Carbec wrote: Sat Nov 04, 2023 9:44 pm Hi,
I found this position : [d]n1N3br/2p1Bpkr/1pP2R1b/pP3Pp1/P5P1/1P1p4/p2P4/K7 w - - 0 1 Philippe
By the way, that position is not attainable in "normal" chess... :)
What does that statement mean? The position is reachable from the starting position by a sequence of legal moves.
[pgn] [Event "-"] [Site "-"] [Date "2023.11.05"] [Round "-"] [White "?"] [Black "?"] [Result "*"] 1. e4 d5 2. c4 h5 3. g4 h4 4. Qb3 d4 5. Qb6 Qd5 6. exd5 a5 7. Qb3 Ra6 8. Qc3 Rb6 9. Qf3 Rb5 10. Qg3 hxg3 11. cxb5 e6 12. a4 Kd8 13. Ra3 Bd7 14. Rf3 Nc6 15. dxc6 Bc8 16. Rf5 Ke8 17. Rd5 exd5 18. h4 Rh5 19. Kd1 Bd6 20. Bd3 Be7 21. Nf3 Ba3 22. Re1+ Kd8 23. Ng1 Rf5 24. Re3 Be7 25. Ke1 Bf8 26. Bf1 Rh5 27. Rc3 Ke8 28. Rc4 Rh8 29. Be2 dxc4 30. Bd1 Rh5 31. Bb3 Rh8 32. Nc3 cxb3 33. Na2 bxa2 34. Kd1 g5 35. Kc2 g2 36. f4 Be6 37. b3 d3+ 38. Kb2 Bf5 39. h5 Nf6 40. h6 Bh7 41. f5 Rg8 42. Nf3 g1=R 43. Ne5 Rh1 44. Ka1 Nd7 45. Ng6 Nb6 46. Ne7 Na8 47. Nc8 Rh3 48. Ba3 b6 49. Bc5 Rg7 50. Bb4 Bg8 51. h7 Rh5 52. h8=R Rh2 53. Rh6 Rh5 54. Rg6 Rh8 55. Kb2 Rgh7 56. Ka1 Bh6 57. Bc5 Rg7 58. Be7 Rgh7 59. Bd8 Kf8 60. Re6 Rg7 61. Rf6 Rgh7 62. Be7+ Kg7 * [/pgn]
User avatar
Ajedrecista
Posts: 2097
Joined: Wed Jul 13, 2011 9:04 pm
Location: Madrid, Spain.

Re: Mate in 2, not found.

Post by Ajedrecista »

Hello:

Just for the record, this problem is based on two problems by Fritz Emil Giegold, one of 1963 (checkmate in five moves) and other of 1976 (checkmate in six moves), both exploiting the same idea:

https://yacpdb.org/#229429
https://pdb.dieschwalbe.de/P1038449

https://yacpdb.org/#66738

------------

OTOH, I understand Ernest's post as that both players must play a bunch of senseless moves in order to reach this position, not that it is unreachable. Peter already provided a proof game, but for example 5.- Qb6??, Qd5?? is what I would also call senseless moves in a normal game, where each player wants to win or at least not lose; they are more logical when constructing a proof game, of course.

------------

Last but not least, I tried SF 16 and it found the checkmate in two moves, but at high depths. Multi-PV helped lowering the depth where the checkmate is found, but it was still high for a simple two-mover.

Regards from Spain.

Ajedrecista.
ernest
Posts: 2046
Joined: Wed Mar 08, 2006 8:30 pm

Re: Mate in 2, not found

Post by ernest »

petero2 wrote: Sun Nov 05, 2023 7:19 am
ernest wrote: Sun Nov 05, 2023 5:46 am
By the way, that position is not attainable in "normal" chess... :)
What does that statement mean? The position is reachable from the starting position by a sequence of legal moves.
Ah OK, Thank you Peter ! My bad !... :shock:
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Mate in 2, not found

Post by lithander »

Interesting position!

Leorik takes >1B positions (1159831095) to find a mate in 11 at depth 41 and one iteration later it finds the mate in 2.

If I disable null-move pruning the search finds the mate quickly at depth 7.

I have code in place that disables null-move pruning in endgame positions but this positions is not recognized as being endgame. What works really well in this scenario is not to look at the available pieces but to count the number of legal moves and skip null-move pruning when the number of legal moves is below a certain threshold e.g. legal_moves < 6.

By tuning the legal move threshold just right it's possible to detect the mate in 2 super quickly in less than a thousand searched nodes.

Code: Select all

info depth 7 score mate 2 nodes 682 nps 56833 time 12 pv e7a3 g7f6 a3b2
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
chessica
Posts: 912
Joined: Thu Aug 11, 2022 11:30 pm
Full name: Esmeralda Pinto

Re: Mate in 2, not found

Post by chessica »

lithander wrote: Mon Nov 06, 2023 12:40 pm Interesting position!

Leorik takes >1B positions (1159831095) to find a mate in 11 at depth 41 and one iteration later it finds the mate in 2.

If I disable null-move pruning the search finds the mate quickly at depth 7.

I have code in place that disables null-move pruning in endgame positions but this positions is not recognized as being endgame. What works really well in this scenario is not to look at the available pieces but to count the number of legal moves and skip null-move pruning when the number of legal moves is below a certain threshold e.g. legal_moves < 6.

By tuning the legal move threshold just right it's possible to detect the mate in 2 super quickly in less than a thousand searched nodes.

Code: Select all

info depth 7 score mate 2 nodes 682 nps 56833 time 12 pv e7a3 g7f6 a3b2
Excellent.

Where in the source code do I have to make the changes so that I can also use these advantages?


Best regards
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Mate in 2, not found

Post by lithander »

chessica wrote: Tue Nov 07, 2023 9:32 am Excellent.

Where in the source code do I have to make the changes so that I can also use these advantages?
I think many engine devs have the same problem: A change that improves puzzle solving often hurts the general playing strength.

In this case counting the legal moves is more expensive than what I currently use to identify positions where Zugzwang may happen. (Expect Zugzwang when the side to move has only Pawns left)

When search speed goes down it always hurts the strength while the ability to better deal with positions like this one seems to be not important enough in "real" play to make the patch gain Elo.

But you might want to give Leorik 1.0 a try. It's hard to beat on exotic positions like this:

Code: Select all

Leorik 1.0
position fen n1N3br/2p1Bpkr/1pP2R1b/pP3Pp1/P5P1/1P1p4/p2P4/K7 w - - 0 1
go
info depth 1 score cp -566 nodes 96 nps 96000 time 1 pv a1a2
info depth 2 score cp 0 nodes 197 nps 24625 time 8 pv a1a2
info depth 3 score mate 2 nodes 583 nps 64777 time 9 pv e7a3 g7f6 a3b2
info depth 4 score mate 2 nodes 1616 nps 161600 time 10 pv e7a3 g7f6 a3b2
It's search does not implement any unsafe pruning techniques or reductions. The disadvantage is that the time to search the next depth grows really quickly but the advantage is that it will solve all mate puzzle with the shortest path. (if there are no bugs^^)
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess