Rudim [1] - .NET Core Chess Engine - Representing the Board & Generating Moves

Rudim is a chess engine I am building in my spare time to learn how chess engines work, and also improve my knowledge in C#.

This blog post is a part of a series of blog posts on Rudim. Click on the 'rudim' tag at the top of the page to see all posts in the series.

Preface#

The drive to build Rudim came from seeing AlphaZero in the news. AlphaZero seemed to fall right in the middle of my Venn Diagram of interests - interesting algorithms, reinforcement learning & chess. Though it took me quite a bit of time to understand the paper fully, I managed to get a pretty good understanding of how AlphaZero worked, and this inspired me to write my own chess engine. The only problem was that I was an absolute novice at it - I had no idea where to start.

Like any person facing a new problem (/s), I dove right into trying to do it myself - and failed miserably. I tried writing my own board representations and also tried using libraries to help me with some of them. On top of this, I was working with Python - because that was what I felt was the simplest language for me, assuming the performance impacts would be negligible.

I failed enough times to understand that I should probably go learn a bit about how chess engines are actually coded before going straight into things.

There began the journey with Rudim. C# was an arbitrary choice for the language Rudim uses - C is the celebrity of the chess engine world for its speed, but I had recently finished a work project in C# and I wanted to learn a bit more into the workings of the language and the .NET Framework.

Code & Concepts#

The source code for this project can be found here.

The descriptions below are a high level overview of the actual code - if you want to understand the actual working of Rudim, it would be better to play around with the code a bit.

Board Representation#

The first problem to be solved when attempting to write a chess engine is a simple one - how do you store the representation of the board?

There are many ways to do this. The approach I used was bitboards - they are fast, and don't take too much memory. But the drawback is that they are hard to understand and involve a lot of complex logic for efficiently calculating moves.

Bitboards take advantage of the fact that a chess board has 64 squares and most systems nowadays can store 64 bits of information in a single word. For our .NET implementation, we would be using the ulong data type to represent a single bitboard.

Let's take a simple example - using one bitboard to indicate whether a piece is present on square x.

The above position would be translated to this :

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

How you want to translate this into a ulong is upto you - and will change the implementation of most of your code based on what you choose (Similar to Little-Endian vs Big-Endian). Rudim represents the square a8 mapped to the first bit and h1 mapped to the 64th bit. (i.e. going top left -> bottom right as 1 -> 64 referring to the above diagram)

This represents a single scenario, now we can extend this to multiple bitboards to represent an entire board - one bitboard for every piece (6 pieces x 2 sides) and 3 more bitboards for occupancies which will help with some optimizations when generating moves.

public Bitboard[,] Pieces { get; set; }
public Bitboard[] Occupancies { get; set; }

Pieces = new Bitboard[Constants.Sides, Constants.Pieces];
Occupancies = new Bitboard[Constants.SidesWithBoth];

You can go through the wiki on Bitboards or check out Maksym's tutorial on building a chess engine in C for a better understanding of bitboards. The latter was very well explained and recommended by me as the wiki is not very well written for a beginner to understand.

Now this doesn't represent an entire board - there are few other things to keep in mind when representing a board.

FEN#

Forsyth–Edwards Notation (FEN) is a standard notation for describing a particular board position of a chess game. Here's an example of an FEN for the starting board position

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Since most chess engines use FEN to communicate positions, the next step would be to write a parser for translating an FEN to board state.

public static BoardState ParseFEN(string FEN)
{
    var board = new BoardState();
    var sections = FEN.Split(' ');
    ParsePieces(board, sections[0]);
    ParseSideToMove(board, sections[1]);
    ParseCastling(board, sections[2]);
    ParseEnPassant(board, sections[3]);
    ParsePly(board, sections[4]);
    return board;
}

Splitting up the sections for the FEN and parsing them individually, we are able to set the BoardState. This would however require us to add a few more sections to the BoardState.

public Side SideToMove { get; set; }
public Square EnPassantSquare { get; set; }
public Castle Castle { get; set; }

Now that we have most of the board represented correctly lets move on to trying to generate all the moves possible in a given position. But before that we need to explore how to use the bitboard representations we made earlier to calculate attacks for a given piece.

Piece Attacks#

Brush up a bit on bitwise operators before diving into this section as it might come in handy.

Each piece moves and attacks differently and this adds some complexity to generating attacks and moves. Lets divide the types of pieces we have into two categories - sliding pieces (Queen, Rook, Bishop) and jumping pieces (King, Knight, Pawn).

Jumping piece attack calculations are pretty straightforward. When you know which square on the board the piece is standing at, you can find which all squares it can 'jump' to. For example - the white pawn can attack two squares in the next rank in the two files right next to it's file.

public static Bitboard GetPawnAttacks(Square square, Side side)
{
    var ResultBoard = new Bitboard(0);
    var PawnBoard = new Bitboard(0);
    PawnBoard.SetBit(square);

    if (side == Side.White)
    {
        ResultBoard.Board |= (PawnBoard.Board >> 9) & ~FileH;
        ResultBoard.Board |= (PawnBoard.Board >> 7) & ~FileA;
    }
    else
    {
        ResultBoard.Board |= (PawnBoard.Board << 7) & ~FileH;
        ResultBoard.Board |= (PawnBoard.Board << 9) & ~FileA;
    }

    return ResultBoard;
}

The same concept can be expanded to knights and kings - you just need to find a way to shift the current bit to the positions it can attack. You can find the rest of the attacks code in Bitboard.Attacks.cs.

When it comes to sliding pieces - you have to iterate through all the squares it can attack. If there is a piece blocking the path of a sliding piece, it can attack every square upto and including that occupied square - but not any square after it. Which would look something like this.

public static Bitboard GetRookAttacks(Square square, Bitboard occupancy)
{
    var ResultBoard = new Bitboard(0);
    var RookRank = (int)square / 8;
    var RookFile = (int)square % 8;

    for (int rank = RookRank + 1; rank < 8; ++rank)
        if (AddSquareToBoardAndStopAtOccupiedSquare(ResultBoard, rank, RookFile, occupancy)) break;

    for (int rank = RookRank - 1; rank >= 0; --rank)
        if (AddSquareToBoardAndStopAtOccupiedSquare(ResultBoard, rank, RookFile, occupancy)) break;

    for (int file = RookFile + 1; file < 8; ++file)
        if (AddSquareToBoardAndStopAtOccupiedSquare(ResultBoard, RookRank, file, occupancy)) break;

    for (int file = RookFile - 1; file >= 0; --file)
        if (AddSquareToBoardAndStopAtOccupiedSquare(ResultBoard, RookRank, file, occupancy)) break;

    return ResultBoard;
}

private static bool AddSquareToBoardAndStopAtOccupiedSquare(Bitboard resultBoard, int rank, int file, Bitboard occupancy)
{
    resultBoard.Board |= 1ul << (rank * 8) + file;
    return (1ul << (rank * 8) + file & occupancy.Board) > 0;
}

So we finally managed to generate all attacks on the board. But this was a pretty costly operation and we don't want to do this every time we have a new position - this would drastically slow down our engine. The fact that these list of squares don't change between boards or games can be used to memoize the values we just calculated.

However, there is a small caveat once again. The jumping pieces don't give us much trouble, we can just directly store the results into one bitboard for each square on the board (two bitboards for a pawn - black and white would attack in different ways).

Sliding pieces are the culprit yet again - there's not really a good way of representing a state of occupancies in the board to be able to map the combination of each square + blocking pieces to all the attacks it can make. This is where Magic Bitboards come in handy. This is a pretty hard to understand topic and it took me some time with the resources at hand - so I've written a small note in the repo for how Magic Bitboards work to make life easier for anyone trying to understand them.

You can check out the article here.

Making Moves#

So we finally have an easy way to find all the attacks for all possibilities of squares, pieces, and blocking pieces. Generating all possible moves now merely becomes a matter of programming it to do so. Just gather all pieces on the board, iterate through every pieces, see what all it attacks (and pushes / en passants in the case of pawns), and append this to a list for all moves. The move generation logic is in BoardState.Moves.cs.

Making a move, however, requires a few extra lines of code - but nothing too complicated to understand. Let's think of how we would make a move.

• Remove the piece from the square it was on.
• Place it on the square that it is going to.
  • If there was already an opponent's piece on that square, remove it (capture).
• Handle extra conditions for Castles, Promotions etc.
• Update the board state with things like Castling Rights, En Passant etc.

Now you would have noticed in the code that we didn't really make sure the move is legal - i.e. we make the move regardless of whether the king was already in check or it moves into check. This is called pseudo legal move generation and is one of the ways of generating moves - we worry about the legality at a later stage, when we are actually going to be making the move and evaluating it.

You can check out BoardState.cs for the implementation for MakeMove()

Conclusion#

This concludes part one of making a chess engine - we managed to generate all moves and represent the board properly. What's next is being able to communicate with this chess engine using the UCI protocol, and later to actually implement some logic for finding out what the best move in a position is.

Part 2 of this blog can be found here