Computer Chess Club Archives




Subject: Re: MTD: an observation and a question

Author: Georg v. Zimmermann

Date: 01:43:43 09/12/02

Go up one level in this thread

On September 11, 2002 at 22:14:57, martin fierz wrote:

>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 :-)

its called fail soft.

Look at this tree:

                           |                           MIN
                          / \
                         /   \
                        /     \
                       /       \
                      /         \                      MAX
                 #1  /\      #2 /\
                    /  \       /  \
                   /    \     /    \
                  7      0   3      5
                 #1     #2  #3     #4

we are searching it with [0,6]

MAX #1 only looks at leaf #1, returns 7 because that is already failing high.
MIN then looks at MAX #2. MAX #2 looks at leaf #3 which is within bounds. So MAX
#2 also looks at #4. This one is 5, so MAX #2 becomes 5. MIN then decides to go
with MAX #2 which is smaller, and returns 5.

we are searching with [0,1] MTD(f)

Within MAX #1 the same happens. When we get to MAX #2 , leaf #3 already fails
high. MIN again choses MAX #2 amd returns the smaller fail soft value, 3.

Repeat that over a lot of recursive loops, and you will very rarely see fail
soft effects at the root of a MTD(f) search.

Of course I am not sure about this, but I think it sounds reasonable.

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

I think it is only then really bad, whe the bouncing over doesnt happen at the
last "test drive". Because then it then sets wrong hash table bounds (on the
next test drive we could have used lower bounds better again) it slows down the
rest of the search.


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