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