Author: Robert Hyatt
Date: 11:40:24 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. This is important. Failing on the "other side" hurts. We want to do that _once_. Think about the math. If you are on the low side, and fail high, that means you search every node at ply=2, which is expensive, and every node there fails low. If you are on the high side, and fail low, you only have to search one node at ply=2 to prove that the move at ply=1 is bad, and that is more efficient. if you bounce "over" the true score, you bounce into a region you don't want to be in until you are forced to get there on the last search, because _one_ must in fact fail high as you reach the bounds real_value-1, real_value for what will be the final search. I tried the binary trick and could not understand why it was producing such enormous trees until I stopped to think about it one night. The idea still has merit, just so you keep the estimated bounds on the high side of the true value so that you always fail low. Of course, as you get closer, it is very tempting to "jump over"... > >You're thinking of NegaC*, which keeps bisecting the intervals. > >-- >GCP
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.