Author: Dave Gomboc
Date: 23:34:15 09/30/99
Go up one level in this thread
On September 30, 1999 at 20:57:35, David Eppstein wrote: >On September 30, 1999 at 15:00:07, Dave Gomboc wrote: > >>On September 30, 1999 at 13:33:26, David Eppstein wrote: >> >>>But, you could keep a flag for each root move, saying whether it failed low >>>in the current window. If the flag is set, you don't bother searching that >>>move in later windows. If the search for a given guess fails low, you narrow >>>the window without updating any of the flags. If the search for a given guess >>>fails high, you narrow the window and flag any move that failed low in that >>>search. Then, you can stop when there is only one unflagged move. >> >>The first thing that should happen when you go to search such a move is that you >>will get a hash hit with an upper bound that is lower than the bound you are >>searching. This will immediately cause the algorithm to move on to the next >>move. I think this would be less work and just as quick as maintaining some >>list of flags by yourself. > >Yes, that's partly why I wasn't sure whether this would actually help. Flagging >a move as having failed low and avoiding searching it again is a little more >reliable than putting it in the hash table (depending on your hash collision >strategy) but doesn't make a huge difference. But, I think the major possibility >for savings is not so much in not searching move lines that have already failed >low, but another source: number of iterations of the overall search. > >In the version of MTD(f) originally described in this thread, you have to keep >going until you know the exact minmax value of the best move. In the version I >described, you can stop once you know it is best, without having to resolve its >value. If the play in the tree below the best move contains many lines with >similar evaluations, you could be wasting a lot of time resolving those lines. You will resolve the best move before you search other moves at the next ply anyway. Let's say you are in the middle of a depth 8 search, with a move that is known to be best (all others have failed low.) You are recommending not resolving the actual depth 8 score and pv, just jumping immediately to the depth 9 search, right? I am thinking that this would be a classic case of not performing iterative deepening (ID). Since ID is a well-known performance win, it doesn't seem right that it would be good to jump immediately to the next ply. Without finishing the depth 8 search, you'd have poorer move-ordering when you're searching the best move to depth 9. If the program is doing internal iterative deepening (IID - also thought to be a performance win), the first thing that's going to happen in ply 9 is that the ply 8 search that didn't get finished is going to get finished anyway (due to the IID). In this case, all that's happening is that you've incremented your depth counter sooner than another program might. The actual amount of work done doesn't seem to change, though. My above argument notwithstanding, I might be missing something. :-) Dave
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.