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.