Author: Ernst A. Heinz
Date: 12:47:23 08/28/00
Go up one level in this thread
On August 28, 2000 at 13:51:22, Robert Hyatt wrote: >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+. But I already know a move to ponder on if Nf3 fails high. >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+. No, I do not play Bh7+ but rather try to complete the next iteration for it. That is the basic scheme. In addition, I collect some statistics about search time of previous iterations. Based thereon, I try to estimate if I can expect the next iteration to complete in reasonable time. If not so, I also resolve the fail-high move with the current iteration depth. >>>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? See above, I measure iteration times and try to avoid these cases. >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. My scheme has never "killed" me in a game so far. >>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... As mentioned above, my scheme has never "killed" me up to now. Moreover, you may run into exactly the same problems while researching the zero-window fail-high move with a full window in the current iteration. Sometimes, this also takes a really long time. What do you do then? Play the previously best move? =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.