The problem with LMR in suprtactical positions.

[Eelco de Groot]

Code: Select all

if &#40;blackKingSafety&#91;ply&#93; < blackKingSafety&#91;ply - 1&#93; - SAFETYMARGIN&#41; 
 reduce;

In this case blackKingSafety should be read as a positive function of attacks on the Black King, I use ei.kingDanger instead of KingSafety in Stockfish/Rainbow Serpent code. Sorry for the confusion.

[bob]

Hi, here is a fine position that has a mate in 7 with Qxd5:

[d]r2qb1nr/pp1n3p/4k1p1/1P1pPpP1/1B3P1P/2R5/3Q4/R3KB2 w - - 0 3

But there is a problem, that in the mate line:

Code: Select all

d2d5 e6d5 a1d1 d5e4 c3c4 e4f3 d1d3 f3g4 f1e2 g4h4 c4c3 d7e5 d3h3

We have the quiet move R4c3, which isn't nor a capture, neither a check, neither anything obvious, so it's probable that LMR would destroy it. And it really happens:

With LMR OliThink doesn't find the mate for SD=10:

Code: Select all

 4  -113      0     18287  c3a3 d8b6 a1d1 g8e7
 5  -113      2     47640  c3a3 d8b6 a1d1 g8e7 b4e7
 6  -124      6    146084  c3a3 d7b6 a3a7 a8a7 a1a7 b6c4
 7  -113     19    458496  c3a3 d8b6 a1d1 g8e7 b4e7 e6e7 d2d5
 8  -141    154   2802580  c3a3 d8b6 a1d1 g8e7 b4e7 e6e7 d2d5 e7f8
 9  -117    209   4037259  b4d6 d8b6 a1d1 g8e7 d6e7 e6e7 d2d5 b6a5 d5d6 e7f7
10   -71    364   8024626  d2d4 d8b6 d4b6 d7b6 c3c7 e8d7 c7b7 g8e7 a1a7 a8a7 b7a7

Without LMR it does:

Code: Select all

 4  -113      0     19926  c3a3 d8b6 a1d1 g8e7
 5  -113      2     58727  c3a3 d8b6 a1d1 g8e7 b4e7
 6  -124      9    224773  c3a3 d7b6 a3a7 a8a7 a1a7 b6c4
 7  -113     30    773468  c3a3 d8b6 a1d1 g8e7 b4e7 e6e7 d2d5
 8  -141     77   1937049  c3a3 d8b6 a1d1 g8e7 b4e7 e6e7 d2d5 e7f8
 9   -76    251   6294206  d2d4 h7h6 a1a7 a8a7 d4a7 d8b6 a7b6 d7b6 c3c7 h6g5
10 31987    395  10243018  d2d5 e6d5 a1d1 d5e4 c3c4 e4f3 d1d3 f3g4 f1e2 g4h4 c4c3 d7e5 d3h3

I verified that R4c3 is the evil move, as if I search with LMR but excluding R4c3 from LMR I get the mate, too.

So this is very bad. How can such thing be avoided? Any ideas?

That is a potential issue, since any reduction along a mating line will make it harder to find. But for this one, Crafty (at least) finds it quite quickly:

Code: Select all

                8     0.62  -2.51   1. Rca3 Ne7 2. Rxa7 Rxa7 3. Rxa7 Qb6
                                    4. Qf2 d4 5. Bc4+ Nd5
                8     0.64     +1   1. Qxd5+!                        
                8     0.64     +3   1. Qxd5+!                        
                8     0.64     +M   1. Qxd5+!                        
                8     0.65  Mat07   1. Qxd5+ Kxd5 2. Rd1+ Ke4 3. Rc4+ Kf3
                                    4. Rd3+ Kg4 5. Be2+ Kxh4 6. Rcc3 Nxe5
                                    7. Rh3#

That on a slow laptop. 8 plies, 0.6 seconds

[metax]

That is a potential issue, since any reduction along a mating line will make it harder to find. But for this one, Crafty (at least) finds it quite quickly:

Code: Select all

                8     0.62  -2.51   1. Rca3 Ne7 2. Rxa7 Rxa7 3. Rxa7 Qb6
                                    4. Qf2 d4 5. Bc4+ Nd5
                8     0.64     +1   1. Qxd5+!                        
                8     0.64     +3   1. Qxd5+!                        
                8     0.64     +M   1. Qxd5+!                        
                8     0.65  Mat07   1. Qxd5+ Kxd5 2. Rd1+ Ke4 3. Rc4+ Kf3
                                    4. Rd3+ Kg4 5. Be2+ Kxh4 6. Rcc3 Nxe5
                                    7. Rh3#

That on a slow laptop. 8 plies, 0.6 seconds

8 plies means you don't reduce Rcc3 at all in Crafty. Why? What is the condition for LMR you have put in.

I also have problems with this position. With everything (LMR, Futility Pruning, Null Move, etc) turned off I also find the mate with 8 plies. But turning on null move pruning, my engine doesn't see it any more...
Does that mean there is a bug in my null move implementation?

[Uri Blass]

That is a potential issue, since any reduction along a mating line will make it harder to find. But for this one, Crafty (at least) finds it quite quickly:

Code: Select all

                8     0.62  -2.51   1. Rca3 Ne7 2. Rxa7 Rxa7 3. Rxa7 Qb6
                                    4. Qf2 d4 5. Bc4+ Nd5
                8     0.64     +1   1. Qxd5+!                        
                8     0.64     +3   1. Qxd5+!                        
                8     0.64     +M   1. Qxd5+!                        
                8     0.65  Mat07   1. Qxd5+ Kxd5 2. Rd1+ Ke4 3. Rc4+ Kf3
                                    4. Rd3+ Kg4 5. Be2+ Kxh4 6. Rcc3 Nxe5
                                    7. Rh3#

That on a slow laptop. 8 plies, 0.6 seconds

8 plies means you don't reduce Rcc3 at all in Crafty. Why? What is the condition for LMR you have put in.

I also have problems with this position. With everything (LMR, Futility Pruning, Null Move, etc) turned off I also find the mate with 8 plies. But turning on null move pruning, my engine doesn't see it any more...
Does that mean there is a bug in my null move implementation?

No

8 plies mean that you do checks in the first ply of the qsearch and not only LMR.

The line is 12 plies without the mating move.
5 of them are checks so without LMR you can get into qsearch after 7 plies before the mating move and the qsearch find the mate so without LMR you can see the mate with 7 plies search.

Uri

[metax]

Ah, I forgot the checks in quiescence because I don't have them. But I still wonder about my problem with null-move...

[bob]

That is a potential issue, since any reduction along a mating line will make it harder to find. But for this one, Crafty (at least) finds it quite quickly:

Code: Select all

                8     0.62  -2.51   1. Rca3 Ne7 2. Rxa7 Rxa7 3. Rxa7 Qb6
                                    4. Qf2 d4 5. Bc4+ Nd5
                8     0.64     +1   1. Qxd5+!                        
                8     0.64     +3   1. Qxd5+!                        
                8     0.64     +M   1. Qxd5+!                        
                8     0.65  Mat07   1. Qxd5+ Kxd5 2. Rd1+ Ke4 3. Rc4+ Kf3
                                    4. Rd3+ Kg4 5. Be2+ Kxh4 6. Rcc3 Nxe5
                                    7. Rh3#

That on a slow laptop. 8 plies, 0.6 seconds

8 plies means you don't reduce Rcc3 at all in Crafty. Why? What is the condition for LMR you have put in.

I also have problems with this position. With everything (LMR, Futility Pruning, Null Move, etc) turned off I also find the mate with 8 plies. But turning on null move pruning, my engine doesn't see it any more...
Does that mean there is a bug in my null move implementation?

I don't follow. Move by move:

starting depth = 8.
after Qd5 depth is still 8 (check extension)
Kxd5 depth is 7, not reduced since it is a capture and in check.
Rd1 depth is still 7 (check extension)
Ke4 depth is 6 but not reduced (in check)
Rc4 depth is still 6 (check)
Kf3 depth is 5 but not reduced (in check)
Rd3 depth is still 5 (check extension)
Kg4 depth is 4 (not reduced since in check)
Be2+ depth is still 4 (check extension)
Kxh4 depth is 3 (not reduced, in check and capture)
Rcc3 depth is 2 (not reduced, too early in move list)
Nxe5 depth is 1
Next move is check and mate, and extends the one ply needed to see that the opponent has no legal moves.

And voila', mate in 7.

[bob]

That is a potential issue, since any reduction along a mating line will make it harder to find. But for this one, Crafty (at least) finds it quite quickly:

Code: Select all

                8     0.62  -2.51   1. Rca3 Ne7 2. Rxa7 Rxa7 3. Rxa7 Qb6
                                    4. Qf2 d4 5. Bc4+ Nd5
                8     0.64     +1   1. Qxd5+!                        
                8     0.64     +3   1. Qxd5+!                        
                8     0.64     +M   1. Qxd5+!                        
                8     0.65  Mat07   1. Qxd5+ Kxd5 2. Rd1+ Ke4 3. Rc4+ Kf3
                                    4. Rd3+ Kg4 5. Be2+ Kxh4 6. Rcc3 Nxe5
                                    7. Rh3#

That on a slow laptop. 8 plies, 0.6 seconds

8 plies means you don't reduce Rcc3 at all in Crafty. Why? What is the condition for LMR you have put in.

I also have problems with this position. With everything (LMR, Futility Pruning, Null Move, etc) turned off I also find the mate with 8 plies. But turning on null move pruning, my engine doesn't see it any more...
Does that mean there is a bug in my null move implementation?

No

8 plies mean that you do checks in the first ply of the qsearch and not only LMR.

The line is 12 plies without the mating move.
5 of them are checks so without LMR you can get into qsearch after 7 plies before the mating move and the qsearch find the mate so without LMR you can see the mate with 7 plies search.

Uri

In the above example, I don't even need the q-search check, there is just enough depth left to see the mate in the normal search (see previous post for move by move analysis)

[metax]

I don't follow. Move by move:

starting depth = 8.
after Qd5 depth is still 8 (check extension)
Kxd5 depth is 7, not reduced since it is a capture and in check.
Rd1 depth is still 7 (check extension)
Ke4 depth is 6 but not reduced (in check)
Rc4 depth is still 6 (check)
Kf3 depth is 5 but not reduced (in check)
Rd3 depth is still 5 (check extension)
Kg4 depth is 4 (not reduced since in check)
Be2+ depth is still 4 (check extension)
Kxh4 depth is 3 (not reduced, in check and capture)
Rcc3 depth is 2 (not reduced, too early in move list)
Nxe5 depth is 1
Next move is check and mate, and extends the one ply needed to see that the opponent has no legal moves.

And voila', mate in 7.

Why is Rcc3 too early in your move list for LMR? How many moves do you search to full depth?

[grant]

I was going to ask the same question.

Grant

[bob]

I don't follow. Move by move:

starting depth = 8.
after Qd5 depth is still 8 (check extension)
Kxd5 depth is 7, not reduced since it is a capture and in check.
Rd1 depth is still 7 (check extension)
Ke4 depth is 6 but not reduced (in check)
Rc4 depth is still 6 (check)
Kf3 depth is 5 but not reduced (in check)
Rd3 depth is still 5 (check extension)
Kg4 depth is 4 (not reduced since in check)
Be2+ depth is still 4 (check extension)
Kxh4 depth is 3 (not reduced, in check and capture)
Rcc3 depth is 2 (not reduced, too early in move list)
Nxe5 depth is 1
Next move is check and mate, and extends the one ply needed to see that the opponent has no legal moves.

And voila', mate in 7.

Why is Rcc3 too early in your move list for LMR? How many moves do you search to full depth?

I only have one limit with respect to the "L" in "LMR". I search moves in phases. Phase 1 is the hash move, phase 2 are captures with SEE >= 0, phase 3 is killers, and for this case, phase 4 is "rest of moves". Only moves in the "rest of moves" phase can be reduced, since there is some logic in thinking that a hash move, a good capture, or a killer will produce a cutoff, and I don't want to reduce those.