Author: Robert Hyatt
Date: 10:51:22 08/28/00
Go up one level in this thread
On August 28, 2000 at 12:41:55, Ernst A. Heinz wrote: >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. > I don't follow. At depth=12, I like the move Nf3, with a PV to go along with it. At depth 12 I then fail high on the move Bh7+. I don't re-search it as I already know it is better than Nf3. No other moves fail high. I start depth=13 and run out of time. I play the move Bh7+. Where do you get a move to ponder from? The hash table has nothing useful, since at ply=2 (after Bh7+) all moves failed low. The PV has nothing useful since it is a one-move PV with Bh7+ but nothing else. I have a mode that will search to find something to ponder, but what I find won't be as good as the N-1 ply search used to find the second move in the PV (which is missing in this case.) >>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. > What if you can't resolve the score at the next iteration? It might be a gross blunder caused by a null-move failure on the null-window search that failed high. This killed me more than one time on ICC, until I took action to not accept null-window fail highs unless they either returned a PV with alpha, beta window, or else failed high a second time on the alpha, beta window. >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. If you are using recursive null-move, with R=2 or R=3, then you will _have_ to have some fail-high/fail-low cases. I haven't seen anyone that doesn't run into this. Here is the ugliest case where your approach will fail: You start pondering, and your opponent takes a _long_ time to move as he thought he could win something only to find with a deep search that he could not. He takes 15 minutes to move. You ponder like mad during this time, and just as he moves, your search fails high on the null-window search. You might resolve the score (or get a fail low) if you research _now_. If you wait to the next iteration, you have absolutely no chance to get a fail low, a fail high or anything else. You have already searched over 15 minutes. The next iteration will take close to an hour... If you play that null-window fail high move, I will guarantee you that at times it will be a _horrible_ blunder. I remember one such move when Bruce and I were playing a crafty/ferret match on ICC. I got killed in a nearly drawn position by playing a gross blunder. We both fixed this in the same way, at about the same time... > >>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. I don't see how the time extension is reliable enough. It would seem to me that you are rolling the dice and hoping that you can even get to the next iteration and have enough time for the suspect move (null-window fail high move) to fail low, or produce a PV so you can trust it and have something to ponder. > >Cheers, > >=Ernst=
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.