Author: James Swafford
Date: 06:20:17 12/13/01
Go up one level in this thread
On December 13, 2001 at 03:33:07, Wylie Garvin wrote: >On December 12, 2001 at 23:27:58, Russell Reagan wrote: > >>Depth-first search is usually what is used in chess programs (at least all that >>I have seen source for). What are the drawbacks of other search algorithms such >>as breadth-first and best-first that prevent them from being more widely used in >>chess programs? > >speed and space requirements. Keep in mind that since nearly all chess programs >use iterative deepening on their depth first searches, and since chess has a >high branching factor, even with all the pruning techniques (well >= 2 anyway), >this means they are essentially getting a breadth-first search in depth-first >space, O(ply). With selective search not all lines have the same "depth", but >the principle still applies. > I agree with all that except the O(ply) part. I think that implies a linear growth, when in fact it's closer to O(bf^ply). -- James >wylie
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.