Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Robert Hyatt

Date: 10:44:16 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.
>
>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.


One issue with progressive bounds is to "bounce" _over_ the true value.
Searching from one side is faster than searching from the other, due to simple
math.  IE I tried several approaches that "died" until I started thinking about
what bouncing over the true score multiple times was doing to the shape of the
tree...



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