Author: martin fierz
Date: 16:24:38 09/10/02
Go up one level in this thread
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... aloha martin
This page took 0.04 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.