Author: Dann Corbit
Date: 16:45:16 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;
>}
Arasan (again, I was too lazy for any surgery):
int Search::
move_search(Board & board, int alpha, int beta,
const int ply, int depth, BOOL in_pv,
BOOL &terminate)
{
// recursive function, implements alpha/beta search. We use
// the PVS (principal variation search) variant of alpha/beta.
search1_start = ply;
if (time_check_counter >= Time_Check_Interval)
{
time_check_counter = 0;
terminate = check_time(ply,0);
}
ASSERT(ply < Constants::MaxPly);
time_check_counter++;
num_nodes++;
// moves into check are illegal.
if (board.any_attacks(board.KingPos(
board.OppositeSide()),board.Side()))
{
#ifdef _TRACE
indent(ply); cout << "Illegal move!" << endl;
#endif
return -Illegal;
}
else if (terminate)
{
return alpha;
}
best[ply] = NullMove; // move we will return
BOOL in_check = FALSE;
BOOL forced = FALSE;
BOOL deepFlag = FALSE;
int threat = 0, extend = 0;
int move_count = 0;
int move_index = 0;
Move best_move = NullMove; // move we will hash
int num_try = 0; // # of legal moves tried
Move hash_move = NullMove;
Position_Info *hash_entry = NULL;
int rep_count;
int score = alpha;
if (is_draw(board,rep_count,ply))
{
#ifdef _TRACE
cout << "draw!" << endl;
#endif
score = draw_score(board);
return score;
}
else if (ply >= Constants::MaxPly-1)
{
return evalu8(board,alpha,beta,ply);
}
if (use_hash_table)
{
// Search the hash table to see if we have hit this
// position before.
hash_entry = searchHash(board,rep_count);
hash_searches++;
if (!hash_entry)
{
// Try the permanent hash table
if (global_options->use_book_learning())
hash_entry = position_book->lookup(board,rep_count);
#ifdef _TRACE
if (hash_entry)
cout << "position book hash hit" << endl;
#endif
}
if (hash_entry)
{
hash_move = hash_entry->best_move(board);
#ifdef _DEBUG
// Found the position in the hash table.
if (!hash_move_valid(board,hash_move))
{
#ifdef _TRACE
indent(ply);
cout << "Warning: hash move invalid" << endl;
#endif
hash_entry = NULL;
hash_move = NullMove;
}
}
if (hash_entry)
{
#endif
hash_hits++;
forced = hash_entry->forced();
board.set_check_status(hash_entry->in_check() ?
Board::InCheck : Board::NotInCheck);
if (hash_entry->depth() >= depth/* ||
(hash_entry->type() == Position_Info::Valid &&
Util::Abs(hash_entry->value()) > Constants::BIG-100)*/)
{
int value = hash_entry->value();
//
// Whether we can use the hash value or not depends on
// the flags:
//
switch (hash_entry->type())
{
case Position_Info::Valid:
// If this is a mate score, adjust it to reflect the
// current ply depth.
//
if (value > Constants::BIG-100)
{
value -= ply;
}
else if (value < -Constants::BIG+100)
{
value += ply;
}
if (value < beta)
{
UPDATE_PV(best_move,ply);
}
#ifdef _TRACE
indent(ply);
cout << "hash hit, type = E" <<
" move = " << MoveImage(hash_move) <<
" alpha = " << alpha << " beta = " << beta <<
" value = " << value << endl;
#endif
return value;
case Position_Info::LowerBound:
if (value >= beta)
{
#ifdef _TRACE
indent(ply);
cout << "hash hit, type = L" <<
" move = " << MoveImage(hash_move) <<
" alpha = " << alpha << " beta = " << beta <<
" value = " << value << endl;
#endif
return value;
}
break;
case Position_Info::UpperBound:
#ifdef _TRACE
indent(ply);
cout << "hash hit, type = U" <<
" move = " << MoveImage(hash_move) <<
" alpha = " << alpha << " beta = " << beta <<
" value = " << value << endl;
#endif
if (value <= alpha)
{
return value;
}
break;
default:
break;
}
}
}
}
#ifdef _TRACE
if (!IsNull(hash_move))
{
indent(ply);
cout << "hash move = " << MoveImage(hash_move) << endl;
}
#endif
int initial_alpha = alpha;
// At this point we need to know if we are in check or not.
in_check = checks[ply] = board.CheckStatus() == Board::InCheck;
Board_State save_state(board);
// Try to get a fast cutoff using a "null move". Skip if the side
// to move is in check or if material balance is low enough that
// zugzwang is a possibility.
if (null_depth && !in_pv && !in_check && !IsNull(last_move[ply-1]) &&
(board.getMaterial(board.Side()).material_level() >= 2) &&
(board.getMaterial(board.OppositeSide()).material_level() >= 1))
{
last_move[ply] = NullMove;
board.DoMove(NullMove);
#ifdef _TRACE
indent(ply);
cout << "trying " << ply << ". " << "(null)" << endl;
#endif
int nu_depth = depth-null_depth-DEPTH_INCREMENT;
int nscore;
if (nu_depth > DEPTH_INCREMENT)
nscore = -move_search(board, -beta, -alpha,
ply+1, nu_depth, in_pv,
terminate);
else if (nu_depth >= 0)
nscore = -move_search1(board, -beta, -alpha,
ply+1, nu_depth, in_pv,
terminate);
else
nscore = -quiesce(board, -beta, -alpha,
ply+1, 0);
#ifdef _TRACE
indent(ply);
cout << ply << ". " << "(null)" << ' ' << nscore << endl;
#endif
board.UndoMove(NullMove,save_state);
if (terminate)
{
return alpha;
}
else if (nscore >= beta) // cutoff
{
#ifdef _TRACE
indent(ply);
cout << "**CUTOFF**" << endl;
#endif
score = nscore;
goto search_end;
}
if (nscore < 100-Constants::BIG)
threat = THREAT_EXTENSION;
}
// Use "internal iterative deepening" to get an initial move to try if
// there is no hash move .. an idea from Crafty. Note that we do
// not try this if we have a hash table entry and no hash move, on
// the theory that we tried it before and didn't get a move.
int dscore;
if (IsNull(hash_move) &&
depth >= 2*DEPTH_INCREMENT &&
(!hash_entry || !hash_entry->deep_flag()))
{
int d = depth >= 3*DEPTH_INCREMENT ? depth-3*DEPTH_INCREMENT :
depth-2*DEPTH_INCREMENT;
#ifdef _TRACE
indent(ply); cout << "== deepening, depth = " << d
<< endl;
#endif
dscore = move_search(board,alpha,beta,ply,d,in_pv,
terminate);
if (terminate)
{
return alpha;
}
if (dscore <= alpha && !IsNull(hash_move))
{
dscore = move_search(board,-Constants::BIG,beta,
ply,d,in_pv,terminate);
if (terminate)
{
return alpha;
}
}
if (IsNull(best[ply])) // don't try this again
deepFlag = TRUE;
#ifdef _TRACE
indent(ply); cout << "== deepening done.";
#endif
hash_move = best[ply];
#ifdef _TRACE
if (!IsNull(hash_move))
{
indent(ply); cout << " hash_move = "
<< MoveImage(hash_move);
}
cout << endl;
#endif
}
{
BOOL generated_moves = FALSE;
Move *moves = moves_generated[ply];
Move_Generator mg(board, ply, hash_move);
int top = -1;
if (IsNull(hash_move))
{
move_count = mg.Generate_Moves(moves);
num_moves += move_count;
Move_Ordering::order_moves(board, moves, move_count, ply,
hash_move,top);
generated_moves = TRUE;
forced = (move_count == 1);
}
else
{
// Delay generating the moves, use the hash move 1st.
// If it causes cutoff, we never need to do full move generation.
move_count = 1;
moves[0] = hash_move;
}
int try_score;
//
// Do the principal variation
//
while (move_index < move_count)
{
if (move_index == top)
Move_Ordering::order_moves2(board,moves,top,move_count);
Move rmove = moves[move_index++];
#ifdef _TRACE
indent(ply);
cout << "trying " << ply << ". " << MoveImage(rmove) << endl;
#endif
last_move[ply] = rmove;
board.DoMove(rmove);
extend = threat + calc_extensions(board,ply,depth,
board.CheckStatus() ==
Board::InCheck,forced);
if (extend > DEPTH_INCREMENT) extend = DEPTH_INCREMENT;
if (depth+extend-DEPTH_INCREMENT > DEPTH_INCREMENT)
{
try_score = -move_search(board, -beta, -alpha,
ply+1, depth+extend-DEPTH_INCREMENT, in_pv,
terminate);
}
else if (depth+extend-DEPTH_INCREMENT >= 0)
{
try_score = -move_search1(board, -beta, -alpha,
ply+1, depth+extend-DEPTH_INCREMENT, in_pv,
terminate);
}
else
try_score = -quiesce(board,-beta,-alpha,ply+1,0);
board.UndoMove(rmove,save_state);
if (terminate)
{
return alpha;
}
#ifdef _TRACE
indent(ply);
cout << ply << ". " << MoveImage(rmove) << ' ';
cout << try_score << " (pv)" << endl;
#endif
if (try_score != Illegal)
{
num_try++;
if (try_score > alpha)
{
score = try_score;
best_move = rmove;
if (try_score >= beta)
{
goto beta_cutoff;
}
best[ply] = rmove;
alpha = try_score;
}
if (try_score >= Constants::BIG-1-ply) goto beta_cutoff;
break;
}
if (!generated_moves)
{
move_count = mg.Generate_Moves(moves);
num_moves += move_count;
Move_Ordering::order_moves(board, moves, move_count, ply,
hash_move,top);
move_index = 1; // start at 1 cause we already did the first move
generated_moves = TRUE;
}
}
if (score >= beta || terminate) goto beta_cutoff;
// Principal variation done.
// If num_try == 0, there are no legal moves - means checkmate
// or stalemate.
// If the p.v. score is outside the alpha-beta window, we
// have set the window wrong and must re-search.
// Otherwise, we proceed to try the non-p.v. moves.
//
if (num_try > 0)
{
in_pv = FALSE;
// Generate the moves if we haven't done so already:
if (!generated_moves)
{
move_count = mg.Generate_Moves(moves);
num_moves += move_count;
Move_Ordering::order_moves(board, moves, move_count, ply,
hash_move,top);
move_index = 1; // start at 1 cause we already did the p.v.
generated_moves = TRUE;
}
while (move_index < move_count)
{
int newbeta = alpha+1;
if (move_index == top)
Move_Ordering::order_moves2(board,moves,top,move_count);
Move rmove = moves[move_index++];
#ifdef _TRACE
indent(ply);
cout << "trying " << ply << ". " << MoveImage(rmove) << endl;
#endif
last_move[ply] = rmove;
board.DoMove(rmove);
extend = threat + calc_extensions(board,ply,depth,
board.CheckStatus() ==
Board::InCheck,forced);
if (extend > DEPTH_INCREMENT) extend = DEPTH_INCREMENT;
if (depth+extend-DEPTH_INCREMENT > DEPTH_INCREMENT)
{
try_score = -move_search(board, -newbeta, -alpha,
ply+1, depth+extend-DEPTH_INCREMENT,
in_pv,
terminate);
}
else if (depth+extend-DEPTH_INCREMENT >= 0)
{
try_score = -move_search1(board, -newbeta, -alpha,
ply+1, depth+extend-DEPTH_INCREMENT,
in_pv,
terminate);
}
else
try_score = -quiesce(board, -newbeta, -alpha,
ply+1, 0);
if (terminate)
{
board.UndoMove(rmove,save_state);
score = alpha;
goto update_pv;
}
if (try_score == Illegal)
{
board.UndoMove(rmove,save_state);
continue;
}
#ifdef _TRACE
else
{
indent(ply);
cout << ply << ". " << MoveImage(rmove) << ' ';
cout << try_score;
cout << endl;
}
#endif
num_try++;
if ((try_score > alpha) && (try_score < beta))
{
// We failed to get a cutoff and must re-search
#ifdef _TRACE
indent(ply); cout << "window = [" << alpha << "," << beta
<< "]" << endl;
indent(ply); cout << "score = " << try_score << " - no cutoff,
researching .." << endl;
#endif
if (depth+extend-DEPTH_INCREMENT > DEPTH_INCREMENT)
try_score=-move_search(board,
-beta,-alpha,ply+1,depth+extend-DEPTH_INCREMENT,in_pv,terminate);
else if (depth+extend-DEPTH_INCREMENT >= 0)
try_score=-move_search1(board,
-beta,-alpha,ply+1,depth+extend-DEPTH_INCREMENT,in_pv,terminate);
else
{
try_score = -quiesce(board, -beta, -alpha,
ply+1, 0);
}
#ifdef _TRACE
indent(ply);
cout << ply << ". " << MoveImage(rmove) << ' ';
cout << try_score;
cout << endl;
#endif
}
board.UndoMove(rmove,save_state);
if (terminate)
{
score = alpha;
goto update_pv;
}
if (try_score != Illegal)
{
if (try_score > alpha)
{
score = try_score;
best_move = rmove;
if (score >= beta)
goto beta_cutoff;
best[ply] = rmove;
alpha = try_score;
if (score >= Constants::BIG-1-ply)
goto beta_cutoff; // found a mate
}
}
}
}
}
beta_cutoff: ;
#ifdef _TRACE
if (score >= beta)
{
indent(ply);
cout << "**CUTOFF**" << endl;
}
#endif
if (num_try == 0)
{
// no moves were tried
if (in_check)
{
if (move_count == 0) // mate
{
#ifdef _TRACE
indent(ply); cout << "mate" << endl;
#endif
return -(Constants::BIG - ply);
}
else
{
// We generated some moves, and some were legal,
// but we skipped them all.
score = evalu8(board,alpha,beta,ply);
}
}
else // stalemate
{
#ifdef _TRACE
indent(ply); cout << "stalemate!" << endl;
#endif
score = draw_score(board);
goto update_pv; // skip the hash insert
}
}
else if (num_try > 0)
{
if (score >= beta)
{
// If the last move caused cutoff, and was not a capture,
// save it as a "killer" move:
if (Capture(last_move[ply]) == EmptyPiece &&
PromoteTo(last_move[ply]) == InvalidPiece)
Move_Ordering::set_killer(board,last_move[ply], ply, depth);
Move_Ordering::update_history(board,last_move[ply],depth);
}
}
search_end:
// don't insert into the hash table if we are terminating - we may
// not have an accurate score.
if (use_hash_table && !terminate)
{
if (best_move == NullMove) best_move = hash_move;
// store the position in the hash table, if there's room
int value = score;
Position_Info::ValueType val_type;
// Adjust mate scores to reflect current ply. But only
// if the score is in bounds.
if (value > initial_alpha && value < beta)
{
if (value < -Constants::BIG+100)
{
value -= ply;
}
else if (value > Constants::BIG-100)
{
value += ply;
}
}
#ifdef _TRACE
char typeChar;
#endif
if (value <= initial_alpha)
{
val_type = Position_Info::UpperBound;
#ifdef _TRACE
typeChar = 'U';
#endif
// We don't have a "best" move, because all moves
// caused alpha cutoff. But if there was a hash
// move or an initial move produced by internal
// interative deepening, save it in the hash table
// so it will be tried first next time around.
best_move = hash_move;
}
else if (value >= beta)
{
val_type = Position_Info::LowerBound;
#ifdef _TRACE
typeChar = 'L';
#endif
}
else
{
val_type = Position_Info::Valid;
#ifdef _TRACE
typeChar = 'E';
#endif
}
#ifdef _TRACE
indent(ply);
cout << "storing " << "type = " << typeChar <<
" depth = " << depth << " value = " << value <<
" move = " << MoveImage(best_move) << endl;
#endif
Position_Info new_pos(board, depth,
age,
val_type, forced,
in_check,
rep_count, value,
best_move);
new_pos.set_deep_flag(deepFlag);
switch (storeHash(new_pos.hash_code(),new_pos))
{
case 0: hash_inserts++; break;
case 1: hash_replaces++; break;
case 2: hash_inserts_failed++; break;
default: break;
}
}
update_pv:
if (initial_alpha != alpha && score < beta)
{
if (num_try == 0)
pv_length[ply] = 0;
else
{
UPDATE_PV(best[ply],ply);
Move_Ordering::update_history(board,best[ply],depth);
}
}
ASSERT(score >= -Constants::BIG && score <= Constants::BIG);
return score;
}
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.