Computer Chess Club Archives




Subject: Re: MTD(F) results

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]

Best-First Fixed-Depth Minimax Algorithms
Aske Plaat, Erasmus University,
Jonathan Schaeffer, University of Alberta,
Wim Pijls, Erasmus University,
Arie de Bruin, Erasmus University,

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