Author: Robert Hyatt
Date: 19:30:20 08/28/00
Go up one level in this thread
On August 28, 2000 at 15:47:23, Ernst A. Heinz wrote: >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. Yes... but Bh7 failed high, and there is no best move for it, which is the problem. > >>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.