Computer Chess Club Archives




Subject: Re: Which Algorithm is considered the best ?

Author: Tim Foden

Date: 09:29:21 08/05/00

Go up one level in this thread

On August 05, 2000 at 11:37:01, Larry Griffiths wrote:

>Which Algorithm is considered the best now-adays.
>NegaScout? MTD? PVS? Others?  I am looking to implement one of the best search
>type algorithms in my program.  I would like to get it into the 2000 rated range
>as this has been my lifetime goal.  Then, maybe install winboard or something so
>it can compete against other programs to get a rating.
>I dont like MTD as it seems to be complex.

It is generally possible, and I would say advisable, to implement the search in
small steps.  Get one version working before moving on to the more complex

Thus the searches you mention above, plus plain A-B search, can be ranked in
order of implementaion:
1) Alpha-Beta
2) PV-search
3) NegaScout
4) MTD(f)

To get from 1) to 2), you need to implement null-window search for non-PV lines.

To get from 2) to 3), you implement the safe forward pruning near the leaves, or
use razoring if you have extensions.

You might want to switch 2) and 3) around.

To get from the 3) to 4) you add the MTD(f) driver on top of the whole thing.

The thing to remember about MTD(f) (if my memory serves me well) is that I think
it requires a fail-soft version of the underlying search.  Fail soft is:  when
you detect a cut-off (value >= beta) you return (value).  Fail hard is you
return (beta).

At some point it would be advisable to implement the Null move heuristic.

All of this is from some hazy memory, so please forgive me if I turn out to be
talking nonsense. :o)

BTW, I don't necessarily think you need the "best" search algorithm.  Just a
good one.  I really don't think MTD(f) is a requirement to get a program that is
2000 (or even 2500) rated.

This page took 0.06 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.