Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Vincent Diepeveen

Date: 12:48:40 09/10/02

Go up one level in this thread


On September 10, 2002 at 13:11:02, Dann Corbit wrote:

>On September 10, 2002 at 12:07:37, Vincent Diepeveen wrote:
>[SNIP]
>>>(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.



>Therefore, you have a paradox.  The more accurately you search, the slower
>MTD(f) will become.  I can't see any solution to it, unless you use progressive
>accuracy to quickly narrow the search.  If you went to long double accuracy in
>your evaluation function, it will take a very long time to resolve the search
>with MTD(f), unless you double the accuracy with each iteration.  So for the
>first search, only (ugh) one significant digit is used.  Then two digits of
>accuracy, then 4, etc.



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.