Author: Robert Hyatt
Date: 15:31:40 11/06/01
Go up one level in this thread
On November 06, 2001 at 11:33:49, Tord Romstad wrote: >On November 05, 2001 at 14:32:50, Robert Hyatt wrote: > >>On November 05, 2001 at 07:00:48, Tord Romstad wrote: >> >>>On November 04, 2001 at 17:41:06, Michel Langeveld wrote: >>> >>>>Don't forget to look at Bruce Mooreland's excellent homepage about >>>>computerchess: http://www.seanet.com/~brucemo/toc.htm >>> >>>This looks like a very good site --- thanks to you for mentioning it, and >>>to Bruce for writing it! >>> >>>I was a bit surprised to see the suggested implementation of the null move >>>heuristic on Bruce's homepage, the alpha-beta window is different from what >>>I have always used. This is the code fragment: >>> >>> MakeNullMove(); >>> val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1); >>> UnmakeNullMove(); >>> if (val >= beta) >>> return beta; >>> >>>In my code, I have something like >>> >>> val = -AlphaBeta(depth - 1 - R, -beta, mate_value); >> >> >> >>No reason. All you want to do, is with minimal effort, prove that if you >>do _nothing_ the score will return >= beta. Whether it is > beta, or = beta >>means nothing here. using mate-value means you will not be able to prune >>many lines in the null-move search that would be discarded by alpha/beta >>with X, X+1 as the bounds. > >I don't follow you here, I'm afraid. My code will never return a value >bigger than beta. It returns a number between -mate_value and beta. The >point is that if the value returned is close to -mate_value, I know that >the side which tried the null move is threatened with a mate in a few moves, >and I can extend the search. OK.. Some use "fail-soft" which can return scores outside the alpha/beta range. But here, all that matters is that by doing nothing, the score doesn't take a plunge. I don't need to search since I know I can always improve my position even more by actually playing a move, except when I am in zugzwang. > >>>which I always thought was the normal way of doing things. The advantage >>>of my method is that I can often detect serious tactical threats, while >>>Bruce's approach has the obvious advantage that it searches fewer nodes. >>>Without extensive testing, it is not clear to me which technique works >>>better. >>> >>>What alpha-beta window do the rest of you use? If anybody has tried both, >>>which approach works better? >>> >>>Tord >> >>I've always used X,X+1 for null-move. I've tried others, but none were as >>efficient. I don't see how it would matter if the score is == beta, or way >>above beta. > >I agree, of course, but I really don't understand how you think this relates >to the discussion. It has to do with the window being discussed. Whether X, X+1, X, X+N or X,+inf. All we want to know is "is the score after I 'pass' >= X, or not?" It doesn't matter how much greater than X it is, which means the upper bound should be as low as possible to minimize the null-move tree size as far as possible. The most obvious choice for a null-move search is simply beta-1, beta. Then if it fails high, the score is >= beta, and you can take the fail high instantly rather than searching. in fact, you should be able to do a null-move with a lower window, such as beta-X, beta-X+1, and still trust the fail-high since the right to move is worth something in a position. But that is another subject... > >> All that says is that you are winning, or you are _really_ >>winning, without having to play a move. Now if the null-move search fails >>_low_ that tells you something. IE the difference between alpha and alpha-100 >>would be interesting. Alpha means doing nothing is not good. alpha-100 >>failing low means doing nothing loses a pawn. Which may mean the opponent >>has a serious threat that you have to actively hold off by playing a move. > >How do you determine how serious the opponent's threat is if you search with >a window smaller than (-mate_value, beta)? > >Tord shift the window downward, but keep it null-width. IE a normal search is entered with values (alpha,beta). The null-window search should be done on (beta-1, beta) to see if we fail high. It could be done on any offset null-window such as (beta-100-1, beta-100) and if you fail low, you know that doing nothing loses at least a pawn. If the normal search doesn't fail low, then you have a move that is possibly holding off a strong threat and it should be re-searched with a deeper depth to see if the threat is really being held off, or if it is being horizoned off.
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.