Computer Chess Club Archives


Search

Terms

Messages

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

Author: Don Dailey

Date: 18:59:57 01/22/98

Go up one level in this thread


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.

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.

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!


- Don






















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