Writing a Chess Engine in C

Bitboards, alpha-beta search and a hand-tuned evaluation.

Source

Contents
  1. Features
  2. How a classical engine works
  3. Board representation: bitboards
  4. Move generation
  5. Search: minimax and alpha-beta
    1. Minimax
    2. Alpha-beta pruning
  6. Evaluation
  7. Implementation and optimizations
  8. Building

BitChess is a chess engine written in C, as a hobby project to dig into low-level optimization and classical game-tree search. It deliberately isn’t a neural-network engine. It’s the traditional approach that engines were built on for decades: bitboards to represent the position, alpha-beta to search it and a hand-written function to judge who’s winning.

Features#

  • Bitboard board representation for fast position updates
  • Alpha-beta search with move ordering and iterative deepening
  • A multithreaded search at the root
  • An evaluation built from material values, piece-square tables, mobility and king safety
  • A terminal interface that updates in real time
  • Standard Algebraic Notation (SAN) for reading and writing moves

How a classical engine works#

Every classical engine is built from the same three parts and it helps to see them separately before looking at the code:

  1. Representation. How the position is stored in memory and how quickly you can generate every legal move from it.
  2. Search. Looking ahead through possible sequences of moves, as deep as time allows.
  3. Evaluation. At the end of each line, a static judgment of how good the position is, without searching further.

The search does the heavy lifting and it calls the other two millions of times, so all three have to be fast.

Board representation: bitboards#

A chessboard has 64 squares and a 64-bit integer has 64 bits. A bitboard is a uint64_t in which each bit stands for one square. The engine keeps one bitboard per piece type and colour: one for white pawns, one for black knights and so on.

8x8 board = 64 bits R shaded = the rook's attack mask, a bitboard of set bits One 64-bit integer per piece one bit per square, 64 squares total sq = rank * 8 + file mask = 1ULL << sq attacks & occupancy moves and attacks are bitwise ops: shift, AND, OR, XOR over the bits. piece attack mask (bit = 1)
64 squares, 64 bits. Questions about the board become bitwise operations.

The payoff is that questions about the board turn into a handful of CPU instructions instead of loops over an array:

  • All occupied squares: OR every piece bitboard together.
  • Squares a piece can move to without capturing its own side: its attack set AND NOT your own pieces.
  • How many pieces of a type are left: a population count, which modern CPUs do in one instruction.
  • Where a piece is: the index of the lowest set bit, also one instruction.

That makes updating and querying positions fast and mostly branch-free.

Move generation#

For each piece type, the engine needs the set of squares it attacks from a given square.

  • Knights, kings and pawns always attack the same pattern from a given square, so those sets are precomputed once at startup into tables of 64 entries. Generating their moves becomes a table lookup and a mask.
  • Sliding pieces (bishops, rooks, queens) move along lines until something blocks them, so their attacks depend on which squares are occupied. They’re also handled with precomputed attack tables, which keeps the hot path down to a few lookups and masks.

Then come the special cases every engine has to get exactly right: castling (including not castling through check), en passant and promotion to each of the four pieces.

Search: minimax and alpha-beta#

Minimax#

The basic idea is minimax. On my move I pick the move that’s best for me, assuming that on your move you’ll pick the move that’s worst for me. Applied recursively to a fixed depth, with the evaluation function scoring the positions at the bottom, that gives the best move under the assumption of perfect play from both sides.

The problem is size. Chess has around 30 to 40 legal moves in a typical position, so every extra move of depth multiplies the work by that factor.

Alpha-beta pruning#

Alpha-beta returns exactly the same answer as minimax while skipping large parts of the tree. It keeps track of two bounds as it searches: the best score you’re already guaranteed (alpha) and the best score your opponent is already guaranteed (beta). As soon as one move is shown to be worse than an alternative that’s already been found, there’s no need to look at any more replies to it. The opponent would never allow that line, so the rest of that branch is cut off.

MAX MIN MIN 7 3 9 2 ? ? alpha-cutoff min = 3, sets alpha = 3 2 is not above alpha(3) Move ordering tries the best move first, so cutoffs fire early and less of the tree is ever searched.
Once one reply refutes a move, the rest of that branch never needs searching.

How much alpha-beta saves depends almost entirely on move ordering. If the best move is searched first, cutoffs happen immediately and the tree shrinks dramatically. If it’s searched last, alpha-beta saves almost nothing. So most of the search work in BitChess goes into trying good moves first:

  • MVV-LVA ordering for captures (most valuable victim, least valuable attacker). Capturing a queen with a pawn is tried before capturing a pawn with a queen.
  • Iterative deepening. Search to depth 1, then 2, then 3 and so on. That sounds wasteful, but each shallow search produces a best move that gets searched first at the next depth, which makes the ordering much better. It also means that when time runs out, there’s always a complete answer from the last finished depth.
  • A multithreaded root search, which spreads the moves at the top of the tree across cores using pthreads.

Evaluation#

When the search reaches its depth limit, the evaluation function scores the position without looking any further. BitChess combines:

  • Material: the classic piece values.
  • Piece-square tables: a bonus or penalty for each piece on each square. Knights are better in the centre than on the rim, pawns are worth more the further they advance and so on.
  • Mobility: how many moves each side has available.
  • King safety: how exposed each king is.

There are no learned weights, just tables and heuristics tuned by hand.

Implementation and optimizations#

The code is modular C, split into bitboard helpers, board state, move generation, evaluation, search and notation. The performance work is the usual low-level toolkit:

  • Precomputed attack tables
  • Careful move ordering, since that’s where alpha-beta gets its speed
  • Multithreading
  • Compiler built-ins for bit manipulation, like population count and finding the lowest set bit
  • Struct layouts that are friendly to the CPU cache

Building#

shell
git clone https://git.srtk.in/sarthak/bitchess.git
cd bitchess
make
./build/bin/bitchess

It needs GCC or Clang with C99 support, a POSIX system and pthreads.