# RankCut

Home * Search * Selectivity * Reductions * RankCut

RankCut,
a probability based depth reduction technique introduced by Yew Jin Lim and Wee Sun Lee in 2006 . 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 , 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: