Computer Chess Club Archives




Subject: Re: Couple of chess programming questions: another MTD drawback

Author: Vincent Diepeveen

Date: 10:20:55 09/11/02

Go up one level in this thread

On September 11, 2002 at 12:31:44, Robert Hyatt wrote:

>On September 10, 2002 at 20:45:43, Vincent Diepeveen wrote:
>>On September 10, 2002 at 18:06:01, Gian-Carlo Pascutto wrote:
>>>On September 10, 2002 at 17:51:11, Vincent Diepeveen wrote:
>>>>On September 10, 2002 at 17:43:15, martin fierz wrote:
>>>>>On September 10, 2002 at 17:18:24, Vincent Diepeveen wrote:
>>>>>>On September 10, 2002 at 17:10:38, martin fierz wrote:
>>>>>>>On September 10, 2002 at 09:26:14, Eli Liang wrote:
>>>>>>>>(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?
>>>>>>losing 1 bit is a problem for you?
>>>>>nope. losing 2 bytes is more like it...
>>>>who stores a bound in 2 bytes?
>>>>Why not in 1 bit?
>>>You want to store two actual values, not flags that indicate what
>>>kind of bound it is.
>>did i implement it smarter then or what?
>>i used 2 bits in total. 'upperbound, lowerbound, truebound'.
>>the search result is based upon a single bound. So it IS the same,
>>it IS higher or it IS lower.
>>What am i missing here?
>A _lot_.
>This is a known issue with mtd(f) and fail-soft.  If you bounce over the
>true score, to the "other side" then suddenly where you were storing
>upper bounds you are now storing lower bounds, and vice-versa.  Now if
>you bounce back over the true score again, you have no useful upper bounds
>where you need them, you only have lower bounds.  And you have no useful lower
>bounds where you need them you have only upper bounds.

you never bounce over the true score.

You go from a score X --> Y in a lineair way.

If it's a big distance, bad luck, we need many researches. If it's
very close, lucky MTD.

I do not see how i can get *anyhow* jump over the true score unless
there is search bugs in the program (like forward pruning or lazy eval
which is wrong implemented or other futility stuff).

If i go from 0.001 0.002 0.003 0.004 0.005 0.006 0.007

then i reached my goal.

If you go to -0.007 then it's simply a few searches more:

 0.001 is first search then: 0.000 -0.001 -0.002 -0.003 -0.004 -0.005 -0.006

I do not see *anyhow* how you can jump over the score.

Because if you *do*, then you aren't searching with MTD, but
with some badly implemented minimal window search.

>if you store _both_ then you don't take as big a performance hit when you
>"bounce over" the true score.
>This is what I mentioned when I said "doing mtd(f) is _not_ just a few lines
>of code changes, it requires fundamental changes in places like hashing."

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.