Author: Dann Corbit
Date: 12:35:48 09/10/02
Go up one level in this thread
On September 10, 2002 at 14:19:24, Gian-Carlo Pascutto wrote: >On September 10, 2002 at 13:11:02, Dann Corbit wrote: > >>The MTD(f) algorithm basically does a binary search between two bounds (on >>average -- it might be faster or slower in individual cases). > >MTD(n,f) _as descibred by Plaat_ does not do a binary search. > >It will take a first guess, and then always fail in the same >direction till it converges. Normally, assuming your first guess is a very good one. The idea is still roughly the same. Let's suppose that the first guess is exactly right -- then the initial second guess (normally negative infinity) will define the other end of the interval. In other words, we have (by a perfect guess) cut the interval in half. Now, our second search will use the next move in the list and replace one of the two bounds (lower or upper) with the new bound. Chances are good that the new estimate will be better than 1/2 of the interval, so we will get some savings. But will subsequent searches continue to do better than a bisection? The time seems to be about the same as the NegaC* search (a small constant factor better -- caused by the initial guess for the search?). I don't think the efficiency is better than a binary search except for a small constant factor. But maybe it depends on some other factors like what sort of evaluation you hook it up to. One thing is sure, that MTD(f) is extremely sensitive to the resolution of your evaluation function. If you use long double precision or 64 bit integers for the result, then it will take a horrible amount of time to converge on the correct answer. >You're thinking of NegaC*, which keeps bisecting the intervals. Which is a minor modification of the same framework. I think that MTD(f) is something like a "heuristic estimate" approximation of a binary search, but it won't do much better. On the other hand, if you could do supremely deep searches or somehow have a fairly accurate estimate of (-1=loss,0=draw,1=win) for your evaluation function, then MTD(f) will be nearly ideal.
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.