Author: Dann Corbit
Date: 16:34:43 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;
>}
Here is the search from crafty, simplified a bit:
/*
----------------------------------------------------------
| |
| now set the search time and iteratively call Search() |
| to analyze the position deeper and deeper. note that |
| Search() is called with an alpha/beta window roughly |
| 1/3 of a pawn on either side of the score last |
| returned by search. also, after the first root move |
| is searched, this window is collapsed to n and n+1 |
| (where n is the value for the first root move.) often |
| a better move is found, which causes search to return |
| <beta> as the score. we then relax beta depending on |
| its value: if beta = alpha+1, set beta to alpha+1/3 |
| of a pawn; if beta = alpha+1/3 pawn, then set beta to |
| + infinity. |
| |
----------------------------------------------------------
*/
TimeSet(search_type);
iteration_depth = 1;
if (last_pv.pathd > 1)
iteration_depth = last_pv.pathd + 1;
time_abort = 0;
abort_search = 0;
program_start_time = ReadClock(time_type);
start_time = ReadClock(time_type);
elapsed_start = ReadClock(elapsed);
/*
----------------------------------------------------------
| |
| now install the learned position information in the |
| hash table. |
| |
----------------------------------------------------------
*/
LearnPositionLoad();
/*
----------------------------------------------------------
| |
| set the initial search bounds based on the last search |
| or default values. |
| |
----------------------------------------------------------
*/
tree->pv[0] = last_pv;
if (iteration_depth > 1) {
root_alpha = last_value - 40;
root_value = last_value - 40;
root_beta = last_value + 40;
} else {
root_alpha = -MATE - 1;
root_value = -MATE - 1;
root_beta = MATE + 1;
}
/*
----------------------------------------------------------
| |
| if we are using multiple threads, and they have not |
| been started yet, then start them now as the search |
| is ready to begin. |
| |
----------------------------------------------------------
*/
root_print_ok = 0;
for (; iteration_depth <= 60; iteration_depth++) {
/*
----------------------------------------------------------
| |
| now install the old PV into the hash table so that |
| these moves will be followed first. |
| |
----------------------------------------------------------
*/
twtm = wtm;
for (i = 1; i <= (int) tree->pv[0].pathl; i++) {
tree->pv[i] = tree->pv[i - 1];
if (!LegalMove(tree, i, twtm, tree->pv[i].path[i])) {
break;
}
HashStorePV(tree, i, twtm);
MakeMove(tree, i, tree->pv[0].path[i], twtm);
twtm = ChangeSide(twtm);
}
for (i--; i > 0; i--) {
twtm = ChangeSide(twtm);
UnmakeMove(tree, i, tree->pv[0].path[i], twtm);
}
if (tree->nodes_searched) {
nodes_between_time_checks = nodes_per_second;
nodes_between_time_checks = Min(nodes_between_time_checks,
MAX_TC_NODES);
nodes_between_time_checks = Max(nodes_between_time_checks,
5000);
if (!analyze_mode) {
if (time_limit > 300 && !auto232);
else if (time_limit > 100 || auto232)
nodes_between_time_checks /= 10;
else if (time_limit > 50)
nodes_between_time_checks /= 20;
else
nodes_between_time_checks /= 100;
} else
nodes_between_time_checks = 5000;
}
while (1) {
thread_start_time[0] = ReadClock(cpu);
value = SearchRoot(tree, root_alpha, root_beta, wtm,
iteration_depth * INCPLY + 30);
root_print_ok = tree->nodes_searched > noise_level;
cpu_time_used += ReadClock(cpu) - thread_start_time[0];
if (abort_search || time_abort)
break;
if (value >= root_beta) {
root_moves[0].status |= 2;
root_moves[0].status &= 255 - 128;
if (root_moves[0].status & 1)
root_alpha = -MATE - 1;
else
root_alpha = root_beta - 1;
root_value = root_alpha;
root_beta = MATE + 1;
root_moves[0].nodes = 0;
} else if (value <= root_alpha) {
if (!(root_moves[0].status & 2)) {
root_moves[0].status &= 255 - 128;
root_moves[0].nodes = 0;
root_moves[0].status |= 1;
if (root_moves[0].status & 2)
root_beta = MATE + 1;
root_alpha = -MATE - 1;
root_value = root_alpha;
easy_move = 0;
} else
break;
} else
break;
}
if (root_value > root_alpha && root_value < root_beta)
last_root_value = root_value;
/*
----------------------------------------------------------
| |
| if the search terminated normally, then dump the PV |
| and search statistics (we don't do this if the search |
| aborts because the opponent doesn't make the predicted |
| move...) |
| |
----------------------------------------------------------
*/
twtm = wtm;
end_time = ReadClock(time_type);
do {
sorted = 1;
for (i = 1; i < n_root_moves - 1; i++) {
if (root_moves[i].nodes < root_moves[i + 1].nodes) {
temp = root_moves[i];
root_moves[i] = root_moves[i + 1];
root_moves[i + 1] = temp;
sorted = 0;
}
}
} while (!sorted);
/*
----------------------------------------------------------
| |
| notice if there are multiple moves that are producing |
| large trees. if so, don't search those in parallel by |
| setting the flag to avoid this. |
| |
----------------------------------------------------------
*/
for (i = 0; i < n_root_moves; i++)
root_moves[i].status = 0;
if (root_moves[0].nodes > 1000)
for (i = 0; i < Min(n_root_moves, 4); i++) {
if (root_moves[i].nodes > root_moves[0].nodes / 2)
root_moves[i].status |= 64;
}
for (i = 0; i < n_root_moves; i++)
root_moves[i].nodes = 0;
if (end_time - start_time > 10)
nodes_per_second = tree->nodes_searched * 100 / (BITBOARD)
(end_time - start_time);
else
nodes_per_second = 10000;
if (!time_abort && !abort_search && (root_print_ok ||
correct_count >= early_exit
|| value > MATE - 300 || tree->pv[0].pathh == 2)) {
if (value != -(MATE - 1))
DisplayPV(tree, 5, wtm, end_time - start_time, value,
&tree->pv[0]);
}
root_alpha = value - 40;
root_value = root_alpha;
root_beta = value + 40;
if (iteration_depth > 3 && value > MATE - 300 &&
value >= (MATE - iteration_depth - 1) && value >
last_mate_score)
break;
if ((iteration_depth >= search_depth) && search_depth)
break;
if (time_abort || abort_search)
break;
end_time = ReadClock(time_type) - start_time;
if (thinking && (int) end_time >= time_limit)
break;
if (correct_count >= early_exit)
break;
if (iteration_depth > 3 && TotalPieces <= EGTBlimit && TB_use_ok
&&
EGTB_use && !EGTB_search && EGTBProbe(tree, 1, wtm, &i))
break;
if (search_nodes && tree->nodes_searched > search_nodes)
break;
}
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.