Author: Robert Hyatt
Date: 07:41:48 01/10/99
Go up one level in this thread
On January 10, 1999 at 02:18:42, Larry Griffiths wrote: >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? > >Steve, > >I used Iterative Deepening for time control. My program keeps increaseing >its max depth and starting another search as long as time remains. >max depth and start another search. > >The other reason I use it is to increase the efficiency of the alpha-beta >search. The principle variation of the last iteration is used as a >"Killer heuristic". The moves for the next iteration are ordered >based on the previous iteration. This tends to increase the number of >alpha-beta cutoffs. this is the wrong type of "iterative deepening". What I do in Crafty is to do searches from 1 thru N. However, suppose that when I search depth=10, I get a fail high on a new move, but don't get a PV because of the hash table, or suppose the PV is simply cut short because the hash table gives me a result that prevents searching that part of the tree. When I do the depth=11 search, and I reach the position where I have no 'pv' move to try (I save the PV in the hash after I finish an iteration so that the next search [which always tries the hash table move first] will follow the pv for good ordering) I have a problem and my tree is going to explode a bit due to bad move ordering. I find it faster, at this position where I am searching the original PV on a new iteration, to do internal iterative deepening. Which means that I just do, from this position, an "iterated" search to get a good first move to try here, but I do this _inside_ the tree, sort of like an iterated search inside an iterated search. In the above case, this speeds me up by about 10% on average. In positions where there is no fail high, or no short PV, or the PV isn't changing somewhere along the path, then this doesn't get executed and has no effect...
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.