Computer Chess Club Archives




Subject: mtdf

Author: Dan Homan

Date: 20:12:41 05/13/99

I've tried the mtdf algorithm a few times with no luck.  It was
always noticably slower than pure PVS.  (For reference: mtdf is
an algorithm which uses a series of null-window searches from the
root to narrow in and find the true score of a position.)

Today I tried mtdf again, but this time with more determination.
It is an easy change to my program because all I need to modify
is the loop that calls my PVS function from the root.  Again, I found
that it was much slower than normal PVS at first.  However,
by modifying the algorithm to use an adaptive step-size (meaning that
I don't try neighboring (+/- 1 point) windows for re-searches but
rather try to bound the score more efficently) and by
reducing my score resolution from 1/100 th of a pawn to 1/25 th of
a pawn, I got better results from mtdf than from pure PVS.

I went from 277 correct solution on the WAC test set (5 sec limit on a
Cel 400) to 281 correct solutions with mtdf.  My rms solution time for
both runs (with and without mtdf) were nearly the same.  Of course,
these tests are not really conclusive...  For example I don't know how
pure PVS will do with 1/25 th of a pawn scoring rather than 1/100 th.
What this does indicate to me is that mtdf is a viable solution.  Previously,
I had assumed it would be very difficult to implement effectively.

If I decide to commit to mtdf, there are (presumably) more optimizations
I could take advantage of.  What kind of experience do other programmers
have with mtdf?

 - Dan

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.