See History section below for list of changes.
Introduction
This is a fully functional yet simple chess program that aims to help you understand how a chess engine works. There are already open source chess engines on the Internet which focus on high performance. This is a standard object oriented C# solution that is meant to be easier to comprehend. The focus has not been to make a fast and high rated chess engine. I have developed a working chess AI that plays descent good moves with code that you hopefully like to read. A few of the more specific goals have been to correctly implement Alpha Beta Pruning and Zobrist Hashing using C# 6.
Table of Contents
Background
The Code
How to Start
Features
The Chess Engine
The Board and the Game
Moves
Evaluation
Search
Performance
What I have learned
History
Background
About ten years ago, I tried to implement a chess engine and failed. This time, I decided to use Test Driven Development (TDD) test first approach. I like TDD and I think using TDD was the main reason the engine worked this time. It is very important that the rules of chess are 100% correctly implemented. Equally important is that undoing moves result exactly into the previous state. I also think that TDD contributes to good code structure and a maintainable system design.
The Code
The solution consists of two main projects. The engine (chess.dll) and the user interface. Chess.dll has everything about the game, the board, the rules and the engine. It also contains all tests. I saw no reason for having unit-tests in a separate project in this implementation. This way, one can easily see what unit-tests belongs to which class.
There are currently 82 tests. Most of them are very fast and code coverage is about 100%. Total number of lines of code are just under 4000, including tests and user interface. The engine and game class where most of the logic is, is less than 900 lines of code.
There is also a small project called BitChess that is under construction.
The Chess UI is a Windows Forms application with only a few features like load, save and setting the time for computer to think. You can also edit and setup custom board positions and save and load FEN-positions.
How to Start
If you are new to TDD, it is very common to think: -“Where should I start?!”. And -“How can I test something that does not exist?” The solution is to write tests that don’t even compile and you will drive the design and the program in the right direction. The first test I wrote when starting this project was:
[TestMethod]
public void BoardHasSquaresTest()
{
var board = new Board();
Assert.AreEqual(64, board.Squares.Length);
}
In Visual Studio, you can then use the built-in short-cuts for generating the missing types and members your test case needs to compile.
There is a lot of free and good literature on the web explaining the different algorithms and techniques in a chess engine. Below, you can find links to pages that have helped me.
Features
- Iterative Alpha-Beta Pruning, which drastically decrease the number of positions that need to be analyzed. At depth zero, a depth two Quiescence Search is also performed to prevent the risk of Horizon Effect. This is a very important feature of a chess engine that I don’t cover so much in this article. But if you don’t extend the search with a Quiescence Search, it’s a high risk that the engine sometimes will make very bad moves.
- Zobrist Hashing to create fast lookup for already evaluated positions. I keep a few million positions in a database so every position only has to be calculated once.
- Parallel threads to increase performance of engine if multiple cores are available.
- The chess board is represented by a single square[64] array. (Bit-boards are a lot faster but perhaps little bit more complicated.)
- Score of the position is based on material and a positional score for each piece. In the opening, a few basic opening principles give extra points. Special calculations are also performed in the end game.
- Draw by repetition, insufficient material, 50 move rule and stale mate are also evaluated.
- Opening book is not yet implemented.
The Chess Engine
This is how my chess engine is implemented.
The Board and the Game
The engine must of course understand what a chess game is. A game has two players. Players have pieces and each piece type has its properties. The game is played on a board which has squares. A square can have a piece on it or not. Below is the class diagram of those types. Click to enlarge.
Moves
Each piece type has a move pattern. It is used to generate moves. A list of pseudo legal moves is generated for all pieces of a player. The legal moves are kept. The code snippets below are from the game class.
internal List<move> GetPseudoLegalMoves() {
var moves = new List<move>();
foreach (var piece in CurrentPlayer.Pieces)
piece.AddPseudoLegalMoves(this, moves);
AddCastling(moves);
return moves;
}
After a pseudo legal move is made, it is tested whether the own king is in check. Own king can´t be in check after a move so those moves are illegal.
private bool KingChecked(Player checkedPlayer) {
var kingSquare = checkedPlayer.King.Square;
var otherPlayer = checkedPlayer == WhitePlayer ? BlackPlayer : WhitePlayer;
foreach (var piece in otherPlayer.Pieces) {
if (piece.Attacks(kingSquare, Board))
return true;
}
return false;
}
Evaluation
It is actually better to evaluate moves right away in move generation and not during engine search. This is because the search is much more effective when moves are ordered. When better moves are evaluated first, it is more likely that the search can disregard many moves. More about that later.
Evaluation gives a score. If black is better, it is positive and negative for positions in favor of white. Each piece has a value. Queen is nine. Rook five. Bishops and knight three and pawns are one. The material score is sum of black’s pieces subtracted by sum of whites. Position of pieces are also important. The engine evaluates:
- Control of center (d and e pawn on rank 4 for white and rank 5 for black)
- Rooks on open files
- Queen movement in the opening is bad
- Castling to get the king safe is good
- Bad knights close to the border
- Double Pawns
- Moving bishops and knights once and only once in the opening is good
Evaluation is also about the game ending and who is the winner. When a player is in check and has no legal moves, it is check mate and the score is set to a very large number if black wins and very low for white.
private int NoChildrenEval(Game gameCopy, Move node) {
if (gameCopy.CurrentPlayer.IsChecked) {
node.ScoreInfo |= ScoreInfo.Mate;
node.ScoreAfterMove = 8000;
gameCopy.Winner = gameCopy.OtherPlayer;
} else {
node.ScoreInfo |= ScoreInfo.StaleMate;
node.ScoreAfterMove = 0;
}
gameCopy.Ended = true;
PositionsDatabase.Instance.Store(gameCopy, node);
return node.ScoreAfterMove.Value;
}
As you probably know, a chess game can also end in draw if a player has no legal moves (Stale mate) or if a game has repeated the same position three times. The game also ends in a draw if no capture or pawn move has been made the last 50 moves.
Search
Now that we can tell bad moves from good, we can search for good moves. The search starts at depth one. White player makes his moves and between every white move black player makes his moves for every white move. Since black player will try its best to get as large score as possible, the best move for white is the move that results into a list of black response moves with the lowest max value. This min max search is also greatly improved by an algorithm called alpha beta pruning, which cuts off many obviously bad moves.
This is a link to a nice animation explaining Alpha Beta Pruning.
Below is also the simplified version of the recursive alpha-beta function as pseudo code.
int alphaBeta(Move node, int alpha, int beta, bool maximisingPlayer) {
int bestValue;
if (node.children.length === 0) {
bestValue = node.data;
}
else if (maximisingPlayer) {
bestValue = alpha;
for (var i=0, c=node.children.length; i < c; i++) {
var childValue = alphaBeta(node.children[i], bestValue, beta, false);
bestValue = Math.max(bestValue, childValue);
if (beta <= bestValue) {
break;
}
}
} else {
bestValue = beta;
for (var i=0, c=node.children.length; i<c; i++) {
var childValue = alphaBeta(node.children[i], alpha, bestValue, true);
bestValue = Math.min(bestValue, childValue);
if (bestValue <= alpha) {
break;
}
}
}
return bestValue;
}
The cut off mechanism is much more efficient if moves are order and the best moves are performed first. The same search is repeated again with the depth increased by one until the set time runs out. After each iteration, the moves are ordered so good moves are evaluated first. It might seem very inefficient, but it is actually a much faster way to find the best move to iteratively increasing the depth than going for a decided depth from the beginning.
If you managed to get everything right, something very cool happens now. Your program suddenly starts to show some intelligence. But you are far from finished. You probably want to make the search more efficient, searching at greater depth and improving performance. What will probably take most of the computer time is score evaluation, and that can be stored in memory with a Zobrist Hash Key for fast lookup.
To further improve performance the goal is to create a key as unique as possible for any setup of the chess board. That key could then be used to store information and quickly load it when the same position is evaluated.
The problem is that the chess board can be in an enormous amount of different states. Each of the 64 squares can have one of twelve different piece types. What also defines the unique state is which player is in turn to play and what castling rights each player has (queen side or king side). It is said that the number of combinations a chess table state can be in, is greater than the estimated number of electrons in the universe!
Zobrist Hashing remarkably solves this by creating a key of just eight bytes. At game start, 768 (64 squares times 12 piece types) different numbers are generated. When a player moves a pieces the previous game hash is changed with a few exclusive or operations(xor) using the state changing random numbers. In most cases, there are only two operations.
When updating the hash-key you should also think of promotion, capturing and castling but these two lines are the most important in the Zobrist Hash Key implementation.
game.Hash ^= ZobristArray[piece, fromSquareIndex];
game.Hash ^= ZobristArray[piece, toSquareIndex];
If you apply the same exclusive operations twice you actually get back to the same Hash Key. That is very useful when undoing moves.
The Zobrist Hash Key is stored in a memory database together with an integer containing a little data about the position. These data only have to be calculated once. Next time the same hash key shows up, the database is queried with the key.
This is the data that is packed in an 32 bit integer. The data is packed to decrease size and increase access to the database using bit shifts.
- Command Number (7 bits), used for cleaning old positions not needed
- If the move was legal, i.e., own king in check (1 bit)
- Opponent king check (1 bit)
- The score of the board (13 bits)
- Free bits not used. (5 bits)
- Draw by Repetition, Insufficient Material, Stale Mate and Mate (4 bits, one bit each)
Function for packing some game data into an integer.
int Pack(byte commandNo, bool legal, bool check, int score, ScoreInfo scorInfo) {
var freeBits = 5;
var build = (int)commandNo;
build <<= 1;
build |= (legal ? 1 : 0);
build <<= 1;
build |= (check ? 1 : 0);
build <<= 1;
build |= score < 0 ? 1 : 0;
build <<= 13;
build |= Math.Abs(score);
build <<= 5;
build |= freeBits;
build <<= 4;
build |= (byte)scorInfo;
return build;
}
Unpacking the game data.
void Unpack(int build, out byte oCommandNo, out bool oLegal, out bool check,
out ScoreInfo oScoreInfo, out int oScore) {
oCommandNo = (byte)((build >> 25) & 0x7F);
oLegal = ((build >> 24) & 1) == 1;
check = ((build >> 23) & 1) == 1;
var negScore = ((build >> 22) & 1) == 1;
oScore = (build >> 9) & 0x1FFF;
oScore = negScore ? oScore * -1 : oScore;
var freeBytes = (byte)((build >> 4) & 0x1F);
oScoreInfo = (ScoreInfo)(build & 0xF);
}
The engine analyzes about 50k positions/sec on my dual core 2.7Ghz laptop. Which is mostly enough to see about five or six moves ahead in the middle game. Most average skilled chess players (like me) should have quite some difficulty beating the engine given the same time to think. When testing it in a chess.com CPU game, I estimate it has a rating around 1300. I think the best way to improve its performance would be to replace board representation with a bit board. That could increase move generation and position evaluation so even deeper searches could be performed.
What I Have Learned During this Project
It is very important to write unit tests and perhaps even write them first. In TDD, you have to have a failing test before you can write the function. This is an excellent way of assuring everything is tested.
The Alpha Beta algorithm is probably the most challenging part of a chess engine. There are many pseudo code examples on the Internet. I only managed to get one of them to work. It is the one from Algorithm Wiki.
Hashing is an important part of Chess programming. The board has to save a position score for faster access. The hash is stored in a 64 bit datatype but there are many more possible states that a chess game can be in. I find it quite remarkable that there were no hash collisions after I implemented the Zobrist hashing that very effectively spreads the risk of having hash collisions.
It is important to run performance profiling. The faster the analysis becomes, more positions are analyzed every second and even some small improvements can have large effects on overall performance.
Another good site for learning is the Chess Programming Wiki.
Chess engines are a big topic and a lot of research has been done on the subject during the centuries. I’m not sure you will be able to write your own chess engine just by reading this article, but hopefully it is a good introduction and it will point you in the right directions if you are interested in becoming a chess engine developer.
History
- Jan 31, 2017 - Version 1.0
- Feb 10, 2017 - Version 1.1
- Edit board functionality
- Pimped UI - Thanks to Daniella Di Lena for the free pictures
- Feb 12, 2017 - Version 1.1.1 (Bugs and performance fixes)
- Feb 19, 2017 - Added code examples in the text and rewrote some parts for better understanding.
- Mar 5, 2017 - Wrote more about Zobrist Hash. Added a TOC.
- May 23, 2017 - Version 1.2
- 50 move rule
- Edit FEN
- Performance and stability
In case this article has inspired you to start digging into this subject and become a chess engine developer, please send me a comment, a question or just say Hello. :)
Happy code reading and good luck on your chess programming learning!
