Computer Chess Club Archives


Search

Terms

Messages

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

Author: Rudolf Huber

Date: 14:00:53 08/14/03

Go up one level in this thread


On August 14, 2003 at 15:10:16, Juergen Wolf wrote:

>
>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.

Formal proofs are very difficult when one has no accurate model how the
search tree will look like. In any case it is much more important that the
algorithm is robust against additional extensions/pruning (nullmove, etc.)

>
>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).

I do not think that IID is important.

>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".

IID should not be your focus. It is not necessary. And no,
Negascout+transposition+IID is not better than mtd(f)+transposition+IID

>
>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.

Good. Please post results.

>
>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 ?
>

Varying the stepsize leads to other problens. How do you handle the
case where you step too far?

>
>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)?

Yes, it is useful for (question 5).

>
>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) ?

I think this is not related to mtd(f)

>
>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)?

You can do better with mtd(f) by delaying the resolution of a new best move.
Just check if there is another move which is also better than the current move.


>
>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

Excellent. Again please post your results.


Rudolf



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