Chess Engine: Faster Move Generation

Question

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

1. Use SIMD instructions to do bitwise operations on multiple bitboards at the same time.
2. Use Kogge-Stone Generators for calculating moves for multiple sliding pieces at the same time.
3. 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?

Answer 1

Move generation has been tested to death in modern chess engines, and the current consensus is that the following two approaches are optimal for sliding pieces:

1. A lookup table indexed by PEXT of the relevant occupancies ("Fancy PEXT Bitboards")
2. A lookup table indexed by the higher order bits of the product of the Bitboard of relevant occupancies and a magic multiplier ("Magic Bitboards")

Option 1 is preferred on CPUs which have a fast hardware PEXT (i.e. Intel Haswell and newer, no AMD CPUs at the time of writing). Otherwise, Option 2 is preferred.

For example, stockfish offers bmi2 and popcnt builds: the former uses PEXT bitboards, the latter uses magic bitboards.

Kogge-stone

The Kogge-stone fill algorithm doesn't tend to be used in top engines for the simple reason that it benchmarks as being worse than the alternatives. I can offer a few reasons as to why this might be the case, but it is more important to recognise the fact that it is the case:

• They require a ludicrous number of CPU instructions. Each ray that must be cast (of which there are four) requires 5 shifts, 5 bitwise '&'s, and 3 '|'s, while the lookup operations only require 3-5 instructions per slider.
• While Kogge-stone can in theory be vectorised, there tend to not be enough sliders on the board to take advantage of this. For example, there tend to only be 3 (or fewer) rook-like sliders on the board at any given time. This makes the parallelism not worth the speed tradeoff.

 Actually improving move generation

A few things to note based on your code:

• Use x & (x - 1) to clear the least significant bit: this is faster than x &= ~(1 << from)
• Don't recompute the mask at every iteration: do it before the generation loop instead
• Use magic bitboards or PEXT bitboards: this is faster than Kogge-stone
• Make sure that hot move generation functions (like GetRookMoves) are inlined.