 |
 |
 |
 |
Writing a chess program in 99 steps
19 Null move pruning
We have seen in Section 14 that if the value returned by the alpha-beta search exceeds beta, we don't have to search any further and can cut-off the remainder of the current branch. Doing a null move is a way of getting a quick (early) indication that it's pretty safe to do a beta cut-off, before actually having completed the full search for this branch. This is based on the assumption that doing a move normally improves the position for the side to move. So, if the side to move passes (i.e. does NOT make a move, or makes a null move) and still have a position strong enough to produce a beta cut-off, then the current position will almost certainly produce a cut-off if the current side to move DOES make a move.
The benefit of null move pruning lies in the fact that a null move search is done at a shallower depth (usually 3 plies less than a full search). If the shallow null move search produces a cutoff, it is assumed that a full-depth search, without null move, would also have produced a beta-cutoff. Since a shallower search is faster, the cutoff is also found much faster. If the shallow search fails to produce a cutoff, then we just continue doing a full-depth search.
There is a possible problem with null move pruning: it can produce false positives, i.e. it can produce a beta cutoff where a full search would not have found one. This happens in zugzwang positions. In zugzwang positions, the side to move only has bad moves to choose from, every move makes things worse. Doing no move (which of course is illegal in chess) would actually be the best option. See the diagram below (with black to move) for an example of a zugzwang position. Moving the black pawn to h6 or h5 will loose the game.
To avoid problems with null move, most programs put restrictions
on its use.
Winglet does not allow null moves if any of the
following is true:
1. The previous move was also a null move (two null moves in a row
would just reduce the normal search depth significantly).
2. The search is following the PV (we need to have at least one good
leaf node value before we can start looking for beta cutoffs)
3. The side to move is in check (in this case, a null move would allow the opponent to
capture the king).
4. The side to move has no queens, rooks, bishops or knights (if a side
has insufficient mobile material, it's more prone to getting tangled up in zugzwang
positions).
There are some important changes in makemove.cpp and movegen.cpp that are not listed hereYou can get the latest versions here
step 91: globals.h
#ifndef WINGLET_GLOBALS_H
#define WINGLET_GLOBALS_H
(...)
// Nullmove parameters:
extern const int NULLMOVE_REDUCTION = 4; // equivalent to R=3
// Material (excluding pawns) must be > NULLMOVE_LIMIT to allow a nullmove:
// Setting this value to 299 ensures that null moves are not done if the
// side to move has no major or minor pieces
extern const int NULLMOVE_LIMIT = KNIGHT_VALUE - 1;
#endif
step 92: extglobals.h
#ifndef WINGLET_EXTGLOBALS_H
#define WINGLET_EXTGLOBALS_H
(...)
extern const int NULLMOVE_REDUCTION;
extern const int NULLMOVE_LIMIT;
#endif
step 93: board.h
#ifndef WINGLET_BOARD_H_
#define WINGLET_BOARD_H_
#include "defines.h"
#include "move.h"
#include "gameline.h"
#include "timer.h"
struct Board
{
BitMap whiteKing, whiteQueens, whiteRooks, whiteBishops, whiteKnights, whitePawns;
BitMap blackKing, blackQueens, blackRooks, blackBishops, blackKnights, blackPawns;
BitMap whitePieces, blackPieces, occupiedSquares;
unsigned char nextMove; // WHITE_MOVE or BLACK_MOVE
unsigned char castleWhite; // White's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
unsigned char castleBlack; // Black's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
int epSquare; // En-passant target square after double pawn move
int fiftyMove; // Moves since the last pawn move or capture
U64 hashkey; // Random 'almost' unique signature for current board position.
// additional variables:
int square[64]; // incrementally updated, this array is usefull if we want to
// probe what kind of piece is on a particular square.
int Material; // incrementally updated, total material balance on board,
// in centipawns, from white’s side of view
int totalWhitePawns; // sum of P material value for white (in centipawns)
int totalBlackPawns; // sum of P material value for black (in centipawns)
int totalWhitePieces; // sum of Q+R+B+N material value for white (in centipawns)
int totalBlackPieces; // sum of Q+R+B+N material value for black (in centipawns)
BOOLTYPE viewRotated; // only used for displaying the board. TRUE or FALSE.
// storing moves:
Move moveBuffer[MAX_MOV_BUFF]; // all generated moves of the current search tree are stored in this array.
int moveBufLen[MAX_PLY]; // this arrays keeps track of which moves belong to which ply
int endOfGame; // index for board.gameLine
int endOfSearch; // index for board.gameLine
GameLineRecord gameLine[MAX_GAME_LINE];
// search variables:
int triangularLength[MAX_PLY];
Move triangularArray[MAX_PLY][MAX_PLY];
Timer timer;
U64 msStart, msStop;
int searchDepth;
int lastPVLength;
Move lastPV[MAX_PLY];
unsigned int whiteHeuristics[64][64];
unsigned int blackHeuristics[64][64];
BOOLTYPE followpv;
BOOLTYPE allownull;
U64 inodes;
void init();
int eval();
Move think();
int minimax(int ply, int depth);
int alphabeta(int ply, int depth, int alpha, int beta);
int alphabetapvs(int ply, int depth, int alpha, int beta);
int qsearch(int ply, int alpha, int beta);
void displaySearchStats(int mode, int depth, int score);
BOOLTYPE isEndOfgame(int &legalmoves, Move &singlemove);
int repetitionCount();
void mirror();
void initFromSquares(int input[64], unsigned char next, int fiftyM, int castleW, int castleB, int epSq);
void display();
void rememberPV();
void selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv);
void addCaptScore(int &ifirst, int &index);
int SEE(Move &move);
BitMap attacksTo(int &target);
BitMap revealNextAttacker(BitMap &attackers, BitMap &nonremoved, int &target, int &heading);
};
#endif
step 94: search.cpp
#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include "defines.h"
#include "extglobals.h"
#include "protos.h"
#include "board.h"
#include "timer.h"
Move Board::think()
{
// ===========================================================================
// This is the entry point for search, it is intended to drive iterative deepening
// The search stops if (whatever comes first):
// - there is no legal move (checkmate or stalemate)
// - there is only one legal move (in this case we don't need to search)
// **later** - time is up
// - the search is interrupted by the user, or by winboard
// - the search depth is reached
// ===========================================================================
int score, legalmoves, currentdepth;
Move singlemove;
// ===========================================================================
// Check if the game has ended, or if there is only one legal move,
// because then we don't need to search:
// ===========================================================================
if (isEndOfgame(legalmoves, singlemove)) return NOMOVE;
if (legalmoves == 1)
{
std::cout << "forced move: "; displayMove(singlemove); std::cout << std::endl;
return singlemove;
}
// ===========================================================================
// There is more than legal 1 move, so prepare to search:
// ===========================================================================
lastPVLength = 0;
memset(lastPV, 0 , sizeof(lastPV));
memset(whiteHeuristics, 0, sizeof(whiteHeuristics));
memset(blackHeuristics, 0, sizeof(blackHeuristics));
inodes = 0;
// display console header
displaySearchStats(1, 0, 0);
timer.init();
msStart = timer.getms();
// iterative deepening:
for (currentdepth = 1; currentdepth <= searchDepth; currentdepth++)
{
// clear the buffers:
memset(moveBufLen, 0, sizeof(moveBufLen));
memset(moveBuffer, 0, sizeof(moveBuffer));
memset(triangularLength, 0, sizeof(triangularLength));
memset(triangularArray, 0, sizeof(triangularArray));
followpv = true;
allownull = true;
score = alphabetapvs(0, currentdepth, -LARGE_NUMBER, LARGE_NUMBER);
msStop = timer.getms();
displaySearchStats(2, currentdepth, score);
// stop searching if the current depth leads to a forced mate:
if ((score > (CHECKMATESCORE-currentdepth)) || (score < -(CHECKMATESCORE-currentdepth)))
currentdepth = searchDepth;
}
return (lastPV[0]);
}
int Board::alphabetapvs(int ply, int depth, int alpha, int beta)
{
// PV search
int i, j, movesfound, pvmovesfound, val;
triangularLength[ply] = ply;
if (depth <= 0)
{
followpv = false;
return qsearch(ply, alpha, beta);
}
// repetition check:
if (repetitionCount() >= 3) return DRAWSCORE;
// now try a null move to get an early beta cut-off:
if (!followpv && allownull)
{
if ((nextMove && (board.totalBlackPieces > NULLMOVE_LIMIT)) || (!nextMove && (board.totalWhitePieces > NULLMOVE_LIMIT)))
{
if (!isOwnKingAttacked())
{
allownull = false;
inodes++;
nextMove = !nextMove;
hashkey ^= KEY.side;
val = -alphabetapvs(ply, depth - NULLMOVE_REDUCTION, -beta, -beta+1);
nextMove = !nextMove;
hashkey ^= KEY.side;
allownull = true;
if (val >= beta) return val;
}
}
}
allownull = true;
movesfound = 0;
pvmovesfound = 0;
moveBufLen[ply+1] = movegen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
selectmove(ply, i, depth, followpv);
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
movesfound++;
if (!ply) displaySearchStats(3, ply, i);
if (pvmovesfound)
{
val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
if ((val > alpha) && (val < beta))
{
// in case of failure, proceed with normal alphabeta
val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha);
}
}
// normal alphabeta
else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha);
unmakeMove(moveBuffer[i]);
if (val >= beta)
{
// update the history heuristic
if (nextMove)
blackHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()] += depth*depth;
else
whiteHeuristics[moveBuffer[i].getFrom()][moveBuffer[i].getTosq()] += depth*depth;
return beta;
}
if (val > alpha)
{
alpha = val; // both sides want to maximize from *their* perspective
pvmovesfound++;
triangularArray[ply][ply] = moveBuffer[i]; // save this move
for (j = ply + 1; j < triangularLength[ply+1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j]; // and append the latest best PV from deeper plies
}
triangularLength[ply] = triangularLength[ply+1];
if (!ply)
{
msStop = timer.getms();
displaySearchStats(2, depth, val);
}
}
}
else unmakeMove(moveBuffer[i]);
}
}
// update the history heuristic
if (pvmovesfound)
{
if (nextMove)
blackHeuristics[triangularArray[ply][ply].getFrom()][triangularArray[ply][ply].getTosq()] += depth*depth;
else
whiteHeuristics[triangularArray[ply][ply].getFrom()][triangularArray[ply][ply].getTosq()] += depth*depth;
}
// 50-move rule:
if (fiftyMove >= 100) return DRAWSCORE;
// Checkmate/stalemate detection:
if (!movesfound)
{
if (isOwnKingAttacked()) return (-CHECKMATESCORE+ply-1);
else return (STALEMATESCORE);
}
return alpha;
}
(...)
|
|
|
|
|
 |
|
last update: Saturday 02 July 2011