Author: Dann Corbit
Date: 15:32:33 11/21/01
Go up one level in this thread
On November 21, 2001 at 18:23:08, Michel Langeveld wrote:
>I build nullmove in my chessprogram and received a problem.
>
>The example which is on Bruce side seems not to work in certain positions.
>Especially positions where it's possible to give mate:
>
>[D] rnbq1bnr/pp2k3/2p1p1B1/3pP1p1/7p/4PQ2/PPPN1PPP/R3K1NR b KQ
>
>After Qc7 white doesn't see Qf7 anymore.
>
>It seems to be that the line:
>
>val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
>
>Must be changed into:
>
>val = -AlphaBeta(depth - 1 - R, -beta+1, -beta);
>
>
>--------- BELOW HERE THE EXAMPLE OF BRUCE ---------------
>
>#define R 2
>
>
>
>int AlphaBeta(int depth, int alpha, int beta)
>{
> if (depth == 0)
> return Evaluate();
> MakeNullMove();
> val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
> UnmakeNullMove();
> if (val >= beta)
> return beta;
> GenerateLegalMoves();
> while (MovesLeft()) {
> MakeNextMove();
> val = -AlphaBeta(depth - 1, -beta, -alpha);
> UnmakeMove();
> if (val >= beta) // Delete these to get straight
> return beta; // min-max instead of alpha-beta.
> if (val > alpha)
> alpha = val;
> }
> return alpha;
Null-move can cause you to miss tactics, up to <reduction> plies. That is to be
expected. The hope is that there is an overall gain in play. You cannot judge
from a single position.
Bruce's code looks right to me. Here is what Beowulf does:
/* -----------==== TRY A NULL MOVE ====------------- */
/* Perform a NULL move if; (1) We're not on the first 2 plies (2) We're
* not in the process of performing a NULL move right now (Note - DoNull
* stores whether or not we are OK to NULL move, not whether we are doing
* one, hence testing for TRUE not FALSE) (3) We're not in check (4)
* There are enough pieces left to avoid high risk of zugzwang (5) We're
* on skill level 6 or higher */
if (USE_NULL && ply > 1 && DoNull && !inchk && (nullreduction = NullOK(B,
depth)) && Skill > 4) {
/* Increase the NULL reduction by one ply to account for the fact
* that we've passed on this move. */
nullreduction += ONEPLY;
/* Set up temporary flags to store the board position */
ep_carry = B->ep;
B->ep = -1;
/* Do the null move reduced-depth search */
B->side = Opponent(B->side);
if (depth - nullreduction < ONEPLY)
score = -Quiesce(B, -tbeta, -tbeta + 1, ply + 1, 0);
else
score = -Search(B, -tbeta, -tbeta + 1, depth - nullreduction, ply +
1, 0, 0, FALSE, -1);
/* Put things back */
B->side = Opponent(B->side);
/* Verification Search. Here we re-search this node at a shallower
* depth if the score is >= beta. The reason we do this is simple:
* we want to make sure that this really is a strong node, and
* therefore worth chopping. This time, instead of actually making a
* NULL move, we play a proper move. Note that we don't bother doing
* this when close to the frontier nodes (this would take us into the
* qsearch). We only fail high if this second search ALSO fails
* high. */
if (USE_VERIFICATION && score >= tbeta && depth - nullreduction >=
ONEPLY)
score = Search(B, tbeta - 1, tbeta, depth - nullreduction, ply + 1,
0, fifty, FALSE, LastMove);
/* Replace the En-Passant flag */
B->ep = ep_carry;
/* If this move returned CM then we must be careful because there is
* a CM threat dangerously close! Only do this on highest skill
* level. */
if (IsCM(score) == -1 && Skill == 10)
threat = TRUE;
/* A fail high means that the positional score here is so high that
* even if the opponent is given a 'free move' then he still can't
* improve his position enough to increase the value of alpha. If
* this is the case then clearly the current position is very strong.
* In fact it is so strong that the opponent would never let it occur
* in the first place, so we should cause a cut off. */
if (score >= tbeta) {
HashUpdate(B, score, BestMoveRet, depth + ONEPLY - nullreduction,
HASH_LOWER, FALSE, ply);
return score;
}
}
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.