Author: Robert Hyatt
Date: 14:51:11 01/04/99
Go up one level in this thread
On January 04, 1999 at 15:06:35, Steve Maughan wrote: >I have been looking through the source code for Crafty and noticed that the >Search routine used "Internal Iterative Deepening" to get a good move to play at >an internal node. I was puzzled as to the actual benefit of this routine. I >can see that it will return a good move but assume that this is a costly method >for finding a such a move. Does it really speed up the search by that much? >How much? Does "everyone" do it? A couple of points. Note that crafty is based on the PVS search variant of alpha/beta, which means almost 100% of the nodes are searched with an alpha/beta window that is "null" (ie alpha=beta-1 almost everywhere). With that in mind, notice that I only do internal iterative deepening when (a) I am searching a position where alpha != beta-1 (which means this is a branch along the PV somewhere usually), and where I don't have a hash move to give me a good clue about what to try here. On PV nodes, move ordering is absolutely critical, after all, that is why we did the depth D-1 search... to give us a PV to follow in the depth D search. If there is no suggested best move (the PV was cut short by a hash hit on the previous search, for example) I resort to IID as a last-gasp measure to get a good move to search first here. where it really helps is in a position where you fail high but are unable to get the true score. After starting the next iteration you have no clue about which move(s) to search first. IID gives you that clue and makes this not so bad event bearable. In such positions, this is 10% (or more) faster. But it is not done very often, in general...
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.