Author: Bo Persson
Date: 03:33:56 08/15/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. This article is one step on the way to his thesis. There he explains it in more detail, but the results are still shown only for a particular engine searching a set of test positions to a fixed depth. The fixed depth part is also a limitation. Generalizing the result is material for another thesis, or three. :-) > >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". I don't do IID, just ID. :-) > >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). I think he is right here. You could very well evaluate in millipawns, and then truncate to the result to centipawns. This helped me reduce the number of steps. >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 ? Someone (lost the name right now, sorry) showed here a couple of years ago how to use an exponentially growing/shrinking step size. I start at stepsize 16 (because that works better than 8 or 32:-) and then double the size for each step, until the first overstep. I then reduce the stepsize (stepsize /= 2 ) for each successive step, forwards or backwards, until I zoom in on the final value. Here 1 pawn = 100 points. > > >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 works much better with both bound. Probably has the biggest effect if you continuously overstep in both directions while zooming in on the score. However, for me Negascout also works better with two bounds! > >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) ? If all moves fail low, which move should we prefer? > >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)? Guess it depends! :-) If you don't resolve the single fail high move, you might have a worse starting point for the next depth. You win some, you lose some. Most people also want to see the evaluation displayed during and after the search... > >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 Bo Persson bop2@telia.com
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.