25,161
edits
Changes
Created page with " '''Home * Search * Selectivity * Pruning * AEL-Pruning''' '''AEL-pruning''', a search technique by Ernst A. Heinz that combines Null Move Pru..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * AEL-Pruning'''
'''AEL-pruning''',
a search technique by [[Ernst A. Heinz]] that combines [[Null Move Pruning#AdaptiveNullMovePruning|Adaptive Null Move Pruning]] (i.e., Null Move pruning with variable [[Depth Reduction R|depth reduction R]]), [[Futility Pruning#Extendedfutilitypruning|Extended Futility Pruning]] (futility pruning at [[Pre Frontier Node|pre-frontier nodes]]) and [[Razoring#LimitedRazoring|limited razoring]].
=Basic Idea=
The basic idea is to first check if the depth is pre-pre-frontier, pre-frontier, or [[Frontier Nodes|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 <ref>[[Ernst A. Heinz]] ('''2000'''). ''AEL-Pruning''. [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]], [http://people.csail.mit.edu/heinz/node17.html zipped postscript], [http://www.top-5000.nl/ps/AEL%20pruning.pdf pdf]</ref>, Ernst A. Heinz] gives the following [[C]] pseudo-code:
<pre>
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 */
/* ... */
}
</pre>
=Publications=
* [[Ernst A. Heinz]] ('''2000'''). ''AEL-Pruning''. [[ICGA Journal#23_1|ICGA Journal, Vol. 23, No. 1]], [http://www.top-5000.nl/ps/AEL%20pruning.pdf pdf]
=See also=
* [[Null Move Pruning#AdaptiveNullMovePruning|Adaptive Null Move Pruning]]
* [[Futility Pruning#Extendedfutilitypruning|Extended Futility Pruning]]
* [[Razoring#LimitedRazoring|Limited Razoring]]
=References=
<references />
'''[[Pruning|Up one Level]]'''
