Author: Robert Hyatt
Date: 05:16:35 01/22/98
Go up one level in this thread
On January 22, 1998 at 02:30:48, Bruce Moreland wrote: >To clarify, all of this is about what happens at the root. It has >nothing to do with what happens inside the tree. To do this inside the >tree would be wrong. > >I think it's probably wrong at the root, too, but that's my problem -- I >don't want to take the time to do the experiment, most of the time I >have a backlog of my own ideas to try, and I don't have time to track >down everything like this. If someone else wants to do the experiment, >that would be great, and would be useful to the rest of us regardless of >how it turned out. > >This idea might be related to some other techniques, by the way, there >are algorithms that do zero-width searches on every move at the root, >and try to close in on the true value. > >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. *huge* difference. >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. But as soon as beta rises above the true value, this doesn't happen. This is why, for 20+ years now, I have elected to start the next iteration even though I know positively that I have no chance to get a PV move searched before I run out of time. Because I know that should the previous "best" move turn out to be bad at this depth, I will find that it fails low quickly, and usually quickly enough that it can fail low before I run out of time, triggering me to allocate more time to see how bad it is, and thento try and find something better. > >This is what will happen to the root successor moves if the poster does >his backwards search, I think. I think he'll end up showing that the >root successor moves are bad before he gets around to understanding the >first root move, and assuming that he does the exact same searches as >he'd otherwise do (he won't, but I don't think this will matter much), >he'll probably take about the same time in total to do all this. > >This could be a win if one of the alternates is great, and you have >enough time to get to it, but not if you search the PV first. > >But there are problems, too. It's complicated and you might end up >having to search some successors more than once. The time spent doing >extra work in the general cases could outweigh the cases where you find >a shot right before time expires. > >Something this might sacrifice is something that Bob pointed out in a >paper years ago -- that if the PV move is going to fail low, it's going >to do it pretty quickly. So if you try to find the shots faster, you >might miss the fail lows more often then you should, and end up failing >to extend time in crucial cases. > >I don't know how this would all weigh out. This needs to be shown >experimentally, I think. > >bruce
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.