Author: Dann Corbit
Date: 18:18:25 01/20/04
Go up one level in this thread
On January 20, 2004 at 20:47:29, Russell Reagan wrote: >I know about the most popular game tree search algorithms that are used for >computer chess like alpha-beta, PVS, and MTD(f), and I have heard of others like >proof number search, conspiracy search, B*, SSS*, and many others. > >Is there any resource which would have a more or less complete listing of game >tree searching algorithms? One work that covered them all would be nice, but >even something that just listed the names would do. I don't mind doing a little >research. An Aske Plaat paper shows that pretty much all of them (except proof number and conspiracy search) can be formulated as a typical framework. For instance the SSS* with AB+TT, and Weil's NegaC* binary search also easily fits into the framework. I think it is this paper, but I am not sure: http://www.recherche.enac.fr/~alliot/ALGOS_JEU/thesis.ps Proof number and conspiracy search are only for win/loss/draw. You can't use them with an ordinary evaluation function (As far as I know anyway). The notions are simple. You already know the enhancement to alpha-beta where we search the current root node's pm full width, and then do a zero window search on all the other child nodes (PVS). MTD variants use the zero window search idea to create fast bounds. The negaC* is a binary search that uses zero width. And MTD(f) uses the obvious (and clever) initial guess of the best current estimate for the evaluation. They develop a framework that can be used to implement lots of algorithm variations. There are so many articles on this sort of thing, I really don't know which direction to point you in. Probably, your own web search will be fastest.
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.