Computer Chess Club Archives


Search

Terms

Messages

Subject: MTD, IID, fail-low, root-research

Author: Juergen Wolf

Date: 12:10:16 08/14/03



According to the publisher of MTD (Plaat,A Minimax Algorithm faster than
NegaScout, http://theory.lcs.mit.edu/~plaat/mtdf.html) , MTD is supposed
to be better than Negascout.
As the article stresses the value of transposition-tables in MTD , i wondering
whether the comparision is done against Negascout without using transposition
tables (question 1) . Also i'm wondering whether the author provided a formal
proof of his statement (question 2). Just in case he compared MTD against
Negascout with transposition-table, I assume he did not provide a formal proof,
as he provides some implementation tips , just in case it turns out that
Negascout is still better.

Nevertheless i think its an interesting idea worth to be tested . I like the
simplicity of MTD. I read some previous threads and there seems to be some
programs where MTD is not of any benefit. Is it correct to assume that those
programs are using IID (question 3). My understanding is that IID is not useful
in zero-window search and is used just in case no move was found in the
transposition-table. Did somebody ever compare Negascout+transposition+IID  vs
MTD (question 4)? My thought is that IID might provide sufficient
"compensation".

My program so far used a window of +/- 0.2pawns for the 1st search, in case of
a fail high i redo another search with a window of 1.2 pawns and in case this
still fails high i'm using the max-window.  I implemented MTD (work of minutes
and is working) and intend to do some extensive benchmarks.

Plaat also mention that the MTD-grain is important. My program has an
eval-grain/stepsize of 1/1000 pawn. Is there a benchmark comparing success of
MTD (using different settings of step-size) wrt to grain of eval-function
(question 5).  For example if i have a grain of 1/1000 in eval - function , is a
stepsize
of 10 , 20 , 40 (1000 points = 1 pawn) better than "worst case" 1 ?


I read that in case of MTD its important to store lower-bound AND upper-bound.
So far my program just stores one value. Did somebody compare these two
approaches (question 6)?

Wrt to transposition table i read statements that using a move from a fail-low
search should not be taken as preferred move. What are the general experiences
on this (please describe feature set of program, question 7) ?

A read a long time ago an article proposing , in case that a Zero-window search
provides a fail high (a better move found than the best-move-so-far), it might
be worthwhile not to do a full research just to find the exact value. In case
another move beats the best-value , both moves have to explored agained to
decide whether move 2 or 3 is better. Are there any statistic/experiences
available (question 7)?

i intend to make those benchmarks with my own program in order to decide which
is the best setting for my program, but would like to compare my results with
the "rest of the world" ( or set my expectation right)

kind regards juergen wolf










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