Author: Dann Corbit
Date: 10:57:57 01/21/04
Go up one level in this thread
On January 21, 2004 at 06:14:39, Tord Romstad wrote: >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 You can find many chess papers here too: ftp://cap.connx.com/chess-papers/
This page took 0.02 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.