Author: Ernst A. Heinz
Date: 09:41:55 08/28/00
Go up one level in this thread
Hi Bob, >>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.'' > >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. The text above already alludes to my solution of this problem. I simply extend the search time and try to finish the next iteration for the fail-high move if it is a new best move. Otherwise, I still have a move to ponder about from the previous iteration. >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. True, but nonetheless I delay the resolution until the next iteration _unless_ I find a second move which is better than the original PV move. Those two I actually resolve directly. If the new move fails low in the next iteration, I simply extend the search time and try to find a new better one (see above). I like this kind of "top-level PV extension" that tends to search deeper in positions were the search looks unstable. According to my experience with "DarkThought" in tournament games, the perceived unstability is mostly real and not an artifact of the implementation caused by e.g. null move and hash tables. >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.. Yes, I also like it very much and there are several solutions to the problem of not having a ponder move. Your "puzzle" search being one of them. My time extension being another. Cheers, =Ernst=
This page took 0.01 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.