I am interested in chess and always wanted to write my own chess engine. About a year ago I started to code my own engine MantaChessEngine in C#. The goal is that the engine beats me. As I’m not a strong player that should not be much of a problem. Today my engine can actually play. Last time I played I won and since then I haven’t significantly improved its strength. So obviously I’m not yet done. If you are interested you can watch the engine progress on Github…
In this article I give a short introduction on how to code a chess engine. If you are interested have a look at the code of my chess engine on Github: MantaChessEngine.
Chess Engine Framework
The framework itself is very simple. It holds references to all the parts of the engine and lets the client access the methods required to play a game of chess. It also holds a reference to the board with its pieces.
I wanted to be able to let one instance of the engine play versus another instance of the engine with the same or with a different configuration. That way one could see how a certain search or evaluation strategy would do versus another.
And of course the engine needs to be easily testable!
Here is an overview of the main classes and interfaces used:
Board Representation
The board holds an array of chess pieces. It can get and set pieces and it can execute moves and take moves back. It knows the state of the board: it knows which player still has the right to do one of the castlings and it knows which pawn has the right to do en passant capture. The board holds a reference to the History object that contains a list of the previously executed moves and board states.
Searching for the Best Move
A chess engine needs to find the best move for one player. Lets say we want find the best move for white for the next 2 plies (1 ply = 1 move of one player). So first the MoveGenerator must find all possible moves for white and then for all those moves it must find all answers of black. Now the Evaluation must evaluate all the end positions. Note that all the moves are followed down to the maximum depth. Even if a queen gets lost after the first ply we still follow the moves to the maximum depth and only then evaluate at the end. The last step is to propagate the choices for each move of black and of white back to the first move. Now we have the best move or at least the best move for that particular algorithm.
Move Generator
The main method of the MoveGenerator is GetAllMoves(color). I implemented my engine as a king capture engine. This means that GetAllMoves() returns a list of all pseudo legal moves for one opponent. Pseudo legal means all the normal moves are included in the list that each chess piece can do. It even includes the moves where the own king is under attack. These illegal moves must not actually be played. These moves will be filtered out later when the evaluation of the position takes place.
There is however one situation where the MoveGenerator returns no moves: if the player has lost its king. As the game has ended already we do not follow all moves down to the maximum depth in this situation.
In my first implementation of the MoveGenerator I did it all in one class. It was easy to test but became astonishingly complicated with a deep nesting of ifs and switches. Then I refactored out the chess pieces Pawn 615-544-5451 , Bishop, Knight, Rook, Queen and King. They all know how they are allowed to move on the board.
Evaluation
The Evaluation calculates the score of the board. If the score is positive then white has the better position, if the score is negative black is better.
My simplest Evaluation was to just add up points for all pieces, positive for white, negative for black: Pawn 1, knight 3, bishop 3, rook 5, queen 9. If the king is missing it returns the score for a lost game.
My next Evaluation includes some position info of the piece. Pawns for instance get 1.2 points if they are in the center or the knight gets 1 point in the middle of the board and 0.95 at the border. The player with two bishops gets a bonus of 0.5 points.
I guess there could be more useful special cases like check gives extra points or a rook on open file which I have not tested yet.
Minimax Search
Lets have a look at the minimax algorithm that I used to search the best move (see image). In this example we search to the maximum depth of 2 plies. At “start” white can do two different moves: w1 and w2. As response to w1 black can do move b1 or b2, to answer w2 black can do b3 or b4. The Evaluation calculates the score of each end position. After move b1 it calculates the score 1, after b2 it calculates -1, and so on.
Let black choose its move. Black wants to have a score as low as possible, white wants as large as possible. In black’s move of course black can choose. From b1 or b2 it chooses b2 because the score is lower, from b3 or b4 black chooses b3 (circle in the image).
The chosen scores propagate back so that white can choose from. White knows its move w1 will score -1 and w2 will score 2. 2 is greater so white chooses w2.
I hope this short intro gave you an overview on how to code a chess engine and made you curious to have a look at the code of MantaChessEngine on github or even to start your own engine.