Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Robert Hyatt

Date: 11:40:24 09/10/02

Go up one level in this thread


On September 10, 2002 at 14:19:24, Gian-Carlo Pascutto wrote:

>On September 10, 2002 at 13:11:02, Dann Corbit wrote:
>
>>The MTD(f) algorithm basically does a binary search between two bounds (on
>>average -- it might be faster or slower in individual cases).
>
>MTD(n,f) _as descibred by Plaat_ does not do a binary search.
>
>It will take a first guess, and then always fail in the same
>direction till it converges.


This is important.  Failing on the "other side" hurts.  We want to do
that _once_.

Think about the math.

If you are on the low side, and fail high, that means you search every node
at ply=2, which is expensive, and every node there fails low.

If you are on the high side, and fail low, you only have to search one node
at ply=2 to prove that the move at ply=1 is bad, and that is more efficient.

if you bounce "over" the true score, you bounce into a region you don't want
to be in until you are forced to get there on the last search, because _one_
must in fact fail high as you reach the bounds real_value-1, real_value for
what will be the final search.

I tried the binary trick and could not understand why it was producing such
enormous trees until I stopped to think about it one night.  The idea still
has merit, just so you keep the estimated bounds on the high side of the
true value so that you always fail low.  Of course, as you get closer, it
is very tempting to "jump over"...

>
>You're thinking of NegaC*, which keeps bisecting the intervals.
>
>--
>GCP



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