Author: Robert Hyatt
Date: 09:02:47 08/28/00
Go up one level in this thread
On August 28, 2000 at 11:01:30, Ernst A. Heinz wrote: >Hi Dan, > >>One scheme I read about (in one of Levy's books I think) involved just >>continuing on when you get a fail-high, and searching all the rest of the >>moves--unless you get a second fail-high. Then the question becomes "which >>of the two fail-high moves is the best?" I don't recall exactly how you >>proceed after this, but you don't need to re-search any of the other moves >>that have already been searched that didn't fail-high. You do have to >>re-search the two fail-highs, however. I guess this scheme isn't very good >>for PVS search since you might end up without a PV to follow. > >In "DarkThought" I have refined this technique of "lazy alpha >bounding" at the top level quite a bit for searching root moves. >My article "How DarkThought Plays Chess" in the ICCA Journal 20(3), >pp. 166-176, Sept. 1997 (http://supertech.lcs.mit.edu/~heinz/dt/) >and my book on "Scalable Search in Computer Chess" >(http://supertech.lcs.mit.edu/~heinz/node1.html) give the following >brief explanation. > >``At the top level, "DarkThought" employs lazy alpha bounding and iterative >deepening with an aspiration window of half a Pawn [127,191]. In contrast to >plain alpha bounding [182], the lazy scheme delays the complete resolution of >both new best moves and fail highs up to the next iteration. Top-level alpha >bounding often saves some effort while at the same time searching new best >moves one ply deeper than usual. If the top-level search is unstable or if the >final score lies far below the score of the previous move, "DarkThought" >extends the duration of the current search up to threefold when playing in >tournament mode.'' > >Cheers, > >=Ernst= I assume you mean that when you fail high on the window alpha, beta, you don't research that move in the current iteration unless another one fails high? That actually works well although I don't use it in crafty. The reason I don't is that you often end a search with no best move, just a fail high. I now have a way to get a move to ponder, so this wouldn't be a problem. There is another case, however, that after searching the first move with alpha,beta, you search the rest with alpha,alpha+1. If you get a fail high there, you had better re-search with alpha,beta, because null-move will give false fail highs in plenty of positions. In Cray Blitz, if we failed high at the root (not on the alpha,alpha+1 search, but on the alpha,beta re-search after the alpha,alpha+1 search failed high) we deferred re-searching again with beta,+infinity until another move failed high. Belle also did this, and it worked well, if you ignore the problem with having no best move to ponder.. I have had this on my to-do list for 2 years now, since I wrote the "puzzle mode" in crafty to find a move to ponder by doing a search for the opponent, if no ponder move can be found by other means (PV, in hash table, etc.)
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.