Author: Tord Romstad
Date: 10:57:28 11/03/03
Go up one level in this thread
On November 03, 2003 at 13:13:31, Mathieu Pagé wrote:
>Hi,
>
>I'm know implementing iterative deepening and i've got to the point where I must
>re-order move between iteration according to there result from the last search.
I don't see why you would need to re-order the moves -- you just postpone
the ordering of the moves until after the reduced depth search is finished.
The following is an outline of how it looks in my engine (hash cuttoffs,
null move search, storing information to the hash table and other
uninteresting stuff removed for brevity):
int search(int gamma, int depth) {
int best_score, value;
move_t *move, *best_move;
hashentry_t *hashentry;
if(depth < PLY) return qsearch(gamma, depth);
hashentry = get_hash();
/* If the position was not found in the hash table and the remaining */
/* depth is big, do internal iterative deepening. */
if(hashentry == NULL && depth >= 5*PLY) {
search(gamma, depth-PLY);
hashentry = get_hash(); }
/* Generate moves and assign move ordering scores */
generate_moves();
score_moves();
best_score = -INFINITY;
for(move = pick_move(); move != NULL; move = pick_move()) {
make_move(move);
value = -search(-gamma+1, depth-PLY);
unmake_move(move);
if(value > best_score) {
best_score = value; best_move = move; }
if(best_score >= gamma) break; }
return best_score; }
>The question is how should i sort them. Do I, simply, have to sort them with a
>standard algorithm like quicksort (that seem to me that will not be so quick :)
I think sorting the whole move list is not a good idea, because you usually
will get a cuttoff at the first move searched. It seems more efficient
to just loop through the move list and pick the move with the highest score.
This is what I do in the pick_move() function called in the code fragment
above.
Tord
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.