Rudim [2] - .NET Core Chess Engine - UCI Protocol & Evaluating Positions

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.

Where we left off#

At this point, Rudim can generate all moves for a position and represent the board properly. We leave the 'brain' of Rudim (picking the best move) for later - and just make sure our implementation is working as expected by trying to load it into a chess GUI.

For this, Rudim needs to be able to talk to other chess engines and GUIs. There are two major protocols that are used

• XBoard / WinBoard (CECP)
• UCI

XBoard used to be the most popular choice a couple of years ago but UCI quickly overtook this as it was a lot more simplified and worked well. Very few chess engines today still use XBoard / WinBoard. Hence, I decided to go ahead with implementing UCI.

UCI#

The UCI Protocol is available for download on the shredderchess website (linked above). Going through the entire document, you would be able to understand the extent to which UCI can communicate with the engine and how the engine communicates back with the CLI.

Let's take a small glimpse into how UCI works.

The above diagram is a vastly oversimplified version of how UCI is actually used and is just to give an idea of how the commands work.

There needs to be some interface between the GUI and the Engine that is able to read the GUI's board state and convert it into a set of UCI-compliant commands, which we shall call the orchestrator.

The orchestrator first intializes everything. i.e. sets the GUI to the starting board, connects to the engine etc. Once the Orchestrator has connected to the engine, it will send a set of commands - the first one being uci to let the engine know that it has started streaming UCI commands. It would then send the position command to the engine to initialise the position of the board and then tell the engine to go, or start searching for the best move.

There are other commands like isready which are sent to the engine but I've left it out for simplicity - the UCI specification has a detailed explanation on all of them.

The go command has a extra few parameters which tells the engine how much time is left, how much increment is present etc. For our use case, we won't really need to parse these yet as we don't have a working implementation of searching the move tree to find the best move - but we will make use of these later and for now just instantaneously return a random legal move.

Now assume the engine has found the best move to be 1.e2 e4. It will then send an output line to the console (UCI CLI) saying bestmove e2e4. The orchestrator will pick up this move and communicate with the GUI to show the change. A human playing against Rudim will then see this change and play a move that they find to be strong.

Let's assume the human played e7 to e5. The orchestrator then picks up this change from the GUI and sends the new positions FEN back to the engine and asks it to search for a best move, and this repeats.

If the game was between two engines, the orchestrator doesn't need a GUI and merely communicates with the two engines via UCI - sending all of black's turns to one engine and all of white's turns to the other engine.

This would hopefully give you a brief understanding of what UCI is. Implementing it is trivial (for now) - merely accept all inputs from the CLI and do whatever UCI expects you to do based on the command.

The implementation Rudim has for UCI can be found in CLI/UCI. I've currently implemented the minimum commands to be able to run the engine on Arena.

We finally have UCI in place! Well, not really. We left out a lot of commands and options for the go command. Let's work on making the engine implement evaluation and searching and come back to UCI after that.

Evaluating Positions#

Our chess engine now needs to be able to look at a random position and rank the moves based on which it finds to have the most advantage for the side it is playing.

Evaluating Positions is a very deep topic and there are many optimizations and methods to evaluate positions - with NNUE being the most popular (and successful) one in recent years.

Let's start off at something simple. This will mean that our engine will play horrible chess initially, but I like to follow my own rule of thumb saying it's better to have something working which is bad than have nothing working in the hope that it will become the best. We will later improve on our evaluation, searching, and move generation to improve the quality of chess Rudim plays.

We shall give each position a score - which is going to be merely an int. The more positive the number, the better for white. The more negative the number, the better for black.

Material Advantage#

The most basic sign of an advantage for a side is the material advantage. Take the below position for example - it is evident that white has a large advantage because of the number of pieces and the types of pieces they have in comparison to black.

A simple way of evaluating material advantage is using centipawn values. I've taken the values from the Simplified Evaluation Function's Constants.

Adding these values to our score would look something like this :

private static readonly IDictionary<Piece, int> PieceValues;

static SimpleEvaluation()
{
    PieceValues = new Dictionary<Piece, int>()
    {
        [Piece.Pawn] = 100,
        [Piece.Knight] = 320,
        [Piece.Bishop] = 330,
        [Piece.Rook] = 500,
        [Piece.Queen] = 900,
        [Piece.King] = 20000
    };
}

public static int Evaluate(BoardState boardState)
{
    int score = 0;

    score += ScoreMaterial(boardState);

    return score;
}

private static int ScoreMaterial(BoardState boardState)
{
    var materialScore = 0;
    for (var piece = Piece.Pawn; piece < Piece.King; ++piece)
    {
        materialScore += PieceValues[piece] * BitOperations.PopCount(boardState.Pieces[(int)Side.White, (int)piece].Board);
        materialScore -= PieceValues[piece] * BitOperations.PopCount(boardState.Pieces[(int)Side.Black, (int)piece].Board);
    }
    return materialScore;
}

Positional Advantage#

Now let's add one more small factor to our score so that our evaluation is atleast a bit stronger. Consider the below position. Both the sides have equal pieces - but it's evident that white has a clear advantage and black seems to be crammed into a corner and about to lose.

White's pieces are on more favourable squares - and much more developed than blacks pieces. So we should adjust our score such that for each piece, we would either reward or penalize the score based on where the piece is on the board. Clearly, the black pawns being so far back and away from promotion are not that well placed, and the queen in a corner too. Ideally the king should also be towards the center of the board in the end game, to be able to support the pawn pushes.

This adjustment of score can be achieved with Piece-Square Tables. Rudim uses the Piece-Square Table values in the Simplified Evaluation Function and the code is mostly similar to the above code - instead we also check the square which the piece is on (Refer SimpleEvaluation.cs). If you scroll to the bottom you'll notice that there are two separate values for the King's tables. This is because we don't want the King running to the center of the square in the middle game and getting mated. We want it to be safe and castled until most of the pieces are off the board.

Game Phase & Tapered Evaluation#

This brings us to understand a concept called Game Phase. Generally, we can define the game in three phases - Opening, Middle Game, and End Game. More advance chess engines make use of these phases for things like Opening Books, End Game tables etc. but for now let's use phase to understand Tapered Evaluation.

Let's assume we can efficiently classify whether a position is the middle game or end game. If we could, we would notice a sudden change in the moves being predicted by our engine during that transition. We would also notice that it may bring ambiguity when a piece promotes. This inability to be able to clearly define a middle and end game would mean a poor performing engine.

This brings us to tapered evaluation which sort of says, this position looks 40% like a middle game and 60% like an endgame so evaluate it treating it as such . This allows for smooth transition between phases in our engine, allowing for stronger evaluations. The concept for implementing this is very simple - the more material there is on the board, the more likely it is a middle game than an end game.

Here is a snippet of Rudim's Tapered Evaluation.

GamePhase.cs#

private static readonly IDictionary<Piece, int> PieceConstants;
public static readonly int TotalPhase;

static GamePhase()
{
    PieceConstants = new Dictionary<Piece, int>()
    {
        [Piece.Pawn] = 0,
        [Piece.Knight] = 1,
        [Piece.Bishop] = 1,
        [Piece.Rook] = 2,
        [Piece.Queen] = 4,
        [Piece.King] = 0
    };
    TotalPhase = PieceConstants[Piece.Pawn] * 16 + PieceConstants[Piece.Knight] * 4 + PieceConstants[Piece.Bishop] * 4 + PieceConstants[Piece.Rook] * 4 + PieceConstants[Piece.Queen] * 2;
      
}
public static int Calculate(BoardState boardState)
{
    int phase = 0;
    for (var piece = Piece.Pawn; piece < Piece.King; ++piece)
    {
        var whiteBoard = boardState.Pieces[(int)Side.White, (int)piece].Board;
        var blackBoard = boardState.Pieces[(int)Side.Black, (int)piece].Board;

        phase += PieceConstants[piece] * BitOperations.PopCount(whiteBoard);
        phase += PieceConstants[piece] * BitOperations.PopCount(blackBoard);
    }
    return Math.Min(phase, TotalPhase);
}

SimpleEvaluation.cs#

var midgamePhase = GamePhase.Calculate(boardState);
var endgamePhase = GamePhase.TotalPhase - midgamePhase;
if (piece == Piece.King)
{
    var whiteKing = whiteBoard.GetLsb();
    var blackKing = MirrorSquare(blackBoard.GetLsb());

    positionalScore += ((MidgameKingValues[whiteKing] * midgamePhase) + (EndgameKingValues[whiteKing] * endgamePhase)) / GamePhase.TotalPhase;
    positionalScore -= ((MidgameKingValues[blackKing] * midgamePhase) + (EndgameKingValues[blackKing] * endgamePhase)) / GamePhase.TotalPhase;
}

At this point Rudim should be able to evaluate positions as any new player would. There are lots of optimizations and improvements that can be done - like analyzing pawn structures, penalizing pinned pieces etc.

Conclusion#

Now that Rudim can evaluate a position, the next step is to implement a searching algorithm to go deep into all the possible moves and see which one would be most advantageous by calculating the evaluations at large depths.

Part 3 of this blog can be found here