Chess Engine Move Generator: PEXT Footnote
In a previous article, I wrote at length about writing a chess engine move generator from scratch. One technique that was discussed at length was using magic bitboards for efficient sliding piece move generation. In this article, we’re going to explore an alternative sliding piece move generation technique using PEXT.
PEXT
PEXT, which stands for parallel bits extract, is an operation supported by BMI2 - Bit Manipulation Instruction Set 2. It’s a set of operations supported on a subset of Intel and AMD processors which allows for fast bit manipulation techniques.
PEXT is an operation which takes three operands - a source, a mask, and a destination. Bits from the source corresponding to the bits in the mask are copied to contiguous lower-order bits in the destination. Consider an example on the following 8-bit numbers
SOURCE: S1 S2 S3 S4 S5 S6 S7 S8
MASK: 0 1 0 0 0 1 0 1
DEST: 0 0 0 0 0 S2 S6 S8
Review of magic bitboards
As a quick review, magic bitboards were a way for us to efficiently generate moves for sliding pieces. Consider the following board:
Board
1.......
.1...1..
....1...
.1......
...R..1.
.1......
...1....
......1.
If our goal is to generate moves for the rook R in this position, the key observation to make was
that the only relevant pieces to consider were those which intersected the rank/file attacks of the rook as such:
Board Attacks Relevant Pieces
1....... ........ ........
.1...1.. ...1.... ........
....1... ...1.... ........
.1...... & ...1.... = ........
...R..1. .11.111. ......1.
.1...... ...1.... ........
...1.... ...1.... ...1....
......1. ........ ........
Using these relevant pieces, we constructed a key by multiplying our board by some magic number
Relevant Key
........ ..1..1..]
........ ..].....
........ ........
........ * magic number = ........
......1. .garbage
........ ........
...1.... ........
........ ........
And taking the relevant bits to use as a key to look up the sliding moves for this position in a pre-computed table.
For a more in-depth exploration of this topic you should read my article on chess engine move generation.
PEXT as a replacement for magic bitboards
With an understanding of how magic bitboards work, PEXT reveals itself as a rather obvious replacement. In short, the goal of magic bitboards is to isolate the relevant bits for a given square so that they can be used as a key for some sort of precomputed lookup table. The way that they do this is rather opaque (hence the term magic), but it is essentially a “hack” to extract the relevant bits from a given position.
PEXT, however, offers a more performant and intuitive way of retrieving these bits so that they may be used as a key.
We can visualize PEXT as doing the following equivalent operation to retrieve the relevant key:
Board MASK
1....... ........
.1...1.. ...1....
....1... ...1....
.1...... ...1....
...R..1. .11.111.
.1...... ...1....
...1.... ...1....
......1. ........
PEXT(board, mask) = 0000000101
At a high-level, magic bitboards give us a key by using the following algorithm
- Lookup the magic number for the given square
- Multiple the occupancy board by the magic number
- Bit-Shift the multiplied number down by (64 - #relevant bits)
- Perform a lookup using the multiplied number as a key
PEXT gives us a key using a similar, although slightly different, algorithm
- Lookup the mask for the given square
- Use PEXT to extract the relevant bits from the occupancy board
- Perform a lookup using the extracted bits as a key
Performance Improvements
Based on some non-rigorous testing, PEXT offers modest performance improvements over magic bitboards during move generation.
Using the Kiwipete position, I calculated the value of Perft(6) which yielded the following results:
Magic: 13.5sec
PEXT: 12.8sec
This comes out to be ~5% improvement in move generation performance.
In conclusion, improvements in move-performance generation are largely trivial given that the majority of cost-saving during a chess engine’s search comes from pruning (alpha-beta pruning, for example). Still, PEXT is so simple to implement that it is fairly low-hanging fruit when it comes to improving move generation performance. If anything, PEXT should be viewed as the standard practice for sliding move generation given it’s intuitive nature. Magic bitboards are more of a “hack” for hardware which doesn’t support the native PEXT BMI2 operation.