Author: Eric Oldre
Date: 17:10:01 04/19/04
Ed Schroder describes a technique for futility pruning on his page located at:
http://members.home.nl/matador/chess840.htm#FUTILITY
here is the code he describes.
if (current_depth == horizon_depth-1) then
{ if (own_king_is_in_check) -> don't try FUTILITY, too
dangerous.
if (move_does_check_the_opponent_king) -> don't try FUTILITY, too
dangerous.
if (move_is_a_capture) -> don't try FUTILITY, too
dangerous.
if (special_case_position) -> don't try FUTILITY, see Lazy
Eval.
Futility_One(); -> calculate (guess) score, more
below.
if (ALPHA < SCORE + MARGIN) -> don't reward FUTILITY, just
proceed.
else: prune tree (don't go deeper) using SCORE as the real score.
}
I have a few questions about it:
1) which part of the search function would this be placed: (i'm going to
paraphase the AB search from Bruce Moreland's site here)
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
***DO FUTILITY PRUNING HERE***
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}
or would it be
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
return Evaluate();
if (depth == 1)
***DO FUTILITY PRUNING HERE***
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}
part of what is confusing me is Ed is testing for both:
own_king_is_in_check
move_does_check_the_opponent_king
since the side to move can't have the opponent's king in check already since
this would be a checkmate, it seems to me that he must be refering to the 1st
case. but i'm not really sure about that. if not, which move is he refering to?
question #2) it seems he is refering to just doing a static eval in the futility
pruning. that just seems dangerous to me, not taking into account hanging pieces
etc. I tested doing a QSearch at depth 1 but found that the cost of doing so
didn't really get me much benefit. IE the reduction in tree size was offest by
the speed cost of the qsearch at depth 1.
question #3) what is the rational behind only doing a test to see if we are
below alpha. and not above beta. it seems like if you can determine that you are
likely to be above beta, that would have a similar effect as testing if you are
below alpha. Since he didn't do it this way, I'm sure there must be a big issue
with it. but i can't think of what that would be.
As always, thanks for your help,
Eric Oldre
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.