OK, I added null-move pruning. This had the expected effect:
The fraction of non-captures is strongly reduced; only 6% of the real moves is now a non-capture. And far less nodes are needed in total to get the same depth. We also see that QS on the average gets more difficult: there are nearly 15 times as many QS as other nodes now, meaning that each QS must have had on the average at least 15 nodes in its sub-tree. This is because NMP makes the search postpone captures when it is already ahead, preferring to null-move instead, and leaving the resolution of the position to QS.
Code: Select all
#include <stdio.h>
#include <time.h>
#include <ctype.h>
#define PATH 0 // ply==0 || path[0]==0x1450 && (ply==1 || path[1]==0x3122 && (ply==2 || path[2]==0x1122 && (ply==3 || path[3]==0x5443 && (ply==4))))
#define WHITE 16
#define BLACK 32
#define COLOR (WHITE|BLACK) // also used for edge guards
#define INF 8000
#define CAPTURED 255
#define MARGIN 30 // for futility pruning / lazy eval
#define STMKEY 123456789
#define KIWIPETE "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1"
#define FIDE "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"
#define PST(PIECE, SQR) pstData[offs[PIECE] + SQR]
#define KEY(PIECE, SQR) zobrist[offs[PIECE] + SQR]
int pstData[7*128];
long long int zobrist[7*128];
unsigned char rawBoard[12*16]; // 0x88 board with 2-wide rim of edge guards
#define board (rawBoard + 2*17)
int stm; // side to move (WHITE or BLACK)
int location[48], offs[48], mvv[48]; // piece list
int firstDir[32] = { // offset of move list in steps[] table, per piece
1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 31, 31, 36, 36, 27, 18, // white pieces
5, 5, 5, 5, 5, 5, 5, 5, 9, 9, 31, 31, 36, 36, 27, 18, // black pieces
};
signed char steps[] = {
0,
16, 15, 17, 0, // 1 wP
-16, -15, -17, 0, // 5 bP
31, -31, 33, -33, 18, -18, 14, -14, 0, // 9 N
16, -16, 1, -1, 15, -15, 17, -17, 0, // 18 K
16, -16, 1, -1, 15, -15, 17, -17, 0, // 27 Q 31 B
16, -16, 1, -1, 0, // 36 R
};
unsigned int moveStack[10000];
int msp; // move stack pointer
int path[100], ply;
int pv[10000];
int *pvPtr = pv;
int followPV;
int nodeCnt, patCnt, genCnt, evalCnt, qsCnt, captCnt[2]; // for statistics
int pType[] = { 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6 };
int pieceVal[] = { 0, 90, 325, 350, 500, 950, 0 };
void Init()
{
int i, r, f;
char *p;
// board with rim
for(i=0; i<12*16; i++) rawBoard[i] = COLOR;
for(i=0; i<16; i++) {
offs[i+WHITE] = 128*pType[i];
offs[i+BLACK] = 128*pType[i] + 8;
mvv[i+WHITE] = mvv[i+BLACK] = 16*pType[i] << 24;
}
for(r=0; r<8; r++) for(f=0; f<8; f++) {
int s = 16*r+f;
int d = 14 - (r-3.5)*(r-3.5) - (f-4)*(f-4);
board[s] = 0;
for(i=1; i<6; i++) {
pstData[128*i+s] =
pstData[128*i+(s^0x70)+8] = pieceVal[i] + d*(i < 4) + 9*(i == 1)*r;
}
pstData[128*6+s] = pstData[128*6+(s^0x70)+8] = -d;
}
p = (char*) (zobrist + 128);
for(i=0; i<6*8*128; i++) *p++ = rand()*rand() >> 6;
}
char *Move2text(int move)
{
static char buf[10];
sprintf(buf, "%c%d%c%d", (move >> 8 & 7) + 'a', (move >> 12 & 7) + 1, (move &7) + 'a', (move >> 4 & 7) + 1);
return buf;
}
#define MOVE(F, T) (256*(F) + (T))
int MoveGen()
{
int i, first = msp;
for(i=0; i<16; i++) {
int piece = stm + i;
int from = location[piece];
if(from != CAPTURED) {
int step, dir = firstDir[piece-16];
while((step = steps[dir++])) {
int to = from;
do {
int victim = board[to += step];
if(victim) { // target square not empty
if(victim & stm) break; // own piece or edge guard
if(!(piece & 8)) { // is Pawn
if(!(step & 7)) break; // straight
}
if((victim & 15) == 15) return 0; // captures King
moveStack[--first] = MOVE(from, to) + mvv[victim] - ((piece & 15) << 24);
break;
} else { // non-capture
if(!(piece & 8)) { // is Pawn
if(step & 7) break; // diagonal
if(from - 32 & 64 && !board[to + step])
moveStack[msp++] = MOVE(from, to + step);
}
moveStack[msp++] = MOVE(from, to); // generate non-capture
}
} while(dir >= 27);
}
}
}
return first;
}
int Evaluate(int pstEval)
{
return pstEval;
}
typedef struct {
long long int hashKey, oldKey; // keys
int pstEval, oldEval, curEval; // scores
int alpha, beta; // scores
int from, to; // squares
int piece, victim; // pieces
int depth; // depth
} UndoInfo;
int MakeMove(int move, UndoInfo *u)
{
// decode the move
u->to = move & 255;
u->from = move >> 8 & 255;
u->piece = board[u->from];
u->victim = board[u->to];
// update the incremental evaluation
u->pstEval = -(u->oldEval + PST(u->piece, u->to) - PST(u->piece, u->from) + PST(u->victim, u->to));
//if(PATH) printf(" eval=%d beta=%d MARGIN=%d\n", u->pstEval, u->beta, MARGIN);
if(u->depth <= 0 && u->pstEval > u->beta + MARGIN) return -INF-1; // futility (child will stand pat)
// update hash key, and possibly abort on repetition
u->hashKey = u->oldKey ^ KEY(u->piece, u->to) ^ KEY(u->piece, u->from) ^ KEY(u->victim, u->to);
// if(REPEAT) return 0;
// update board and piece list
board[u->from] = 0;
board[u->to] = u->piece;
location[u->piece] = u->to;
location[u->victim] = CAPTURED;
path[ply++] = move & 0xFFFF; captCnt[!u->victim]++;
return INF+1; // kludge to indicate success
}
void UnMake(UndoInfo *u)
{
// restore board and piece list
ply--;
board[u->from] = u->piece;
board[u->to] = u->victim;
location[u->piece] = u->from;
location[u->victim] = u->to;
}
int Search(UndoInfo *u) // pass all parameters in a struct
{
UndoInfo undo;
int first, curMove, noncapts, alpha = u->alpha;
int *myPV = pvPtr;
nodeCnt++;
*pvPtr++ = 0; // empty PV
// QS / stand pat
if(u->depth <= 0) {
qsCnt++;
if(u->pstEval > alpha - MARGIN) { // don't bother with full eval if hopeless
undo.curEval = Evaluate(u->pstEval); evalCnt++;
if(undo.curEval > alpha) {
if(undo.curEval >= u->beta) { patCnt++; return u->beta; }
alpha = undo.curEval;
}
}
} else if(u->pstEval > u->beta - MARGIN) { // null-move pruning
int score;
undo.hashKey = u->hashKey ^ STMKEY;
undo.pstEval = -u->pstEval;
undo.alpha = -u->beta;
undo.beta = 1 - u->beta;
undo.depth = (u->depth > 3 ? u->depth - 3 : 0);
stm ^= COLOR;
score = -Search(&undo);
stm ^= COLOR;
if(score >= u->beta) return u->beta;
}
// generate moves
noncapts = msp += 70; // reserve space for new move list
first = MoveGen();
genCnt++;
if(!first) { alpha = INF; goto abort; } // King capture detected
if(followPV >= 0) { // first branch
int i, m = pv[followPV++]; // get the move
if(m) { // move to follow
m |= 255<<24; // assign highest sort priority
for(i=first; i<msp; i++) { // run through move list
if(!(m - moveStack[i] & 0xFFFF)) { // search it amongst generated moves
moveStack[--first] = m; // prepend to move list
moveStack[i] = 0; // zap PV move in list
break;
}
}
} else followPV = -1;
}
// set child & make-move parameters that are always the same
undo.oldKey = u->hashKey ^ STMKEY;
undo.oldEval = u->pstEval;
undo.depth = u->depth - 1;
undo.alpha = -u->beta;
stm ^= COLOR;
// move loop
for(curMove = first; curMove < msp; curMove++) {
int score;
unsigned int move = moveStack[curMove];
// move picker
if(curMove < noncapts) { // still has to be sorted
int i, j = curMove;
for(i=curMove+1; i<noncapts; i++) { // extract best capture
unsigned int m = moveStack[i];
if(m > move) j = i, move = m;
}
moveStack[j] = moveStack[curMove]; moveStack[curMove] = move;
} else if(u->depth <= 0) { // in QS no non-captures at all
break;
}
if(!move) continue; // skip zapped moves
// recursion
undo.beta = -alpha;
score = MakeMove(move, &undo); // rejected moves get their score here
if(score < -INF) break; // move is futile, and so will be all others
if(score > INF) { // move successfully made
score = -Search(&undo);
UnMake(&undo);
}
if(PATH) printf("%2d:%d %3d. %08x %s %5d %5d\n", ply, u->depth, curMove, move, Move2text(move), score, alpha), fflush(stdout);
// minimaxing
if(score > alpha) {
int *p;
if(score >= u->beta) {
alpha = u->beta;
break;
}
alpha = score;
p = pvPtr; pvPtr = myPV; // pop old PV
*pvPtr++ = move; // push new PV, starting with this move
while((*pvPtr++ = *p++)) {} // and append child PV
}
}
stm ^= COLOR;
abort:
msp = noncapts - 70; // pop move list
pvPtr = myPV; // pop PV (but remains above stack top)
return alpha;
}
void SearchRoot(UndoInfo *u, int maxDepth)
{
nodeCnt = patCnt = evalCnt = genCnt = qsCnt = captCnt[0] = captCnt[1] = 0;
u->alpha = -INF;
u->beta = INF;
followPV = -1; // nothing to follow at d=1
for(u->depth=1; u->depth<=maxDepth; u->depth++) { // iterative deepening
int i, score;
score = Search(u);
printf("%2d %4d %9d %d", u->depth, score, nodeCnt, 0);
for(i=0; pv[i]; i++) printf(" %s", Move2text(pv[i]));
printf("\n"), fflush(stdout);
followPV = 0; // follow this PV on next search
}
}
int Setup(UndoInfo *u, char *fen)
{
static char pieces[] = "PPPPPPPPNNBBRRQK";
int r, f, i;
for(i=WHITE; i<COLOR; i++) location[i] = CAPTURED;
for(r=0; r<8; r++) for(f=0; f<8; f++) board[16*r+f] = 0;
u->pstEval = 0; u->hashKey = 0;
r = 7; f = 0;
while(*fen) {
if(*fen == '/') r--, f = 0;
else if(*fen > '0' && *fen <= '9') f += *fen - '0'; // empties
else if(*fen >= 'A') { // piece
int color = (*fen >= 'a' ? BLACK : WHITE);
for(i=0; i<16; i++) {
if(location[color+i] == CAPTURED && !(*fen - pieces[i] & 31)) {
location[color+i] = 16*r + f;
board[16*r+f] = color + i;
u->pstEval += PST(color + i, 16*r + f)*(color == WHITE ? 1 : -1);
u->hashKey ^= KEY(color + i, 16*r + f);
break;
}
}
f++;
} else break;
fen++;
}
while(*fen == ' ') fen++;
if(*fen == 'b') u->pstEval *= -1;
return (*fen == 'b' ? BLACK : WHITE);
}
UndoInfo root;
int main()
{
time_t t;
Init();
stm = Setup(&root, FIDE);
stm = Setup(&root, KIWIPETE);
t = clock();
SearchRoot(&root, 8);
t = clock() - t;
printf("t = %6.3f sec\n", t * (1./CLOCKS_PER_SEC));
printf("%10d nodes (%3.1f Mnps)\n%10d QS (%3.1f%%)\n", nodeCnt, nodeCnt*1e-6*CLOCKS_PER_SEC/t, qsCnt, qsCnt*100./nodeCnt);
printf("%10d evals (%3.1f%%)\n%10d stand-pats (%3.1f%%)\n", evalCnt, evalCnt*100./qsCnt, patCnt, patCnt*100./qsCnt);
printf("%10d move gens\ncaptures: %3.1f%%\n", genCnt, captCnt[0]*100./(captCnt[0] + captCnt[1]));
return 0;
}
