Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 13:03:47 09/11/02

Go up one level in this thread


On September 11, 2002 at 13:20:55, Vincent Diepeveen wrote:

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

_not_ necessarily.  In pure mtd(f), maybe not, it depends on how you
adjust the score between iterations.  Using fail-soft _can_ make you bounce
over the true score...


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

fail-soft stores various scores in the hash table that might not be correct
for lots of reasons.  null-move and other things already cause false fail highs.
That happens in mtd(f) also...

>
>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
>-0.007
>
>I do not see *anyhow* how you can jump over the score.

See above.  And you should start _above_ the score anyway and work down,
because fail lows are easier to prove than fail highs at the root.

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



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.