Author: Dann Corbit
Date: 12:54:09 09/10/02
Go up one level in this thread
On September 10, 2002 at 15:48:40, Vincent Diepeveen 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. > >perhaps it is good to clarify one thing. As soon as a MTD search >needs to use a binary form of search to get from value A to B, then >mtd will fail of course. > >the advantage of mtd is that if you have a bound search at 0.01 which says: >"it's more than 0.01" then you try 0.02. In this way you need only a >few minimal windows to get from 0.01 to 0.03 > >The statement of Rudolf is very clearly: "such minimal windows are >very cheap", and looking to SOS i can only agree with him. > >A major problem is like bob says if you have a 0.3 difference. >even with pawn = 100 and 0.3 being 30, that means you need 30 researches. > >If you jump binary, then the only advantage which MTD offers is gone directly. > >So going from 1000 to 1300 in DIEP that's 300 researches. I think even worst case it won't do more than log2(interval) searches. I suppose it is possible for each search to refine the interval by only 1 unit, but it seems incredibly improbable. I would expect a window of 300 to take about 8 searches to resolve, on average. Perhaps you tested with some pathological positions? I have not seen behavior that bad, but maybe I have not looked at the worst cases.
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.