Author: Tord Romstad
Date: 23:54:15 02/23/05
Go up one level in this thread
On February 24, 2005 at 01:20:26, Scott Gasch wrote:
>I'm positive. The reason it is so high, I suspect, is that I am tagging moves
>in qsearch as checking... which is a criteria for whether they are searched or
>not. This is a big overhead. I don't know anything about your engine but I'd
>be interested in knowing if you are tagging qsearch moves as you generate them
>and still see such a low overhead from your check detection code?
No, I don't tag qsearch moves as checks when I generate them. I once did, but
I am now convinced that it is a bad idea. The point is that you do lots of
unnecessary work. At almost 50% of all qsearch nodes, you will only search
a single move (because the first move searched causes a beta cutoff). Knowing
which of the remaining moves are checks is not very interesting.
I guess there are also some qsearch moves you always search, even if they are
not checks. For instance, a winning capture where the value of the captured
piece is sufficiently big to bring the score above alpha. For such a move,
it is not very important to know whether the move is a check. You are going
to search it anyway.
Therefore, it makes sense to do the check detection as late as possible.
In my program, I don't even search checks at all qsearch nodes (I do it
at the first ply of the qsearch, but very rarely at deeper plies). I
call my is_check() directly before each move is made, and only if the
move is a candidate to be futility pruned.
In simplified pseudo code, my qsearch looks approximately like this:
int qsearch(int alpha, int beta, int depth) {
int value;
move_t move;
BOOL search_checks;
value = evaluate();
if(value >= beta) return value;
if(value > alpha) alpha = value;
search_checks = should_search_checks_at_this_node();
generate_captures_and_promotions();
order_moves();
while((move = pick_move())) {
if(futile(move) && (!search_checks || !is_check(move))) continue;
if(!is_legal(move)) continue;
make_move(move);
value = -qsearch(-beta, -alpha, depth-1);
unmake_move(move);
if(value >= beta) return value;
if(value > alpha) alpha = value;
}
if(search_checks()) {
generate_non_capturing_checks();
order_moves();
while((move = pick_move())) {
if(!is_legal(move)) continue;
make_move(move);
value = -qsearch(-beta, -alpha, depth-1);
unmake_move(move);
if(value >= beta) return value;
if(value > alpha) alpha = value;
}
}
return alpha;
}
The full code can be found here:
http://www.math.uio.no/~romstad/glaurung/glaurung.html
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.