Computer Chess Club Archives




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

Author: Robert Hyatt

Date: 09:33:46 09/11/02

Go up one level in this thread

On September 10, 2002 at 21:01:49, martin fierz 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?
>i'm doing the same. but in plaat's papers, he suggests you store both an upper
>bound, and a lower bound. the idea seems to be that since MTD potentially
>produces lots of researches, you could maybe use the additional information. at
>least that's what i think it's supposed to be.
>as an example, take a position somewhere in your search tree with true value 15.
>you do your first test with 0. you get e.g. lowerbound(p)=13. then you try 20.
>you get e.g. upperbound(p)=18.
>now, if your third test is for +10, and you get to this position again, you get
>a HT cutoff because of lowerbound(p)=13. the way you and i implemented it, we
>would only have the information upperbound(p)=18 in our table. which would give
>you no cutoff here. that's what i think this is about.
>however, there was this discussion about MTD always approaching the score from
>the same side. like that the sequence of tests i described 0,20,10 is not
>possible for certain MTD implementations. then you don't need to store 2 values,
>as bob pointed out.
>  martin

It is a very "iffy" thing.  If you can approach from the same side until the
last search, you will be ok.  But that means you will approach the true score
more slowly if you have a "big" score swing.  If you "bounce over" then all
the hash entries are going to be worthless.  But then again, by bouncing over
you are also killing performance anyway since it is better to approach the true
score from the "upper side" for reasons already given.


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.