# Difference between revisions of "RankCut"

GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||

Line 55: | Line 55: | ||

* [[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]]''' |

## Revision as of 21:20, 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 Pseudocode

^{[3]}

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

- ↑ 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