Author: Dann Corbit
Date: 13:52:50 12/17/03
Go up one level in this thread
On December 17, 2003 at 16:37:15, Dann Corbit wrote: >On December 17, 2003 at 05:38:52, Tord Romstad wrote: > >>On December 16, 2003 at 21:22:56, Anthony Cozzie wrote: >> >>>Recently I experimented with adding MTD(F) into Zappa. It has been an >>>interesting experiment, but I am going back to PVS(). >>> >>>I thought that since Zappa has a [UL,LL] paired transposition table and an >>>evaluation granularity of only 1/100 of a pawn, >> >>I use 1/64 of a pawn in Gothmog. In the new engine I am writing, the >>granularity will be configurable by the user, with possible values between >>1/8 and 1/512 of a pawn. > >Here's an idea: > >Start searching with a granularity of (a-b)/k, >and for every iteration change the granularity to the new value. > >The values a and b are the start and end of the search interval being searched >and k is some integer constant used to tune the program (e.g. 8). The idea works even better with MTD(bi) [A.K.A. the C* algorithm] Ref: Best-First Fixed-Depth Minimax Algorithms Aske Plaat, Erasmus University, plaat@theory.lcs.mit.edu Jonathan Schaeffer, University of Alberta, jonathan@cs.ualberta.ca Wim Pijls, Erasmus University, whlmp@cs.few.eur.nl Arie de Bruin, Erasmus University, arie@cs.few.eur.nl "Since MT can be used to search from above (SSS*) as well as from below (DUAL*), an obvious try is to bisect the interval and start in the middle. Since each pass produces an upper or lower bound, we can take some pivot value in between as the next center for our search. This algorithm, called MTD(bi) for short, bisects the range of interest, reducing the number of MT calls. To reduce big swings in the pivot value, some kind of aspiration searching may be beneficial in many application domains [47]. Coplan introduced an equivalent algorithm which he named C* [9]. He does not state the link with best-first SSS*-like behavior, but does prove that C* dominates Alpha-Beta in the number of leaf nodes evaluated, provided there is enough storage. (This idea has also been discussed in [1, 52].)"
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.