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. > > >Regards, >Georg 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 correctly.
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.