This series covers my attempt at writing a half-decent chess engine using C# targeting .NET 6. Chess programming is a new area for me, so I can’t claim that anything shown here will be the most optimal, but I do hope that it will prove useful for others just starting out on their own chess programming adventure.
The goals of this project are:
Achieve an initial Elo rating of 2000 (enough for a “master” level FIDE rating). If it makes it past a Grandmaster rating of 2500 Elo, that would be great.
A simple and easy-to-follow implementation that newcomers can understand.
Support the UCI protocol and leave all the fancy graphics stuff to a dedicated GUI.
All source code will be up on my GitHub repo. I suck at naming things, so for now, I’ve called this project “Chess Engine”. It might not have the same ring to it as Stockfish or Komodo Dragon, but a better name can wait for later.
Throughout this series, there will be links to the Chess Programming Wiki (referred to as CPW from here on). This is a treasure trove of information, covering everything you could possibly need related to chess programming.
One minor criticism of the CPW I would make is that it can be difficult to follow in places. Some of the code snippets can be quite terse, or reference snippets from other sections, leaving the reader to piece them together. With this series, I hope anyone reading can avoid some of those issues I encountered.
A Note on FEN Notation
FEN positions are the standard way to describe a chess position. It is also the format within the UCI protocol and will be encountered throughout the various chess programming resources, so a quick primer on understanding it is in order.
As an example, this is what the starting position described in FEN looks like:
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
It might look inscrutable at first glance, but it’s quite simple. Starting from the 8th rank, the contents of each square of given by writing the symbol of the piece on that square. Black pieces use lowercase letters and white uppercase. Numbers show how many consecutive blank squares are present until the next piece or end of the rank.
Finally, you have the side to move, casting rights for each side, en passant target square, half-move clock (used for implementing the 50-move rule), and move count. Full details of the grammar and further examples are on the CPW.
Anatomy of a UCI chess engine.
A “UCI Chess Engine” is at its core a console application. Whilst a user can play chess with only the engine, it’s much easier with a UCI GUI. The GUI will handle all interactions with the user and handle the communication with the engine during the game.
For example, consider a new game where the engine is playing black. After white plays the move d4, the following is the communication flow between the GUI and Stockfish 14.1. This shows how it has searched different move sequences to find its best response of `Nf6’:
gui: ucinewgame
gui: isready
engine: readyok
gui: position startpos moves d2d4
gui: go wtime 1500000 btime 1500000 winc 0 binc 0 movestogo 40
engine: info string NNUE evaluation using nn-13406b1dcbe0.nnue enabled
engine: info depth 1 seldepth 1 multipv 1 score cp -31 nodes 20 nps 10000 tbhits 0 time 2 pv d7d5
engine: info depth 2 seldepth 2 multipv 1 score cp 4 nodes 41 nps 20500 tbhits 0 time 2 pv d7d5 a2a3
engine: info depth 3 seldepth 3 multipv 1 score cp -16 nodes 97 nps 48500 tbhits 0 time 2 pv d7d5 a2a3 b8d7
engine: info depth 4 seldepth 4 multipv 1 score cp -43 nodes 422 nps 140666 tbhits 0 time 3 pv c7c6 b1c3 d7d5 e2e4 d5e4
enine: info depth 5 seldepth 5 multipv 1 score cp -23 nodes 795 nps 198750 tbhits 0 time 4 pv d7d5 c2c4 d5c4 e2e4
engine: info depth 6 seldepth 6 multipv 1 score cp -29 nodes 1402 nps 350500 tbhits 0 time 4 pv d7d5 c2c4 e7e6 b1c3 g8f6 c4d5 e6d5
engine: info depth 7 seldepth 7 multipv 1 score cp -19 nodes 3119 nps 445571 tbhits 0 time 7 pv g8f6 g1f3 d7d5 c2c4 e7e6 b1c3 d5c4
engine: info depth 8 seldepth 9 multipv 1 score cp -28 nodes 6926 nps 629636 tbhits 0 time 11 pv g8f6 e2e3 d7d5 c2c4 e7e6 g1f3 f8e7 b1c3
engine: info depth 9 seldepth 10 multipv 1 score cp -24 nodes 10440 nps 652500 tbhits 0 time 16 pv g8f6 c2c4 e7e6 g1f3 d7d5 c4d5 e6d5 c1f4 f8b4 b1c3
engine: info depth 10 seldepth 15 multipv 1 score cp -32 nodes 24441 nps 698314 tbhits 0 time 35 pv g8f6 c2c4 e7e6 g1f3 d7d5 b1c3 f8b4 c4d5 e6d5 c1g5 h7h6
<snip>
engine: bestmove g8f6 ponder c2c4
Full details of what the protocol looks like are on the official site. It’s not a complicated protocol and will be the subject of a later post implementing UCI support.
To get started, Arena is a decent - if somewhat clunky - option, another is Tarrasch. One useful feature of Arena is the option to view the stream of commands sent between the GUI and the engine. Seeing this can be a great reference when implementing UCI by seeing how other engines handle the various UCI commands and help avoid silly bugs.
Beyond the UCI protocol, there are three major components of a chess engine:
Move generation. Given a position, generate the set of legal moves. This includes the fancier stuff like en passant, casting, and promotions.
Search. For each legal move (and any replies to those moves and so on) that the engine thinks is the best move.
Evaluation. Take a position and calculate a score of the relative advantage for each side. Positive scores mean white has an advantage. Negative scores are better for black.
Board Representation
The most fundamental aspect of a chess engine is representing the board. This includes what pieces are in play and where they are. There are a few options here, but the most popular among the best chess engines today are bitboards.
The bits in a bitboard will be a 1 if a piece is present, or 0 for an empty square. As such, bitboards don’t know what type of chess piece is occupying it. To answer that question, the engine requires twelve different bitboards - one bitboard per piece per side.
Using bitboards offers a performance advantage over other methods due to their 64-bit requirement. Today's CPUs operate on 64-bits at a time so can manipulate the entire board in a single CPU instruction. Even more recent CPUs also support bit manipulation instruction extensions for speeding up these bit-twiddling operations further which are also consumable via .NET with the System.Runtime.Intrinsics APIs.
Knowing which bit in a bitboard represents a certain square is handled via a mapping scheme. There are a couple of options here, all covered in the CPW's Square Mapping Considerations section. I've gone with the “File Rank Mapping” option where bit 0 is A1, bit 1 is B1, etc.
The bitboard implementation itself is a simple wrapper around a ulong field:
public struct Bitboard
{
private readonly ulong _squares;
...
}
Having a Bitboard type offers a few advantages over using a plain ulong everywhere. It makes the code clearer and provides a convenient home for any helper methods or overloaded operators. Since a lot of the operations on bitboards involve bit manipulations, the ability to overload the &, |, ^, and ~ operators, for example, can make the code more concise and readable.
Finally, to make things more manageable, a PiecePositions type encapsulates the six bitboards for a single side:
public class PiecePositions
{
private readonly Bitboard[] _positions;
public PiecePositions(Bitboard pawns,
Bitboard rooks,
Bitboard knights,
Bitboard bishops,
Bitboard queens,
Bitboard king)
{
_positions = new Bitboard[6];
_positions[(int)PieceType.Pawn] = pawns;
_positions[(int)PieceType.Rook] = rooks;
_positions[(int)PieceType.Knight] = knights;
_positions[(int)PieceType.Bishop] = bishops;
_positions[(int)PieceType.Queen] = queens;
_positions[(int)PieceType.King] = king;
}
public Bitboard Pawns
=> _positions[(int)PieceType.Pawn];
...
}
Position Representation
There is more to a game of chess than where the pieces are. Additional information, such as whose turn it is, what castling rights each side has, en passant capture availability, etc. is also required. This results in a Position type that brings everything together:
public class Position
{
private readonly Stack<PositionState> _state;
private readonly PiecePositions _whitePiecePositions;
private readonly PiecePositions _blackPiecePositions;
...
}
PositionState is a nested type that stores the bulk of the information needed in a position. When making a move, the new state is calculated and pushed onto the stack. Undoing a move is then a matter of popping the last state. More details on making and unmaking moves are covered in the next post.
private class PositionState
{
...
public Move AppliedMove { get; }
public CastlingFlags WhiteCastlingRights { get; }
public CastlingFlags BlackCastlingRights { get; }
public Colour NextToMove { get; }
public short EnPassantTarget { get; }
public ushort HalfMoveClock { get; }
public ushort FullMoveCount { get; }
public PieceType? CapturedPieceType { get; }
public int? CaptureSquare { get; }
}
Move is a type that stores information about a single move. This includes where the piece has moved from, where it’s moved to, what that piece was, and, for promotions, what it promoted to:
public readonly struct Move
{
public byte SourceSquare { get; }
public byte TargetSquare { get; }
public PieceType MovedPiece { get; }
public CastlingFlags CastlingFlags { get; }
public PieceType? PromotedToPiece { get; }
}
CastlingFlags and Colour are two simple enumerations for kingside / queenside castling for white and black.
With the ability to represent a position in place, being able to convert a Position instance to, and create one from, a FEN position is very useful. Dumping a position as its FEN equivalent during debugging to load into your favourite chess site’s analysis board can make tracking down tricky bugs a lot easier.
Going the other way, being able to construct a Position from a FEN position is great for unit tests. By creating an assortment of test positions, a Position instance can easily be created for exercising other areas without all the make / unmake move complications.
Parsing and generating FEN is straightforward by assuming that the input is well-formed and allowing the engine to abort if it’s not. This is the approach taken by Stockfish, for instance, and keeps the parsing code simple.
To test for any bugs in this process, round-tripping a FEN position via a Position and asserting the generated FEN matches the input works for flushing out any bugs. This approach also lends itself well to using a data-driven unit test using VSTest like so:
[TestClass]
public class Position_ToFENString
{
[DataTestMethod]
[DataRow(“rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1”)]
public void Position_ToFENString_OutputsExpectedFENResult(string inputFEN)
{
//Arrange
var objectUnderTest = new Position(inputFEN);
//Act
var result = objectUnderTest.ToFENString();
//Assert
Assert.AreEqual(inputFEN, result);
}
}
Adding in additional test positions is just a matter of adding new DataRow attributes with the input FEN.
With that, the core part of the engine is now taking shape. It can take a representation of a position in FEN notation and convert it to an internal representation of the board. It can track the locations of the pieces for each side and has a tentative outline of what making and unmaking a move might look like.
The next post in the series will cover move generation and how to test it for correctness, given the ridiculously large number of potential ways a game of chess can play out.
Until then, thanks for reading!