Author: Ulrich Tuerke
Date: 04:53:16 09/13/02
Go up one level in this thread
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
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.03 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.