Saturday, June 6, 2015

Nullmove Blindness

White moves and Mates in 3 (1. Rh5 h6 2. h4 Kh2 3. Rh3#)

From time to time I challenge iCE with some Mate in X problems. Usually iCE has no problems solving them, at least if the Mate is not to far away. But lately I encountered a position (above) where iCE surprisingly struggled.

It is a Mate in 3 but iCE solves it as a Mate in 5.

iCE 3.0 v386 x64/popcnt [2015.6.1]
position fen 8/7p/8/8/3p4/3P2RR/6PP/5K1k w - - 0 1
analyze depth 20
Analysing 14 moves up to depth 20

g3g7  mate 5    1. Rg7 h6 2. Rg8 h5 3. Rg7 h4 4. g4 hg 5. hg
g3g5  mate 5    1. Rg5 h6 2. Rg8
g3g8  mate 5    1. Rg8 h6 2. Rg6 h5 3. Rg7
h3h5  mate 5    1. Rh5 h6 2. Rh3 h5 3. Rg7 h4 4. g4 hg 5. hg
..


Mate is Mate in in game play it will not really matter if it takes 2 moves longer. But it is kind of embarrassing for a 2900 ELO engine to not be able to solve a Mate in 3.

I looked into the problem and it turned out to be a combination of 2 things.
  1. iCE is doing a Mate distance pruning in the root node. This means if it finds a Mate in 5 it will stop search at ply 10 because searching more plies should not find shorter Mates. This was true for early versions of iCE but as it is now having such an aggressive reduction and pruning scheme more plies will reveal shorter mates (when formerly reduced or pruned moves turn out to be good).
  2. The null move reduction was to high if a forced Mate was found, pruning away possible better candidates.
So I turned off Mate distance pruning in the root position and also reduced the null move reduction to not exceed a certain threshold. This seems to fix the problem at least for this position.

iCE 3.0 v392 x64/popcnt [2015.6.4]
position fen 8/7p/8/8/3p4/3P2RR/6PP/5K1k w - - 0 1
analyze depth 18
Analysing 14 moves up to depth 18
 

h3h5  mate 3    1. Rh5 h6 2. h4 Kh2 3. Rh3
f1f2  mate 4    1. Kf2 h6 2. Rg7 h5 3. Rc7 h4 4. Rc1
..


A final regression test with 16000 games showed that the patched version is very likely not weaker than the previous one. It scored (W/L/D) 4300-4181-7515.

Rank Name                      Elo    +    - games score oppo. draws
   1 iCE 3.0 v392 x64/popcnt     1    4    4 16000   50%    -1   47%
   2 iCE 3.0 v386 x64/popcnt    -1    4    4 16000   50%     1   47%


Patch committed.