Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: MTD: an observation and a question

Author: martin fierz

Date: 13:10:38 09/12/02

Go up one level in this thread


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