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