Computer Chess Club Archives




Subject: Re: Couple of chess programming questions - MTD(f)

Author: Vincent Diepeveen

Date: 09:13:29 09/10/02

Go up one level in this thread

On September 10, 2002 at 10:51:32, Omid David wrote:

>On September 10, 2002 at 09:26:14, Eli Liang wrote:
>>A couple of chess programming questions:
>>(1) Are there any uses for ProbCut and/or Multi-ProbCut in chess positions where
>>the variance of leaf-nodes is low?  What about the use of Warren Smith's BPIP or
>>Russell&Wefald's meta-greedy algorithms in chess?  Any wins?
>>(2) Is it practical to use partial-order bounding as an improvement over
>>conventional static evaluation?
>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>>is something of a magic bullet.  But I note it seems that more programs don't
>>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>>doesn't say?
>There has been a good discussion recently here, concerning Plaat's PhD thesis,
>and in particular his MTD(f) algorithm. The problem with all his research, is
>that he has conducted it merely on fixed-depth full-width trees, i.e. without
>considering any variable depth algorithm.

Didn't he forget to include a quiescencesearch either?

>Today there is no program which uses sheer brute-force, as researched by Plaat;
>and even in 1996 (thesis' publication) almost all of the programs used some kind
>of forward pruning (mostly null-move pruning R = 2). In fact, no brute-force
>searcher has won the World Computer Chess Championships since 1992.
>Another problem with Plaat's thesis, is that all chess test positions have been
>searched to a depth of 8 plies. To obtain a more realistic assessment, the
>depths 9, 10, 11 will yield better results.
>I agree with Dr. Hyatt's recent comment which said: "I think that for normal
>programs, they should be equivalent if they are both implemented with the same
>skill and development time". Anyway, a research regarding MTD(f)'s performance
>in variable depth environments is badly needed in my opinion.

I disagree. Some conditions in programs can take care it's
completely unusable (pawn=1000), whereas other conditions
in certain programs can take care that it works great (pawn=32),
with the other critics i agree completely.

Note that the biggest problem i have with most researches on search
methods is that they use testsets for it which aren't the problem.

Look if i'm +10.0 i don't care to get another ply or save a few nodes.
Anything wins there.

If i'm having a difficult position where i might either win,lose or draw
then it's important to have an efficient search IMHO. It is here where
no researcher has ever measured things like MTD versus other forms of
search. It's here where MTD is very weak.

I can see it clearly in SOS for example. Its search depth sucks ass when
it's having a difficult position. Further MTD works great for it overall.


>>(4) What are the current thoughts concerning bitboards/rotated-bitboards versus
>>conventional 0x88 or other algorithms?  Just looking at open source chess
>>programs, it doesn't seem that the chess programming community has come to a
>>consensus on relative performance... or have you?
>>(5) What is currently thought to be the best algorithm for autofitting the
>>static evaluation function parameters? DT's least-squares approach seems
>>simplest, but it seems as if a dozen other things have been tried too.  Is there
>>any best-of-breed approach here?
>>(6) Has anyone found any real "practical" benefits to fractional-ply extensions?
>>(7) Dennis Breuker has a paper comparing 5 different transposition table
>>replacement schemes.  Has any else been able to validate his results that
>>replacement should be based on the number of nodes searched and not search

This page took 0.01 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.