Author: martin fierz
Date: 17:23:36 09/10/02
Go up one level in this thread
On September 10, 2002 at 19:52:32, Dann Corbit wrote: >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. i'm using MTD myself and it works for me. i just wanted to point out that it can behave badly. it doesnt usually for me :-) aloha martin
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.