Author: Dann Corbit
Date: 16:52:32 09/10/02
Go up one level in this thread
On September 10, 2002 at 19:24:38, martin fierz wrote: >On September 10, 2002 at 18:39:40, Dann Corbit wrote: > >>On September 10, 2002 at 18:25:25, Dann Corbit wrote: >> >>>On September 10, 2002 at 18:13:51, Gian-Carlo Pascutto wrote: >>> >>>>On September 10, 2002 at 18:12:01, Dann Corbit wrote: >>>> >>>> >>>>>Suppose that we perform a binary search >>>> >>>>I'm talking about MTD(n,f). It does *not* do that. >>> >>>No it does not. But it is similar. And about the same speed (within a small >>>constant factor). >> >>Here is what I originally said: >>"The MTD(f) algorithm basically does a binary search between two bounds (on >>average -- it might be faster or slower in individual cases)." >> >>Now, that is not an accurate description - I must admit. >> >>What I should have said is that MTD(f) does a heuristic search based on >>estimates which gradually narrows the interval of possible solution. It is >>approximately of the same efficiency as a binary search, but there is no >>relationship between them. >> >>Better? >>;-) > >i don't think so. in MTD, if the true eval is 1 and you start out with a guess >of 0 and your evaluation grain is 0.01, it is possible that you search the value >sequence 0.01, 0.02,0.03,...0.98,0.99,1. that is, MTD needs N=100 steps in the >worst case for this example. a binary search needs log_2 (100) for such an >example. MTD in the worst case is linear in N, binary search is always log(N). >big differenc IMO. > >it's another question how realistic that worst-case scenario is... In real life, it looks a lot like a binary search with the first guess very near the answer and the order of searching reversed. The first few trials of the binary search will be far from the answer. But for a long time, the search will labor very near the correct answer. Just like MTD(f). Only backwards. From some trials, it seems that MTD(f) is slightly faster than binary search, on average. Therefore, I make a silly, wild guess that they take about the same number of comparisons. In real life. If MTD(f) were linear [or linear behavior happened more than once in a blue moon], then PostModernist would not score nearly so well, I think. Theoretically, they are very different. In practice, there is very little difference. Even in the interval of effort.
This page took 0.11 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.