Author: Robert Hyatt
Date: 12:27:20 01/22/98
Go up one level in this thread
On January 22, 1998 at 12:17:37, Bruce Moreland wrote: > >On January 22, 1998 at 08:16:35, Robert Hyatt wrote: > >>On January 22, 1998 at 02:30:48, Bruce Moreland wrote: > >>>I don't know exactly why the PV (first) move takes so long to resolve, >>>but I can guess. I think that it takes a while to resolve because the >>>window is wide, and the value will probably be within the window. >>> >> >>Think about ply=2. For a non-first move, you search one move there. >>That >>is enough to refute the ply=1 move. For the first move, you have to >>search *every* ply=2 move since there is no bound to cut off against >>yet. >> >>For the first move, as you advance down the left-side of the search >>tree, >>assuning it is drawn so you search left-to-right, *every* left-most node >>must have every alternative searched. >> >>For non-first moves, in a perfectly ordered tree, every even-ply >>position >>only has to search one move. > >I want to point out that we aren't arguing, in case I am wrong and we >really are. > >The fact that you are within the window is *why* you aren't cutting off, >right? > >>>From experience it seems like you get a faster result if you have a >>>narrow window and the move fails low. If someone wants to prove this, >>>cool, there is probably an easy proof for the mathematically inclined. >> >> >>this is written up in a technical report by Jonathan Schaeffer, and was >>referred to as "the minimax wall". As long as alpha/beta are below the >>true value of the search result, searches run like the blazes, because >>the entire tree is searched as though it had *no* best move and >>everything >>at the root gets refuted by the first move at ply=2 and so forth for >>all >>even/odd plies. > >Do you mean instead that alpha and beta are *above* the true value of >the search? > >bruce I really hate questions like the above. Because this is complicated enough that no matter how I first answer, I later decide it was backward. :) In any case, yes. If the window is above the true value, so that you will fail low, you get maximal efficiency. here's the way to follow why. If every root move fails low, it can do so after searching only one move at ply 2, the one move necessary to 'refute' the root move. So you get a truly small tree. if the window is below the true value, so you fail high on every move at the root, to fail high at the root means *every* move at ply=2 must fail low. The tree is roughly W times larger in this case. Schaeffer noticed this and referred to this as the "minimax wall", that point where the window just drops down over the real score so that you don't get the quick fail lows. I saw this when I played with mtd(f) a few months ago, as it was faster when the window was too high. Fast enough that it is best to keep it up there rather than dropping below the real value and having to fail upward...
This page took 0.01 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.