Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD(f) (was Re: New(?) search idea.)

Author: Alessandro Damiani

Date: 01:40:19 01/23/98

Go up one level in this thread


I got the same PV problems when I tested MTD(f). So I changed back to
NegaScout.

Now I am still fighting against silly PV moves with NegaScout. This has
to do with my forward-pruning combined with researches:

to avoid that a move leading to a node, which has been cut off by
forward-pruning, gets a PV-move I return a second "infinity"-score (=:M)
in my forward-pruning. M is a bit less than "infinity". So in the parent
node there will be (if not all sons have the score -M) a best move to
store in the hashtable. If the score of the best move is <=alpha it gets
the score alpha.

When a research has to be done this best move will be searched first.
Assume that it is a loosing move. The hashtable tells us it has an upper
bound. Then, if all other moves are cut off by forward-pruning they will
have a score -M, the first (and silly) move stays best. Result: there is
a loosing move in the PV and the minimax-score does not reflect it.

One possibility would be to go back to the old alphabeta. Other ideas?


Ciao

Alessandro




On January 23, 1998 at 01:19:24, Don Dailey wrote:

>Bob,
>
>This is a good post from you.  It does address many of my misgivings
>with MTD(f) and your experiences closly mirror mine.
>
>First of all I didn't mean to imply you were not a performance freak,
>I know in fact that you are.  Also I want to emphasize that I'm not
>critical of you or anyone else who does not use MTD(f).  I can see
>you clearly understand the problems involved and have made an informed
>decision.  I can't even say for sure my decision to use it is right.
>
>We do get a lot of benefit from it so it's hard to throw it away.
>Your point about the PV's cancelling the benefit of the speedup it
>probably not the case, at least for us.  I agree it cancels some
>of the benefit but we do in fact predict a lot of moves.  It just
>really pisses me off that occasionally a really obvious move like
>a recapture does not get predicted and we have lost some free time.
>But most of the time we get these.   A good solution for tournaments
>is to do a short search for prediction and this will always produce
>a good move.  We could do a 9 ply search for instance and stop if
>it exceeds 1/2 second or some such hack.  It's ugly but workable.
>
>I am with you in my distaste for this behavior.  I HATE these ugly
>PV's I cannot trust.  I have yet to see what will happen when I
>implement proper PV's but I'll let you know.  Your note is discouraging!
>
>I realized you clearly knew what you were talking about (as if there
>was any doubt!) when you brought up the issue of lazy evaluation!
>Yes, mtd(f) plays hell with it.   I have always relied heavily on
>lazy evaluation (I call it score fudging) but over the years have
>grown to hate it.  With mtd(f) my experiences with it have been
>awful.  mtd(f) (for those watching) relies heavily on the scores
>returned from each probe.  With lazy evaluation you tend to return
>relaxed scoring information which affects the efficiency of mtd(f)!
>Your nodes per second go up, but the number of nodes needed go up
>to match it!  It really sucks!  There is also some bad side behavior
>if your "fudge margin" is too small AND it crosses the beta boundary.
>For instance you
>interpret (sc - fudge) as a lower bound because it is above beta but
>fudge is too small and it turns out the real situation is that the
>score is in fact and upper bound (below beta!)   Your error can
>propogate to the root and be more than the difference between your
>error and fudge when this happens.  What happens is blunders.
>My solution to this one was to limit the evaluation so that it never
>was greater than FUDGE in either direction.  Another hack.  I
>discovered this one when the error got GREATER as I increased the
>fudge margin until it exactly matched my error and was suddenly
>fixed.  This never happened unless the error "crossed over!"
>
>But now I'm about to commit hearesy.  I know this will generate a
>ton of HATE mail but here goes (my arms now protecting my face):
>I now believe lazy evaluation is problematic at best, incorrect in
>general.  Even without mtd(f), as my evaluation has grown more
>sophisticated I am noticing lots of problems with lazy evaluation.
>I simply have too many big scoring terms now and it's getting harder
>and harder to cascade them.  I used to calculate material and pawn
>structure (looking for square of pawn stuff) and then fudge it.  Then
>try the next largest big scoring thing etc.  But now I have aggressive
>king safety, more aggressive pawn evaluation in general, and much more.
>It's impossible to arrange my code
>such that I can test these in cascading order to take advantage
>of lazy eval.  Too many things depend on other things and I would
>have to use too big a margin to fix it (which decreases its benefit.)
>I end up doing almost all my evaluation to get to all the big scoring
>things.
>
>Even with fudging I get little benefit (I used to get 30% in the
>old days when life was simpler), now get very little, so I'm not
>crying too much over the loss of it.  YES I threw it out.  I feel
>this huge burden being lifted now and have found peace!  I know
>now that my scores are always correct and I don't lose any sleep
>over it!    I am looking into some ways to do really fast evaluation
>and still keep it sophisticated and will share my discoveries (assuming
>I come up with any) with the group.   I'll probably reinvent someone
>elses wheels!
>
>Not to mention the way information is presented.  I always liked
>watching the move list proceed and with MTD(f) this is gone too
>(unless you want to watch it over and over for each probe of each
>iteration!)  It's only a semantic issue but I prefer the normal
>mini-max behavior.
>
>Anyway, all your points are well taken.  MTD(f) is a strange beast
>and I'm not really promoting it.   If anyone wants to try it out
>who hasn't yet, be prepared for a real struggle.   I consider it
>worth the problems and I believe it makes my program stronger.  But
>it's not hard for me to believe it could also be the wrong choice
>for a different program.  If your program relies heavily on score
>fudging it will probably decrease your performance.
>
>
>- Don
>
>
>
>
>
>
>
>On January 22, 1998 at 22:23:36, Robert Hyatt wrote:
>
>>On January 22, 1998 at 21:59:57, Don Dailey wrote:
>>
>>>On January 22, 1998 at 14:28:27, Stuart Cracraft wrote:
>>>
>>>>On January 22, 1998 at 13:33:42, Don Dailey wrote:
>>>>
>>>>>By the way, I use an algorithm called mtd(f) and there is no concept
>>>>>of a "window" in the search itself (just the search driver.)  All
>>>>>searches return quickly and are guaranteed to fail!  In some sense
>>>>>the same moves get searched over and over on the same iteration
>>>>>although the hash table tends to avoid most of this work (except
>>>>>when it is needed to prove a point.)   The search driver is tricky
>>>>>piece of code and the obvious approach is quite bad (don't use a
>>>>>binary search mtd probe strategy!)
>>>>>
>>>>>The thing I hate about mtd is the data returned is so different
>>>>>from a conventional program.  You cannot get a nice list of moves
>>>>>showing progress and the pv appears many times (usually modified)
>>>>>each time.  Even though I have good root move ordering I stopped
>>>>>thinking about it with mtd(f).  Your ideas almost sounded foreign
>>>>>to me because of this!   Massaging my root move list would clearly
>>>>>be a problem for efficiency.   MTD is so good I cannot imagine
>>>>>using anything else though.  I am getting over 15%  speedup over
>>>>>my very best implementation of pvs search (margin on first move,
>>>>>zero width on siblings with research on fail hi's)   I prefer
>>>>>PVS's behavior but cannot ignore the extra performance of MTD(f).
>>>>>
>>>>>The (f) refers to the type of driver used.  I don't strictly use
>>>>>the 'f' driver because I found some enhancements of my own but
>>>>>it's basically mtd(f)
>>>>>
>>>>>- Don
>>>>
>>>>I tried MTD(f) at one point and was impressed as well. Also, I saw
>>>>the tables in Aske Platt's thesis comparing it with other search
>>>>techniques for three strategy games. Those tables show really good
>>>>speedups for chess.
>>>>
>>>>Now, the question. I still have my MTD(f) code but it does not
>>>>record the principal variation.
>>>>
>>>>How did you do it? Please be as specific as you can. Now that my
>>>>transposition table is working much better, I'd like to consider
>>>>re-using my past MTD(f) code.
>>>>
>>>>15% is nothing to sneeze at.
>>>>
>>>>--Stuart
>>>
>>>
>>>Hi Stuart,
>>>
>>>I have problems with PV's.  In Cilkchess 1, I implemented MTD(f) and
>>>Aske Plaat improved the driver (I was doing it wrong and still getting
>>>a small speedup over PVS.)  Aske Plaat implemented the PV reporting
>>>which basically walked the hash table and picked up the best moves.
>>>However I don't think this is a good strategy if you want accurate
>>>PV's.   Cilkchess 1 had trouble reporting PV's and often the 2nd move
>>>would be a silly blunder.  This was scary and made us think the search
>>>was broken but it solved every problem in our test sets in the expected
>>>depth.  We won Dutch championship without a single loss out of 11 games
>>>and pronounced the search SOUND.   We are now are confident it's a PV
>>>issue only.  But for the tournament we simply did a 2 ply search to
>>>get the opponents move and hoped the quality of it was high enough to
>>>be a good predictor.  We never got blunders but often predicted weaker
>>>moves or did not see simple tactics in the prediction.
>>>
>>>In Cilkchess 2.0 I implemented the PV again using the same technique.
>>>At the Dutch this year we kept predicting these horrible moves for our
>>>opponents and basically rarely got to think on the opponents time.  Our
>>>hash table was broken too and we operated with 1/16 of the hash table
>>>we could have used and this may also affect the PV thing.  We lost a
>>>game and could only manage 2nd place with all that hardware and our PV
>>>implementation is partly to blame (and the fact that the program
>>>basically
>>>sucks!)
>>>
>>>We tried to fix the PV problem in the middle of the tournament, mainly
>>>by paying attention to "beta."   We have no Alpha in our search and
>>>beta is equivalent to alpha (and beta) in other programs.  We did some
>>>hack to make sure we did not change the 2nd move in the hash table
>>>unless the score is properly bounded.  On my list of "things to do"
>>>is to experiment with this in general (not for PV reasons) to see if
>>>there are conditions under which you should or should not change the
>>>best move in the hash table.  The end result seemed (this is a
>>>subjective
>>>judgement) to be an improvement and in 1 game we actually predicted
>>>almost every single move of the opponent, having 45 minutes on our
>>>clock at move 60 while the opponent had to reset for speedchess (they
>>>allow this in this tournament.)   I thought the problem was fixed for
>>>good but in the next few games the bad behavior reared it's ugly head
>>>again but seemed much less severe.  All of my non MTD programs had
>>>sound PV's to the best of my knowledge.
>>>
>>
>>when I tried this, I used (eventually) the idea of storing two bounds.
>>When
>>I stored a fail high bound, I stored the best move.  When I stored a
>>fail low
>>move, there obviously is no best move to store.  In this case I left the
>>fail-high move there.
>>This partially worked.  But it is *far* from perfect.  Particularly if
>>you
>>get the occasional lucky break of getting one fail high, followed by
>>several
>>fail lows.  It is possible to overwrite enough stuff that the PV simply
>>isn't
>>available.
>>
>>Of all the problems I had, this was the worst.  1. I want good moves.
>>15%
>>faster is a totall loss if you can't predict good moves for the
>>opponent,
>>because the lost "ponder" time is *much* worse than 15%.
>>
>>Lazy eval is another big problem... because I cut off evaluating if It
>>seems
>>I can't get close to alpha, or close to beta depending.  And when I back
>>this
>>partial eval back to the root, it won't give me a good estimate for the
>>next
>>mtd(f) re-search.  So I move the window up, search again, and the score
>>goes
>>even higher.  Until I finally reach a point where the lazy eval won't
>>exit
>>early.  But 3-4-5 re-searches and this is not as efficient as pure PVS.
>>
>>That's where I left off.  My lazy eval gets much more than 15%.  I'd
>>have
>>to discard that or suffer thru extra re-searches...
>>
>>
>>>I am soon going to implement PV's the right way and tackle this problem.
>>>Essentially a PV is just information passed toward the top of the tree
>>>(the
>>>root node) in recursive fashion and is trivial to implement.   I don't
>>>know what problems I will find but I intend to get it right.  I will
>>>definitely post my results if you find it interesting.
>>
>>I don't see how you can get a good PV from mtd(f).  The problem is that
>>every node fails either high or low.  The ones that fail low give you
>>zero
>>information on which move is best.  The hash table can't be depended on
>>to
>>provide this any more than it can in a normal PVS search, because of the
>>overwriting problem, not to mention the problem of storing fail-low
>>results
>>that are just as important (actually these are the *most* important when
>>you measure performance) but which don't have a best move.  If you are
>>lucky enough to overwrite an identical position that was a fail high or
>>PV
>>node, you can save the best move, but this didn't happen often for me...
>>
>>
>>
>>>
>>>MTD(f) is hell bent on not doing any more work than necessary and causes
>>>problems with PV's but I don't think they are unsolvable.  I definitely
>>>want sound PV's.  I mentioned there were things about MTD I didn't like
>>>and this is only one of them.   I would love to throw it out completely
>>>and actually tried to, but could not even come within 15% of matching
>>>its  performance.  It's really quite powerful on the serial as well as
>>>the parallel program.   Unless you are a performance freak (which I am)
>>>don't use it!
>>>
>>
>>
>>Hmmm...  I have *always* been a performance freak.  :)  That's why I
>>have
>>worked on parallel search algorithms..., wrote 20,000 lines of Cray
>>assembly code, etc.  and then did the bitmap algorithms now used in
>>Crafty...  I *never* ignore potential speedups...  When I first heard
>>about
>>it I downloaded Aske's paper about it and went to work...
>>
>>However, have you done a lazy eval?  If not you can get 15% there, but
>>it
>>will play hell with mtd(f) by not letting fail-soft give you a very
>>accurate
>>estimate.  Although in my case, when I turned it off, I still didn't get
>>a
>>very good estimate.  Closer than using either alpha or beta of course,
>>but
>>not close enough to make it pay off for me...
>>
>>
>>>
>>>- Don



This page took 0.03 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.