Author: David Eppstein
Date: 17:57:35 09/30/99
Go up one level in this thread
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.
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.