Computer Chess Club Archives




Subject: Re: MTD: an observation and a question

Author: Robert Hyatt

Date: 06:31:26 09/12/02

Go up one level in this thread

On September 12, 2002 at 04:43:43, Georg v. Zimmermann wrote:

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

While that is all true, the point is that somewhere you are going to produce
a static eval that is either above beta, or below alpha.  And if you back
this up correctly, it will reach the root and provide a _better_ estimate
of the true score than just backing up the raw bound you are searching.

Not every time, but it should happen a _lot_ if failsoft is implemented

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