Computer Chess Club Archives




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

Author: Stuart Cracraft

Date: 11:28:27 01/22/98

Go up one level in this thread

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.


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.