Author: Andrew Williams
Date: 14:16:19 08/23/01
Go up one level in this thread
On August 23, 2001 at 16:55:17, Bob Green wrote: >On August 23, 2001 at 11:47:03, Robert Hyatt wrote: > >>On August 23, 2001 at 11:08:54, Sune Fischer wrote: >> > >>>If may ask, what algorithm do you people use, is it alpha-beta or negascout >>>or...? >>>Is there a clear answer to what the best search algorithm is? >>> >>>Cheers, >>>Sune >> >> >> >>Most everyone uses negamax as the framework. Whether you use simple >>alpha/beta on top of that, or something more sophisticated (I use PVS for >>example) doesn't change the look of the basic search that much. > >I read a paper by Plaat, Schaefer, et. al. which used the basic negamax >framework to compare AB, negascout, SSS*, DUAL* and MTD(f). The paper indicated >a dramatic (ok, 5-10%) improvement using MTD(f) when the move ordering was >"good" (i.e. within 10-15% of "best" order.) There was a flurry of papers on >this algorithm. Was it ultimately found wanting? > >Bob Green > MTD(f) is used in some programs, including mine. My program is far from the strongest (putting it mildly), but I doubt whether anyone could sensibly claim that this is due to the use of MTD(f) instead of a more established technique. To the best of my knowledge, Plaat is the only person who has compared MTD(f) with other techniques *in the same program* The debate on how useful MTD(f) is is controversial, to say the least. It's fair to say that many of the standard pruning tricks that can be used with (eg) PVS need re-thinking when applied to MTD(f) programs. Amongst the WMCC crew, I believe that SOS *used* to use MTD(f). I don't know if it still does. >ps. If any other newbies are lurking, the "Yellow Bishop" site has a great set >of papers on tree searching algorithms. See http://ybishop.cjb.net/ Cheers Andrew
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.