Difference between revisions of "RankCut"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * Selectivity * Reductions * RankCut''' '''RankCut''',<br/> a probability based depth reduction technique introduced by Yew Jin L...") |
GerdIsenberg (talk | contribs) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * RankCut''' | '''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Reductions]] * RankCut''' | ||
+ | |||
+ | [[FILE:Rank badge.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Korea Korean] [https://en.wikipedia.org/wiki/Mandarin_square Rank badge] <ref>[https://en.wikipedia.org/wiki/Korea Korean] [https://commons.wikimedia.org/wiki/File:Rank_badge.jpg Rank badge], 1850-1900, [https://en.wikipedia.org/wiki/Victoria_and_Albert_Museum V&A Museum] (no. FE.272-1995), [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]] | ||
'''RankCut''',<br/> | '''RankCut''',<br/> | ||
Line 6: | Line 8: | ||
RankCut was successfully implemented with [[Crafty]] and [[Toga|Toga II]]. | RankCut was successfully implemented with [[Crafty]] and [[Toga|Toga II]]. | ||
− | =RankCut | + | =RankCut Pseudocode= |
+ | <ref>based on pseudocode pp. 90 in [[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]</ref> | ||
<pre> | <pre> | ||
RankCutReSearch = false; | RankCutReSearch = false; | ||
Line 19: | Line 22: | ||
features = determineFeatures(state); | features = determineFeatures(state); | ||
if (pruneRest || (probability(features) < threshold) ) { | if (pruneRest || (probability(features) < threshold) ) { | ||
− | + | r = depthReduction(state); | |
pruneRest = true; | pruneRest = true; | ||
− | + | } | |
score = −RankCut(successor(state, move), −β, −α, depth−1−r); | score = −RankCut(successor(state, move), −β, −α, depth−1−r); | ||
if (RankCutReSearch && (score > α) && pruneRest) | if (RankCutReSearch && (score > α) && pruneRest) | ||
score = −RankCut(successor(state, move), −β, −α, depth−1); | score = −RankCut(successor(state, move), −β, −α, depth−1); | ||
− | + | if (score ≥ β ) | |
− | + | break; | |
if (score > α) { | if (score > α) { | ||
pruneRest = false; | pruneRest = false; | ||
α = score; | α = score; | ||
− | + | } | |
} | } | ||
return score; | return score; | ||
Line 49: | Line 52: | ||
=See also= | =See also= | ||
* [[Late Move Reductions]] | * [[Late Move Reductions]] | ||
+ | * [[ProbCut]] | ||
=Publications= | =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]], [[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] | * [[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] | ||
+ | |||
+ | =External Links= | ||
+ | * [https://en.wikipedia.org/wiki/Ranking Ranking from Wikipedia] | ||
+ | * [https://en.wikipedia.org/wiki/Decision_tree_pruning Pruning from Wikipedia] | ||
=References= | =References= | ||
<references /> | <references /> | ||
'''[[Reductions|Up one level]]''' | '''[[Reductions|Up one level]]''' |
Latest revision as of 23:00, 6 November 2019
Home * Search * Selectivity * Reductions * RankCut
RankCut,
a probability based depth reduction technique introduced by Yew Jin Lim and Wee Sun Lee in 2006 [2]. 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 and fail-soft to work well. Further elaborated by Yew Jin Lim in his 2007 Ph.D. thesis [3],
RankCut was successfully implemented with Crafty and Toga II.
RankCut Pseudocode
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; }
Crafty
In the case of Crafty 19.19, The probability computation considers following features:
- Depth
- In Check
- Move 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)
- Phase of the Move Generation (History Moves or Remaining Moves)
See also
Publications
- Yew Jin Lim, Wee Sun Lee (2006). RankCut - A Domain Independent Forward Pruning Method for Games. AAAI 2006, pdf
- Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore, pdf
External Links
References
- ↑ Korean Rank badge, 1850-1900, V&A Museum (no. FE.272-1995), Wikimedia Commons
- ↑ Yew Jin Lim, Wee Sun Lee (2006). RankCut - A Domain Independent Forward Pruning Method for Games. AAAI 2006
- ↑ Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore
- ↑ based on pseudocode pp. 90 in Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore, pdf