Author: Dann Corbit
Date: 16:42:33 05/31/02
Go up one level in this thread
On May 31, 2002 at 18:50:18, Omid David wrote:
>I forgot to change "negascout" to "AlphaBeta" in 7th line for better
>illustration. Here is the correction:
>
>int AspWin(int estimate, int delta, int depth)
>{
>int alpha = estimate - delta;
>int beta = estimate + delta;
>int best;
>
>best = AlphaBeta(alpha, beta, depth);
>
>/* re-search */
>if(best <= alpha)
>best = AlphaBeta(-10000, beta, depth);
>else if(best >= beta)
>best = AlphaBeta(alpha, 10000, depth);
>
>/* is there any better way to handle this very rare case? */
>if(best >= beta || best <= alpha)
>best = AlphaBeta(-10000, 10000, depth);
>
>return best;
>}
Amy (I was too lazy to trim out all except the relevant parts):
/*
* The main negascout routine with handles things like
* search extensions, hash table lookup etc.
*
* It recursively calls itself until depth is exhausted.
* Than `quies` is called.
*
* This is modified to perform an 'ABDADA' search if MP is defined.
* See Jean-Christophe Weill, "The ABDADA Distributed Minimax-Search Algorithm"
* ICCA Journal, Volume 19, No. 1, pp. 3-16
*/
int negascout(struct SearchData * sd,
int alpha,
int beta,
int depth,
int node_type
#if MP
,int exclusiveP
#endif /* MP */
)
{
struct Position *p = sd->position;
struct SearchStatus *st;
int best = -INF;
int bestm = M_NONE;
int tmp;
int talpha;
int incheck;
int lmove;
int move;
int extend = 0;
int threat = FALSE;
int reduce_extensions;
int next_type;
int was_futile = FALSE;
#if FUTILITY
int is_futile;
int optimistic;
#endif
#if MP
int deferred_cnt = 0;
int deferred_list[64];
int deferred_depth[64];
#endif
EnterNode(sd);
Nodes++;
/* check for search termination */
if (sd->master && TerminateSearch(sd)) {
AbortSearch = TRUE;
goto EXIT;
}
/* max search depth reached */
if (sd->ply >= MaxDepth)
goto EXIT;
/* Check for insufficent material or theoretical draw. */
if ( /* InsufMat(p) || CheckDraw(p) || */ Repeated(p, FALSE)) {
best = 0;
goto EXIT;
}
/* check extension */
incheck = InCheck(p, p->turn);
if (incheck && p->material[p->turn] > 0) {
extend += CheckExtend(p);
ChkExt++;
}
/* Check the hashtable */
st = sd->current;
HTry++;
#if MP
switch (ProbeHT(p->hkey, &tmp, depth, &(st->st_hashmove), &threat, sd->ply,
exclusiveP))
#else
switch (ProbeHT(p->hkey, &tmp, depth, &(st->st_hashmove), &threat, sd->ply))
#endif /* MP */
{
case ExactScore:
HHit++;
best = tmp;
goto EXIT;
case UpperBound:
if (tmp <= alpha) {
HHit++;
best = tmp;
goto EXIT;
}
break;
case LowerBound:
if (tmp >= beta) {
HHit++;
best = tmp;
goto EXIT;
}
break;
case Useless:
threat = !incheck && MateThreat(p, OPP(p->turn));
break;
#if MP
case OnEvaluation:
best = -ON_EVALUATION;
goto EXIT;
#endif
}
/* Probe EGTB */
if (ProbeEGTB(p, &tmp, sd->ply)) {
best = tmp;
goto EXIT;
}
/* Probe recognizers */
switch (ProbeRecognizer(p, &tmp)) {
case ExactScore:
best = tmp;
goto EXIT;
case LowerBound:
if (tmp >= beta) {
best = tmp;
goto EXIT;
}
break;
case UpperBound:
if (tmp <= alpha) {
best = tmp;
goto EXIT;
}
break;
}
#if NULLMOVE
/* Null move search. See Christian Donninger, "Null Move and Deep Search"
* ICCA Journal Volume 16, No. 3, pp. 137-143 */
if (!incheck && node_type == CutNode && !threat) {
int next_depth;
int nms;
next_depth = depth - ReduceNullMove;
DoNull(p);
if (next_depth < 0) {
nms = -quies(sd, -beta, -beta + 1, 0);
} else {
#if MP
nms = -negascout(sd, -beta, -beta + 1, next_depth, AllNode, 0);
#else
nms = -negascout(sd, -beta, -beta + 1, next_depth, AllNode);
#endif
}
UndoNull(p);
if (AbortSearch)
goto EXIT;
if (nms >= beta) {
if (p->nonPawn[p->turn] >= Value[Queen]) {
best = nms;
goto EXIT;
} else {
if (next_depth < 0) {
nms = quies(sd, beta - 1, beta, 0);
} else {
#if MP
nms = negascout(sd, beta - 1, beta, next_depth,
CutNodeNoNull,
0);
#else
nms = negascout(sd, beta - 1, beta, next_depth,
CutNodeNoNull);
#endif
}
if (nms >= beta) {
best = nms;
goto EXIT;
} else {
extend += ExtendZugzwang;
ZZExt++;
}
}
} else if (nms <= -CMLIMIT) {
threat = TRUE;
}
}
#endif /* NULLMOVE */
lmove = (p->actLog - 1)->gl_Move;
reduce_extensions = (sd->ply > 2 * sd->depth);
talpha = alpha;
switch (node_type) {
case AllNode:
next_type = CutNode;
break;
case CutNode:
case CutNodeNoNull:
next_type = AllNode;
break;
default:
next_type = PVNode;
break;
}
#if FUTILITY
is_futile = !incheck && !threat && alpha < CMLIMIT && alpha > -CMLIMIT;
if (is_futile) {
if (p->turn == White) {
optimistic = MaterialBalance(p) + MaxPos;
} else {
optimistic = -MaterialBalance(p) + MaxPos;
}
}
#endif /* FUTILITY */
/* Internal iterative deepening. If we do not have a move, we try a
* shallow search to find a good candidate. */
if (depth > 2 * OnePly && alpha + 1 != beta && !LegalMove(p,
st->st_hashmove)) {
int useless;
#if MP
useless = negascout(sd, alpha, beta, depth - 2 * OnePly, PVNode, 0);
#else
useless = negascout(sd, alpha, beta, depth - 2 * OnePly, PVNode);
#endif
st->st_hashmove = sd->pv_save[sd->ply + 1];
}
/* Search all legal moves */
while ((move = incheck ? NextEvasion(sd) : NextMove(sd)) != M_NONE) {
int next_depth = extend;
if (move & M_CANY && !MayCastle(p, move))
continue;
/* recapture extension */
if ((move & M_CAPTURE) && (lmove & M_CAPTURE) &&
M_TO(move) == M_TO(lmove) &&
IsRecapture(p->piece[M_TO(move)], (p->actLog - 1)->gl_Piece)) {
RCExt += 1;
next_depth += ExtendRecapture[TYPE(p->piece[M_TO(move)])];
}
/* passed pawn push extension */
if (TYPE(p->piece[M_FROM(move)]) == Pawn &&
p->nonPawn[OPP(p->turn)] <= Value[Queen]) {
int to = M_TO(move);
if (((p->turn == White && to >= a7) ||
(p->turn == Black && to <= h2)) &&
IsPassed(p, to, p->turn) && SwapOff(p, move) >= 0) {
next_depth += ExtendPassedPawn;
PPExt += 1;
}
}
/* limit extensions to sensible range. */
if (reduce_extensions)
next_depth /= 2;
next_depth += depth - OnePly;
#if FUTILITY
/* Futility cutoffs */
if (is_futile) {
if (next_depth < 0 && !IsCheckingMove(p, move)) {
tmp = optimistic + ScoreMove(p, move);
if (tmp <= alpha) {
if (tmp > best) {
best = tmp;
bestm = move;
was_futile = TRUE;
}
continue;
}
}
#if EXTENDED_FUTILITY
/* Extended futility cutoffs and limited razoring. See Ernst A.
* Heinz, "Extended Futility Pruning" ICCA Journal Volume 21, No.
* 2, pp 75-83 */
else if (next_depth >= 0 && next_depth < OnePly
&& !IsCheckingMove(p, move)) {
tmp = optimistic + ScoreMove(p, move) + (3 * Value[Pawn]);
if (tmp <= alpha) {
if (tmp > best) {
best = tmp;
bestm = move;
was_futile = TRUE;
}
continue;
}
}
#if RAZORING
else if (next_depth >= OnePly && next_depth < 2 * OnePly
&& !IsCheckingMove(p, move)) {
tmp = optimistic + ScoreMove(p, move) + (6 * Value[Pawn]);
if (tmp <= alpha) {
next_depth -= OnePly;
}
}
#endif /* RAZORING */
#endif /* EXTENDED_FUTILITY */
}
#endif /* FUTILITY */
DoMove(p, move);
if (InCheck(p, OPP(p->turn))) {
UndoMove(p, move);
} else {
/* Check extension */
if (p->material[p->turn] > 0 && InCheck(p, p->turn)) {
next_depth += (reduce_extensions) ?
ExtendInCheck >> 1 : ExtendInCheck;
}
/* Recursively search this position. If depth is exhausted, use
* quies, otherwise use negascout. */
if (next_depth < 0) {
tmp = -quies(sd, -beta, -talpha, 0);
} else if (bestm != M_NONE && !was_futile) {
#if MP
tmp = -negascout(sd, -talpha - 1, -talpha, next_depth,
next_type,
bestm != M_NONE);
if (tmp != ON_EVALUATION && tmp > talpha && tmp < beta) {
tmp = -negascout(sd, -beta, -tmp, next_depth,
node_type == PVNode ? PVNode : AllNode,
bestm != M_NONE);
}
#else
tmp = -negascout(sd, -talpha - 1, -talpha, next_depth,
next_type);
if (tmp > talpha && tmp < beta) {
tmp = -negascout(sd, -beta, -tmp, next_depth,
node_type == PVNode ? PVNode : AllNode);
}
#endif /* MP */
} else {
#if MP
tmp = -negascout(sd, -beta, -talpha, next_depth, next_type,
bestm != M_NONE);
#else
tmp = -negascout(sd, -beta, -talpha, next_depth, next_type);
#endif /* MP */
}
UndoMove(p, move);
if (AbortSearch)
goto EXIT;
#if MP
if (tmp == ON_EVALUATION) {
/* This child is ON_EVALUATION. Remember move and depth. */
deferred_list[deferred_cnt] = move;
deferred_depth[deferred_cnt] = next_depth;
deferred_cnt++;
} else {
#endif /* MP */
/* beta cutoff, enter move in Killer/Countermove table */
if (tmp >= beta) {
if (!(move & M_TACTICAL)) {
PutKiller(sd, move);
sd->counterTab[p->turn][lmove & 4095] = move;
}
StoreResult(sd, tmp, alpha, beta, move, depth, threat);
best = tmp;
goto EXIT;
}
/* Improvement on best move to date */
if (tmp > best) {
best = tmp;
bestm = move;
was_futile = FALSE;
if (best > talpha) {
talpha = best;
}
}
next_type = CutNode;
#if MP
}
#endif /* MP */
}
}
#if MP
/* Now search all moves which were ON_EVALUATION in pass one. */
while (deferred_cnt) {
int next_depth = deferred_depth[--deferred_cnt];
move = deferred_list[deferred_cnt];
DoMove(p, move);
tmp = -negascout(sd, -talpha - 1, -talpha, next_depth, next_type, 0);
if (tmp > talpha && tmp < beta) {
tmp = -negascout(sd, -beta, -talpha, next_depth,
node_type == PVNode ? PVNode : AllNode, 0);
}
UndoMove(p, move);
/* beta cutoff, enter move in Killer/Countermove table */
if (tmp >= beta) {
if (!(move & M_TACTICAL)) {
PutKiller(sd, move);
sd->counterTab[p->turn][lmove & 4095] = move;
}
StoreResult(sd, tmp, alpha, beta, move, depth, threat);
best = tmp;
goto EXIT;
}
/* Improvement on best move to date */
if (tmp > best) {
best = tmp;
bestm = move;
was_futile = FALSE;
if (best > talpha) {
talpha = best;
}
}
next_type = CutNode;
}
#endif /* MP */
/* If we get here, no legal move was found. Score this position as mate
* or draw. */
if (bestm == M_NONE) {
if (incheck)
best = -INF + sd->ply;
else
best = 0;
}
if (!was_futile) {
StoreResult(sd, best, alpha, beta, bestm, depth, threat);
}
EXIT:
if (node_type == PVNode) {
sd->pv_save[sd->ply] = bestm;
}
LeaveNode(sd);
return best;
}
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.