Computer Chess Club Archives

Messages

Subject: Re: Couple of chess programming questions

Author: martin fierz

Date: 16:24:38 09/10/02

Go up one level in this thread

```On September 10, 2002 at 18:39:40, Dann Corbit wrote:

>On September 10, 2002 at 18:25:25, Dann Corbit wrote:
>
>>On September 10, 2002 at 18:13:51, Gian-Carlo Pascutto wrote:
>>
>>>On September 10, 2002 at 18:12:01, Dann Corbit wrote:
>>>
>>>
>>>>Suppose that we perform a binary search
>>>
>>>I'm talking about MTD(n,f). It does *not* do that.
>>
>>No it does not.  But it is similar.  And about the same speed (within a small
>>constant factor).
>
>Here is what I originally said:
>"The MTD(f) algorithm basically does a binary search between two bounds (on
>average -- it might be faster or slower in individual cases)."
>
>Now, that is not an accurate description - I must admit.
>
>What I should have said is that MTD(f) does a heuristic search based on
>estimates which gradually narrows the interval of possible solution.  It is
>approximately of the same efficiency as a binary search, but there is no
>relationship between them.
>
>Better?
>;-)

i don't think so. in MTD, if the true eval is 1 and you start out with a guess
of 0 and your evaluation grain is 0.01, it is possible that you search the value
sequence 0.01, 0.02,0.03,...0.98,0.99,1. that is, MTD needs N=100 steps in the
worst case for this example. a binary search needs log_2 (100) for such an
example. MTD in the worst case is linear in N, binary search is always log(N).
big differenc IMO.

it's another question how realistic that worst-case scenario is...

aloha
martin

```