The problem with LMR in suprtactical positions.

[OliverBr]

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?

[Don]

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?

The age old question. LMR and static null move are both speculative algorithms, so you should expect to this from time to time. There will always be some positions that are more conservative version of your program will get, but the more conservative version will play weaker. It goes with the territory.

That is not to say we shouldn't try to address the issues. I myself am looking for the general answer to the question you just raised. Chance are that if you find another rule for certain moves to include, it will make your program weaker - that is what seems to happen with me!

[rvida]

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

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

Just search with SD=11

[Ferdy]

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?

In my case I prefer to measure this by search time, not by depth.
Can you post your other LMR conditions?

[OliverBr]

In my case I prefer to measure this by search time, not by depth.
Can you post your other LMR conditions?

Of course you are right, as OliThink with LMR finds the mate quite quickly at SD=11.

Here are my LMR conditions, where d = depth, and i = nr. of move.

Code: Select all

if (nch) ext++; // Check Extension
else if (n == 1) ext++; //Singular reply extension
else if (d >= 3 && i >= 4 && !pvnode) { //LMR
   if (CAP(m) || PROM(m)); //Don't reduce Captures and Promotions
   else if &#40;PIECE&#40;m&#41; == PAWN && (&#40;TO&#40;m&#41; + 16&#41; & 48&#41; < 32&#41;; //Don't reduce pawns to 7th rank
   else ext--;
&#125;

[Ferdy]

In my case I prefer to measure this by search time, not by depth.
Can you post your other LMR conditions?

Of course you are right, as OliThink with LMR finds the mate quite quickly at SD=11.

Here are my LMR conditions, where d = depth, and i = nr. of move.

Code: Select all

if (nch) ext++; // Check Extension
else if (n == 1) ext++; //Singular reply extension
else if (d >= 3 && i >= 4 && !pvnode) { //LMR
   if (CAP(m) || PROM(m)); //Don't reduce Captures and Promotions
   else if &#40;PIECE&#40;m&#41; == PAWN && (&#40;TO&#40;m&#41; + 16&#41; & 48&#41; < 32&#41;; //Don't reduce pawns moving to 7th rank
   else ext--;
&#125;

Can you check your killer moves, I do not reduce killers. Also there are cases that I do not reduce when it is a king move.

[grant]

If you keep record of king safety scores then

Code: Select all

if (blackKingSafety[ply] - blackKingSafety[ply - 1] > SAFETYMARGIN)
 do not reduce;

where kingSafety values are stored as positives.

Grant

[zamar]

All reductions and pruning techniques are based on statistical success. Most of the time they help, but sometimes they hurt.

Extension also help in this specific position. There are a lot of checks and singular moves in mating line.

[P. Villanueva]

In my case I prefer to measure this by search time, not by depth.
Can you post your other LMR conditions?

Of course you are right, as OliThink with LMR finds the mate quite quickly at SD=11.

Here are my LMR conditions, where d = depth, and i = nr. of move.

Code: Select all

if (nch) ext++; // Check Extension
else if (n == 1) ext++; //Singular reply extension
else if (d >= 3 && i >= 4 && !pvnode) { //LMR
   if (CAP(m) || PROM(m)); //Don't reduce Captures and Promotions
   else if &#40;PIECE&#40;m&#41; == PAWN && (&#40;TO&#40;m&#41; + 16&#41; & 48&#41; < 32&#41;; //Don't reduce pawns to 7th rank
   else ext--;
&#125;

You may considere to test:
1) Avoid reductions in all passed pawn advances.
2) Avoid reductions in killer moves (as Ferdinand says).
3) Avoid reductions in moves that give check.

[Eelco de Groot]

If you keep record of king safety scores then

Code: Select all

if (blackKingSafety[ply] - blackKingSafety[ply - 1] > SAFETYMARGIN)
 do not reduce;

where kingSafety values are stored as positives.

Grant

I think that is certainly promising Grant. Vas mentioned something along these lines in a response to Tord, once upon a time. I was in fact sure that Rybka was doing something like this in general so I am surprised it was not yet mentioned by people reviewing the Ippolit/Robbolito codes. Maybe it is not in there, or well hidden.

I think it is probably difficult to do the reductions/extensions in the right places or to not to overdo it. I tried King Safety to increase the Futility margins in Stockfish but that seemed to work not so well, as Futility Pruning was hard to improve. Marco mentioned something similar that it all came out even, but for me analysis results seemed to get worse in either direction.

It can also be used in the quiescence search as someone here proposed with working code, also for Stockfish. But that was not with the (blackKingSafety[ply] - blackKingSafety[ply - 1]) condition.
Increasing the Futility Margins more using King Safety in quiescence search, this is already done now but it can be done differently, seemed to have better effect but in situations where there is no real gain from an attack, I think you will have to scale it down earlier and this approach seems better suited for that than King Safety extensions in quiescence search; you can scale down extensions with it before you reach quiescence search. So I would probably want approach it from the other direction, reduce when King Safety is not increasing. It is exactly the same thing, codewise, but you would maybe write it down differently then:

Code: Select all

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

I have not actually tried if this works and if it can work without hurting finding of King attacks, makes play more passive maybe.

Eelco