Difference between revisions of "RankCut"

From Chessprogramming wiki
Jump to: navigation, search
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:

See also

Publications

External Links

References

  1. Yew Jin Lim, Wee Sun Lee (2006). RankCut - A Domain Independent Forward Pruning Method for Games. AAAI 2006
  2. Yew Jin Lim (2007). On Forward Pruning in Game-Tree Search. Ph.D. thesis, National University of Singapore
  3. 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

Up one level