Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Dann Corbit

Date: 12:35:48 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.

Normally, assuming your first guess is a very good one.  The idea is still
roughly the same.  Let's suppose that the first guess is exactly right -- then
the initial second guess (normally negative infinity) will define the other end
of the interval.  In other words, we have (by a perfect guess) cut the interval
in half.  Now, our second search will use the next move in the list and replace
one of the two bounds (lower or upper) with the new bound.  Chances are good
that the new estimate will be better than 1/2 of the interval, so we will get
some savings.  But will subsequent searches continue to do better than a
bisection?  The time seems to be about the same as the NegaC* search (a small
constant factor better -- caused by the initial guess for the search?).

I don't think the efficiency is better than a binary search except for a small
constant factor.  But maybe it depends on some other factors like what sort of
evaluation you hook it up to.  One thing is sure, that MTD(f) is extremely
sensitive to the resolution of your evaluation function.  If you use long double
precision or 64 bit integers for the result, then it will take a horrible amount
of time to converge on the correct answer.

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

Which is a minor modification of the same framework.  I think that MTD(f) is
something like a "heuristic estimate" approximation of a binary search, but it
won't do much better.

On the other hand, if you could do supremely deep searches or somehow have a
fairly accurate estimate of (-1=loss,0=draw,1=win) for your evaluation function,
then MTD(f) will be nearly ideal.



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