Perft using nullmove

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
Lasse Hansen
Posts: 27
Joined: Wed May 28, 2008 1:07 pm
Location: Porsgrunn, Norway

Perft using nullmove

Post by Lasse Hansen »

Some time ago I thought I should try out some of the features of C++, and eventually rewrite my engine Sillycon from scratch using C++.
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%
CPW 2: Kiwipete position
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%
Sorry for the long post, but I didnt want to try to explain this by words.
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
Some defines used:

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)
BtmSpace is generated by the GenSpace function:

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;
}
The other helper bitboards are generated by:

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;
		}
	}
}
and the perft function for nullmove is (only called when not in check):

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);
}
The king vulnerability bitboards BishKVA and RookKVA are generated by my CheckDetect function:

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;
}
Top
User avatar
cdani
Posts: 2204
Joined: Sat Jan 18, 2014 10:24 am
Location: Andorra

Re: Perft using nullmove

Post by cdani »

Excuse my ignorance. What has to do perft with nullmove?
Thanks.
Top
User avatar
Lasse Hansen
Posts: 27
Joined: Wed May 28, 2008 1:07 pm
Location: Porsgrunn, Norway

Re: Perft using nullmove

Post by Lasse Hansen »

cdani wrote:
Excuse my ignorance. What has to do perft with nullmove?
When remaining depth in perft is 1 (before end leaf) one may use nullmove to count the number of moves for the other side (BTM) = NullMoveCt. All moves= FreeMoves (for side to move WTM) that does not influence BTM moves, perft(1) may be counted as FreeMoves * NullMoveCt. This saves the effort of making the FreeMoves, doing perft(0), and unmaking FreeMoves. The perft function may look like this:

Code: Select all

template <TColour WTM> 
U64 PositionClass::Perft(PosState *st, int depth)
{
	const TColour BTM = WTM ? BLACK : WHITE;
	TMove MoveList[MAXMOVES], *LastMove, *M;

	CheckDetect<WTM>(st);

	if (depth == 0) {
		if (st->InCheck) return MovgenEvasions<WTM>(st, MoveList) - MoveList;
		if (QKVA) return MovgenPopCount<WTM, ASSUME_PINS>(st);
		return MovgenPopCount<WTM, NO_PINS>(st); 
	}

	if (!st->InCheck && depth == 1) return PerftNullmove<WTM>(st); 

	U64 ct = 0;
	if (st->InCheck) LastMove = MovgenEvasions<WTM>(st, MoveList);
	else {
		if (QKVA) LastMove = Movgen<WTM, ASSUME_PINS>(st, MoveList);
		else  LastMove = Movgen<WTM, NO_PINS>(st, MoveList);
	}
	M = MoveList;
	while (M < LastMove) {
		MakeMove<WTM,NO_HASH>(st, *M);
		ct += Perft<BTM>(st+1, depth-1);
		UnmakeMove<WTM>(st, *M++);
	}
	return ct;
}
Top
ibid
Posts: 89
Joined: Mon Jun 13, 2011 12:09 pm

Re: Perft using nullmove

Post by ibid »

Lasse Hansen wrote:Some time ago I thought I should try out some of the features of C++, and eventually rewrite my engine Sillycon from scratch using C++.
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%
CPW 2: Kiwipete position
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%
Sorry for the long post, but I didnt want to try to explain this by words.
Of course, if there are any questions, Ill be happy to answer.
Hello,

gperft 1.1 uses a number of tricks, but not nullmove. The still unreleased 1.2 uses nullmove. I've put a windows binary for 1.2d here:
https://www.dropbox.com/s/9n0u2r048enjk ... d.zip?dl=0
This intermediate version should compute correct perfts, but has some bugs (certain command line options crash it). There are a number of optimization ideas I am still playing with before I release an official 1.2, but I am not expecting any significant speedup from this one. If you need a linux build (which is generally a little faster than windows), let me know, and I'll make one later tonight...

From the speedups between 1.1 and 1.2d on my machine, I would guess gperft might be a little faster than your nullmove version on the initial position and still noticably slower on kiwipete, but my machine is AMD so I'd love to see how it does on your machine.

I will take a look at your code later tonight when I have more time to see how similar our nullmove implementations are for perfts...

-paul
Top
User avatar
Lasse Hansen
Posts: 27
Joined: Wed May 28, 2008 1:07 pm
Location: Porsgrunn, Norway

Re: Perft using nullmove

Post by Lasse Hansen »

A little update. If the code for pawn nullmove count is replaced by this:

Code: Select all

	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 and captures
		fr = FROM(*M), to = TO(*M);
		
		if (SetBit(fr) & (BtmSpace | QKVA | Pinned2NoTouch)) { *LM++ = *M++; continue; }
		if (SetBit(to) & (BtmSpace | NoIntercept)) { *LM++ = *M++; continue; }

//		if (SetBit(fr) & ~BORDER & (ExtBishKVA | ExtRookKVA))  { *LM++ = *M++; continue; }
//		if (SetBit(to) & ~BORDER & (ExtBishKVA | ExtRookKVA))  { *LM++ = *M++; continue; }
		if (Mag[ksqr].BMask & QB(WTM)) {
			if ((SetBit(fr) | SetBit(to)) & ~BORDER & ExtBishKVA) { *LM++ = *M++; continue; }
		}
		if (Mag[ksqr].RMask & QR(WTM)) { // Pawn MUST capture to get out of BORDER, pawn cant be on 1,8'th rank
			if ((SetBit(fr) | SetBit(to)) & ~BORDER & 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++;
	}
the speed of perft with nullmove now is(single thread, no hash, no unique):

Code: Select all

CPW 1: Starting position
Perft 1             20    0.000s    0.00Mnps   0.00%              0
Perft 2            400    0.000s   36.36Mnps 100.00%            400
Perft 3           8902    0.000s  387.04Mnps  92.96%           8275
Perft 4         197281    0.000s  495.68Mnps  87.40%         172428
Perft 5        4865609    0.007s  670.47Mnps  80.67%        3925046
Perft 6      119060324    0.115s 1034.20Mnps  76.54%       91132336
Perft 7     3195901860    3.168s 1008.95Mnps  70.97%     2268291228
Perft 8    84998978956   87.564s  970.71Mnps  68.19%    57958532076
Perft 9  2439530234167 2594.017s  940.45Mnps  63.74%  1554878537163

CPW 2: Kiwipete
Perft 1             48    0.000s    0.00Mnps   0.00%              0
Perft 2           2039    0.000s  185.36Mnps  29.52%            602
Perft 3          97862    0.000s  881.64Mnps  41.60%          40715
Perft 4        4085603    0.005s  823.05Mnps  29.75%        1215301
Perft 5      193690690    0.196s  986.88Mnps  40.41%       78261264
Perft 6     8031647685    9.576s  838.74Mnps  29.85%     2397800143
Perft 7   374190009323  376.537s  993.77Mnps  39.20%   146681492105

CPW 3: En-passant traps FEN="8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -"
Perft 1             14    0.000s    0.00Mnps   0.00%              0
Perft 2            191    0.000s   12.73Mnps  15.71%             30
Perft 3           2812    0.000s   72.10Mnps   1.00%             28
Perft 4          43238    0.000s  107.02Mnps  31.00%          13402
Perft 5         674624    0.004s  159.49Mnps  21.82%         147175
Perft 6       11030083    0.038s  287.98Mnps  35.42%        3906448
Perft 7      178633661    0.565s  316.18Mnps  31.56%       56373334
Perft 8     3009794393    9.220s  326.45Mnps  37.36%     1124315382
Perft 9    50086749815  145.809s  343.51Mnps  35.26%    17658314868
When using 4GiB hash (64 bit key, replace if depth >= draft) I get these results:

Code: Select all

CPW 1: Starting position
Perft 1             20    0.000s    0.00Mnps   0.00%              0
Perft 2            400    0.000s    1.65Mnps 100.00%            400
Perft 3           8902    0.005s    1.78Mnps  92.96%           8275
Perft 4         197281    0.052s    3.83Mnps  87.40%         172428
Perft 5        4865609    0.202s   24.05Mnps  48.48%        2358884
Perft 6      119060324    0.063s 1882.35Mnps  28.00%       33338865
Perft 7     3195901860    0.719s 4443.23Mnps  11.86%      379027132
Perft 8    84998978956    9.070s 9371.41Mnps   5.34%     4535770806
Perft 9  2439530234167  114.451s 21315.01Mnps   2.07%    50610404061
Perft10 69352859712417 1756.701s 39479.03Mnps   1.11%   773050676580
Perft11 2097651003696806 48505.039s 43246.04Mnps   0.99% 20752317250614

CPW 2: Kiwipete
Perft 1             48    0.000s    0.00Mnps   0.00%              0
Perft 2           2039    0.000s    8.00Mnps  29.52%            602
Perft 3          97862    0.011s    9.06Mnps  41.60%          40715
Perft 4        4085603    0.171s   23.93Mnps  29.73%        1214553
Perft 5      193690690    0.350s  552.90Mnps  23.56%       45638917
Perft 6     8031647685    3.380s 2376.15Mnps   9.88%      793740492
Perft 7   374190009323   59.263s 6314.03Mnps   5.54%    20739894364
Perft 8 15493944087984 1340.522s 11558.15Mnps   1.95%   302161673442
PS. There is (at least) one position gperft by Paul Byrne beats my program:
CPW 3: gperft takes 139.764 seconds, mine 145.809s
Top
Aleks Peshkov
Posts: 922
Joined: Sun Nov 19, 2006 9:16 pm
Location: Russia
Full name: Aleks Peshkov

Re: Perft using nullmove

Post by Aleks Peshkov »

Wow! Interesting direction of view!

My engine generates attack bitboards for each piece (and then legal moves bitboards from this attacks for each piece separately).

In my case it is possible to detect distinct affected pieces and generate moves only for them, keeping the relevant position difference "in mind". So even non free moves could skip copy-make stage completely.
Top
ibid
Posts: 89
Joined: Mon Jun 13, 2011 12:09 pm

Re: Perft using nullmove

Post by ibid »

Lasse Hansen wrote:PS. There is (at least) one position gperft by Paul Byrne beats my program:
CPW 3: gperft takes 139.764 seconds, mine 145.809s
I'm glad such a position still exists! :)

I've been playing with a number of ways of doing nullmove-based perfts, at present I am going about it in a somewhat different way from you (assuming my quick scan of your code is semi-accurate!)

Instead of simply doing a nullmove perft and then looking for moves which will not change the perft value, I am storing extra information in the nullmove perft function. For example, the number of legal moves of each rook, bishop and queen. I then iterate though the moves and decide for each move which pieces need to be recomputed and which are guaranteed to be the same as the nullmove case. There is a balancing act there, an accurate test for a rook is as slow as simply recomputing the rook. A very quick test misses a lot of cases and recomputes too many positions.

In any case, I have played with your approach also, and, at least for me, it depends heavily on the type of position. When many moves do not change the perft value at all, the approach you are using does well. In other cases there are not many moves where the nullmove perft value can just be used as is. In these cases, my current approach can sometimes use bits and pieces of the nullmove perft computation.

-paul
Top

Return to “Computer Chess Club: Programming and Technical Discussions”