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 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.