Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Game tree search algorithms

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.