Mate Distance Pruning

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Selectivity * Pruning * Mate Distance Pruning

If a forced mate has been found, Mate Distance Pruning (MDP) will cut trees and adjust bounds of lines where no shorter mate is possible. Mate Distance Pruning is a safe type of pruning, as it only cuts irrelevant nodes. It will not add much to a programs playing strength as this pruning only comes into effect when a position is already decided, still it helps with analysis and solving "Mate in n" problems.

Mating Value

The prerequisite for Mate Distance Pruning is that decided positions are properly scored. So a position where the opponent is mated is scored SCORE_MATE (a very high value), a position where the victory is one move away is worth less SCORE_MATE - 1, Mate in 2 plies is scored SCORE_MATE - 2 and so on. On the other side, a position where the side to move is mated in n plies is evaluated -SCORE_MATE + n. The difference between the actual value and SCORE_MATE is always the number of plies the mate is away from the root position.

Upper Bound

Assume we are in a winning position. Through another line we have already found a forced mate in n plies. Thus our alpha is SCORE_MATE - n. From this information we can take that should we be searching a line that already is equal to or longer than n, we can impossibly increase alpha even if another mate was found. This means we could safely prune that tree.

Furthermore we can lower the upper bound. If we are n plies away from the root, the opponent can impossibly be evaluated > SCORE_MATE - n. Thus beta can be set to this value should it be higher.

mating_value = SCORE_MATE - RootDistance;

if (mating_value < beta) {
   beta = mating_value;
   if (alpha >= mating_value) return mating_value;
}

Lower Bound

Contrary to the pruning if we are in a winning position, scores can also be adjusted and trees pruned if we are in a loosing position.

mating_value = -SCORE_MATE + RootDistance;

if (mating_value > alpha) {
   alpha = mating_value;
   if (beta <= mating_value) return mating_value;
}

In Practice

Using the Chess Engine Glass 1.0 the treesize of a search without Mate Distance Pruning is compared to one with this feature enabled.

    
    
    
    
    
    
    
    
        
       
        
        
        
        
       
       
        
       ♔
        
        
        
        
♖       
       ♚

8/7K/8/8/8/8/R7/7k w - - 0 1


Depth MDP Disabled

(Score / Nodes) [1]

MDP Enabled

(Score / Nodes)

1 1041 / 3 1041 / 3
2 1041 / 23 1041 / 23
3 1051 / 103 1051 / 103
4 1051 / 551 1051 / 551
5 1055 / 2151 1055 / 2151
6 1051 / 7638 1051 / 7638
7 1055 / 24353 1055 / 24353
8 1065 / 62692 1065 / 62692
9 1065 / 139241 1065 / 139241
10 1085 / 253338 1085 / 253338
11 1085 / 409101 1085 / 409101
12 1105 / 610285 1105 / 610285
13 1105 / 873959 1105 / 873959
14 1105 / 1417047 1105 / 1417047
15 1105 / 1907578 1105 / 1907578
16 M8 / 2846864 M8 / 2547293
17 M8 / 3715208 M8 / 2819164
18 M8 / 4842666 M8 / 3092833
19 M8 / 6181827 M8 / 3368068
20 M8 / 7774698 M8 / 3643489

From this table one can see that the treesize is equal for the first 15 plies, but then the Version with Mate Distance Pruning enabled found the exact mating line about 10% smaller. Furthermore the risk of treesize explosion for further iterations is greatly decreased. In this example the treesize of the Version with this type of Pruning enabled is less than half as big.

Forum Posts

References

  1. Nodes until PV is found

Up one level