Mate in 2, not found

Discussion of chess software programming and technical issues.

Moderator: Ras

Carbec
Posts: 162
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 :
8 
7 
6 
5 
4 
3 
2 
1 
abcdefgh

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: 469
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 :
8 
7 
6 
5 
4 
3 
2 
1 
abcdefgh

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: 724
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 :
8 
7 
6 
5 
4 
3 
2 
1 
abcdefgh

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.
User avatar
Ajedrecista
Posts: 2103
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: 922
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