👑 Writing a chess engine in C++

Chess engine programming by someone who is bad at chess.

17 minute read

Jump to heading Introduction

For a university course this semester we had to write a chess engine in C++. I'm not a chess player and was only familiar with the most basic chess rules so this was quite a challenge. Below is a video of my engine winning a game during a chess tournament (playing as white).

Jump to heading Board representation

In my chess engine, a board gets represented using bitboards. A bitboard is basically just 64 bits. By having this simple representation, the computer is able to very rapidly perform certain operations on it. Having just 1 bitboard representation for the whole board is not enough since 1 bit is not enough to store what is going on at a specific square. That is why in total, 12 bitboards are defined. The starting position of a chess board is shown below. The board has 64 squares, 6 types of pieces and 2 colors. In total, I use 12 bitboards to represent this because there are 12 piece types if you take into account the color of a piece.

In C++, I use the uint64_t type for representing bitboards. I also define several operations in order to work with them more easily. For some of these operation, you can use so called built-in functions like __builtin_ctzll which will return the total number of trailing 0-bits. Because we store a bitboard as 64 bits, it is very easy to represent things like the 'A file' or the '5th rank' in just a single line.

typedef uint64_t U64;

const U64 FILE_A = 0x8080808080808080ULL;
const U64 RANK_5 = 0xff00000000ULL;

#define set_bit(b, i) ((b) |= (1ULL << i))
#define get_bit(b, i) ((b) & (1ULL << i))
#define clear_bit(b, i) ((b) &= ~(1ULL << i))
#define get_LSB(b) (__builtin_ctzll(b))

inline int pop_LSB(U64 &b) {
    int i = get_LSB(b);
    b &= b - 1;
    return i;
}

Once you have your bitboards, you can work with them by using bitwise operations. As an example let's say we want to get all the possible promotions of the white pawns. All of the possible promotions are shown in the image below.

In code, the following steps are performed.

// only look at the pawns on the 7th rank
U64 promotions = (bitboards[P] & RANK_7)

// promote north if the square is empty
U64 north_promotions = north(promotions) & empties;

// promote west/east if there is an enemy piece there that we may capture
U64 west_promotions = north_west(promotions) & blacks;
U64 east_promotions = north_east(promotions) & blacks;

This is a good example of why we use bitboards. We just need to use some bitwise operations and we're done. The north/west/etc. are helper functions to perform bit-shift operations.

constexpr U64 west(U64 b) { return (b & ~FILE_A) << 1; }
constexpr U64 east(U64 b) { return (b & ~FILE_H) >> 1; }
constexpr U64 north_west(U64 b) { return (b & ~FILE_A) << 9; }
constexpr U64 north_east(U64 b) { return (b & ~FILE_H) << 7; }
// ... etc

When performing the bit-shift operations, I also do out-of-bounds checks which makes these helper functions useful.

Jump to heading Attack tables

In a chess game there are 2 kind of pieces:

🐇 Leaping pieces: pawns, knights, kings

⛸️ Sliding pieces: bishop, rook, queen

Leaping pieces can just immediately jump to their target square and do not need to take into account any blocking pieces. Sliding pieces are pieces that cannot jump over other pieces. Instead, they slide towards their target and may be blocked by other pieces during the process.

Jump to heading Leaping pieces

For leaping pieces, all of the attacks are pre-calculated and put in a simple lookup table. During the game when we want to find the possible attacks for a piece, we query the lookup table by index using the position of the piece and in return we get a bitboard that has 1-bits wherever the possible attacks of the piece are located. These attack tables are pre-calculated before the game which saves on runtime-performance. For example the knight attack table is generated as follows.

U64 attacks, knights = 0ULL;

// place knight on board
set_bit(knights, square);

// add attacks
attacks = (((knights >> 6)  | (knights << 10)) & ~FILE_GH) |
          (((knights >> 10) | (knights << 6))  & ~FILE_AB) |
          (((knights >> 15) | (knights << 17)) & ~FILE_H)  |
          (((knights >> 17) | (knights << 15)) & ~FILE_A);

Again, bitwise operations are used to easily generate these, but it doesn't really matter whether this attack generation is fast or not since it's precalculated anyway.

The image below shows the possible attacks for a given knight piece. All of these attacks can be generated using straightforward bit-shift operations (>>, <<). Each attack is added together using a bitwise-OR operation (|) and finally it is checked if the attack ends up out of bounds of the board.

At runtime, the potential moves can easily be queried. For example, querying the potential moves for a king is shown below. We perform a bitwise-AND operation to get the actual possible moves since the king can not move to a square where there already is a piece with the same color.

U64 attacks = KING_ATTACKS[from] & targets;

Jump to heading Sliding pieces

For the sliding pieces, generating the attacks is a bit more complicated since possible attacks depend on possible blocking pieces that are placed on the board. The image below shows how the attack pattern of a queen is influenced by blocking pieces on the board.

I won't go too much into detail but essentially we use magic bitboards which is a hashing technique. The idea is that for each sliding piece, for each square, for each possible blocking pattern, we generate the possible attacks.

The sentence above has a lot of 'for each' in it and so as expected, storing all these combinations take up a significant amount of space. The pre-calculation involves generating all of the possible attack patterns and storing them, indexable by a key. The payoff is worth it. We end up with an easy lookup of possible attacks, given a square and blocker pattern. The attack patterns are stored in a 2D array where the square of the piece is used as a first index, and then a key is generated based on the blocker pattern and the square.

U64 ROOK_ATTACKS[64][4096];

U64 Board::getRookAttacks(int square, U64 blockers) const {
  return ROOK_ATTACKS[square][getRookKey(blockers, square)];
}

If you want to know more about magic bitboards, I put some links at the bottom.

💬 Disclaimer: magic bitboards are not actually magic :/

Now that we have handled both board representation and pre-calculating attack tables, we can get to actually generating the moves.

Jump to heading Move generation

For a given board position, we want to be able to calculate all the possible moves so that the engine can pick one of them to perform. The main function looks like this:

Board::MoveVec Board::generateMoves<LEGAL>(MoveVec &moves) const {
  // if the king is in check then the legal moves can only be evasions
  isKingInCheck(boardTurn) ? generateMoves<EVASIONS>(moves) : generateMoves<PSEUDO_LEGAL>(moves);

  // extract legal moves from pseudo-legal moves
  std::vector<Move> legal_moves;
  legal_moves.reserve(MOVES_RESERVE_SIZE);

  for (auto &move: moves) {
    if (isMoveLegal(move)) legal_moves.push_back(move);
  }
  return legal_moves;
}

I do a test to see if the king is in check, because then we only need to generate a subset of all the possible moves since the only legal move is to resolve the check. If the king is not in check, we generate pseudo-legal moves (moves that could leave the king in check) and then we filter out the non-legal moves.

Jump to heading Pseudo-legal moves

Generating pseudo-legal moves is fairly straightforward for most pieces since we have the attack tables pre-calculated. For example for the queen moves are generated as follows:

MoveVec &moves;
generateQueenMoves(moves, friendly_queens, ~friendlies);

void Board::generateQueenMoves(MoveVec &moves, U64 queens, U64 targets) const {
  // for each of our queens
  while (queens) {
    // get the position of the queen
    int from = pop_LSB(queens);
    // get the (pre-calculated) attacks of the queen
    // we limit the attacks to contain enemy squares (captures) and
    // empty squares (regular moves), moving to a friendly square is not possible
    U64 attacks = getQueenAttacks(from, all) & targets;
    // add a move for each attack
    while (attacks) addMove(Move(getSquare(from), getSquare(pop_LSB(attacks))), moves);
  }
}

The generated moves are pseudo-legal since they might leave the king in check. For example in the image below, the white bishop has 4 moves generated for it but none of them are legal since they all would leave the king in check. It is easier and faster to generate pseudo-legal moves, and then check if they are legal, compared to generating only legal moves in the first place, so that is why we do it this way.

Jump to heading Pawn moves

Pawn moves are more complicated because pawns can move in more complex ways. For example in the image below, the pawn on rank 2 is in its starting position so it could move 1 or 2 squares upwards. The pawn on rank 5 could move either 1 square upwards or do an en-passant capture since black did a double pawn-push in the previous move. The pawn on rank 7 could go for a promotion by moving upwards or by capturing the black rook.

Luckily, our bitboard-approach makes this relatively easy to do. The code below shows how pawn moves are generated. Some of the code is left out since the original code is quite long and contains additional things that need to happen based on whether we're generating captures, evasions or general moves, but you should get the idea.

// promotion-eligible pawns are on rank 7
U64 promotions = pawns & RANK_7;
U64 non_promotions = pawns & ~RANK_7;

// pawns can be pushed if there is an empty space
U64 singles = north(non_promotions) & empties;
U64 doubles = north(singles & RANK_3) & empties;

if (promotions) {
  // north promotions are regular pushes and need an empty square
  U64 north_promotions = north(promotions) & empties;

  // west/east promotions can only be captures
  U64 west_promotions = north_west(promotions) & blacks;
  U64 east_promotions = north_east(promotions) & blacks;
}

// captures can happen left/right and need an enemy piece
U64 west_captures = north_west(non_promotions) & blacks;
U64 east_captures = north_east(non_promotions) & blacks;

if (enpassant) {
  U64 enpassants = non_promotions & PAWN_ATTACKS[0][get_LSB(enpassant)];
}

Jump to heading Castling

Castling is a special move involving the king and the rook. Before you can perform the move, several criteria need to be met.

The conditions are checked using the following code.

if (turn == WHITE && hasCastlingRights(CastlingRights::WhiteKingside)) {
  if (!get_bit(all, f1) && !get_bit(all, g1) &&
    !isSquareAttackedBy(e1, BLACK) &&
    !isSquareAttackedBy(f1, BLACK))
    addMove(Move(Square::E1, Square::G1), moves);
}

The castling rights (whether or not we can castle) are updated after a move (that has an effect on the castling rules) is performed. The code above checks if the necessary preconditions like squares being empty/not attacked are met.

Jump to heading Check evasions

When our king is in check, we need to resolve the check. In the board setup below, the black king is attacked and check evasion can be done by either moving the king to one of the marked spots, or alternatively we can use the black queen to capture the white knight, which would also resolve the check.

I will not go into detail of how the evasion code works, but it involves finding out the attackers of the king and figuring out the attack lines between the attackers and the king. The possible moves for pieces to resolve the check then include:

king moves that resolve the check
moves that capture the attacker (if the attacker is a sliding or leaping piece)
moves that block the attack line between enemy attacker and king (if the attacker is a sliding piece)

Jump to heading Testing for correctness

Now that our move generation is done, we want to know if it actually is correct. The easiest way to test if your move generation code is correct is by using perft tests. Basically, given a initial board position, you generate all the possible moves. For each generated move, you perform the move and recursively call the perft function again. Then you undo the move which restores the board to its previous position.

The perft function will essentially count all possible moves up to a specified depth, given an intial board setup. This is useful because if you try this function up to a depth of 5 or 6 and the result is the same as what some established chess engines get as a result, you can be fairly certain that your move generation is correct. The perft function is shown below.

uint64_t perft(Board &board, int depth) {
  std::vector<Move> moves;
  moves.reserve(MOVES_RESERVE_SIZE);
  moves = board.generateMoves<LEGAL>(moves);

  uint64_t nodes = 0;

  if (depth == 1) return moves.size();

  for (const auto &move: moves) {
    Position position = board.copyBoard(board);
    board.makeMove(move);
    nodes += perft(board, depth - 1);
    board.restorePosition(board, position);
  }
  return nodes;
}

I wrote some unit tests where around 10 board positions are evaluated up until a depth of 6. This is very useful to make sure that a change to your engine does not mess up move generation. If your perft result does not match the expected result, you can compare the amount of moves branch-by-branch using another chess engine that you 'know' is correct, and track down where your move generation goes wrong.

Jump to heading Move selection and search

Jump to heading Board evaluation

Now that we can correctly generate moves, we can write an algorithm that picks the best move for us, given a board position. At the core of this, there is an evaluation function that evaluates whether or not a position is 'good'. At this stage, it probably helps if you are a good chess player so that you can come up with some good heuristics. I evaluate boards based on 2 criteria:

material
positional

Material means that some pieces are worth more than others. Positional means that a piece on some square, is better than that piece being on a different square. In code, this looks like this.

const int PIECE_SCORES_MATERIAL[6] = {
    // pawn, knight, bishop, rook, queen, king
    100, 300, 300, 500, 900, 12000
};

const int KNIGHT_SCORES_POSITIONAL[64] = {
  // a score for each square on the board
  -58, -38, -13, -28, -31, -27, -63, -99,
  -25,  -8, -25,  -2,  -9, -25, -24, -52,
  -24, -20,  10,   9,  -1,  -9, -19, -41,
  -17,   3,  22,  22,  22,  11,   8, -18,
  -18,  -6,  16,  25,  16,  17,   4, -18,
  -23,  -3,  -1,  15,  10,  -3, -20, -22,
  -42, -20, -10,  -5,  -2, -20, -23, -44,
  -29, -51, -23, -15, -22, -18, -50, -64,
};

The material scores are pretty straightforward, the king is worth the most, a pawn the least. For the positional scores, I found some tables online that seemed to work well. A good example is the knight: it has a better evaluation if the knight is positioned in the center of the board since that means that it can reach more squares and thus has a larger influence. If the knight is put in the corner of the board, many of its usual attacks fall out of bounds of the board.

I have defined these scores for 3 stages of the game: start, middle and end and depending on the stage of the game, a linear interpolation occurs between them.

Jump to heading Finding the best move

My chess engine uses an alpha-beta pruning search algorithm. In short, it goes over the game tree (all possible moves up to a certain depth) and finds the best move. The pruning part is useful because by encountering certain good positions, it can remove huge chunks of the tree that are guaranteed not to give a better result.

In order to help the algorithm, moves are sorted because the earlier the search algorithm encounters a good move, the more branches can be pruned and less board positions have to be evaluated. The move ordering uses some heuristics to estimate whether or not a move will be good. I use a scoring system that among other things considers capturing moves and promotion moves to be good.

Captures are evaluated using the most valuable victim, least valuable attacked principle where a pawn capturing a queen is seen as the best, and a queen capturing a pawn is seen as the worst. Promotions to more valuable pieces are considered better.

for (auto &move: moves) {
  int score = 0;

  // capture moves (10010 - 10055)
  if (captured.has_value()) {
    score = 10000 + MVV_LVA[moved.value().toInt() - 6 * (moved.value().toInt() >= 6)][captured.value().toInt()
        - 6 * (captured.value().toInt() >= 6)];
  }

  // promotion moves (9300 - 9900)
  if (promotion.has_value()) {
    score = 9000 + PIECE_SCORES[static_cast<int>(promotion.value())];
  }

  move.setScore(score);
}

This move ordering results in a significant reduction in nodes of the tree that need to be evaluated. Lastly, the search algorithm uses an iterative-deepening approach which allows the engine to keep search depth-by-depth, until the time for searching is up. This allows the engine to use up all the time that is allocated for a search, without using up too much time.

Jump to heading Conclusion

Writing a chess engine is complex, and frustrating. I can highly recommend it.

Jump to heading Additional resources

Jump to heading Magic Bitboards

https://www.chessprogramming.org/Magic_Bitboards

Jump to heading Chess engines

Sebastian Lague chess engine

Published March 2022

👑 Writing a chess engine in C++

Jump to heading # Introduction

Jump to heading # Board representation

Jump to heading # Attack tables

Jump to heading ## Leaping pieces

Jump to heading ## Sliding pieces

Jump to heading # Move generation

Jump to heading ## Pseudo-legal moves

Jump to heading ## Pawn moves

Jump to heading ## Castling

Jump to heading ## Check evasions

Jump to heading # Testing for correctness

Jump to heading # Move selection and search

Jump to heading ## Board evaluation

Jump to heading ## Finding the best move

Jump to heading # Conclusion

Jump to heading # Additional resources

Jump to heading ## Magic Bitboards

Jump to heading ## Chess engines