Author: Ed Schröder
Date: 15:37:45 05/31/00
Go up one level in this thread
On May 31, 2000 at 18:20:09, Bas Hamstra wrote:
>On May 31, 2000 at 12:12:42, Ed Schröder wrote:
>
>>On May 30, 2000 at 20:18:24, Robert Hyatt wrote:
>>
>>>On May 30, 2000 at 19:57:00, Tom Kerrigan wrote:
>>>
>>>>Bob has suggested (in a thread below) that quiescence search nodes should
>>>>account for 50% or less of the total nodes searched.
>>>>
>>>>Here's what my code looks like:
>>>>
>>>>int search(int alpha, int beta, int depth)
>>>>{
>>>> if (depth <= 0)
>>>> return qsearch(...);
>>>> ++nodes;
>>>> ...
>>>>}
>>>>
>>>>int qsearch(int alpha, int beta)
>>>>{
>>>> ++nodes;
>>>> ...
>>>>}
>>>
>>>A couple of points need to be clearly defined, because this discussion always
>>>gets way out of hand.
>>>
>>>There are three kinds of nodes in the tree:
>>>
>>>(1) interior nodes. These occur at any ply where depth is > 0. IE these are
>>>standard interior nodes.
>>>
>>>(2) quiescence-frontier nodes. These occur at any ply where depth == 0. IE
>>>you _must search one of these for every node at the previous ply in the tree.
>>>You have no choice aboug getting here, but you have a lot of choice in
>>>
>>>(3) quiescence nodes. These are nodes produced by your making a decision to
>>>search a capture after reaching (2) above. And these are the _only_ thing you
>>>can control.
>>>
>>>I don't count (2) above as a "quiescence node". There is no choice in searching
>>>that node, any more than there is any choice in searching each interior tree
>>>node.
>>>
>>>What can you do to control (3)? Futility testing for one thing. If the current
>>>score is so bad when compared to alpha, that the proposed capture doesn't have a
>>>chance of lifting this score back over alpha, then this capture can be safely
>>>ignored. Ditto if the current score is so far over beta, why try to improve
>>>something that can not be improved?
>>
>>
>>"score with alpha" is a safe thing to do. "score with beta" is tricky tricky.
>>Using "score with beta" you have to exclude cases like "king in check" and
>>"opponent promotion" + a window of 9.00 and even then I get move and score
>>differences which smell badly. Not many but still.... All in all I don't like
>>the "score with beta" idea.
>>
>>Ed
>
>I don't see why "score with alpha" is so much safer. If you put some debug code
>on you can exactly trace where it goes wrong. Especially in the endgame it can
>be tricky. Maybe I do something wrong, but doing it like in Crafty, I measured a
>few times that you hardly search any deeper and lose some accuracy. For some
>strange reason it did solve a few extra test positions.
"Score with alpha" is safe because in QS your main goal (and for some program
that is the ONLY goal) to see if the horizon position is safe. So why go
deeper in QS when the position is (already) safe (as alpha proofs). In Rebel I
have only one exception and that is in the case the move gives a check so QS
has to go deeper.
Ed
>Regards,
>Bas.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>>
>>
>>
>>>If you count q-search nodes as above, (3) can be held to well below 50% of the
>>>total nodes. Just don't factor in (2) since that can not be controlled at all.
>>>
>>>
>>>
>>>>
>>>>With this code, I find it hard to believe that anyone could get a percentage <
>>>>50. Are people doing things differently than me? Is anyone getting more than
>>>>50%?
>>>>
>>>>-Tom
This page took 0.11 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.