AEL-Pruning
Home * Search * Selectivity * Pruning * AEL-Pruning
AEL-pruning,
a search technique by Ernst A. Heinz that combines Adaptive Null Move Pruning (i.e., Null Move pruning with variable depth reduction R), Extended Futility Pruning (futility pruning at pre-frontier nodes) and limited razoring.
Basic Idea
The basic idea is to first check if the depth is pre-pre-frontier, pre-frontier, or frontier, and create a bound based on the razoring margin (likely a queen), extended futility margin (usually around a rook), or futility margin (usually around a minor piece) accordingly. If none applied, only then use Adaptive Null Move Pruning. Now, when you are searching the moves of this position, apply the created bound if it applies. If the bound, plus any immediate material gain by the move is less than or equal to alpha, you may prune this move. Typically, you don't apply extended futility pruning or razoring on nodes you're extending.
Pseudo-Code
In his paper [1], Ernst A. Heinz] gives the following C pseudo-code:
int search (int alpha, int beta, int move, node parent, int depth) {
node current;
int extend, fmax, fscore, tt_hit;
/* declare the local variables that require constant initialization */
int fprune = 0;
int fpruned_moves = 0;
int score = -infinite_val;
/* execute the opponent's move and determine how to extend the search */
make_move(parent, move, ¤t;
extend = extensions(move, current, depth);
depth += extend;
/* decide about limited razoring at the pre-pre-frontier nodes */
fscore = (mat_balance(current) + razor_margin);
if (!extend && (depth == pre_pre_frontier) && (fscore <= alpha)
{ fprune = 1; score = fmax = fscore; }
/* decide about extended futility pruning at pre-frontier nodes */
fscore = (mat_balance(current) + extd_futil_margin);
if (!extend && (depth == pre_frontier) && (fscore <= alpha))
{ fprune = 1; score = fmax = fscore; }
/* decide about selective futility pruning at frontier nodes */
fscore = (mat_balance(current) + futil_margin);
if (!check(move) && (depth == frontier) && (fscore <= alpha))
{ fprune = 1; score = fmax = fscore; }
/* ... */
/* probe the transposition tables at the current node */
tt_hit = probe_transposition_tables(current, depth, &tt_ref);
if (tt_hit) {/* ... */} else {/* ... */}
/* try the adaptive null-move search with a minimal window around */
/* "beta" only if it is allowed, desired, and really promises to cut off */
if (!fprune && !check(move) && null_okay(current, move)
&& try_null(alpha, beta, current, depth, move, tt_ref)) {
/* ... */
null_score = -search(-beta, -beta + 1, null_move, current,
depth - R_adpt(current, depth) - 1);
if (null_score >= beta) return null_score;
/* ... */ /*fail-high null-move cutoff*/
}
/* ... */
/* now continue as usual but prune all futile moves if "fprune == 1"*/
for (move = first(current), (move != 0), move = next(current, move))
if (!fprune || check(move) /*recursive PVS part*/
|| (fmax + mat_gain(move) > alpha)) {/* ... */}
else fpruned_moves++;
/* "fpruned_moves > 0" => the search was selective at the current node */
/* ... */
}
Publications
- Ernst A. Heinz (2000). AEL-Pruning. ICGA Journal, Vol. 23, No. 1, pdf
See also
References
- ↑ Ernst A. Heinz (2000). AEL-Pruning. ICGA Journal, Vol. 23, No. 1, zipped postscript, pdf
