Chess

A chess engine with focus on fast move generation.

Building

The following dependencies are used for the GUI:

• gtk 4
• librsvg (for loading the piece images)

The engine can be built with cmake.

cmake .
make

If you do not use make, replace it with ninja for example. The build script contains multiple targets:

• chess: This is the main target. It has a GUI and the user plays as white. The engine responds with a move for black.
• chessNoComputer: The user can play both sides in a GUI. Mainly added for testing the move generator.
• findMagicNumber: finds Magic Numbers for the magic bitboard.
• moveGenTest: tests the move generator,
• genMoveConsts: produces constants to generate moves faster.

Testing

The target moveGenTest with its source in the test directory is a perft. It works by counting the number of leaf nodes of the move generation with a certain depth. The results where verified with stockfish.

Implementation

The engine is implemented using bitboards to store the position. A bitboard is an array of 64-Bit unsigned integers. The bitboard contains one element per piece and square. Each Bit of the integer corresponds to one field on the board, whether the piece stands there (1) or not (0). This allows use to use bitwise operations to calculate information we need, really fast.

The move generation of pseudo-legal moves (moves without considering whether the king is in check) is mostly straightforward. We pre-generate some data in src/generateCode/moveConsts.c, so that we can calculate the moves faster. For the king and the knight the moves are pre-generated because they can only possibly move to fixed target squares for one given source square. For the other pieces we pre-generated the distance, the piece can move in one given direction.

For testing, if the king is in check, so we get legal moves, magic Bitboards are used. This allows us to calculate really fast whether the king is in check compared to looping over all moves to see, if a piece can capture the king. Essentially we get the bitboard of all pieces and null all bits but the file and rank, the rook we want to the moves for, is on (or the relevant diagonals for the bishop). We can look up the moves by using this mask as a key of a hashmap. A hashing algorithm that multiplies with a so-called magic number and right shift, is used. The hashing is fast, and we can find magic numbers, so there are no hash collisions. To simplify the task of finding magic numbers, we use a different magic number for each square (fancy magic bitboard). The magic numbers for this engine are simply found by trying randomly generated one. The Implementation in src/findMagicNumber.c is based on ideas there.

For seraching the moves, we use a variant of Alpha-Beta. Alpha-Beta is based on minimax with an added upper and lower bound for the position score with makes it much faster than minimax.

The engine has a partly implemented UCI interface with its code in src/uci.c.

To detect repetitions we need a way to easily lookup, if the position already accrued. This done by calculating a Zobrist Hash for the board position. Zobrist Hashing is really nice because it allows incremental updating. With this hash the engine has implemented its own hash tables, which allow for detecting repetitions. Later on this can also be used for a transposition table.

The evaluation is currently simple. Here is currently the most room for optimizations.