Author: Scott Gasch
Date: 07:05:33 02/24/05
Go up one level in this thread
On February 24, 2005 at 02:54:15, Tord Romstad wrote:
>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
Good point about extra work. To try to mitigate this I have two generators for
qsearch: one where I care about checks and one where I don't. In the initial
few plies of qsearch I call the one that generates moves and tags them with a
check tag so that when I'm deciding to prune or not I can go ahead and search
under moves like "losing capture that checks" or "random noncapture that checks"
Once the qplies get below a variable threshold I stop caring about checks and
only want to do winning/even captures/promotes. At that point I no longer tag
moves as check at generation time. And there is no leniency given to moves that
look "bad" (i.e. losing material). They are simply pruned.
I re-ran a profile after this thread started and my WouldGiveCheck function is
still #1 as I remembered but the exact overhead number is 6.8%. My program
spends nearly 80% of its time under qsearch and a mere 20% in the main search...
so if your follows a similar pattern and you are not bothering with checks in
qsearch then I'd expect your number to be much lower...
Scott
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.