Author: Andrew Williams
Date: 12:24:53 04/14/04
Go up one level in this thread
On April 14, 2004 at 14:13:04, Dann Corbit wrote: >On April 14, 2004 at 14:09:04, Bo Persson wrote: > >>On April 14, 2004 at 13:47:06, Dann Corbit wrote: >> >>>On April 14, 2004 at 13:33:38, Robert Hyatt wrote: >>> >>>>On April 14, 2004 at 03:30:22, Dann Corbit wrote: >>>> >>>>>I decided to toss an MTD(f) search into TSCP, and I've got something wrong, but >>>>>I can't quite see what it is. >>>> >>>>There is a lot more to do. >>>> >>>>1. you need to modify the hash table to store 2 bounds, not 1. >>> >>>That was not done yet. >> >>But not too hard! >> >>> >>>>2. the search must be fail-soft. TSCP isn't. >>> >>>I had already done that. >>> >>>>3. PV has to be yanked from the hash table and that makes it flakey at times as >>>>has been discussed many times. There is another way to get the PV, but it is a >>>>special case solution only for mtd... >>> >>>Tord showed a very nice way to do that with a clever "hash only" update. >>> >>>>4. the convergence has to be accelerated. IE on a fail high searching v and >>>>v+1 won't cut it. >> >>I can supply that part, learned from CCC a couple of years ago of course. >> >> // Calculate next gamma and Step >> >> if (gamma < Beta) >> { >> GlobalUpperBound = gamma; >> gamma = max(gamma - Step, GlobalLowerBound + 1); >> SteppedDown = true; >> } >> else >> { >> GlobalLowerBound = gamma; >> gamma = min(gamma + Step, GlobalUpperBound - 1); >> SteppedUp = true; >> } >> >> if (SteppedUp & SteppedDown) >> Step /= 2; >> else >> if (Step < (GlobalUpperBound - GlobalLowerBound) / 2) >> Step *= 2; >> >> >>Here gamma is your f. The idea is to accellerate the stepping, until you have >>over stepped the score twice, once in each direction. Then you have an >>acceptable bound, and can start to zoom in, using smaller and smaller steps as >>you get closer and closer. >> >>The GlobalUpperBound and GlobalLowerBound should really be global. If you use >>lazy evaluations those are the bounds to use there, not the local alpha/beta >>which are always just 1 point apart. > >I have lots of ideas along these lines. > >I thought of using an MTD(f) like driver, but in MTD(bi) format, so that I will >binary search. > When I first started with MTD (aeons ago now), i tried MTD(bi) and it just didn't work. It looks like it should, but doesn't. I then switched to using MTD(bi) after something similar to what Bo posted above. That didn't work either. YMMV of course. >I thought of doing a parabolic fit of the last few guesses and extrapolating the >next guess. > >I thought of doing an aspiration window around the last bound and MTD(bi) search >of that. > >Some others besides. But I want to understand the algorithm through and through >before I venture into that land. > >I got reinterested in MTD(f) because Uri mentioned that he would like to be able >to experiment with it in his search. > >In case he wants me to give him a hand, I had better understand it well myself. It's good fun playing with MTD, but make sure your hash-table works properly first! Andrew
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.