25,161
edits
Changes
Created page with "'''Home * Search * Selectivity * Reductions * RankCut''' '''RankCut''',<br/> a probability based depth reduction technique introduced by Yew Jin L..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * RankCut'''
'''RankCut''',<br/>
a probability based depth reduction technique introduced by [[Yew Jin Lim]] and [[Wee Sun Lee]] in 2006 <ref>[[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games''. [[Conferences#AAAI-2006|AAAI 2006]]</ref>. It estimates the probability of discovering a better move later in the search by using the relative frequency of such cases for various states during the search. These probabilities are pre-computed off-line using several self-play games. RankCut can then reduce search effort by performing a shallow search when the probability of a better move appearing is below a certain threshold.
RankCut requires good [[Move Ordering|move ordering]] and [[Fail-Soft|fail-soft]] to work well. Further elaborated by [[Yew Jin Lim]] in his 2007 Ph.D. thesis <ref>[[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore]</ref>,
RankCut was successfully implemented with [[Crafty]] and [[Toga|Toga II]].
=RankCut Code=
<pre>
RankCutReSearch = false;
int RankCut(State & state, int α, int β, int depth) {
if ((depth == 0) || isTerminal(state))
return Evaluate(state);
pruneRest = false;
score = −∞;
while (move = NextMove(state) ) {
r = 0;
features = determineFeatures(state);
if (pruneRest || (probability(features) < threshold) ) {
r = depthReduction(state);
pruneRest = true;
}
score = −RankCut(successor(state, move), −β, −α, depth−1−r);
if (RankCutReSearch && (score > α) && pruneRest)
score = −RankCut(successor(state, move), −β, −α, depth−1);
if (score ≥ β )
break;
if (score > α) {
pruneRest = false;
α = score;
}
}
return score;
}
</pre>
=Crafty=
In the case of [[Crafty]] 19.19, The probability computation considers following features:
* [[Depth]]
* [[Check|In Check]]
* [[Moves|Move]] [[Extensions|Extended]]
* Move Number
* Number of times [[Best Move]] changed
* Difference between the [[Score]] of the current [[Best Move]] from [[Alpha]] (discretized to 7 intervals)
* Difference between the [[Score]] of the Last Move from the current [[Best Move]] (discretized to 7 intervals)
* [[Move Generation#Staged|Phase]] of the [[Move Generation]] (History Moves or Remaining Moves)
=See also=
* [[Late Move Reductions]]
=Publications=
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games''. [[Conferences#AAAI-2006|AAAI 2006]], [http://www.yewjin.com/storage/papers/rankcut.pdf pdf]
* [[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore], [http://www.yewjin.com/storage/papers/PhDThesisLimYewJin.pdf pdf]
=References=
<references />
'''[[Reductions|Up one level]]'''
'''RankCut''',<br/>
a probability based depth reduction technique introduced by [[Yew Jin Lim]] and [[Wee Sun Lee]] in 2006 <ref>[[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games''. [[Conferences#AAAI-2006|AAAI 2006]]</ref>. It estimates the probability of discovering a better move later in the search by using the relative frequency of such cases for various states during the search. These probabilities are pre-computed off-line using several self-play games. RankCut can then reduce search effort by performing a shallow search when the probability of a better move appearing is below a certain threshold.
RankCut requires good [[Move Ordering|move ordering]] and [[Fail-Soft|fail-soft]] to work well. Further elaborated by [[Yew Jin Lim]] in his 2007 Ph.D. thesis <ref>[[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore]</ref>,
RankCut was successfully implemented with [[Crafty]] and [[Toga|Toga II]].
=RankCut Code=
<pre>
RankCutReSearch = false;
int RankCut(State & state, int α, int β, int depth) {
if ((depth == 0) || isTerminal(state))
return Evaluate(state);
pruneRest = false;
score = −∞;
while (move = NextMove(state) ) {
r = 0;
features = determineFeatures(state);
if (pruneRest || (probability(features) < threshold) ) {
r = depthReduction(state);
pruneRest = true;
}
score = −RankCut(successor(state, move), −β, −α, depth−1−r);
if (RankCutReSearch && (score > α) && pruneRest)
score = −RankCut(successor(state, move), −β, −α, depth−1);
if (score ≥ β )
break;
if (score > α) {
pruneRest = false;
α = score;
}
}
return score;
}
</pre>
=Crafty=
In the case of [[Crafty]] 19.19, The probability computation considers following features:
* [[Depth]]
* [[Check|In Check]]
* [[Moves|Move]] [[Extensions|Extended]]
* Move Number
* Number of times [[Best Move]] changed
* Difference between the [[Score]] of the current [[Best Move]] from [[Alpha]] (discretized to 7 intervals)
* Difference between the [[Score]] of the Last Move from the current [[Best Move]] (discretized to 7 intervals)
* [[Move Generation#Staged|Phase]] of the [[Move Generation]] (History Moves or Remaining Moves)
=See also=
* [[Late Move Reductions]]
=Publications=
* [[Yew Jin Lim]], [[Wee Sun Lee]] ('''2006'''). ''RankCut - A Domain Independent Forward Pruning Method for Games''. [[Conferences#AAAI-2006|AAAI 2006]], [http://www.yewjin.com/storage/papers/rankcut.pdf pdf]
* [[Yew Jin Lim]] ('''2007'''). ''On Forward Pruning in Game-Tree Search''. Ph.D. thesis, [https://en.wikipedia.org/wiki/National_University_of_Singapore National University of Singapore], [http://www.yewjin.com/storage/papers/PhDThesisLimYewJin.pdf pdf]
=References=
<references />
'''[[Reductions|Up one level]]'''
