cade.site — Chess Engine (#0) - Setup

Home | About | Contact | Archive

Chess Engine (#0) - Setup

Let’s learn how to program a chess engine, from scratch, in C/C++! Specifically, we’ll target UCI (Universal Chess Interface) so we can play with various GUIs on multiple platforms

History

Chess is a well known game, and has been played for hundreds of years by millions of people. For about 97% of that time, the best players of chess have all been humans. For the last 3%, that title has been held by some sort of computer, and in that time, the gap between the best human player and the best computer player has grown astronomically.

In fact, the gap has gotten so large that even world champions refuse to play engines because it wouldn’t even be close.

For your own reading and entertainment, here are some popular computer chess programs:

Methods

There are many methods for writing a chess engine, ranging from simple to complex. There are many considerations that need to be made, which we will cover. In all cases, we will make our engine UCI compatible, so we can use many chess GUI programs to test it. Here is a link to download the UCI interface: https://www.shredderchess.com/download.html

We will originally write a so-called “traditional” engine, which consists of a few parts:

In the future, I plan to expand this series to include machine learning, which will help with the static position evaluator, as well as move generator (the idea is to use a machine learning model to tell which moves are more promising, and try them out first)

Setup

We will be programming this engine in C/C++, and using makefile-driven development. And, for reference, I will use links to the Chess Programming Wiki, which is a great resource. I’ll be calling my chess engine cce (Cade’s Chess Engine)

Build System

We’ll use makefile to build our project. In general, our project structure will look like:

The file makefile describes how to build our project:

# makefile - build system for cce (Cade's Chess Engine)
#
# Just run `make` to build `cce`, which is the UCI-compatible binary
#
# @author: Cade Brown <cade@cade.site>

# -*- Programs -*-

# C++ compiler
CXX          ?= c++

CXXFLAGS     += -std=c++11
LDFLAGS      += 

# -*- Files -*-

src_CC       := $(wildcard src/*.cc)
src_HH       := $(wildcard include/*.hh)


# -*- Output -*-

# Output binary which can be ran
cce_BIN      := cce

# -*- Generated -*-

src_O        := $(patsubst %.cc,%.o,$(src_CC))


# -*- Rules -*-

.PHONY: default clean FORCE

default: $(cce_BIN)

clean: FORCE
	rm -f $(wildcard $(src_O) $(cce_BIN))

FORCE: 

$(cce_BIN): $(src_O)
	$(CXX) $(CXXFLAGS) $(LDFLAGS) $^ -o $@

%.o: %.cc $(src_HH)
	$(CXX) $(CXXFLAGS) -Iinclude -fPIC -c $< -o $@

Source Code

First, we’ll create a header (include/cce.hh), which defines datastructures, includes required headers, and defines constants. Here’s all the C/C++ headers we need to include at the moment:

// in 'include/cce.h'

// C standard
#include <assert.h>
#include <stdint.h>

// Stanard library
#include <iostream>
#include <sstream>

// STL
#include <string>
#include <vector>

// Use C++ standard libary without 'std::' prefix
using namespace std;

And, we’ll put all our code in the cce:: namespace (but, we will have using namespace cce to make it less verbose).

We can define some enum constants, so our code is more readable:

// in 'include/cce.h'

/* Constants */

// Color enumeration
enum Color {
    // W: White
    WHITE    = 0,
    // B: Black
    BLACK    = 1,
};

// Piece enumeration
enum Piece {

    // K: King
    K        = 0,
    // Q: Queen
    Q        = 1,
    // B: Bishop
    B        = 2,
    // N: Knight (since K is used for King)
    N        = 3,
    // R: Rook
    R        = 4,
    // P: Pawn
    P        = 5,

};

// Number of colors
#define N_COLORS 2

// Number of pieces
#define N_PIECES 6

// FEN for the starting position
// (we'll get to this later)
#define FEN_START "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

We need a way to represent a tile. For example, a1 is the position of the white queenside rook (at the start). However, we can’t be referring to strings in the source code, as that will be inefficient. Instead, we can use an int, and store them as positions 0 through 63, basically laying tiles out in one long row. For example:

In general, the pattern will be:

Here is a diagram showing the index of each tile (from white’s perspective):

assets/img/chess-tileidx.jpg

In code, we won’t specify with tile names, but we can use the TILE macro to convert 2D coordinates to the 1D integer:

// in 'include/cce.h'

// Creates a position from the board, from a rank (_i) and file (_j)
// NOTE: These are 0-indexed! For example, the square 'a1' is TILE(0, 0)
// Examples:
// b3 -> TILE(b->1, 3->2) = TILE(1, 2) 
#define TILE(_i, _j) (8 * (_i) + (_j))

// Un-does the 'TILE' macro on '_val', and decomposes it into the '_i' and '_j' variables
#define UNTILE(_i, _j, _val) do { \
    int val_ = _val; \
    (_i) = val_ % 8; \
    (_j) = val_ / 8; \
} while (0)

Now, we need some way of representing a board. Most people would opt for an 8x8 array of tiles, containing the color and piece of each tile (or, something like -1 for empty tiles). While this is the obvious solution, and would certainly work, we want to make a fast and efficient engine. Believe it or not, there are better ways of doing this!

We’ll use bitboards, which are basically 64 bit integers which are interpreted as values of a chess board. Bitboards may be difficult to explain to people, and it may be difficult to see why we want to go through the trouble of such a thing. However, you will soon see the benefit of bitboards

In C++, we can represent a bitboard with a uint64_t (defined in stdint.h). However, we don’t want to type that all over the place. So, let’s make a typedef:

// in 'include/cce.h'

// cce::bb - Bitboard integer type
//
// A bitboard is a collection of 64 bits, one corresponding to each tile
//   on the board. They typically answer a question like "is a piece on tile X?",
//   and can be combined with bitwise operators
//
// Use 'ONEHOT(_i)' to create a bitboard with a single bit set
//
typedef uint64_t bb;

// Creates a bitmask from a single bit, _i, as a 1 bit, the rest being zeros
#define ONEHOT(_i) (1ULL << (_i))

Now, we can write bb where we want to specify a bitboard. Whenever you see this in the code, just remember it is an integer that has 1 bit for every tile on the chess board. You’ll notice that, as I said earlier, multiple bitboards are needed for a single chess board. So, let’s go ahead and define a structure for a chess board state, which we’ll call State:

// in 'include/cce.h'
// cce::move - Simple move structure, just containing the from and to 
//
//
struct move {

    // Tile being moved from
    int from;

    // Tile being moved to
    int to;

    move(int from_=-1, int to_=-1) : from(from_), to(to_) {}

    // Returns whether the move is unintialized or out of range
    bool isbad() const { return from < 0 || to < 0 || from >= 8 || to >= 8; }

};


// cce::State - Chess board state
//
// This is like the board, except it also keeps bits storing
//   castling rights, en-passant, etc
//
struct State {
    
    // Bitboard telling which color occupies which tile
    bb color[N_COLORS];

    // Bitboard array (indexed by 'Piece::*' enum members) telling which
    //   pieces are located where on the board
    // 0==not on this tile, 1==on this tile
    bb piece[N_PIECES];

    // Which color is about to move?
    Color tomove;

    // Castling rights, whether W==white, B==black, K==Kingside, Q==Queenside
    // i.e. 'c_WK' tells whether the White king can castle Kingside
    bool c_WK, c_WQ;
    bool c_BK, c_BQ;

    // En-passant target square (i.e. the square on which it could be captured)
    // Or, -1 if there is no such square
    // This should be reset every half-move
    int ep;

    // Half-moves since last capture or pawn advance
    // Used for the fifty-move rule
    int hmclock;

    // The number of full-moves, starting at 0, and incremented after black's move
    int fullmove;

    // Initializes as empty state
    State() {
        for (int i = 0; i < N_COLORS; ++i) {
            color[i] = 0;
        }
        for (int i = 0; i < N_PIECES; ++i) {
            piece[i] = 0;
        }
        tomove = Color::WHITE;
        c_WK = c_WQ = c_BK = c_BQ = true;
        ep = -1;
        hmclock = 0;
        fullmove = 0;
    }

    // Create a new state from FEN notation
    // SEE: https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation
    static State from_FEN(const string& fen);

    // Convert to FEN notation
    // SEE: https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation
    string to_FEN() const;

    // Gets a list of valid moves (from the 'tomove's players perspective), populating 'res'
    // Clears 'res' first
    // If 'ignorepins==true', then generate moves ignoring pinned pieces
    // If 'ignorecastling==true', then generate moves ignoring castling
    void getmoves(vector<move>& res, bool ignorepins=false, bool ignorecastling=false) const;

    // Queries a tile on the board, and returns whether it is occupied
    // If it was occupied, sets 'c' and 'p' to the color and piece that occupied
    //   it, respectively
    bool query(int tile, Color& c, Piece& p) const {
        bb m = ONEHOT(tile);
        for (int i = 0; i < N_PIECES; ++i) {
            if (piece[i] & m) {
                // Found
                c = (color[Color::WHITE] & m) ? Color::WHITE : Color::BLACK;
                p = Piece(i);
                return true;
            }
        }
        // Not found
        return false;
    }

};

So, our structure stores a bitboard corresponding to color, and one for each game piece kind. We also store some extra information about which player’s turn it is, castling rights, en-passant square (since it can only happen the move directly after a pawn moves 2 squares), and a half-move clock, which is used in the fifty-move rule for automatic draws.

There are also some methods here, the most important being query, which allows you to check whether a square is occupied, and by which piece. The basic logic is fairly obvious, we convert the tile to a mask m, and then check if any pieces occupy that square. If they do, then we check the color bitboard, and set c and p appropriately. If nothing was found, we return false.

There are also methods that deal with FEN (converting to and from). We’ll cover that next post, when we actually start writing code! See you then!


Cade Brown's personal blog, licensed under CC-BY 4.0.