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) |
||
Line 19: | Line 19: | ||
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; |
Revision as of 21:03, 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 [1]. 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 [2],
RankCut was successfully implemented with Crafty and Toga II.
RankCut Code
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
References
- ↑ 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