Computer Chess Club Archives


Search

Terms

Messages

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

Author: Juergen Wolf

Date: 14:17:19 08/14/03

Go up one level in this thread


On August 14, 2003 at 17:00:53, Rudolf Huber wrote:

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


 than in my opinion the article should have a different headline or at least an
question-mark.


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

i read threads were exactly the opposite is stated. as far as i seen these
are from chessprograms not using MTD and stating MTD doesn't help

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

i was looking for an explanation why some programs dont see a benefit by MTD.
those programs seems to use IID. I think crafty is/was one of those programs.
I didnt state its better rather equal

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

as described in plaats article. going into the opposite direction

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

This is understood. By how much % ?

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

 yes, this is not related to mtd but instead of posting multiple threads
  i created one
>
>>
>>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.



from what i seen so far , based on limited results , at least in ID  (might be
different for fix-depth-search) is that due to the fact that i have a best move
w/o knowing the exact value, the next iteration gets much more expensive and
sometimes more expensive than a search targeting accurate values.

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