Author: Dann Corbit
Date: 10:11:02 09/10/02
Go up one level in this thread
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.
This page took 0.01 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.