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.