Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Dann Corbit

Date: 11:07:01 09/10/02

Go up one level in this thread


On September 10, 2002 at 13:44:16, Robert Hyatt wrote:
>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...

One partial solution is to use a ceil() type idea for the upper bound and a
floor() type idea for the lower bound {perhaps even with a small fuzz window}.

But I still think PVS wins, in general.  At least I have not figured out how to
make MTD(f) work as well.

I do have a notion that if you have enough data you can improve the search a
great deal.  MTD(f) is very sensitive to the initial guess and works best if you
guess the true eval accurately.  However, even a perfect guess only halves the
interval.  If you have a lot of data (perhaps by precomutation that has been
stored in a database) you could search a narrow window around a central guess,
and then switch to PVS when you run out of data.

Suppose (for instance) that you have a 9 ply search for the position in question
and you want to search to 14 plies.  You use your initial estimate (let's say it
is +40 centipawns) and then your window is one full piece of 300 centipawns.  So
you set the intial bounds at +190, -110 and search that interval.  Most of the
time, the true value will be within a window of that size, and you will have
saved a lot of time.  Only 8 searches will be needed if you have a resolution of
1/100 pawn.  The deeper your inital search data is, the narrower your window can
be.



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.