25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Pruning * Mate Distance Pruning''' If a forced mate has been found, '''Mate Distance Pruning''' (MDP)..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Mate Distance Pruning'''
If a forced [[Checkmate|mate]] has been found, '''Mate Distance Pruning''' (MDP) will cut trees and adjust [[Bound|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|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 [[Score|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.
<pre>
mating_value = SCORE_MATE - RootDistance;
if (mating_value < beta) {
beta = mating_value;
if (alpha >= mating_value) return mating_value;
}
</pre>
=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.
<pre>
mating_value = -SCORE_MATE + RootDistance;
if (mating_value > alpha) {
alpha = mating_value;
if (beta <= mating_value) return mating_value;
}
</pre>
=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.
<fentt border="double" style="font-size:24pt">8/7K/8/8/8/8/R7/7k</fentt>
8/7K/8/8/8/8/R7/7k w - - 0 1
{| class="wikitable"
|-
! Depth
! MDP Disabled
(Score / Nodes) <ref>Nodes until [[Principal variation|PV]] is found</ref>
! MDP Enabled
(Score / Nodes)
|-
! 1
| style="text-align:center;" | 1041 / 3
| style="text-align:center;" | 1041 / 3
|-
! 2
| style="text-align:center;" | 1041 / 23
| style="text-align:center;" | 1041 / 23
|-
! 3
| style="text-align:center;" | 1051 / 103
| style="text-align:center;" | 1051 / 103
|-
! 4
| style="text-align:center;" | 1051 / 551
| style="text-align:center;" | 1051 / 551
|-
! 5
| style="text-align:center;" | 1055 / 2151
| style="text-align:center;" | 1055 / 2151
|-
! 6
| style="text-align:center;" | 1051 / 7638
| style="text-align:center;" | 1051 / 7638
|-
! 7
| style="text-align:center;" | 1055 / 24353
| style="text-align:center;" | 1055 / 24353
|-
! 8
| style="text-align:center;" | 1065 / 62692
| style="text-align:center;" | 1065 / 62692
|-
! 9
| style="text-align:center;" | 1065 / 139241
| style="text-align:center;" | 1065 / 139241
|-
! 10
| style="text-align:center;" | 1085 / 253338
| style="text-align:center;" | 1085 / 253338
|-
! 11
| style="text-align:center;" | 1085 / 409101
| style="text-align:center;" | 1085 / 409101
|-
! 12
| style="text-align:center;" | 1105 / 610285
| style="text-align:center;" | 1105 / 610285
|-
! 13
| style="text-align:center;" | 1105 / 873959
| style="text-align:center;" | 1105 / 873959
|-
! 14
| style="text-align:center;" | 1105 / 1417047
| style="text-align:center;" | 1105 / 1417047
|-
! 15
| style="text-align:center;" | 1105 / 1907578
| style="text-align:center;" | 1105 / 1907578
|-
! 16
| style="text-align:center;" | M8 / 2846864
| style="text-align:center;" | M8 / 2547293
|-
! 17
| style="text-align:center;" | M8 / 3715208
| style="text-align:center;" | M8 / 2819164
|-
! 18
| style="text-align:center;" | M8 / 4842666
| style="text-align:center;" | M8 / 3092833
|-
! 19
| style="text-align:center;" | M8 / 6181827
| style="text-align:center;" | M8 / 3368068
|-
! 20
| style="text-align:center;" | M8 / 7774698
| style="text-align:center;" | 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=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007» [[Fail-Soft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=26995 Discussion about Mate Distance Pruning] by [[Don Dailey]], [[CCC]], March 14, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=41337 mate distance pruning problems and static null move pruning] by Pierre Bokma, [[CCC]], December 04, 2011 » [[Reverse Futility Pruning]]
=References=
<references/>
'''[[Pruning|Up one level]]'''
If a forced [[Checkmate|mate]] has been found, '''Mate Distance Pruning''' (MDP) will cut trees and adjust [[Bound|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|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 [[Score|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.
<pre>
mating_value = SCORE_MATE - RootDistance;
if (mating_value < beta) {
beta = mating_value;
if (alpha >= mating_value) return mating_value;
}
</pre>
=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.
<pre>
mating_value = -SCORE_MATE + RootDistance;
if (mating_value > alpha) {
alpha = mating_value;
if (beta <= mating_value) return mating_value;
}
</pre>
=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.
<fentt border="double" style="font-size:24pt">8/7K/8/8/8/8/R7/7k</fentt>
8/7K/8/8/8/8/R7/7k w - - 0 1
{| class="wikitable"
|-
! Depth
! MDP Disabled
(Score / Nodes) <ref>Nodes until [[Principal variation|PV]] is found</ref>
! MDP Enabled
(Score / Nodes)
|-
! 1
| style="text-align:center;" | 1041 / 3
| style="text-align:center;" | 1041 / 3
|-
! 2
| style="text-align:center;" | 1041 / 23
| style="text-align:center;" | 1041 / 23
|-
! 3
| style="text-align:center;" | 1051 / 103
| style="text-align:center;" | 1051 / 103
|-
! 4
| style="text-align:center;" | 1051 / 551
| style="text-align:center;" | 1051 / 551
|-
! 5
| style="text-align:center;" | 1055 / 2151
| style="text-align:center;" | 1055 / 2151
|-
! 6
| style="text-align:center;" | 1051 / 7638
| style="text-align:center;" | 1051 / 7638
|-
! 7
| style="text-align:center;" | 1055 / 24353
| style="text-align:center;" | 1055 / 24353
|-
! 8
| style="text-align:center;" | 1065 / 62692
| style="text-align:center;" | 1065 / 62692
|-
! 9
| style="text-align:center;" | 1065 / 139241
| style="text-align:center;" | 1065 / 139241
|-
! 10
| style="text-align:center;" | 1085 / 253338
| style="text-align:center;" | 1085 / 253338
|-
! 11
| style="text-align:center;" | 1085 / 409101
| style="text-align:center;" | 1085 / 409101
|-
! 12
| style="text-align:center;" | 1105 / 610285
| style="text-align:center;" | 1105 / 610285
|-
! 13
| style="text-align:center;" | 1105 / 873959
| style="text-align:center;" | 1105 / 873959
|-
! 14
| style="text-align:center;" | 1105 / 1417047
| style="text-align:center;" | 1105 / 1417047
|-
! 15
| style="text-align:center;" | 1105 / 1907578
| style="text-align:center;" | 1105 / 1907578
|-
! 16
| style="text-align:center;" | M8 / 2846864
| style="text-align:center;" | M8 / 2547293
|-
! 17
| style="text-align:center;" | M8 / 3715208
| style="text-align:center;" | M8 / 2819164
|-
! 18
| style="text-align:center;" | M8 / 4842666
| style="text-align:center;" | M8 / 3092833
|-
! 19
| style="text-align:center;" | M8 / 6181827
| style="text-align:center;" | M8 / 3368068
|-
! 20
| style="text-align:center;" | M8 / 7774698
| style="text-align:center;" | 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=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007» [[Fail-Soft]]
* [http://www.talkchess.com/forum/viewtopic.php?t=26995 Discussion about Mate Distance Pruning] by [[Don Dailey]], [[CCC]], March 14, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=41337 mate distance pruning problems and static null move pruning] by Pierre Bokma, [[CCC]], December 04, 2011 » [[Reverse Futility Pruning]]
=References=
<references/>
'''[[Pruning|Up one level]]'''
