Computer Chess Club Archives




Subject: Re: Couple of chess programming questions

Author: Robert Hyatt

Date: 16:59:49 09/10/02

Go up one level in this thread

On September 10, 2002 at 16:58:01, Vincent Diepeveen wrote:

>On September 10, 2002 at 15:54:09, Dann Corbit wrote:
>>On September 10, 2002 at 15:48:40, Vincent Diepeveen wrote:
>>>On September 10, 2002 at 13:11:02, Dann Corbit wrote:
>>>>On September 10, 2002 at 12:07:37, Vincent Diepeveen wrote:
>>>>>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>>>>>>is something of a magic bullet.  But I note it seems that more programs don't
>>>>>>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>>>>>>doesn't say?
>>>>>There is nothing wrong with it. However a softwareprogram must have certain
>>>>>conditions to let it work well (in hardware other issues play a role)
>>>>>  a) it must be a static evaluation with a small granularity;
>>>>>     if pawn=32 it will work great, if pawn=1000 like in DIEP it won't
>>>>>     work at all, other things aren't interesting then.
>>>>I have found this to be true also with experiments, and the reason is obvious.
>>>>The MTD(f) algorithm basically does a binary search between two bounds (on
>>>>average -- it might be faster or slower in individual cases).  If the interval
>>>>varies from 3276700 to -327600 you have between 22 and 23 searches to resolve
>>>>it.  If the interval varies from  3276 to -3276 you have between 12 and 13
>>>>searches to resolve it.
>>>perhaps it is good to clarify one thing. As soon as a MTD search
>>>needs to use a binary form of search to get from value A to B, then
>>>mtd will fail of course.
>>>the advantage of mtd is that if you have a bound search at 0.01 which says:
>>>"it's more than 0.01" then you try 0.02. In this way you need only a
>>>few minimal windows to get from 0.01 to 0.03
>>>The statement of Rudolf is very clearly: "such minimal windows are
>>>very cheap", and looking to SOS i can only agree with him.
>>>A major problem is like bob says if you have a 0.3 difference.
>>>even with pawn = 100 and 0.3 being 30, that means you need 30 researches.
>>>If you jump binary, then the only advantage which MTD offers is gone directly.
>>>So going from 1000 to 1300 in DIEP that's 300 researches.
>>I think even worst case it won't do more than log2(interval) searches.  I
>>suppose it is possible for each search to refine the interval by only 1 unit,
>>but it seems incredibly improbable.
>>I would expect a window of 300 to take about 8 searches to resolve, on average.
>>Perhaps you tested with some pathological positions?  I have not seen behavior
>>that bad, but maybe I have not looked at the worst cases.
>The problem is you don't know in advance that it's going to get up 0.300
>And doing a search at 0.001 first then 0.002 that's way cheaper
>than doing 0.001 first then 0.250. The problem of doing 2 searches
>of 0.001 and then 0.250 or something, is that this second search
>is just as expensive as a research of PVS is doing, whereas a search
>of 0.002 after 0.001 is very cheap.
>I made myself clear?
>Best regards,

First, I think you should search _down_ and not _up_.  Fail lows are cheaper
than fail highs, on average, because fail lows search 1 move at ply=2, while
fail highs search every move at ply=2...  Depending on whether it ends at an
even or odd ply, they can be equivalent, or fail low will be significantly

Also, I don't see why it is cheaper to first search X,X+1, and then X+1,X+2
then it is to search X+200,X+201.  In fact, I could see where it would be
better since getting _above_ the true score quickly is an advantage.  The
hash scores for X,X+1 won't help the X+1,X+2 search...

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