Introduction
I'm in the process of rewriting my chess engine for better performance. I've started with the move generation function first. I've been looking at this person's article (Their Article) about generating moves quickly. At the bottom, they have their list of tips for better performance. They claim using these tips gives them about 100 million nodes per second from the starting position, while qperft (qperft download) does 190 million (qperft does 290 million on my pc). While the fastest I have gotten from my move generation function has been about 10 million nodes per second.
QPerft Output on my PC
From the starting position.
Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes
perft( 1)= 20 ( 0.000 sec)
perft( 2)= 400 ( 0.000 sec)
perft( 3)= 8902 ( 0.000 sec)
perft( 4)= 197281 ( 0.000 sec)
perft( 5)= 4865609 ( 0.016 sec)
perft( 6)= 119060324 ( 0.414 sec)
119060324 / 0.414 ~= 290 million
The Tips
- Use SIMD instructions to do bitwise operations on multiple bitboards at the same time.
- Use Kogge-Stone Generators for calculating moves for multiple sliding pieces at the same time.
- Use the o^(o-2r) trick for calculating moves for single sliding pieces.
Problem
The problem I am having is I don't understand how to use these tips.
Problems with Tip #1
Their main tip for performance gain is to use SIMD (Single Instruction Multiple Data) instructions to do operations on multiple bitboards at the same time. The problem is I don't see how these are useful for generating moves. This is an example of how I've been generating moves (rooks for example).
Bitboard rooks = turn ? pieces[WROOK] : pieces[BROOK];
Square from = 0, to = 0;
while (rooks != 0) {
_BitScanForward64(&from, rooks);
// GetRookMoves uses magic bitboards (a lookup table using the _pext_u64 instruction for speed).
// As far as I am aware magic bitboards are faster than Kogge-Stone Generators.
// & (empty | (turn ? bPieces : wPieces) is to only get the moves that are on empty squares or capture squares.
Bitboard rookMoves = GetRookMoves(start, full) & (empty | (turn ? bPieces : wPieces));
while (rookMoves != 0) {
_BitScanForward64(&to, rookMoves);
// I am using a 32-bit integer to store all the information about the move
moves[moveCount++] = /* move information (rook, from, to, etc...) */;
// This is ofc to remove the move we have just looked at
rookMoves &= ~(ONE << to);
}
// This is ofc to remove the rook we have just looked at
rooks &= ~(ONE << from)
}
I don't see where using SIMD instructions could help in this move generation function as I don't see any bitboard operations that can be done together. Am I missing some obvious way where using SIMD instructions would actually help or am I just doing the move generation wrong in the first place?
Problems with Tip #2
Their isn't much of a problem with tip #2. I am just wondering if magic bitboards are actually faster or if Kogge-Stone Generators with SIMD instructions are somehow faster. Also, Kogge-Stone is for calculating the moves for multiple sliding pieces at a time for legal move generation (I think). However, I am doing pseudo legal move generation because I think it is faster and easier.
Problems with Tip #3
The problem with tip #3 is the same as number 2. Isn't it faster to use magic bitboards?