Author: Robert Hyatt
Date: 06:28:28 09/12/02
Go up one level in this thread
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;
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.
>
>cheers
> martin
This page took 0.28 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.