Computer Chess Club Archives




Subject: Re: Couple of chess programming questions

Author: martin fierz

Date: 17:23:36 09/10/02

Go up one level in this thread

On September 10, 2002 at 19:52:32, Dann Corbit wrote:

>On September 10, 2002 at 19:24:38, martin fierz wrote:
>>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.
>>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...
>In real life, it looks a lot like a binary search with the first guess very near
>the answer and the order of searching reversed.
>The first few trials of the binary search will be far from the answer.
>But for a long time, the search will labor very near the correct answer.
>Just like MTD(f).  Only backwards.
>From some trials, it seems that MTD(f) is slightly faster than binary search, on
>average.  Therefore, I make a silly, wild guess that they take about the same
>number of comparisons.  In real life.
>If MTD(f) were linear [or linear behavior happened more than once in a blue
>moon], then PostModernist would not score nearly so well, I think.
>Theoretically, they are very different.  In practice, there is very little
>difference.  Even in the interval of effort.

i'm using MTD myself and it works for me. i just wanted to point out that it can
behave badly. it doesnt usually for me :-)


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.