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 prerequisit 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.
external image 7k%20w%20-%20-&size=medium&coord=yes&cap=no&stm=yes&fb=no&theme=classic&color1=E3CEAA&color2=635147&color3=000000
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

What links here?


Up one level