Then of course the first step is to write a move generator, and this needs a perft function for verification.
Since I have seen some other using nullmove in perft calculations, I also gave this a try.
My results were faster than I expected. Here are some results compared to:
1. Mine with nullmove and popcount
2. Mine with popcount
3. Mine with generating all moves to movelist, then bulk count
4. gperft 1.1 by Paul Byrne (using nullmove as I understand)
5. qperft.exe by H.G.Müller
Free. This tells the fraction of nodes found by nullmove in column 1.
All results are single threaded, no unique positions, no hash, on an i7 2600K@3.4GHz
CPW 1: Start position
FEN rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Code: Select all
1 2 3 4 5 Free
d6 119060324 0.13 0.25 0.44 0.700 71.20%
d7 3195901860 3.47 6.38 11.42 5.000 18.000 66.43%
d8 84998978956 92.96 172.66 311.96 135.000 480.000 64.55%FEN r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w QKqk - 0 1
Code: Select all
1 2 3 4 5 Free
d5 193690690 0.20 0.28 0.60 - 0.987 40.39%
d6 8031647685 9.61 12.55 26.71 12.046 44.081 29.85%
d7 374190009323 385.60 540.42 - 514.651 - 39.16%Of course, if there are any questions, Ill be happy to answer.
For doing nullmove, I generate some helper bitboards:
Code: Select all
// Perft nullmove helper variables
U64 BtmSpace; // BTM move space = most attacks + piece occupation + potential pawn pushes
U64 NoTouch; // Squares around BTM king that must not be attacked
U64 DoTouch; // Squares around BTM king that must be attacked
U64 NoIntercept; // Squares in slider rays that block attacks on DoTouch
U64 Pinned2NoTouch; // WTM pieces pinned to NoTouch by WTM sliders
U64 WtmAtks; // WTM attacks union
U64 ExtBishKVA; // BTM king xray vulnerability, for where QB (QR) can not move freely
U64 ExtRookKVA; // into, because it will make pins (when not already pinned)
U64 NoTouchBishKVA; // Not to set QB on (prevents BTM king moves to NoTouch bb)
U64 NoTouchRookKVA; // Not to set QR on
Code: Select all
#define QR(c) (Pcs[BQueen+8*c] | Pcs[BRook+8*c])
#define QB(c) (Pcs[BQueen+8*c] | Pcs[BBishop+8*c])
#define QMASK(c) (Mag[st->KingSquare[c]].RMask | Mag[st->KingSquare[c]].BMask)
#define QKVA (st->BishKVA | st->RookKVA)Code: Select all
template <TColour WTM>
U64 PositionClass::GenSpace(PosState *st)
// Generates a BB of squares not to be moved from or to when using nullmove in perft.
{
U64 Atk = Pcs[BPcs+WTM]; // Piece occupation
U64 Pieces = Pcs[BRook+8*WTM] | Pcs[BQueen+8*WTM];
while (Pieces) {
int fr = FirstOne(Pieces); Pieces &= Pieces-1;
U64 Ptn = RookAttacks(fr, Pcs[AllPcs]);
Atk |= SetBit(fr) & BORDER ? Ptn : Ptn & ~BORDER;
}
Pieces = Pcs[BBishop+8*WTM] | Pcs[BQueen+8*WTM];
while (Pieces) {
int fr = FirstOne(Pieces); Pieces &= Pieces-1;
Atk |= BishAttacks(fr, Pcs[AllPcs]) & ~BORDER;
}
Pieces = Pcs[BPawn+8*WTM];
Atk |= WTM ? (~FILE_A & Pieces)>>7 : (~FILE_A & Pieces)<<9;
Atk |= WTM ? (~FILE_H & Pieces)>>9 : (~FILE_H & Pieces)<<7;
Atk |= WTM ? Pieces>>8 : Pieces<<8; // Pawn push
Pieces = WTM ? (Pieces & RANK_2)>>8 : (Pieces & RANK_7)<<8;
Pieces &= ~Pcs[AllPcs];
Atk |= WTM ? Pieces>>8 : Pieces<<8; // Pawn double push
Atk |= KingAttacks[st->KingSquare[WTM]];
return Atk;
}Code: Select all
template <TColour WTM>
void PositionClass::GenNullMoveBBs(PosState *st)
// Generates BtmSpace, NoTouch, DoTouch, NoIntercept, Pinned2NoTouch, WtmAtks
{
const TColour BTM = WTM ? BLACK : WHITE;
U64 Atk, Pieces, Ptn;
int ksqr = st->KingSquare[BTM];
BtmSpace = GenSpace<BTM>(st);
NoTouch = ~Pcs[BPcs+BTM] & KingAttacks[ksqr] | SetBit(ksqr);
if (st->CastlingRights) {
if (WTM && !(Pcs[AllPcs] & 0x0000000000000006ull) && st->CastlingRights & SetBit(H8)) NoTouch |= SetBit(G8);
if (WTM && !(Pcs[AllPcs] & 0x0000000000000070ull) && st->CastlingRights & SetBit(A8)) NoTouch |= SetBit(C8);
if (BTM && !(Pcs[AllPcs] & 0x0600000000000000ull) && st->CastlingRights & SetBit(H1)) NoTouch |= SetBit(G1);
if (BTM && !(Pcs[AllPcs] & 0x7000000000000000ull) && st->CastlingRights & SetBit(A1)) NoTouch |= SetBit(C1);
}
NoIntercept = 0; Pinned2NoTouch = 0; WtmAtks = 0;
Pieces = QR(WTM);
while (Pieces) { // WtmAtks, Pinned2NoTouch, NoIntercept
int fr = FirstOne(Pieces); Pieces &= Pieces-1;
WtmAtks |= Atk = RookAttacks(fr, Pcs[AllPcs]);
if ((Mag[fr].RMask & NoTouch) == 0) continue;
// Direct attacks on NoTouch and BTM pieces in BTM king vicinity
Ptn = Atk & (NoTouch | Pcs[BPcs+BTM] & KingAttacks[ksqr]);
while (Ptn) {
NoIntercept |= Atk & RookAttacks(FirstOne(Ptn), Pcs[AllPcs]);
Ptn &= Ptn-1;
}
// Pinned2NoTouch = WTM pieces (maybe) pinned to NoTouch
Ptn = Atk & Pcs[BPcs+WTM]; // Candidate pinned pieces
Ptn = NoTouch & RookAttacks(fr, Pcs[AllPcs] ^ Ptn); // Xray attacks on NoTouch
if (Ptn) {
// Pinned2NoTouch |= Atk & Pcs[BPcs+WTM] & Mag[FirstOne(Ptn)].RMask;
Pinned2NoTouch |= Atk & Pcs[BPcs+WTM] & RookAttacks(FirstOne(Ptn), Pcs[AllPcs]);
Ptn &= Ptn-1;
}
}
Pieces = QB(WTM);
while (Pieces) { // WtmAtks, Pinned2NoTouch, NoIntercept
int fr = FirstOne(Pieces); Pieces &= Pieces-1;
WtmAtks |= Atk = BishAttacks(fr, Pcs[AllPcs]);
if ((Mag[fr].BMask & NoTouch) == 0) continue;
// Direct attacks on NoTouch and BTM pieces in BTM king vicinity
Ptn = Atk & (NoTouch | Pcs[BPcs+BTM] & KingAttacks[ksqr]);
while (Ptn) { // Black bishop at e3 may attack g1 and c1
NoIntercept |= Atk & BishAttacks(FirstOne(Ptn), Pcs[AllPcs]);
Ptn &= Ptn-1;
}
// Pinned2NoTouch = WTM pieces (maybe) pinned to NoTouch
Ptn = Atk & Pcs[BPcs+WTM]; // Candidate pinned pieces
Ptn = NoTouch & BishAttacks(fr, Pcs[AllPcs] ^ Ptn); // Xray attacks on NoTouch
if (Ptn) {
// Pinned2NoTouch |= Atk & Pcs[BPcs+WTM] & Mag[FirstOne(Ptn)].BMask;
Pinned2NoTouch |= Atk & Pcs[BPcs+WTM] & BishAttacks(FirstOne(Ptn),Pcs[AllPcs]);
Ptn &= Ptn-1;
}
}
WtmAtks |= KingAttacks[st->KingSquare[WTM]];
Pieces = Pcs[BKnight+8*WTM];
while (Pieces) {
WtmAtks |= KnightAttacks[FirstOne(Pieces)];
Pieces &= Pieces-1;
}
WtmAtks |= WTM ? (~FILE_H & Pcs[WPawn])>>9 : (~FILE_H & Pcs[BPawn])<<7; // East
WtmAtks |= WTM ? (~FILE_A & Pcs[WPawn])>>7 : (~FILE_A & Pcs[BPawn])<<9; // West
DoTouch = NoTouch & WtmAtks;
NoTouch ^= DoTouch; // If separated, a piece that is not attacking NoTouch may attack DoTouch
ExtBishKVA = ExtRookKVA = NoTouchBishKVA = NoTouchRookKVA = 0;
if (QB(WTM)) { // Alternative code
Ptn = (BishAttacks(ksqr, Pcs[AllPcs]) & Pcs[BPcs+BTM]) ^ Pcs[AllPcs];
ExtBishKVA = BishAttacks(ksqr, Ptn); // Xray BTM pieces
Ptn = NoTouch;
while (Ptn) {
NoTouchBishKVA |= BishAttacks(FirstOne(Ptn), Pcs[AllPcs]);
Ptn &= Ptn-1;
}
}
if (QR(WTM)) { // Alternative code
Ptn = (RookAttacks(ksqr, Pcs[AllPcs]) & Pcs[BPcs+BTM]) ^ Pcs[AllPcs];
ExtRookKVA = RookAttacks(ksqr, Ptn); // Xray BTM pieces
Ptn = NoTouch;
while (Ptn) {
NoTouchRookKVA |= RookAttacks(FirstOne(Ptn), Pcs[AllPcs]);
Ptn &= Ptn-1;
}
}
}Code: Select all
template <TColour WTM>
U64 PositionClass::PerftNullmove(PosState *st)
{
const TColour BTM = WTM ? BLACK : WHITE;
(st+1)->CastlingRights = st->CastlingRights; (st+1)->EpSquare = NO_SQUARE;
(st+1)->KingSquare[BTM] = st->KingSquare[BTM]; (st+1)->KingSquare[WTM] = st->KingSquare[WTM];
CheckDetect<BTM>(st+1); // Need KVA's for (st+1)
int NullMoveCt = ((st+1)->RookKVA | (st+1)->BishKVA) ? MovgenPopCount<BTM, ASSUME_PINS>(st+1)
: MovgenPopCount<BTM, NO_PINS>(st+1);
GenNullMoveBBs<WTM>(st);
TMove MoveList[MAXMOVES], *LM = MoveList, *M = MoveList;
TMove MoveListNm[MAXMOVES], *LastMoveNm, *Mnm = MoveListNm;
int fr, to, FreeMoves = 0;
int ksqr = st->KingSquare[BTM];
U64 Atk, RestAtk, Pieces, Ptn;
//--------------------------------------------------------------------------
// LM = MovgenQueens<WTM, ASSUME_PINS>(st, LM);
Pieces = Pcs[BQueen+8*WTM];
while (Pieces) {
fr = FirstOne(Pieces); Pieces &= Pieces-1;
if (SetBit(fr) & (QKVA | BtmSpace | ExtBishKVA | ExtRookKVA)) {
LM = MovgenQueen<WTM, ASSUME_PINS>(st, LM, fr);
continue;
}
Atk = RookAttacks(fr, Pcs[AllPcs]) | BishAttacks(fr, Pcs[AllPcs]);
if (Atk & DoTouch) {
LM = MovgenQueen<WTM, NO_PINS>(st, LM, fr);
continue;
}
Atk &= ~Pcs[BPcs+WTM];
RestAtk = Atk & (BtmSpace | NoTouchBishKVA | NoTouchRookKVA | ExtBishKVA | ExtRookKVA);
Atk ^= RestAtk;
FreeMoves += PopCount(Atk);
fr = (fr<<6) + ((BQueen+8*WTM)<<12);
while (RestAtk) {
to = FirstOne(RestAtk); RestAtk &= RestAtk-1;
*LM++ = fr + to + (Board[to]<<16);
}
}
//--------------------------------------------------------------------------
// LM = MovgenRooks<WTM, ASSUME_PINS>(st, LM);
Pieces = Pcs[BRook+8*WTM];
while (Pieces) {
fr = FirstOne(Pieces); Pieces &= Pieces-1;
if (SetBit(fr) & (QKVA | BtmSpace | Pinned2NoTouch | ExtBishKVA | ExtRookKVA)) {
LM = MovgenRook<WTM, ASSUME_PINS>(st, LM, fr);
continue;
}
Atk = RookAttacks(fr, Pcs[AllPcs]);
if (Atk & DoTouch) {
LM = MovgenRook<WTM, NO_PINS>(st, LM, fr);
continue;
}
Atk &= ~Pcs[BPcs+WTM];
RestAtk = Atk & (BtmSpace | NoTouchBishKVA | NoTouchRookKVA | ExtBishKVA | ExtRookKVA);
RestAtk |= Atk & NoIntercept;
Atk ^= RestAtk;
FreeMoves += PopCount(Atk);
fr = (fr<<6) + ((BRook+8*WTM)<<12);
while (RestAtk) {
to = FirstOne(RestAtk); RestAtk &= RestAtk-1;
*LM++ = fr + to + (Board[to]<<16);
}
}
//--------------------------------------------------------------------------
// LM = MovgenBishops<WTM, ASSUME_PINS>(st, LM);
Pieces = Pcs[BBishop+8*WTM];
while (Pieces) {
fr = FirstOne(Pieces); Pieces &= Pieces-1;
if (SetBit(fr) & (QKVA | BtmSpace | Pinned2NoTouch | ExtBishKVA | ExtRookKVA)) {
LM = MovgenBishop<WTM, ASSUME_PINS>(st, LM, fr);
continue;
}
Atk = BishAttacks(fr, Pcs[AllPcs]);
if (Atk & DoTouch) {
LM = MovgenBishop<WTM, NO_PINS>(st, LM, fr);
continue;
}
Atk &= ~Pcs[BPcs+WTM];
RestAtk = Atk & (BtmSpace | NoTouchBishKVA | NoTouchRookKVA | ExtBishKVA | ExtRookKVA);
RestAtk |= Atk & NoIntercept;
Atk ^= RestAtk;
FreeMoves += PopCount(Atk);
fr = (fr<<6) + ((BBishop+8*WTM)<<12);
while (RestAtk) {
to = FirstOne(RestAtk); RestAtk &= RestAtk-1;
*LM++ = fr + to + (Board[to]<<16);
}
}
//--------------------------------------------------------------------------
// LM = MovgenKnights<WTM, ASSUME_PINS>(st, LM);
Pieces = Pcs[BKnight+8*WTM];
while (Pieces) {
fr = FirstOne(Pieces); Pieces &= Pieces-1;
if (SetBit(fr) & (QKVA | BtmSpace | Pinned2NoTouch | ExtBishKVA & ~BORDER | ExtRookKVA)) {
LM = MovgenKnight<WTM, ASSUME_PINS>(st, LM, fr);
continue;
}
Atk = KnightAttacks[fr];
if (Atk & DoTouch) {
LM = MovgenKnight<WTM, NO_PINS>(st, LM, fr);
continue;
}
Atk &= ~Pcs[BPcs+WTM];
RestAtk = Atk & (BtmSpace | ExtBishKVA & ~BORDER | ExtRookKVA);
RestAtk |= Atk & NoIntercept;
Ptn = RestAtk ^ Atk;
while (Ptn) {
to = FirstOne(Ptn); Ptn &= Ptn-1;
if (KnightAttacks[to] & NoTouch) RestAtk |= SetBit(to);
}
Atk ^= RestAtk;
FreeMoves += PopCount(Atk);
fr = (fr<<6) + ((BKnight+8*WTM)<<12);
while (RestAtk) {
to = FirstOne(RestAtk); RestAtk &= RestAtk-1;
*LM++ = fr + to + (Board[to]<<16);
}
}
//--------------------------------------------------------------------------
// LM = MovgenPawns<WTM, ASSUME_PINS>(st, LM);
TMove PawnMoves[32], *MPL;
MPL = MovgenPawns<WTM, ASSUME_PINS>(st, PawnMoves);
M = PawnMoves;
while (M < MPL) {
if (SPECIAL2(*M)) { *LM++ = *M++; continue; } // en-passant and promotions
fr = FROM(*M), to = TO(*M);
if (SetBit(fr) & (BtmSpace | QKVA | Pinned2NoTouch)) { *LM++ = *M++; continue; }
if (SetBit(fr) & ~BORDER & (ExtBishKVA | ExtRookKVA)) { *LM++ = *M++; continue; }
if (SetBit(to) & (BtmSpace | NoIntercept)) { *LM++ = *M++; continue; }
if (SetBit(to) & ~BORDER & (ExtBishKVA | ExtRookKVA)) { *LM++ = *M++; continue; }
if (PawnAttacks[WTM][fr] & DoTouch) { *LM++ = *M++; continue; }
if (PawnAttacks[WTM][to] & NoTouch) { *LM++ = *M++; continue; }
if (BtmSpace & SetBit(fr+8-16*WTM)) { *LM++ = *M++; continue; } // Possible ep square
FreeMoves++;
M++;
}
//--------------------------------------------------------------------------
// LM = MovgenKing<WTM>(st, LM);
TMove KingMoves[8], *MKL;
MKL = MovgenKing<WTM>(st, KingMoves);
M = KingMoves;
while (M < MKL) {
if (SPECIAL2(*M)) {*LM++ = *M++; continue; } // castlings
fr = FROM(*M), to = TO(*M);
if (SetBit(fr) & (BtmSpace | Pinned2NoTouch | ExtBishKVA & ~BORDER | ExtRookKVA)) { *LM++ = *M++; continue; }
if (SetBit(to) & (BtmSpace | NoIntercept | ExtBishKVA & ~BORDER | ExtRookKVA)) { *LM++ = *M++; continue; }
if (KingAttacks[fr] & DoTouch) { *LM++ = *M++; continue; }
if (KingAttacks[to] & NoTouch) { *LM++ = *M++; continue; }
FreeMoves++;
M++;
}
//--------------------------------------------------------------------------
Nfree += FreeMoves * NullMoveCt; // Global counter
int RestNodes = 0; // Nodes found the hard way
M = MoveList;
while (M < LM) {
MakeMove<WTM,NO_HASH>(st, *M);
if (CheckDetect<BTM>(st+1)) RestNodes += MovgenEvasionsPopCount<BTM>(st+1);
else {
if ((st+1)->BishKVA | (st+1)->RookKVA)
RestNodes += MovgenPopCount<BTM, ASSUME_PINS>(st+1);
else RestNodes += MovgenPopCount<BTM, NO_PINS>(st+1);
}
UnmakeMove<WTM>(st, *M++);
}
return (U64)(FreeMoves * NullMoveCt + RestNodes);
}Code: Select all
template <TColour WTM>
int PositionClass::CheckDetect(PosState *st)
// Detects if WTM is in check or double check
// Returns 0: no check, 1: single check, >1: double check
// Generates BishKVA and RookKVA
// Generates CheckAtk, all squares to be intercepted for evading a single check
{
const TColour BTM = WTM ? BLACK : WHITE;
int ksqr = st->KingSquare[WTM];
st->RookKVA = st->BishKVA = 0;
if (Mag[ksqr].RMask & QR(BTM)) {
st->RookKVA = RookAttacks(ksqr, Pcs[AllPcs]);
// See if st->RookKVA may be reduced
if (st->EpSquare == NO_SQUARE && (st->RookKVA & QR(BTM)) == 0) { // Not in rook check
U64 Atk = Pcs[BPcs+WTM] & st->RookKVA; // Target WTM pieces only
Atk = RookAttacks(ksqr, Pcs[AllPcs] ^ Atk); // Xray attacks
if ((Atk & QR(BTM)) == 0) st->RookKVA = 0; // No rook pins
}
}
if (Mag[ksqr].BMask & QB(BTM)) {
st->BishKVA = BishAttacks(ksqr, Pcs[AllPcs]);
if (st->EpSquare == NO_SQUARE && (st->BishKVA & QB(BTM)) == 0) { // Not in bishop check
U64 Atk = Pcs[BPcs+WTM] & st->BishKVA; // Target WTM pieces only
Atk = BishAttacks(ksqr, Pcs[AllPcs] ^ Atk); // Xray attacks
if ((Atk & QB(BTM)) == 0) st->BishKVA = 0;
}
}
st->InCheck = 0;
st->CheckAtk = 0ull;
U64 Atk = PawnAttacks[WTM][ksqr] & Pcs[BPawn+8*BTM]
| KnightAttacks[ksqr] & Pcs[BKnight+8*BTM];
if (Atk) {
st->InCheck = 1;
st->CheckAtk = Atk;
}
Atk = st->RookKVA & QR(BTM);
if (Atk) {
st->InCheck += 1 + (PopCount(Atk) > 1);
Atk |= RookAttacks(FirstOne(Atk), Pcs[AllPcs]) & st->RookKVA;
st->CheckAtk |= Atk;
}
Atk = st->BishKVA & QB(BTM);
if (Atk) {
st->InCheck += 1 + (PopCount(Atk) > 1);
Atk |= BishAttacks(FirstOne(Atk), Pcs[AllPcs]) & st->BishKVA;
st->CheckAtk |= Atk;
}
return st->InCheck;
}
