Computer Chess Club Archives




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

Author: Robert Hyatt

Date: 14:55:24 09/11/02

Go up one level in this thread

On September 11, 2002 at 16:14:30, martin fierz wrote:

>On September 11, 2002 at 12:33:46, Robert Hyatt wrote:
>>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.
>thanks for pointing this out. i hadn't seen that in plaat's description, but
>maybe i just missed it :-)
>i'll have to see what my program does...
>  martin

I'm not sure it _is_ in his description in fact, but it has been a known fact
for almost forever that it is easier to search a fail-low at the root than a
fail high...

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