Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD: an observation and a question

Author: Josť Carlos

Date: 06:19:36 09/13/02

Go up one level in this thread


On September 13, 2002 at 07:53:16, Ulrich Tuerke wrote:

>On September 12, 2002 at 16:10:38, martin fierz wrote:
>
>>On September 12, 2002 at 09:28:28, Robert Hyatt wrote:
>>
>>>On September 11, 2002 at 22:14:57, martin fierz wrote:
>>>
>>>>prompted by the discussion on MTD before, i decided to look once again what my
>>>>program does.
>>>>
>>>>1. observation
>>>>dann corbit suggested that MTD works "binary-search-like" in zooming in on the
>>>>true value, in the sense that it converges rapidly. assuming the grain size of
>>>>my eval to be 1, i have seen ONLY search window changes of 1. like when my eval
>>>>jumps from 0 to 10
>>>>
>>>>(0,1) returns value 1
>>>>(1,2) returns value 2
>>>>...
>>>>(9,10) returns 10
>>>>(10,11) returns 10.
>>>>
>>>>not once did i see it do something like
>>>>(0,1) returns value 9
>>>>
>>>>i forget which is which, fail-soft/fail-hard, but i'm using the one which
>>>>returns the maximum of the successors, not the one which returns beta. so in
>>>>theory (0,1) could return 9, but it never does. i guess that's not really
>>>>surprising, since alpha-beta just tries to do as little work as possible :-)
>>>>
>>>>2. question
>>>>my question is related to bob's "bouncing over". MTD necessarily has to bounce
>>>>over once, as in the example above, it has to search both (9,10) and (10,11),
>>>>and fail high on the first search, and fail low on the second. so the question
>>>>is: isn't this bouncing over too? and if this is really bad, then: has anybody
>>>>ever measured the difference between MTD storing just one bound in the hashtable
>>>>with storing both bounds?
>>>
>>>
>>>The gotcha is to use fail-soft.  And this probably requires a few changes
>>>to how you back up scores.  IE you might do something like this:
>>>
>>>        v=Search(-beta, -alpha, etc);
>>>        if (v > alpha) {
>>>            if (v > beta) return beta;
>
>Probably just a minor remark, also a bit off-topic: but i think, usually you
>have here
>
>    if (v >= beta) return beta;
>
>Usually the values alpha and beta themselves are considered being already out of
>the window.
>Of course just a matter of convention. But I think that you have to be quite
>careful if you deviate from this; for instance differentiating between bounds
>and exact values when accessing the transposition table depends on the
>convention chosen.
>
>Also a minimum window search is different for the other convention.
>You would have
>  Search (x, x) in your convention, but

  That wouldn't work either, because a value of x would be exact, while
standard (x,x+1) is a null window (no exact value possible).

  Josť C.


>  Search (x, x+1) in the standard convention.
>
>I suspect that there are a lot of cases where you have to be quite careful.
>
>Uli
>
>>>            alpha=v;
>>>        }
>>>
>>>That return beta is not fail-soft.  it should be changed to
>>>
>>>            if (v > beta) return v;
>>>
>>>And you have to do that everywhere.  Doing so should get you a value
>>>back to the root that is outside the normal X,X+1 window you search
>>>with mtd(f).
>>>
>>>Note that lazy eval exits need to behave in the same way, returning the
>>>best estimate of the score they can, not just simply alpha or beta.
>>>
>>
>>i am using fail-soft. as i wrote in my post, i just didn't know what you guys
>>call it, but i'm using the one which returns max(child values), not beta. and
>>just like dieter suggests in his post, i start out with
>>
>>bestvalue = -mate;
>>for all moves do
>>  {
>>  value = -search(-beta,-alpha,etc);
>>  bestvalue = max(value, bestvalue);
>>  if(value>beta)
>>     break;
>>  }
>>return bestvalue;
>>
>>is there anything wrong with this?
>>
>>aloha
>>  martin



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.