Due to the complexity of this topic I have divided this post into two entries.  This article will discuss the Transposition Table and Zobrist Hashing techniques with no code samples.  The second part in the series will discuss the code used in my chess engine.

An Alpha Beta search will often have to consider the same position several times.   This occurs due to the fact that in chess there are many ways to reach the same piece arrangement.   For this reason most chess engines implement a Transposition Table that stores previously searched positions and evaluations.

The problems

The first problem is that although same chess positions do often re-occur during an alpha beta search, we can only count on having this happen somewhere between 15%-20%.  We can’t know which positions these will be ahead of time so for every 100 entries we save in our Transposition Table we might only use 20 entries.  Hence whatever Transposition Table scheme we choose, it has to be very efficient because we will be storing and searching more useless entries than useful ones.

In a perfect world we would have the ability to simply save every single node we search in our Transposition Table.  Unfortunately this is simply not practical.  The memory requirements for this scheme would be higher than most computers can accommodate.  Furthermore the time wasted on searching such a large table would outweigh any time saving benefits.  So we have to accept that our Transposition Table is limited in size will not store all the nodes we search.

Implementation

First we need to figure out how uniquely identify each position we come across.  This has to be extremely efficient since we will have to do this for every node in our search.  Simply converting the chess board to a string of values like FEN is far too slow. 

Zobrist Hashing

Fortunately for us a process for indexing game positions called Zobrist Hashing has already been invented by professor at the University of Wisconsin by the name of Albert Zobrist.

The Zobrist Hash uniquely representing our chess board will be a 64 bit variable.  In C# we can implement this as an unsigned long (ulong).  We calculate a chess boards Zobrist Hash using the following steps

1.       Generate an array of 12 * 64 Pseudo Random numbers representing each chess piece type on each of the 64 positions on a chess board.  You only do this once at when your chess engine initiates.  This will give you a single hash value for every single chess piece for every single position on the board.  You will have to elect which portions of the array represent which chess piece.  Let’s say you choose to have the first 64 entries in your array represent the white pawn.  So the 9^th value in your array will be White Pawns A2 square etc.

2.       For each chess piece on the chess board XOR its positions random number against the current Zobrist hash value.  So a white pawn on B2 might be the 10^th value in the array.

This is easy enough, however we don’t necessary want to calculate the Zobrist hash from scratch each time we make a move.  That would be very slow and would make the whole exercise futile.  For this reason each time a move is made on our chess board, whether during game play or alpha beta search we simply update the Zobrist Hash by:

1.       XOR the chess pieces previous positions random number against the current Zobrist hash value, this erases the chess piece from our hash.

2.       XOR the chess pieces new positions random number against the current Zobrist hash value adding the chess piece back to its new position.

A bit about the XOR operator:

If you don’t understand what I mean by XOR in the above paragraphs you may want to read this:

 XOR or Exclusive Or is one of the standard bit operators available to you in most programming languages.  By bit operator I mean it allows you to manipulate the individual bits in a value.  If you are not sure what that means, you might need to Google this first.  The one nice side effect of the XOR operator is that if you XOR a value 2 times by the same value it will return to its original value.    

For example

1110 XOR 1001 = 0111

0111 XOR 1001 = 1110

In order to add and remove chess pieces from our hash we will be using the XOR operator to add the chess piece to a position and then use the XOR again to erase it once it moves.  For example if we XOR the Zobrist Hash representing our chess board against the 64 bit number representing a white pawn on A2 it would be like adding the pawn to the chess board on A2.  If we do it again we remove or erase the pawn from A2.  We can than XOR the hash against the 64 bit value representing a white pawn on A3.  The last 2 operations would essentially move the white pawn from A2 to A3.

Collisions

Right about now you might have noticed that a 64bit value is not large enough to represent every single possible chess position.  So using the above scheme it is possible to have 2 different chess positions evaluate to the same 64 bit hash value.  This is called a collision and no matter how you implement this, you will always have a small chance of a collision.  The key here is to minimise the chance of a collision down to a small enough value so that the speed gain you get from having a transposition table (and perhaps constantly deeper search) outweighs the negative effect of the possibility of a collision.  In most chess circles a 64 bit value is considered to be large enough to make collisions not a practical problem.

Transposition Table Contents

So what goes in a transposition table entry?  Here are the items included in my Transposition Table:

Hash: This is a Zobrist Hash representing the chess position

Depth: The depth remaining in the alpha beta search.  So depth 5 would mean the score is recorded for a 5 ply search.  This can also be referred to as the Depth of the Search Tree.

Score: The evaluation score for the position.

Ancient: Boolean flag, if false the node will not be replaced with a newer entry.

Node Type:  There are 3 node types, Exact, Alpha and Beta.  Exact means this is an exact score for the tree.  However in the events that an alpha beta cut-off occurs we can’t use the score as an exact score.  An Alpha Node Type means the value of the node was at most equal to Score.  The Beta Node Type means the value is at least equal to score.

Replacement Schemes

Since your Transposition Table can’t hold all the moves searched in a game you will have to start replacing your entries fairly soon.   In the same time you don’t simply want to replace all entries regardless of their usefulness.  For this reason in the event that I find an entry that is useful (was used in a lookup), I set a Boolean flag Ancient to false, meaning doesn’t replace.  This way you always replace entries that are unused and keep the ones that were historically useful.  To prevent your table from filling up with Ancient nodes from 10 turns ago, the Ancient flag gets set to true for every entry after every search.

Table Lookup

The last problem we have to find is how to we quickly search a Zobrist Table.  We can’t just do a for loop.  This would be slow.  The trick is actually in how we store the entries in the first place.  Rather than simply adding an entry in the order we received them we calculate the entry index as follows:

Table Entry Index =  Hash mod TableSize

This way when we search the table to see if a certain Hash exists we know there is only one place it could be stored Table[Hash mod TableSize]

That’s it for this article on the Transposition Table.  Stay tuned for the next article that will discuss C# implementation.

Now that we have all the necessary parts for keeping track of our chess pieces, generating valid moves and searching for the best computer move, we are ready to put it all together and complete our chess engine.  We have already started to discuss the chess engine class in the previous post titled: Starting the Chess Engine.  Just to recap that post we have already:

Declared the class as:

Declared its internal members representing our chess board and the previous chess board as well as variables representing whose move it is.

Declared a constructor that will initiate the chess board, move history, pre-calculate all possible moves from all positions, register starting positions of a new chess game and calculate all valid moves from that position.

Since we now have discussed the Chess Board Evaluation class I will modify this listing slightly to evaluate the board score as its last operation.

We also created a Move Piece method that will allow us to move chess pieces around the board.  The important fact to notice here is that if the move fails, say because it would cause an invalid position, the chess board reverts to its previous state.

That’s it for the review now onto the remainder of the code needed for our chess engine to successfully play chess.

First we will introduce a few public variables:

We want to know which side of the board contains the human player.

We need to know how deep to perform the AI search, how many plies. Remember each ply is a single move.  So if white moves that is one ply, if black responds that is two ply.

We also would like to keep track of all of the moves made during the game.  This will solve two problems.  First in order to call a draw for a three move repetition we need to somehow know what moves have been made.  Second we might want to be able to display the move history to the human player as we go along.

First we need to declare the OpeningMove class:

The next method will add moves to the above declared Current Game Book as they occur.  This method also searches the Game Book to see if a repeat move has occurred.  Notice the use of FEN notation to store the chess board history.  More on FEN notation in the next post.
Now we have a mechanism for testing for 3 move repetition.  Remember our chess board class already handles the 50 move rule.  The last step is to create a method that will check for mate scenarios, check and stale.  This method takes advantage of the code we already wrote in the Move Search class that checks for all available moves and records if the king has any moves not in check.

The last method will make the chess move for the computer as well as check for mate, and save current game moves.  This is the method our external user interface calls when we want to get the computer to make the move.  Otherwise if the human player is moving you would just call the move method.  Notice that the check for mate method is called two times.  Once before the move is made and once after.  This is because the previous human move might have caused a mate (first call) or the computer move might have caused a mate (second call).
The above methods are all you need to start coding your chess user interface.  However because we have declared most of our variables as private or internal if your user interface is in another assembly you might need a few additional methods that will expose certain properties of your chess board and chess engine.  I have included some of these below.

Notice this method will check for all game ending scenarios including 50 move and 3 move repetition.

This post is a bit of a milestone as it wraps up the bulk of the chess engine source code.  There are still a few points I have not discussed such as an opening book or some more advanced search features such as Quiescence, FEN, Pondering, Iterative Deepening or Principle Variation Search.   However the sum of the code posted thus far will provide you will a working chess engine that will play fairly good chess.

If you feel like you don’t want to start typing up all the code posted here, I have made available a C# chess engine starter kit that includes most of the source code you will need to start a chess engine including a simple user interface.  You can download the development kit from here.

Over the last month I have been focusing on increasing the performance of the move generation code in my Chess Engine.  Based on my tests I believe I have gained about a 25% speed improvement in move generation.

The largest speed gain came from the removal of the Board Column and Board Row members from the Board Square class.  I came to a realization that I have been storing the same information about the position of the chess piece 2 times.  Once in the Board class via the 64 square array indexers and once in the Board Square class in the Board Column and Row variables.  Although having the Board Column and Row specifically in the Board Square class made it much easier to understand my code, at the end the performance loss was not worth it.

Unfortunately this means that I have to modify some of the code listings in previous entries so that the next sections will make sense.  I will eventually also modify the Chess Game Starter Kit to include the newer faster code.

Until then if you are waiting for the next sections of the chess engine, please be patient until I finish updating the previous entries.

2008-Dec-06 Performance Reconstruction is now complete (at least for now)

 

From what information I could gather on the internet, it seems that most experts agree that the evaluation function of a chess engine has the greatest capability to dictate the strength of your chess game. Rybka, currently considered to be the top computer chess engine in the world, is not famous for its search speed but rather for its advanced chess board evaluation written by an international chess master.  Furthermore the evaluation function can make your move searching faster by allowing your chess engine to search better moves first.

Unfortunately for you Rybka’s evaluation function is not available.  To make things worse I am not considered by anyone to be a chess master.

Chess Piece Evaluation

As seen in the Chess Piece Class, the following values are assigned to chess pieces:

    Pawn     100
    Knight   320
    Bishop   325
    Rook     500
    Queen    975
    King     32767

About the numbers.

Writing your chess board evaluation method, think about the numbers as percentages of a pawn.  In my chess engine a pawn is worth 100 points.  If you award 10 points to a tactical position you are telling the chess engine that this position is worth 1/10th of a pawn.  The problem can arise when a move combines several tactical advantages for the moving side and several tactical penalties for the opponent.  This can result in unnecessary pawn sacrifice for set of minor tactical advantages.  When writing your evaluation function always keep this in mind.

The Chess Board Score is represented by a signed integer.  The higher the score the better it is for White.  The lower the score the better it is for black.  Using a single integer makes everything a bit faster since I can always just reference one variable.

For example if the value of a single pawn is 100 points and there was only one single black pawn on the chess board the score would be -100.  If there were two pawns, one white and one black the score would be 0.  If white had 2 pawns and black 1 pawn the score would be 100. 

On to the code

Chess Bin Board evaluation is implemented as a static class with two static methods. 

We first declare our Piece Square Tables discussed in the previous post:

The first method will evaluate the score for a single chess piece on the board.

We declare a single variable representing the score for the current chess piece.  This score will always start at 0 and go up if the position is evaluated to be better, and go down if the position is evaluated to be worse.  When the score is returned to the main Evaluation Function, it will be subtracted for black and added for white.

We also declare one local variable that will hold a position we will use to look up the Pieces Piece Square Table value.  As you saw above the Piece Square Table is an array of 64 elements, basically representing the chess board from white’s perspective.  In that case we can simply use white’s position value to lookup it’s Piece Square Table value.  However if the chess piece is black, we need to invert its position to use the same tables for both white and black.
Each piece type has a value.  For example a pawn is worth 100 points, a Rook 500 etc.  We add that value to the score. During move generation we record how many pieces are protecting each piece on the board.  This is done by adding the protecting pieces PieceProtectionValue to the protected pieces ProtectedValue.  In the evaluation method we add this Protected Value to the score.   I know this sounds confusing.  The trick here is that I don't want to simply count the number of pieces protecting or attacking another piece.  Rather I want to give more points for being attacked or protected by a Pawn and fewer points for being attacked or protected by a minor or major piece.Similarly during move generation we added each attacking piece’s Piece Attack Value to the attacked pieces Attacked Value.  We now subtract the attacked value from the score.  The idea here is that we reward the computer for protecting its pieces and penalize it for having the pieces attacked.
Furthermore if the chess piece is getting attacked and it is not protected then will consider that piece EnPrise, meaning we are about to lose it.  There is an additional penalty applied by subtracting the Attack Value from the Score again.
We will also add score for mobility.  This discourages trapped pieces and blocked pawns.
 The remainder of the code is chess piece specific, starting with Pawns.

The following code will perform 3 Evaluations:

• Remove some points for pawns on the edge of the board.  The idea is that since a pawn of the edge can only attack one way it is worth 15% less.

• Give an extra bonus for pawns that are on the 6th and 7th rank as long as they are not attacked in any way.

• Add points based on the Pawn Piece Square Table Lookup.

We will also keep track in what column we find each pawn.  This will not be a pawn count but a value of what that pawn means in that column if we later find him to be isolated passed or doubled.  This information will be used later to score isolated passed and doubled pawns.

Knights also get a value from the Piece Square Table.  However knights are worth less in the end game since it is difficult to mate with a knight hence they lose 10 points during the end game.Opposite to Knights, Bishops are worth more in the end game, also we add a small bonus for having 2 bishops since they complement each other by controlling different ranks.We want to encourage Rooks not to move out of their corner positions before castling has occurred. Also if a rook is present on the board we will set a variable called Insufficient Material to false.  This allows us to catch a tie scenario if insufficient material is present on the board.

Furthermore we want to discourage Queen movement in the beginning of the game so we give a small penalty if the Queen has moved.
Finally in order to encourage the computer to castle we will remove points if castling is no longer possible.   Furthermore we will also take away points if the king has less than 2 moves.  The idea here is that if the king has only one move, we are possibly one move away from a mate.
At the end our method simply returns the score:

The second method in the Board Evaluation Class is a static method that accepts the chess board and the currently moving side.    This is the main Evaluation Function used in the chess engine.  It will evaluate board specific events such as check and mate as well as loop through all of the chess pieces on the board and call the above described Evaluate Piece Score for each piece.

At the beginning of the evaluation the score will always be set to 0.

We will also declare a variable called insufficient material that will be set to true only if enough chess pieces (material) are found to prevent the Insufficient Material Tie Rule.

The evaluation method will first examine board wide specific events.  Is there a check, stale mate, has any side castled etc.  Most of the work on figuring out these events has already been done in the Chess Piece Motion or Chess Board classes; all we are doing now is summing up the score.

Next we give bonuses and penalties for board level scenarios such as King Checks, Mates and Castles.
The following two integers will keep track of how many bishops and knights are remaining on the board.  This will allow us to give an additional bonus if a player has both bishops.  Also if there 2 are 2 knights we can't call the Insufficient Material Tie rule.
The following integer will calculate remaining material on the board.  We will use this later on to make the decision if we are currently in the middle or end game.  End game evaluation can differ from the middle game.  For example in the middle game Knights are very useful since they can hop behind enemy lines and take out vulnerable pieces, however in an end game Knights have a hard time placing the king in a corner for a mate so their value is slightly diminished.  Also castling in an end game has a diminished bonus.
We also need to keep track how many pawns exist in each column so that later we can figure out if we have any isolated and doubled pawns.

The next step of the evaluation is a loop through all of the chess pieces on the chess board and call the EvaluatePieceScore method defined above.
Next section does will handle the remaining board level events, such as calling a tie if there is insufficient material on the chess board.

After looping through all of the chess pieces we also know how many pieces are remaining on the chess board.  If there are less than 10 pieces we will mark the chess board as being in an endgame.  This way the next evaluation will change slightly based on the end game rules defined.

The last section of code uses the previously stored pawn position information and figures out if there are any doubled and isolated pawns.  Each one of these pawns are given a strong penalty.

This concludes the Chess Piece Evaluation.  The ChessBin evaluation function is by no means complete.  I will be spending some additional time on this evaluation function soon and post any updates to this page. 

In my experience modifying the evaluation function is extremely dangerous.  Even small changes can significantly weaken your chess engine.  The problem is that we are dealing here with a system of values that relate to each other in various and complicated ways.  It is difficult to tell ahead of time how a small change in a bonus or penalty will affect how the engine will interpret this change in various situations.  When modifying the chess engine evaluation function is best to always test against the previous version. 

I always play the new version of my chess engine against the previously released one.  This means that you should save different version of your chess game as you go along.  Furthermore if you find your chess engine made a blunder, save the game, correct the mistake in your code then load the save game to see if that solved it.  Over time you will have a few save games that will allow you to quickly test your new code.  I found that often new code re-introduced some old bug I solved in an older save game and actually made the chess engine weaker.

If you want to get started on creating your own chess engine download my C# Chess Game Starter Kit.   

Today I want to discuss the Piece Square Table. 

Originally the piece square tables were declared in a separate class that was used by the Evaluation function.  However I found that it is more efficient to save the extra method calls and perform the piece square table lookups directly in the evaluation function. 

Hence I have modified this post to simply describe the piece square table and the logic behind the numbers assigned to each position.

As I have already stated the piece square tables are used chess board Evaluation class to score points based on the current position of the chess piece.  The main idea behind this code is that certain positions for chess pieces are better than others.  Fox example it is better for knights to stay away from the edge of the board.  Pawns should control the center of the board and advance forward. 

I have decided not to create a piece square table for every single chess piece.  I have omitted Queens and Rooks.  I could not find good enough positional tactical advantages for Rooks and Queens to warrant the performance cost of a table lookup for each of their positions.

Here are the piece square tables used by my chess engine:

Pawns are encouraged to stay in the center and advance forward:

Knights are encouraged to control the center and stay away from edges to increase mobility:

Bishops are also encouraged to control the center and stay away from edges and corners:

Kings have 2 piece square tables, one for the end game and one for the middle game.  During the middle game kings are encouraged to stay in the corners, while in the end game kings are encouraged to move towards the center.

The above tables are used during the evaluation method to lookup the positional values to help calculate the chess board score.

Here is an example of how the above tables would be used to lookup a value for a white pawn position:

And here is the code to perform the same lookup for a black pawn:

If you want to download a C# Solution project that contains all of the above code plus a graphical user interface that will allow you to make valid moves on the board have a look my C# Chess Game Starter Kit.

Bringing it all together, starting the chess engine.

This post will bring all of the previous sections together in the discussion of the chess engine class.  At this time I will assume that you have already read the previous sections related to Chess Board Square, Chess Board and Chess Piece Representation as well as the Chess Piece Moves and Chess Piece Valid Moves.  Today I will not provide a complete chess engine listing because we have not yet discussed move searching and Chess Board Evaluation.  However at the end of this section we will have a basic chess engine that can:

    1. Track chess piece locations on the chess board
    2. Provide a list of valid moves for each chess piece, including en passant and castling
    3. Track whose move it is.
    4. Track move history.
    5. Setup a starting chess board.

This in theory once we create a graphical user interface this skeleton chess engine would allow you to play a two human player chess game.

Chess Engine class is declared as public sealed

Chess Engine class will contain 3 members that will represent the current chess board, previous chess board whose move it currently is.  Previous Chess Board will store the last chess board prior to the last move.  Please notice that the Previous Chess Board member will potentially give us easy undo functionality.

The constructor is a bit complicated as it performs the following actions:

    • Instantiate above members and set the initial move to White
    • Initiate Chess Piece Motion (Pre-calculate all possible moves for all pieces on all chess board squares possible)
    • Assign Chess pieces to the chess board in the starting position of a standard chess game.
    • Generate valid moves for the chess pieces in their current positions.

Notice the Constructor uses a method called Register Starting Board.  This method constructs all the chess pieces necessary for the starting chess board and registers them with the chess board object.

In the above code a helper method was used called Register Piece. This method assigns the created chess piece to the desired location on the chess board.

The remaining method that I will indroduce today is the MovePiece method.  This code will allow you to move chess pieces around the chess board.  The method will return true if the move was successful and false if the move was not valid.

Generating a Starting Chess Position

At this point we it would be nice if we were able to add some chess pieces to our chess board.  Originally I wrote a method that would declare 32 chess pieces and assign them to the correct chess board square.  However eventually I wanted to implement FEN notation into my chess engine.  FEN notation is an easy way to describe chess board positions.  It is somewhat of a standard in computer chess circles.  Hence once I implemented a method that can read a FEN string and setup the chess board based on the FEN string values, I had an easy way to create my starting chess position. 

The full source code for the FEN methods can be found on the FEN page.

To summarize, our chess engine class contains the current chess board (Board ChessBoard) as well as a copy of the chess board as it looked prior to the last move (Board PreviousChessBoard).  The Chess Engine knows whose move it currently is (ChessPiece.ChessPieceColor WhoseMove).  The constructor of the Chess Engine creates all the chess pieces required for a standard chess game and registers them with the chess board using the Register Piece method.  The chess engine constructor will also Initiate Chess Piece Motion and Assign valid moves to each chess piece based on the pieces current position and the board layout.  Moving chess pieces around the board is handled by the MovePiece method.

If you want to download a C# Solution project that contains all of the above code plus a graphical user interface that will allow you to make valid moves on the board have a look my C# Chess Game Starter Kit.

Goal 1

Create a chess game that was capable of consistently winning games against me.

Status: Achieved as of August 18, 2008. 

Goal 2 

Defeat Chess Titans at level 10, the free Chess Game that comes with Windows Vista.

Status: Achieved as of November 7th, 2009 although not consistently

Goal 3 

Interface with WinBoard, the open source chess board.  This is necessary to submit my Chess Engine to most Computer Chess tournaments. 

Status: Achieved as of December 18th 2009: Download Link

Goal 4 

Enter a computer chess tournament and beat someone’s chess engine. 

Status: Acheived as of April 5th 2010, Entered WBEC Ridderkerk's 18th Edition Tournament and beat more than one chess engine.

Goal 5 

Defeat Little Chess Partner , the free Java Chess Game from the nice people at Lokasoft.

Status: October 28th 2008, tied based on three move repetition

Goal 5 

Create an Online Interface for ChessBin Chess

Status: January 14th 2009, created an online interface using Microsoft Silverlight

Additional Goals will be added from time to time or as older Goals are completed.