Author: Tord Romstad
Date: 03:14:39 01/21/04
Go up one level in this thread
On January 20, 2004 at 21:18:25, Dann Corbit wrote: >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. B* should also be an exception, I guess? >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). This is only true for proof number search. Conspiracy number search is not win/loss/draw-only. A few years back, Ulf Lorenz even used it as his main search algorithm in a reasonably strong chess program, IIRC. >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. For MTD type algorithms, Aske Plaat's papers are a good place to start: http://www.cs.vu.nl/~aske/pubs.html PN search and similar algorithms are explained in detail in the PhD thesises of Viktor Allis and Dennis Breuker. For some of the other algorithms mentioned, there are some nice (though mostly old) papers to be found at: http://digilander.libero.it/gargamellachess/papers.htm Tord
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.