Author: Dann Corbit
Date: 18:28:30 01/27/04
Go up one level in this thread
On January 27, 2004 at 21:20:00, Dann Corbit wrote:
>On January 27, 2004 at 20:50:25, Russell Reagan wrote:
>
>>On January 27, 2004 at 15:42:27, Dann Corbit wrote:
>>
>>>>> /* ----------==== INTERNAL ITERATIVE DEEPENING ====----------- */
>>>>>
>>>>> /* If we're not doing a NULL move and we don't have a hash move and we're
>>>>> * at least 3 ply away from the quiescence search, then try to get a good
>>>>> * guess for the best move by doing a shallower search from here. */
>>>>> if (depth >= 3 && !do_null) {
>>>>> w = search(on_move, ply, depth-2, alpha, beta, do_null, 1);
>>>>> /* Re-search properly if the previous search failed low, so that we
>>>>> * know we're getting a good move, not just the move with the highest
>>>>> * upper bound (which is essentially random and depends on the search
>>>>> * order.) */
>>>>> if (w <= alpha)
>>>>> w = search(on_move, ply, depth-2, -32500, alpha+1, do_null, 1);
>>>>> }
>>
>>>Because it is used for move ordering, and because the depth is 2 plies below the
>>>current search depth, it is a sure win. The cost is 1/400th of a full search,
>>>and the win is a good guess for the pv node.
>>>
>>>At least when I tested it in Beowulf it worked well. But I did not try it both
>>>ways in Olithink.
>>
>>Hi Dann,
>>
>>I have a few questions about this code.
>>
>>The first IID search that you are doing (with alpha and beta as bounds) is
>>considered an aspiration search, correct?
>>
>>If that is correct, then I have another question. I thought that if an
>>aspiration search failed, then you couldn't reliably use the score that was
>>returned as you are doing by re-searching with (-32500, alpha+1). Bruce writes
>>about this problem on his webpage (scroll down to the part about search
>>instability in aspiration searches). The code you posted looks equivalent to the
>>code that he says will cause bad search instability.
>>
>>http://www.brucemo.com/compchess/programming/aspiration.htm
>
>It's not the same thing. The aspiration search is in a loop. This only checks
>the root at two plies less than the main search.
>
>The entire purpose is to find a pretty good choice for the pv node if we don't
>have a guess yet.
>
>In other words:
>No data in the hash table? Then compute a shallower answer.
>
>It is two plies shallower than the main search. Even if your branching factor
>is only 2, it is still 1/4 of the effort of a full search depth. If your
>branching facter were 6, it would be 1/36 of the effort. And chances are good
>we have already examined some side branches in the sub-tree, since we are
>already deeper than the depth we are requesting.
Ed Schroder calls it the "unsorted tree" problem.
Look here:
http://members.home.nl/matador/chess840.htm#MOVE%20ORDERING
For section "Move Ordering in REBEL (3)"
Colin has a nice explanation here:
http://www.chessbrain.net/beowulf/theory.html#iid
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.