Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Game tree search algorithms

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.05 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.