UCI 'go mate x'

mcostalba · Post by **mcostalba** » Sun Dec 30, 2012 5:04 pm

Someone asked me for supporting UCI command 'go mate x' that finds the checkmate variation in a given position.

I looked at Fruit/Toga sources that seem the only open sources I know to support the feature, but there I saw they simply fall back on a search at fixed depth x, so nothing fancy here.

So I implemented a bit smarter algorithm (but IMO still well improvable):

https://github.com/mcostalba/Stockfish/ ... f486a5ea80

Here the trick is to return from a PV node if we are already above the 'x' moves limits. It means we still don't have found the mate so there is no need to continue the search. Note that non-PV search is not affected (also because I don't want to slow down the search with this toy feature, so I can afford an extra check in PV, but don't want _any_ slowdown in non-PV case).

Someone has/knows a better approach ?

P.S: It should be light, non-intrusive and easy to implement.

mcostalba · Post by **mcostalba** » Sun Dec 30, 2012 5:13 pm

While testing the patch I have collected some mate test positions across the net. The last group are the ones SF has great difficult to find the mate.

Code: Select all

1Bb3BN/R2Pk2r/1Q5B/4q2R/2bN4/4Q1BK/1p6/1bq1R1rb w - - 0 1 # bm Qa3 Mate in 1
2rqr3/1p1n1Rbk/p2p2pN/3Np1P1/2P4Q/1P2B3/P5KP/3n4 w - - 0 1 # bm Nf5 Mate in 3
1k3b1r/pp1q2pp/3pR3/8/8/2Q5/PP3PPP/2R3K1 w - - 0 1 # bm Qc7 Mate in 3
2rk3r/8/1p1K2P1/q7/6n1/6B1/8/2R1R3 w - - 0 1 # bm Bh4+ Mate in 3
q3r2k/2pn1p1p/1p3p1B/5P2/3P3Q/7R/6bP/3B2K1 w - - 0 1 # bm Bg7 Mate in 4
r1b4r/p4k1p/5Pp1/2p5/2Pn1QP1/2Np4/P1qB1P1P/R5K1 w - - 0 1 # bm Qc7 Mate in 4
r1bkr3/pppp3Q/3n4/1P1q4/5R2/7P/P1P2RPK/8 w - - 0 1 # bm Qh4+ Mate in 5
6k1/8/4N3/5PP1/5K2/2pR4/1p6/2r2b2 w - - 0 1 # bm Rd8+ Mate in 5
5k2/3b1p1r/1p3Q2/6pp/5B1P/5PP1/P3P3/7K w - - 0 1 # bm Bd6 Mate in 5
rnb2k1r/1p5p/5b2/pB2pR2/5p1P/1Q3P2/P1PP1P2/R1B1K3 w Q - 0 1 # bm Rxf6 Mate in 5
2b5/K2p3P/2k5/1qp5/8/p6B/3R3B/8 w - - 0 1 # bm Rd6 Mate in 5
5rk1/pp5p/3NP3/2B1R3/n1P3p1/6P1/P5KP/5r2 w - - 0 1 # bm Rg5+ Mate in 5
1r5r/6p1/6R1/2R1p3/3pB3/1P1Pn1Pk/1P6/6K1 w - - 0 1 # bm Rc2 Mate in 6
1r3r2/3p4/2bNpB2/p3Pp1k/6R1/1p1B2P1/PP3P1P/6K1 w - - 0 1 # bm Bxf5 Mate in 6
r1b2rk1/ppp2p2/6n1/8/4B3/2B2PP1/qPP1N1P1/2KR3R w - - 0 1 # bm Rh8 Mate in 6
8/8/p7/2k5/2B2Q1P/1Pn1P3/2q2P1K/8 w - - 0 1 # bm Qc7+ Mate in 6
1r5r/6p1/6R1/2R1p3/3pB3/1P1Pn1Pk/1P6/6K1 w - - 0 1 # bm Rc2 Mate in 6
rq6/pp1r3k/5p2/7p/3PR3/6Q1/PP3P1K/6R1 w - - 0 1 # bm Re5 Mate in 7
3q2k1/5r2/3p2pB/1p1r3n/pP4Q1/2P4P/2B2PP1/4R1K1 w - - 0 1 # bm Qxg6 Mate in 7
r1b1qr1k/5ppp/2p1p3/p1PpP3/P2N1PQB/2P1R3/6PP/3n2K1 w - - 0 1  # bm Qxg7 Mate in 7
r2q2k1/pb2b1pp/1p3n2/2pp2N1/3P4/2P5/P1P1Q1PP/R1B2RK1 w - - 0 1 # bm Qe6 Mate in 7
1r3rk1/1b4Np/5p1R/8/2q5/5P2/2BQ2PP/6RK w - - 1 1 # bm Bxh7 Mate in 7
5r1k/Q6p/2q5/p5B1/1pBPP3/6P1/1P5P/6K1 w - - 0 40 # bm Qe7 Mate in 7
4r1k1/p4pb1/2p4p/5qp1/P1P3n1/2Np1P2/3B2PP/R2Q2K1 b - - 0 30 # bm Qc5 Mate in 7
rn3rk1/pbppq1pp/1p2pb2/4N2Q/3PN3/3B4/PPP2PPP/R3K2R w KQkq - 0 1 # bm Qxh7 Mate in 7
r4rk1/3b1p1p/p5p1/2pP2q1/2pb1P2/2N3P1/PPB2nKP/R2Q4 b - - 0 1 # bm Bh3 Mate in 7
r1bq1b1r/ppp1k2p/2n4p/5p1Q/1PBp4/P1N5/2P2PPP/R3K1NR w KQkq - 0 1 # bm Qf7+ Mate in 7
1k6/3b4/PK1N4/3p3p/7P/4P3/8/8 w - - 0 1 # bm a7+ Mate in 7 !
k7/pp6/1n2N2p/3p1Ppq/8/PP2P1BP/8/K1Q5 w - - 0 1 # bm Nc7 Mate in 8
6rk/pp5p/2p2R1Q/2n1p2p/3p2Bq/8/P1P3K1/R7 b - - 0 1 # bm Rxg4 Mate in 8
rnbqkb1r/pppp2pp/5p2/2n1N3/2B5/2N5/PPPP1PPP/R1BQK2R w KQkq - 0 1 # bm Qh5 Mate in 8
r2q1rk1/ppp2p1p/1nbbp2P/n2pN1Pp/3P1P2/2P1P3/PP6/RBBQK2R w KQkq - 0 1 # bm Qc2 Mate in 8
8/1Qpk1pR1/8/1N1p1b1R/3P4/1P6/PKP3r1/6q1 b - - 0 1 # bm Rxc2 Mate in 9
r4rk1/p1p2ppp/1p5P/n1nN4/4p1q1/2Q5/PPP2PP1/1K1R3R w - - 0 1 # bm Ne7 Mate in 9
r1bk3r/pp5p/2nN4/3N2qn/2Kbppp1/P7/1PP1B1P1/R1BQ3R b - - 0 1 # bm Qxd5+ Mate in 9
3Q4/5q1k/4ppp1/2Kp1N1B/RR6/3P1r2/4nP1b/3b4 w - - 0 1 # bm Rb7 Mate in 9 !!
5bnr/p1B2p2/2B1k3/3N4/8/4N3/PPP2P1P/R3R1K1 w - - 6 27 # bm Ng4 Mate in 10 !!!!
2qrr1n1/3b1kp1/2pBpn1p/1p2PP2/p2P4/1BP5/P3Q1PP/4RRK1 w - - 0 1 # bm Qh5+ Mate in 10
2b4k/7P/8/8/4P1NN/1B5K/p1p1p3/8 w - - 0 1 # bm Bg8 Mate in 10
1r3r1k/3nb2p/6B1/p3P3/3P4/2q1B2Q/P6P/3K4 b - - 0 1 # bm Qa1 Mate in 10
R1b2bnr/p2k2pp/2p1pp2/B7/2qPN3/5N2/5PPP/3Q1RK1 w - - 0 1 # bm Ne5+ Mate in 10
r1b2r2/3pNpkp/3pn1p1/2pN3P/2PnP3/q3QP2/4BKP1/1R5R w - - 0 1 # bm Qh6+ Mate in 11 !!!
8/8/8/8/8/8/ppQKPPP1/k7 w - - 0 1 # bm Qc3 Mate in 12
2kr1r2/pb1R4/1p2pq1p/bBp2pp1/P1Q5/4BP2/5NPP/3R2K1 w K - 0 1 # bm Bxc5 Mate in 12
q7/n2BNp2/5k1P/1p5P/1p2RP2/1K6/8/8 w - - 0 1 # bm Re3 Mate in 12
8/1nq5/bppp4/1p1k1K1N/1rrp3b/2pp2p1/8/n7 w - - 0 1 # bm Nf4+ Mate in 12
rb3rk1/p2b2pp/nqp1p3/1p1nPpN1/4N3/1P1B4/PB3PPP/R2Q1RK1 w - - 0 1 # bm Qh5 Mate in 13
6R1/8/3B4/8/6K1/8/p1p1p1p1/6kb w - - 0 1 # bm Bc5 Mate in 14
r3r1k1/pppq3p/6p1/3p1pR1/5b2/1P3P2/PBPP2QP/6RK w - - 0 1# bm Rxg6+ Mate in 14 !!!
3r2k1/2Q2p1p/4p1p1/2pq4/1p1b4/1P4P1/2R2P1P/6K1 b - - 0 37 # bm Qa8 Mate in 17



r3k1nr/pQBp1ppp/1pp1p3/8/3bP1P1/8/bq1NKPBP/6R1 b - - 0 1 # bm xxx Mate in 7
7r/pp4kp/b2R2pp/1p1p3P/1b6/2R3P1/5PKP/8 w - - 1 1 # bm xxx Mate in 8
r1r3k1/1pp1Rpp1/p1q4p/8/5BQ1/3B2K1/PPP2PP1/R7 w - - 0 1 # bm xxx Mate in 8
3rr1k1/pp3ppp/q1pbp3/8/2P1Q1NP/2B5/PP3PP1/3RR1K1 w - - 0 1 # bm xxx Mate in 9
1n3r2/6pp/ppkp4/1p4b1/1q2PB2/5Q2/PPP3PP/R4RK1 w - - 0 1 # bm xxx Mate in 9
8/3K3p/7p/p6p/P1PP3p/2PP1P2/pp1p1P1P/qkbB4 w - - 0 1 # bm xxx Mate in 10
rnq2rk1/pb1p1pbp/npp3p1/7P/2N1P3/1Q6/P4P2/1KB3RR w - - 0 1 # bm xxx Mate in 11
1q1r2k1/rb2b1p1/pp3nP1/8/2PP4/7Q/PB4PP/R4RK1 w - - 0 1 # bm xxx Mate in 12

ZirconiumX · Post by **ZirconiumX** » Sun Dec 30, 2012 6:01 pm

It depends which Fruit version you chose. Fruit 1.0 had a dedicated mate search (read full-width alpha-beta with TT) for this task. It takes its sweet time.

One think that should be easy to implement is setting ss->skipNullMove when doing a mate search - you may run into a zugzwang position - or the problem has a horizon effect.

Matthew:out

Houdini · Post by **Houdini** » Sun Dec 30, 2012 6:20 pm

Houdini has a "Mate Search" UCI option that limits the search depth in a similar fashion - not just for the PV but for all the nodes.
I didn't know about the "go mate X" UCI command, is there any GUI that uses it?

Robert

bob · Post by **bob** » Sun Dec 30, 2012 7:02 pm

ZirconiumX wrote:It depends which Fruit version you chose. Fruit 1.0 had a dedicated mate search (read full-width alpha-beta with TT) for this task. It takes its sweet time.

One think that should be easy to implement is setting ss->skipNullMove when doing a mate search - you may run into a zugzwang position - or the problem has a horizon effect.

Matthew:out

Null-move is not as big a problem as LMR. Used to be if you were searching for mate in N, you could stop after iteration 2*N - 1, but not with reductions.

mar · Post by **mar** » Sun Dec 30, 2012 10:26 pm

bob wrote:Null-move is not as big a problem as LMR. Used to be if you were searching for mate in N, you could stop after iteration 2*N - 1, but not with reductions.

It's funny that I have a different experience.
Consider the following two positions (occured in real testing where my engine lost to SOS due to tactical blindness):

[D]2kr1b1r/ppp3p1/5nbp/4B3/2P5/3P2Nq/PP2BP2/R2Q1RK1 b - - 0

[D]r5n1/p2q3k/4b2p/3pB3/2PP1QpP/8/PP4P1/5RK1 w - - 1

I always thought I had a bug until I tried Critter 1.2 on the latter position and
to my surprise it required 20 plies to find the winning move.
Note that any engine I tried either sees it very fast or misses it.
Disabling nullmoves always helped (saw it at depth 10 or 11). Were zugzwangs involved? I doubt.
With LMR you bet that the move doesn't raise alpha and thus prune a move.
The problem IMHO is that with null move you prune a whole node (subtree), I therefore think that null move is more unsafe than LMR.
Am I missing something?

lucasart · Post by **lucasart** » Mon Dec 31, 2012 2:57 am

mcostalba wrote:Someone asked me for supporting UCI command 'go mate x' that finds the checkmate variation in a given position.

I looked at Fruit/Toga sources that seem the only open sources I know to support the feature, but there I saw they simply fall back on a search at fixed depth x, so nothing fancy here.

So I implemented a bit smarter algorithm (but IMO still well improvable):

https://github.com/mcostalba/Stockfish/ ... f486a5ea80

Here the trick is to return from a PV node if we are already above the 'x' moves limits. It means we still don't have found the mate so there is no need to continue the search. Note that non-PV search is not affected (also because I don't want to slow down the search with this toy feature, so I can afford an extra check in PV, but don't want _any_ slowdown in non-PV case).

Someone has/knows a better approach ?

P.S: It should be light, non-intrusive and easy to implement.

Shouldn't it be:

Code: Select all

VALUE_MATE - bestValue < 2 * Limits.mate

instead of

Code: Select all

VALUE_MATE - bestValue <= 2 * Limits.mate

?

And I agree with Bob: the fix depth is not a good idea. And not just because of LMR, but also Razoring, as well as all the aggressive futility pruning techniques that SF uses "near the leaves" (in SF that means up to depth 7 for value based pruning, and 16 for move count based pruning... that's hardly "near").

What's even worse than the tactical mistakes of LMR, Razoring, Futility pruning etc, is the combination of them !! Examples
- you are searching a node at depth = 6, and decide that a quiet move shoud get a reduction of 2 plies (because it happens to have been unlucky so far in the history table), so you are now at depth 3, and you just return the eval by doing a "static null move pruning".
- you do a null move going from depth 7.5 to depth 3 (eval >= beta + pawn), and then you razor at depth = 3, just by doing a qsearch()
- That list is endless...

That being said, you need some stop condition, if the mate is not found.

Karlo Bala · Post by **Karlo Bala** » Mon Dec 31, 2012 3:36 am

mar wrote: With LMR you bet that the move doesn't raise alpha and thus prune a move.

That is Futility pruning.

mar wrote: The problem IMHO is that with null move you prune a whole node (subtree), I therefore think that null move is more unsafe than LMR.
Am I missing something?

I'd say it is due to LMR. Some engines reduce very late moves with r=2(3), and that's a very risky reduction (pruning), mostly based on weak assumptions.

mar · Post by **mar** » Mon Dec 31, 2012 4:33 am

Karlo Bala wrote:
mar wrote: With LMR you bet that the move doesn't raise alpha and thus prune a move.
That is Futility pruning.

mar wrote: The problem IMHO is that with null move you prune a whole node (subtree), I therefore think that null move is more unsafe than LMR.
Am I missing something?
I'd say it is due to LMR. Some engines reduce very late moves with r=2(3), and that's a very risky reduction (pruning), mostly based on weak assumptions.

Perhaps I didn't make myself clear.
Futility pruning means you skip moves where you bet that a move cannot raise alpha (static eval + margin <= alpha) without any search.
LMR means that for moves which pass futility test, you do reduced search first.
If it fails low, you in fact prune that move based on a reduced search, although I agree that "prune" is probably misleading here.

Ad 2) No it's not due to LMR, in my tests I disabled everything (futility, LMR, razoring) and the problem still persists. Only if I disable null move it's gone.

Desperado · Post by **Desperado** » Mon Dec 31, 2012 8:03 am

mcostalba wrote:Someone asked me for supporting UCI command 'go mate x' that finds the checkmate variation in a given position.

I looked at Fruit/Toga sources that seem the only open sources I know to support the feature, but there I saw they simply fall back on a search at fixed depth x, so nothing fancy here.

So I implemented a bit smarter algorithm (but IMO still well improvable):

https://github.com/mcostalba/Stockfish/ ... f486a5ea80

Here the trick is to return from a PV node if we are already above the 'x' moves limits. It means we still don't have found the mate so there is no need to continue the search. Note that non-PV search is not affected (also because I don't want to slow down the search with this toy feature, so I can afford an extra check in PV, but don't want _any_ slowdown in non-PV case).

Someone has/knows a better approach ?

P.S: It should be light, non-intrusive and easy to implement.

Hello Marco,

sitting here and drinking my first coffee in the morning to wake up
and reading your post i just have an idea never tested or seen somewhere. Maybe it is nonsense, but anyway.

The first thing i would try without changing the search would be to
modify the root's alpha beta window. I dont think we need to
search lbound to ubound or sth. like that. If we are in mate-search
mode we only need to test for mateIn(d) score. if that fails we continue
with the next depth, until we find a depth having a mate.

The first advantage i see is that in a mate search we only have to set
the root window different, which keeps the code clean. The second
point is that it should find existing mates (much) faster than the normal
search.

I think that would be the first step, if i would setup the feature. Further
code improvements would be a matter of how important this feature
is to me.

Happy new year to you and everyone here.

Michael

UCI 'go mate x'

UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'

Re: UCI 'go mate x'