Computer Chess Club Archives


Search

Terms

Messages

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

Author: Omid David

Date: 07:51:32 09/10/02

Go up one level in this thread


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.

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.

Omid.


>
>(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
>depth?



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