Author: Tord Romstad
Date: 07:31:37 02/24/05
Go up one level in this thread
On February 24, 2005 at 10:05:33, Scott Gasch wrote:
>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"
As you can see in the pseudo code above, I also have two different move
generators for qsearch: One which generates all captures and promotions,
and one which generates all checks which are neither captures and promotions.
The captures+promotions generator is called at *all* qsearch nodes, and does
not care about checks. The non-capturing checks generator is called only
called at nodes where I want to search checks, and only after all captures
and promotions have been searched without causing a beta cutoffs. This means
that at almost 50% of my "search checks qnodes", I don't have to generate
checks or do any check detection at all.
It seems to me that this is a more efficient way to do it than your approach.
Think about it like this: The moves you want to search at your "don't search
checks qnodes" is probably a subset of the moves you want to search at your
"search checks qnodes". It makes sense to generate and search this
subset first at *all* qnodes, without any check detection. Most often, the
best move will be found in this subset. When all moves in this subset have
been searched, you generate and search the remaining moves, *with* check
detection (assuming that you are at a "search checks qnode", of course).
>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.
Sounds similar to how I do it, except the time when move generation and
check detection is done.
>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...
My program follows a similar pattern, and I do bother with checks in qsearch.
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.