Patzer Gambit
I got really hooked into chess this year, and I wanted to one-up my 2019 Connect 4 AI with something insane: a chess engine. At first, my goal was to build an AI bot stronger than me (~1200 ELO) while also learning the Rust programming language.
The biggest challenge was generating moves. Chess has a lot of rules and generating all legal moves for a given position is super hard. So, I made a compromise most chess engines make: I would generate pseudolegal moves. Pseudolegal moves are essentially chess moves that follow all rules besides checks. So, pseudolegal move generators also generate moves that are illegal because they leave the player in check. To address that, we test if a move leaves us in check. If it does, we do not consider it.
Move generators are the backbone of a chess engine, and it’s important to make the generator relatively fast. To do that, we represent the game position using bitboards, which are essentially numbers, where the individual bits represent whether a piece is present. In total, we have 13 bitboards: one for occupancy and one for each piece type for each player. Bitboards allow us to generate moves faster because we can generate multiple moves at once by using common bit operations like AND, OR, XOR, etc. This allows us to simulate multiple logic expressions in fewer CPU cycles. I also tried avoiding branches, but it seemed like the compiler did a better job at creating performant code.
To generate moves, I needed to create masks to represent the positions pieces can move to. This becomes hard with sliding pieces like rooks, bishops, and queens because their movement can be blocked by other pieces. To address this, we use magic bitboards. We essentially consider all possibilities beforehand and create a hashtable using perfect hashing so that we can get the moves of a piece at a position given all other occupancies on the board.
A large part of verifying move generations was using perft tests, which compare the total amount of moves generated after X to known benchmarks. Creating a perft test suite was crucial for finding bugs and making sure regressions did not go unnoticed.
Once move generation, the next steps were searching all possible positions reachable after X moves and evaluating the position. Since chess has a branching factor of about 35, the amount of positions we’d look at after X moves is 35^X. When X is 6, that’s more than 64 billion positions. It would be unreasonable to look at all possibilities, so we must prune the search tree. By pruning the search tree, we are simply ignoring certain positions that are likely not going to be the best variation of moves that can be played.
Basic testing was essential to making sure the engine was bug free. I implemented tests to check whether the engine was able to find mates in 4 full moves (8 half moves) and to see if it’s incremental updates to scoring values was accurate. I was trying out a lot of performance optimizations, and these tests (along with perft) helped me catch bugs right away.
Patzer Gambit is a pretty strong chess AI, but it can be even stronger with a better evaluation function. In the future, I’d love to have the chess engine consider pawn structure, mobility, and king safety when scoring positions. Thanks for reading all this!
