Transposition Table and Zobrist Hashing

by aberent 19. February 2010 11:08

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.

Currently rated 4.7 by 3 people

Currently 4.666667/5 Stars.
1
2
3
4
5

Tags: transposion table, zobrist hashing, zobrist, computer chess, chess engine, previous moves, collisions, table lookup, replacement schemesearch

Chess Bin Engine

Quiescence Search and Extensions

by aberent 5. August 2009 05:57

Now that we have discussed the basics of Alpha Beta we can add some small modifications to increase the strength of our move searching and solve the problems of the Horizon Affect

Horizon Affect

The Horizon Affect is a problem that affects every chess engine whose search depth is limited to a certain depth or ply. The Horizon of what your computer chess engine can see is set by the ply or depth limit on the Alpha Beta Search. If we asked the computer to examine 5 moves then the computer will not see that the sixth move made by the opponent will possibly be detrimental to its position. This is especially problematic when we start considering the long exchanges of chess pieces that often occur in a chess game.

There are two ways to battle this problem. The first solution is a simple hack. The trick is to make sure that we always ask the computer to search to an odd ply or depth. This means that the last move the computer will always consider will be the opponents move. This very easily prevents the computer from leaving hanging or unprotected pieces.

However this odd ply solution does not solve the issue related to long exchanges. During the middle game opponents will often build up an attack and defense of a weak piece located in a crucial position such as the center of the chess board. It is not unusual to have a center pawn both protected and attacked by 5-6 chess pieces, including knight’s pawns bishops and even queens. If your chess engine is limited to 5 or even 7 ply, it will never be able to search these exchanges to the end. This means your chess engine will never know if during the course of the piece exchange it will come out on top or lose an extra piece. To solve this issue most chess engines implement what is called a Quiescence Search.

Quiescence Search

The word Quiescence means calm or still. Quiescence Search in computer chess terms simply means searching for a calm position.

The idea behind a Quiescence Search is simple, once your reach your horizon, the last ply you will search, perform a deeper search considering only moves that capture other chess pieces. This deeper search occurs in the same Alpha Beta algorithm. Now you might think that this will significantly slow down your search. In practice however this is not the case. First not every single move is evaluated, only captures so there are much fewer moves to evaluate. Second with every single ply searched more pieces are captured and there are even less moves to evaluate. Very quickly you will often end up with 0 possible captures a few ply down. Third captures often make for very good beta cutoffs in our Alpha Beta. At most your quiescence search should not take more than 10-20% of your search. The difference in the accuracy of your search algorithm however is much higher than 20%. Implemented correctly you will see a significant improvement in the strength of your chess engine.

Extensions

Extensions are a fairly simple concept. An extension will allow your Alpha Beta to search deeper by 1 ply if the position is especially interesting. Interesting positions can be checks or really valuable captures.

Extensions are really needed if your Alpha Beta search is limited to a shallow search such as 5 ply. The usefulness of Extensions diminishes with the increase of the depth of the main Alpha Beta Search.

First I will list the modified Alpha Beta code that makes use of Extensions and Quiescence at depth 0.

private static int AlphaBeta(Board examineBoard, byte depth, int alpha, int beta, bool extended)
{
if (examineBoard.FiftyMove >= 50 || examineBoard.RepeatedMove >= 3)
return 0;

//End Main Search with Quiescence
if (depth == 0)
{
  if (!extended && examineBoard.BlackCheck || examineBoard.WhiteCheck)
  {
   depth++;
   extended = true;

  }
  else
  {
   //Perform a Quiessence Search
   return Quiescence(examineBoard, alpha, beta);
  }
}
List<Position> positions = EvaluateMoves(examineBoard);

if (examineBoard.WhiteCheck || examineBoard.BlackCheck || positions.Count == 0)
{
  if (SearchForMate(examineBoard.WhoseMove, examineBoard, ref examineBoard.BlackMate, ref examineBoard.WhiteMate, ref examineBoard.StaleMate))
  {
   if (examineBoard.BlackMate)
   {
    if (examineBoard.WhoseMove == ChessPieceColor.Black)
     return -32767-depth;

    return 32767 + depth;
   }
   if (examineBoard.WhiteMate)
   {
    if (examineBoard.WhoseMove == ChessPieceColor.Black)
     return 32767 + depth;

return -32767 - depth;
}

   //If Not Mate then StaleMate
   return 0;
  }
}

positions.Sort(Sort);

foreach (Position move in positions)
{
//Make a copy
Board board = examineBoard.FastCopy();

//Move Piece
Board.MovePiece(board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

//We Generate Valid Moves for Board
PieceValidMoves.GenerateValidMoves(board);

  if (board.BlackCheck)
  {
   if (examineBoard.WhoseMove == ChessPieceColor.Black)
   {
    //Invalid Move
    continue;
   }
  }

  if (board.WhiteCheck)
  {
   if (examineBoard.WhoseMove == ChessPieceColor.White)
   {
    //Invalid Move
    continue;
   }
  }

value = -AlphaBeta(board, (byte)(depth - 1), -beta, -alpha, extended);

  if (value >= beta)
  {
   return beta;
  }
  if (value > alpha)
  {
   alpha = (int)value;
  }
}

return alpha;
}

I would like you to notice that in the call to Alpha Beta now has a Boolean variable called: Extended. No matter what we only want to extend the depth of the search a maximum of one time per leaf of the search. Else we run the risk that the search will continue to perform extensions indefinitely. For this reason once we start one of the extension we will set the Boolean value to true, preventing it from occurring again.

Here is the listing for the Quiescence Search method:

private static int Quiescence(Board examineBoard, int alpha, int beta)
{
//Evaluate Score
Evaluation.EvaluateBoardScore(examineBoard);
//Invert Score to support Negamax
examineBoard.Score = SideToMoveScore(examineBoard.Score, examineBoard.WhoseMove);

if (examineBoard.Score >= beta)
return beta;

if (examineBoard.Score > alpha)
alpha = examineBoard.Score;

List<Position> positions = EvaluateMovesQ(examineBoard);

if (positions.Count == 0)
{
return examineBoard.Score;
}
positions.Sort(Sort);

foreach (Position move in positions)
{
//Make a copy
Board board = examineBoard.FastCopy();

//Move Piece
Board.MovePiece(board, move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

//We Generate Valid Moves for Board
PieceValidMoves.GenerateValidMoves(board);

  if (board.BlackCheck)
  {
   if (examineBoard.WhoseMove == ChessPieceColor.Black)
   {
    //Invalid Move
    continue;
   }
  }

  if (board.WhiteCheck)
  {
   if (examineBoard.WhoseMove == ChessPieceColor.White)
   {
    //Invalid Move
    continue;
   }
  }

  int value = -Quiescence(board, - beta, -alpha);

  if (value >= beta)
  {
   return beta;
  }
  if (value > alpha)
   alpha = value;
}
return alpha;
}

You may have noticed that the Quiescence Search uses a new method called EvaluateMovesQ. This method is virtually the same as the previously discussed Evaluate Moves except it only collects moves that capture.

private static List<Position> EvaluateMovesQ(Board examineBoard)
{
//We are going to store our result boards here
List<Position> positions = new List<Position>();

for (byte x = 0; x < 64; x++)
{
Piece piece = examineBoard.Squares[x].Piece;

  //Make sure there is a piece on the square
  if (piece == null)
   continue;

  //Make sure the color is the same color as the one we are moving.
  if (piece.PieceColor != examineBoard.WhoseMove)
   continue;

  //For each valid move for this piece
  foreach (byte dst in piece.ValidMoves)
  {
   if (examineBoard.Squares[dst].Piece == null)
   {
    continue;
   }

Position move = new Position();

move.SrcPosition = x;
move.DstPosition = dst;

Piece pieceAttacked = examineBoard.Squares[move.DstPosition].Piece;

move.Score += pieceAttacked.PieceValue;

   if (piece.PieceValue < pieceAttacked.PieceValue)
   {
    move.Score += pieceAttacked.PieceValue - piece.PieceValue;
   }

move.Score += piece.PieceActionValue;

positions.Add(move);
}
}

return positions;
}

During the Quiescence Search we will often reach a position where no more captures are available. Hence there will be no positions to evaluate. For this reason we have to add the following line of code:

if (positions.Count == 0)
{
return examineBoard.Score;
}

This last piece of code that I want to explain is called the Stand Pad. It’s just a complicated way of saying that during the quiescence search we will set a default value for alpha that is equal to the board being examined. It just prevents you from examining moves that make your situations worse than it already is.

if (examineBoard.Score >= beta)
return beta;

if (examineBoard.Score > alpha)
alpha = examineBoard.Score;

That completes the post on Quiescence Search and Extension. If you have any questions about this post feel free to post a comment below. Chances are someone else has the same question and I would love a chance for improvement.

Currently rated 5.0 by 1 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: quiescence search, extensions, alpha beta, horizon affect, move searchingalpha, beta, min max, negamax, computer chess

Some Performance Optimization Advice

by aberent 13. July 2009 08:17

Over the last year of development of my chess engine, much of the time has been spent optimizing my code to allow for better and faster move searching. Over that time I have learned a few tricks that I would like to share with you.

Measuring Performance

Essentially you can improve your performance in two ways:

Evaluate your nodes faster
Search fewer nodes to come up with the same answer

Your first problem in code optimization will be measurement. How do you know you have really made a difference? In order to help you with this problem you will need to make sure you can record some statistics during your move search. The ones I capture in my chess engine are:

Time it took for the search to complete.
Number of nodes searched

This will allow you to benchmark and test your changes. The best way to approach testing is to create several save games from the opening position, middle game and the end game. Record the time and number of nodes searched for black and white.
After making any changes I usually perform tests against the above mentioned save games to see if I have made improvements in the above two matrices: number of nodes searched or speed.

To complicate things further, after making a code change you might run your engine 3 times and get 3 different results each time. Let’s say that your chess engine found the best move in 9, 10 and 11 seconds. That is a spread of about 20%. So did you improve your engine by 10%-20% or was it just varied load on your pc. How do you know? To fight this I have added methods that will allow my engine to play against itself, it will make moves for both white and black. This way you can test not just the time variance over one move, but a series of as many as 50 moves over the course of the game. If last time the game took 10 minutes and now it takes 9, you probably improved your engine by 10%. Running the test again should confirm this.

Finding Performance Gains

Now that we know how to measure performance gains lets discuss how to identify potential performance gains.
If you are in a .NET environment then the .NET profiler will be your friend. If you have a Visual Studio for Developers edition it comes built in for free, however there are other third party tools you can use. This tool has saved me hours of work as it will tell you where your engine is spending most of its time and allow you to concentrate on your trouble spots. If you do not have a profiler tool you may have to somehow log the time stamps as your engine goes through different steps. I do not suggest this. In this case a good profiler is worth its weight in gold. Red Gate ANTS Profiler is expensive but the best one I have ever tried. If you can’t afford one, at least use it for their 14 day trial.

Your profiler will surly identify things for you, however here are some small lessons I have learned working with C#:

Make everything private
Whatever you can’t make private, make it sealed
Make as many methods static as possible.
Don’t make your methods chatty, one long method is better than 4 smaller ones.
Representing your chess board as an array [8][8] is slower then representing it as an array [64]
Replace int with byte where possible.
Return from your methods as early as possible.
Stacks are better than lists
Arrays are better than stacks and lists.
If you can define the size of the list before you populate it.
Casting, boxing, un-boxing is evil.

Further Performance Gains:

I find move generation and ordering is extremely important. However here is the problem as I see it. If you evaluate the score of each move before you sort and run Alpha Beta, you will be able to optimize your move ordering such that you will get extremely quick Alpha Beta cutoffs. This is because you will be able to mostly try the best move first.

However the time you have spent evaluating each move will be wasted. For example you might have evaluated the score on 20 moves, sort your moves try the first 2 and received a cut-off on move number 2. In theory the time you have spent on the other 18 moves was wasted.

On the other hand if you do a lighter and much faster evaluation say just captures, your sort will not be that good and you will have to search more nodes (up to 60% more). On the other hand you would not do a heavy evaluation on every possible move. As a whole this approach is usually faster.

Finding this perfect balance between having enough information for a good sort and not doing extra work on moves you will not use, will allow you to find huge gains in your search algorithm. Furthermore if you choose the poorer sort approach you will want to first to a shallower search say to ply 3, sort your move before you go into the deeper search (this is often called Iterative Deepening). This will significantly improve your sort and allow you to search much fewer moves.

Currently rated 5.0 by 2 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: alpha beta, move searching, move pruning, performance, move sorting, optimization, computer chess, speed, c# performance, computer chess

Chess Bin Engine | Computer Chess General

Forsyth–Edwards Notation

by aberent 22. June 2009 07:47

In this post I am going to discuss Forsyth-Edwards Notation (FEN) and its implementation in a chess engine. FEN is a standard way of describing a chess position, containing enough information to restart the chess game from that position. It is based on a notation developed by a Scottish journalist, David Forsyth in the 19th century.

Why is FEN useful to us?

1. We can use FEN to store game history allowing us to search for move repetitions as well as display the history of the game to the user. Furthermore if we find a FEN position that has occurred in the past, we can skip searching for the best move and use the same response we used before.

2. We can use FEN strings to implement an Opening Book. With two FEN strings I can store position pairs representing a starting position and the prescribed response.

The implementation of Forsyth–Edwards Notation

FEN notation uses only ASCII characters stored in a single line. A FEN string or record contains 6 fields. These are separated by a space.

Piece placement from white’s perspective. Each row is noted, starting from row 8 (blacks row0 and ending with row 1 (white’s row). Each piece is described from column to column h. Each piece is identified by a single letter.

Pawn: P

Knight: K

Bishop: B

Rook: R

Queen: Q

King: K

White pieces are noted using capital letters and black using lower case. So P would be a white pawn and p would signify a black pawn.
Empty squares (spaces) are described using numbers, each number representing the number of empty squares before the next chess pieces. The number 8 would describe a completely empty row.
The character / describes a new row.

So for a starting position we may see: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

The second column in the Forsyth–Edwards Notation represents whose turn it is. A single character is used w for white and b for black.

The third column represents if castling is still allowed. If neither side can castle then the character – is used. Otherwise the following letters are used. K means white can castle King Side, Q means White can castle Queen side. Lower case k and q mean the same for black.

The fourth column represents an En Passant target square. The square that the pawn hopped to get to its row, or the position behind the pawn. If there is no En Passant square then the character – is used. So if the last move was pawn to e4, we will record e3 in this column.

The fifth column contains the number of half moves since the last pawn move or capture. This is used to determine the 50 move draw scenario.

The last column contains the full move number. The number starts at 1 and is incremented after black’s move.

Examples:

FEN for the starting position:

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

FEN after the white pawn moved to E4:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

FEN after the black pawn moved to C5

rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNR w KQkq c6 0 2

And then after the white knight moves to F3:

rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2

Forsyth–Edwards Notation Code

In my chess engine FEN is implemented in two methods. The first method will produce a FEN string for any chess Board.

internal static string Fen(bool boardOnly, Board board)
{
string output = String.Empty;
byte blankSquares = 0;

for (byte x = 0; x < 64; x++)
{
byte index = x;

  if (board.Squares[index].Piece != null)
  {
   if (blankSquares > 0)
   {
    output += blankSquares.ToString();
    blankSquares = 0;
   }

   if (board.Squares[index].Piece.PieceColor == ChessPieceColor.Black)
   {
    output += Piece.GetPieceTypeShort(board.Squares[index].Piece.PieceType).ToLower();
   }
   else
   {
    output += Piece.GetPieceTypeShort(board.Squares[index].Piece.PieceType);
   }
  }
  else
  {
   blankSquares++;
  }

  if (x % 8 == 7)
  {
   if (blankSquares > 0)
   {
    output += blankSquares.ToString();
    output += "/";
    blankSquares = 0;
   }
   else
   {
    if (x > 0 && x != 63)
    {
     output += "/";
    }
   }
  }
}

if (board.WhoseMove == ChessPieceColor.White)
{
output += " w ";
}
else
{
output += " b ";
}

string spacer = "";

if (board.WhiteCastled == false)
{
  if (board.Squares[60].Piece != null)
  {
   if (board.Squares[60].Piece.Moved == false)
   {
    if (board.Squares[63].Piece != null)
    {
     if (board.Squares[63].Piece.Moved == false)
     {
      output += "K";
      spacer = " ";
     }
    }
    if (board.Squares[56].Piece != null)
    {
     if (board.Squares[56].Piece.Moved == false)
     {
      output += "Q";
      spacer = " ";
     }
    }
   }
  }
}

if (board.BlackCastled == false)
{
  if (board.Squares[4].Piece != null)
  {
   if (board.Squares[4].Piece.Moved == false)
   {
    if (board.Squares[7].Piece != null)
    {
     if (board.Squares[7].Piece.Moved == false)
     {
      output += "k";
      spacer = " ";
     }
    }
    if (board.Squares[0].Piece != null)
    {
     if (board.Squares[0].Piece.Moved == false)
     {
      output += "q";
      spacer = " ";
     }
    }
   }
  }

}

if (output.EndsWith("/"))
{
output.TrimEnd('/');
}

if (board.EnPassantPosition != 0)
{
output += spacer + GetColumnFromByte((byte)(board.EnPassantPosition % 8)) + "" + (byte)(8 - (byte)(board.EnPassantPosition / 8)) + " ";
}
else
{
output += spacer + "- ";
}

if (!boardOnly)
{
output += board.FiftyMove + " ";
output += board.MoveCount + 1;
}
return output.Trim();
}

The second method is a Board constructor that will accept a FEN string and create a Chess Board based on the content of the string. Strictly speaking you will not need this code. I only use this to allow people to enter FEN strings in the user interface. Since FEN is a standard used in many chess programs allowing users to input FEN strings will allow them to visualize chess positions they might find on the internet.

internal Board(string fen) : this()
{
byte index = 0;
byte spc = 0;

WhiteCastled = true;
BlackCastled = true;
byte spacers = 0;

WhoseMove = ChessPieceColor.White;

if (fen.Contains("a3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 40;
}
else if (fen.Contains("b3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 41;
}
else if (fen.Contains("c3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 42;
}
else if (fen.Contains("d3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 43;
}
else if (fen.Contains("e3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 44;
}
else if (fen.Contains("f3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 45;
}
else if (fen.Contains("g3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 46;
}
else if (fen.Contains("h3"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 47;
}

if (fen.Contains("a6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 16;
}
else if (fen.Contains("b6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 17;
}
else if (fen.Contains("c6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition =18;
}
else if (fen.Contains("d6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 19;
}
else if (fen.Contains("e6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 20;
}
else if (fen.Contains("f6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 21;
}
else if (fen.Contains("g6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 22;
}
else if (fen.Contains("h6"))
{
  EnPassantColor = ChessPieceColor.White;
  EnPassantPosition = 23;
}

foreach (char c in fen)
{

  if (index < 64 && spc == 0)
  {
   if (c == '1' && index < 63)
   {
    index++;
   }
   else if (c == '2' && index < 62)
   {
    index += 2;
   }
   else if (c == '3' && index < 61)
   {
    index += 3;
   }
   else if (c == '4' && index < 60)
   {
    index += 4;
   }
   else if (c == '5' && index < 59)
   {
    index += 5;
   }
   else if (c == '6' && index < 58)
   {
    index += 6;
   }
   else if (c == '7' && index < 57)
   {
    index += 7;
   }
   else if (c == '8' && index < 56)
   {
    index += 8;
   }
   else if (c == 'P')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Pawn, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'N')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Knight, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'B')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Bishop, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'R')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Rook, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'Q')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Queen, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'K')
   {
    Squares[index].Piece = new Piece(ChessPieceType.King, ChessPieceColor.White);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'p')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Pawn, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'n')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Knight, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'b')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Bishop, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'r')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Rook, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'q')
   {
    Squares[index].Piece = new Piece(ChessPieceType.Queen, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == 'k')
   {
    Squares[index].Piece = new Piece(ChessPieceType.King, ChessPieceColor.Black);
    Squares[index].Piece.Moved = true;
    index++;
   }
   else if (c == '/')
   {
    continue;
   }
   else if (c == ' ')
   {
    spc++;
   }
  }
  else
  {
   if (c == 'w')
   {
    WhoseMove = ChessPieceColor.White;
   }
   else if (c == 'b')
   {
    WhoseMove = ChessPieceColor.Black;
   }
   else if (c == 'K')
   {
    if (Squares[60].Piece != null)
    {
     if (Squares[60].Piece.PieceType == ChessPieceType.King)
     {
      Squares[60].Piece.Moved = false;
     }
    }

    if (Squares[63].Piece != null)
    {
     if (Squares[63].Piece.PieceType == ChessPieceType.Rook)
     {
      Squares[63].Piece.Moved = false;
     }
    }

    WhiteCastled = false;
   }
   else if (c == 'Q')
   {
    if (Squares[60].Piece != null)
    {
     if (Squares[60].Piece.PieceType == ChessPieceType.King)
     {
      Squares[60].Piece.Moved = false;
     }
    }

    if (Squares[56].Piece != null)
    {
     if (Squares[56].Piece.PieceType == ChessPieceType.Rook)
     {
      Squares[56].Piece.Moved = false;
     }
    }

    WhiteCastled = false;
   }
   else if (c == 'k')
   {
    if (Squares[4].Piece != null)
    {
     if (Squares[4].Piece.PieceType == ChessPieceType.King)
     {
      Squares[4].Piece.Moved = false;
     }
    }

    if (Squares[7].Piece != null)
    {
     if (Squares[7].Piece.PieceType == ChessPieceType.Rook)
     {
      Squares[7].Piece.Moved = false;
     }
    }

    BlackCastled = false;
   }
   else if (c == 'q')
   {
    if (Squares[4].Piece != null)
    {
     if (Squares[4].Piece.PieceType == ChessPieceType.King)
     {
      Squares[4].Piece.Moved = false;
     }
    }

    if (Squares[0].Piece != null)
    {
     if (Squares[0].Piece.PieceType == ChessPieceType.Rook)
     {
      Squares[0].Piece.Moved = false;
     }
    }

    BlackCastled = false;
   }
   else if (c == ' ')
   {
    spacers++;
   }
   else if (c == '1' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 1);
   }
   else if (c == '2' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 2);
   }
   else if (c == '3' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 3);
   }
   else if (c == '4' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 4);
   }
   else if (c == '5' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 5);
   }
   else if (c == '6' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 6);
   }
   else if (c == '7' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 7);
   }
   else if (c == '8' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 8);
   }
   else if (c == '9' && spacers == 4)
   {
    FiftyMove = (byte)((FiftyMove * 10) + 9);
   }
   else if (c == '0' && spacers == 4)
   {
    MoveCount = (byte)((MoveCount * 10) + 0);
   }
   else if (c == '1' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 1);
   }
   else if (c == '2' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 2);
   }
   else if (c == '3' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 3);
   }
   else if (c == '4' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 4);
   }
   else if (c == '5' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 5);
   }
   else if (c == '6' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 6);
   }
   else if (c == '7' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 7);
   }
   else if (c == '8' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 8);
   }
   else if (c == '9' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 9);
   }
   else if (c == '0' && spacers == 5)
   {
    MoveCount = (byte)((MoveCount * 10) + 0);
   }

}
}

}

This concludes the post on Forsyth–Edwards Notation. If you want to get started on creating your own chess engine download my C# Chess Game Starter Kit.

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags: fen, forsyth–edwards notation, 3 move repetition, chess board, computer chess engine, computer chess

Chess Bin Engine

Completing the chess engine

by aberent 19. May 2009 01:29

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:

public sealed class Engine

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

internal Board ChessBoard;
internal Board PreviousChessBoard;

public ChessPieceColor WhoseMove
{
get { return ChessBoard.WhoseMove; }
set { ChessBoard.WhoseMove = value; }
}

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.

public Engine()
{
ChessBoard = new Board();
MoveHistory = new Stack<MoveContent>();

    RegisterStartingBoard();
    ChessBoard.WhoseMove = ChessPieceColor.White;

    ChessPieceMoves.InitiateChessPieceMotion();
    PieceValidMoves.GenerateValidMoves(ChessBoard);
Evaluation.EvaluateBoardScore(ChessBoard);
}

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.

public bool MovePiece(byte sourceColumn, byte sourceRow,
byte destinationColumn, byte destinationRow)
{
byte srcPosition = (byte)(sourceColumn + (sourceRow * 8));
byte dstPosition = (byte)(destinationColumn + (destinationRow * 8));

Piece Piece = ChessBoard.Squares[srcPosition].Piece;

PreviousChessBoard = new Board(ChessBoard);

Board.MovePiece(ChessBoard, srcPosition, dstPosition, PromoteToPieceType);

PieceValidMoves.GenerateValidMoves(ChessBoard);

//If there is a check in place, check if this is still true;
if (Piece.PieceColor == ChessPieceColor.White)
{
if (ChessBoard.WhiteCheck)
{
   //Invalid Move
   ChessBoard = new Board(PreviousChessBoard);
   PieceValidMoves.GenerateValidMoves(ChessBoard);
   return false;
}
}
else if (Piece.PieceColor == ChessPieceColor.Black)
{
if (ChessBoard.BlackCheck)
{
   //Invalid Move
   ChessBoard = new Board(PreviousChessBoard);
   PieceValidMoves.GenerateValidMoves(ChessBoard);
   return false;
}
}

MoveHistory.Push(ChessBoard.LastMove);

return true;
}

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.

public ChessPieceColor HumanPlayer;

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.

public byte PlyDepthSearched = 5;

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:

internal class OpeningMove
{
public string EndingFEN;
public string StartingFEN;
public List<MoveContent> Moves;

public OpeningMove()
{
  StartingFEN = String.Empty;
  EndingFEN = String.Empty;
  Moves = new List<MoveContent>();
}
}

internal static List<OpeningMove> CurrentGameBook;

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.

internal static void SaveCurrentGameMove(Board currentBoard, Board previousBoard, ICollection<OpeningMove> gameBook, MoveContent bestMove)
{
try
{
var move = new OpeningMove();

  move.StartingFEN = Board.Fen(true, previousBoard);
  move.EndingFEN = Board.Fen(true, currentBoard);
  move.Moves.Add(bestMove);

gameBook.Add(move);

  foreach (OpeningMove move1 in gameBook)
  {
   byte repeatedMoves = 0;

   foreach (OpeningMove move2 in gameBook)
   {
    if (move1.EndingFEN == move2.EndingFEN)
    {
     repeatedMoves++;
    }
   }

   if (previousBoard.RepeatedMove < repeatedMoves)
   {
    previousBoard.RepeatedMove = repeatedMoves;
    currentBoard.RepeatedMove = repeatedMoves;
   }
  }
  if (currentBoard.RepeatedMove >= 3)
  {
   currentBoard.StaleMate = true;
  }
}
catch (Exception)
{
  return;
}

return;
}
}

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.

private static bool CheckForMate(ChessPieceColor whosTurn, ref Board chessBoard)
{
Search.SearchForMate(whosTurn, chessBoard, ref chessBoard.BlackMate,
ref chessBoard.WhiteMate, ref chessBoard.StaleMate);

if (chessBoard.BlackMate || chessBoard.WhiteMate || chessBoard.StaleMate)
{
return true;
}

return false;
}

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).

public void AIPonderMove()
{
    if (CheckForMate(WhoseMove, ref ChessBoard))
    {
        return;
    }
MoveContent bestMove = new MoveContent();

    //If there is no playbook move search for the best move
    bestMove = AlphaBetaRoot(ChessBoard, PlyDepthSearched);

    //Make the move
    PreviousChessBoard = new Board(ChessBoard);

    Board.MovePiece(ChessBoard, bestMove.MovingPiecePrimary.SrcPosition, bestMove.MovingPiecePrimary.DstPosition, ChessPieceType.Queen);

    SaveCurrentGameMove(bestBoard, ChessBoard, CurrentGameBook);

PieceValidMoves.GenerateValidMoves(ChessBoard);
Evaluation.EvaluateBoardScore(ChessBoard);

    if (CheckForMate(WhoseMove, ref ChessBoard))
    {
        return;
    }
}

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.

public bool GetBlackMate()
{
return ChessBoard.BlackMate;
}

public bool GetWhiteMate()
{
return ChessBoard.WhiteMate;
}

public bool GetBlackCheck()
{
return ChessBoard.BlackCheck;
}

public bool GetWhiteCheck()
{
return ChessBoard.WhiteCheck;
}

public byte GetRepeatedMove()
{
return ChessBoard.RepeatedMove;
}

public byte GetFiftyMoveCount()
{
return ChessBoard.FiftyMove;
}

public bool IsValidMove(byte sourceColumn, byte sourceRow, byte destinationColumn, byte destinationRow)
{
if (ChessBoard == null)
{
return false;
}

if (ChessBoard.Squares == null)
{
return false;
}

byte index = GetBoardIndex(sourceColumn, sourceRow);

if (ChessBoard.Squares[index].Piece == null)
{
return false;
}

foreach (byte bs in ChessBoard.Squares[index].Piece.ValidMoves)
{
  if (bs % 8 == destinationColumn)
  {
   if ((byte)(bs / 8) == destinationRow)
   {
    return true;
   }
  }
}

index = GetBoardIndex(destinationColumn, destinationRow);

if (index == ChessBoard.EnPassantPosition)
{
return true;
}

return false;
}

public ChessPieceType GetPieceTypeAt(byte boardColumn, byte boardRow)
{
byte index = GetBoardIndex(boardColumn, boardRow);

if (ChessBoard.Squares[index].Piece == null)
{
return ChessPieceType.None;
}

return ChessBoard.Squares[index].Piece.PieceType;
}

public ChessPieceType GetPieceTypeAt(byte index)
{
if (ChessBoard.Squares[index].Piece == null)
{
return ChessPieceType.None;
}

return ChessBoard.Squares[index].Piece.PieceType;
}

public ChessPieceColor GetPieceColorAt(byte boardColumn, byte boardRow)
{
byte index = GetBoardIndex(boardColumn, boardRow);

if (ChessBoard.Squares[index].Piece == null)
{
return ChessPieceColor.White;
}
return ChessBoard.Squares[index].Piece.PieceColor;
}

public ChessPieceColor GetPieceColorAt(byte index)
{
if (ChessBoard.Squares[index].Piece == null)
{
return ChessPieceColor.White;
}
return ChessBoard.Squares[index].Piece.PieceColor;
}

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

public bool IsGameOver()
{
if (ChessBoard.StaleMate)
{
  return true;
}
if (ChessBoard.WhiteMate || ChessBoard.BlackMate)
{
  return true;
}
if (ChessBoard.FiftyMove >= 50)
{
  return true;
}
if (ChessBoard.RepeatedMove >= 3)
{
  return true;
}

if (ChessBoard.InsufficientMaterial)
{
return true;
}
return false;
}

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.

Currently rated 5.0 by 3 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: chess engine, 50 move count, 3 move repetition, move searching, alpha beta, computer chess

Chess Bin Engine

Move Searching Alpha Beta Part 2

by aberent 14. April 2009 05:15

Last time I discussed Min Max and the Alpha Beta algorithms. However you might have noticed that the algorithm I showed last time does not really tell you which of the available moves is the best, but rather which was the best score out of all the available moves. To figure out which resulting chess board is the best I have implemented another method called Alpha Beta Root.

Alpha Beta Root is very similar to the regular Alpha Beta Method with the exception of keeping track of the best board found so far. Alpha Beta Root is also our entry method into searching; it calls the regular Alpha Beta method. You pass it a chess board and it returns Move Content containing the best move you can make. Alpha Beta Root does not also need to perform a Quiescence Search since it is already performed in the regular Alpha Beta method.

The code below can be divided into 3 sections.

Initial examination of what legal moves I can make and what their resulting score is. This is followed by a sort to give us the best chance of trying the best move first
Initial 1 ply call of Alpha Beta to see if there is an instant check mate so we can exit.
Regular Alpha Beta call.

Before we get started we will need a helper struct to keep a list of our starting positions.

internal struct ResultBoards
{
internal List<Board> Positions;
}

Now onto the main Alpha Beta Root Method:

internal static MoveContent AlphaBetaRoot(Board examineBoard, byte depth)
{
int alpha = -400000000;
const int beta = 400000000;

Board bestBoard = new Board(short.MinValue);

//We are going to store our result boards here
ResultBoards succ = new ResultBoards
{
Positions = new List<Board>(30)
};

for (byte x = 0; x < 64; x++)
{
Square sqr = examineBoard.Squares[x];

  //Make sure there is a piece on the square
  if (sqr.Piece == null)
   continue;

  //Make sure the color is the same color as the one we are moving.
  if (sqr.Piece.PieceColor != examineBoard.WhoseMove)
   continue;

  //For each valid move for this piece
  foreach (byte dst in sqr.Piece.ValidMoves)
  {
   //We make copies of the board and move so that we can move it without effecting the parent board
   Board board = examineBoard.FastCopy();

//Make move so we can examine it
Board.MovePiece(board, x, dst, ChessPieceType.Queen);

//We Generate Valid Moves for Board
PieceValidMoves.GenerateValidMoves(board);

   //Invalid Move
   if (board.WhiteCheck && examineBoard.WhoseMove == ChessPieceColor.White)
   {
    continue;
   }

   //Invalid Move
   if (board.BlackCheck && examineBoard.WhoseMove == ChessPieceColor.Black)
   {
    continue;
   }

//We calculate the board score
Evaluation.EvaluateBoardScore(board);

//Invert Score to support Negamax
board.Score = SideToMoveScore(board.Score, board.WhoseMove);

succ.Positions.Add(board);
}
}

succ.Positions.Sort(Sort);

//Can I make an instant mate?
foreach (Board pos in succ.Positions)
{
int value = -AlphaBeta(pos, 1, -beta, -alpha);

  if (value >= 32767)
  {
   return pos.LastMove;
  }
}
depth--;

byte plyDepthReached = ModifyDepth(depth, succ.Positions.Count);

int currentBoard = 0;

alpha = -400000000;

succ.Positions.Sort(Sort);

foreach (Board pos in succ.Positions)
{
currentBoard++;

int value = -AlphaBeta(pos, plyDepthReached, -beta, -alpha);

pos.Score = value;

  //If value is greater then alpha this is the best board
  if (value > alpha)
  {
   alpha = value;
   bestBoard = new Board(pos);
  }

}

return bestBoard.LastMove;
}

The obvious question might be why do we do this? Why not simply copy the best board in the regular Alpha Beta method and return it. The simple answer is performance. Because the regular Alpha Beta method is recursive we want it to be as fast as possible. It is much faster to copy integers rather than calling the copy constructor for the board object.

One last piece of code that I would like to add here is the Modify Ply method. One thing I noticed while testing my chess engine is that during the end game my engine made moves at a much faster rate than it did during the opening and middle game. This had a very simple explanation as during the end game there are far fewer chess pieces and there are less moves to calculate. For this reason I added a small method to that adds 2 plies to my search if there are less then 6 root moves on the board. This way I can search deeper during the end game, increasing my odds of finding a check mate.

private static byte ModifyDepth(byte depth, int possibleMoves)
{
if (possibleMoves <= 15)
{
depth += 1;
}

return depth;
}

If you have any questions about this post feel free to post a comment below. Chances are someone else has the same question and I would love a chance for improvement.

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

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags: alpha beta, beta, alpha, board, move searching, negamax, performance, computer chess engine, computer chess

Chess Bin Engine

Performance Reconstruction

by aberent 30. October 2008 07:21

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)

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags: board, chess board design, chess board square, performance, computer chess performance, chess engine, computer chess

Chess Bin Engine

Chess Board Evaluation

by aberent 20. October 2008 07:26

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.

internal static class Evaluation

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

private static readonly short[] PawnTable = new short[]
{
0, 0, 0, 0, 0, 0, 0, 0,
50, 50, 50, 50, 50, 50, 50, 50,
10, 10, 20, 30, 30, 20, 10, 10,
5, 5, 10, 27, 27, 10, 5, 5,
0, 0, 0, 25, 25, 0, 0, 0,
5, -5,-10, 0, 0,-10, -5, 5,
5, 10, 10,-25,-25, 10, 10, 5,
0, 0, 0, 0, 0, 0, 0, 0
};

private static readonly short[] KnightTable = new short[]
{
-50,-40,-30,-30,-30,-30,-40,-50,
-40,-20, 0, 0, 0, 0,-20,-40,
-30, 0, 10, 15, 15, 10, 0,-30,
-30, 5, 15, 20, 20, 15, 5,-30,
-30, 0, 15, 20, 20, 15, 0,-30,
-30, 5, 10, 15, 15, 10, 5,-30,
-40,-20, 0, 5, 5, 0,-20,-40,
-50,-40,-20,-30,-30,-20,-40,-50,
};

private static readonly short[] BishopTable = new short[]
{
-20,-10,-10,-10,-10,-10,-10,-20,
-10, 0, 0, 0, 0, 0, 0,-10,
-10, 0, 5, 10, 10, 5, 0,-10,
-10, 5, 5, 10, 10, 5, 5,-10,
-10, 0, 10, 10, 10, 10, 0,-10,
-10, 10, 10, 10, 10, 10, 10,-10,
-10, 5, 0, 0, 0, 0, 5,-10,
-20,-10,-40,-10,-10,-40,-10,-20,
};

private static readonly short[] KingTable = new short[]
{
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
-20, -30, -30, -40, -40, -30, -30, -20,
-10, -20, -20, -20, -20, -20, -20, -10,
20, 20, 0, 0, 0, 0, 20, 20,
20, 30, 10, 0, 0, 10, 30, 20
};

private static readonly short[] KingTableEndGame = new short[]
{
-50,-40,-30,-20,-20,-30,-40,-50,
-30,-20,-10, 0, 0,-10,-20,-30,
-30,-10, 20, 30, 30, 20,-10,-30,
-30,-10, 30, 40, 40, 30,-10,-30,
-30,-10, 30, 40, 40, 30,-10,-30,
-30,-10, 20, 30, 30, 20,-10,-30,
-30,-30, 0, 0, 0, 0,-30,-30,
-50,-30,-30,-30,-30,-30,-30,-50
};

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

private static int EvaluatePieceScore(Square square, byte position, bool castled,
bool endGamePhase,ref byte bishopCount,
ref bool insufficientMaterial)

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.

int score = 0;

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.

byte index = position;

if (square.Piece.PieceColor == ChessPieceColor.Black)
{
index = (byte)(63-position);
}

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.

score += square.Piece.PieceValue;

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.

score += square.Piece.DefendedValue;

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.

score -= square.Piece.AttackedValue;

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.

//Double Penalty for Hanging Pieces
if (square.Piece.DefendedValue < square.Piece.AttackedValue)
{
score -= ((square.Piece.AttackedValue - square.Piece.DefendedValue)* 10);
}
}

We will also add score for mobility. This discourages trapped pieces and blocked pawns.

if (square.Piece.ValidMoves != null)
{
score += square.Piece.ValidMoves.Count;
}

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.

if (square.Piece.PieceType == ChessPieceType.Pawn)
{
insufficientMaterial = false;

if (position % 8 == 0 || position % 8 == 7)
{
//Rook Pawns are worth 15% less because they can only attack one way
score -= 15;
}

//Calculate Position Values
score += PawnTable[index];

if (square.Piece.PieceColor == ChessPieceColor.White)
{
  if (whitePawnCount[position % 8] > 0)
  {
   //Doubled Pawn
   score -= 16;
  }

  if (position >= 8 && position <= 15)
  {
   if (square.Piece.AttackedValue == 0)
   {
    whitePawnCount[position % 8] += 200;

    if (square.Piece.DefendedValue != 0)
     whitePawnCount[position % 8] += 50;
   }
  }
  else if (position >= 16 && position <= 23)
  {
   if (square.Piece.AttackedValue == 0)
   {
    whitePawnCount[position % 8] += 100;

    if (square.Piece.DefendedValue != 0)
     whitePawnCount[position % 8] += 25;
   }
  }

  whitePawnCount[position % 8]+=10;
}
else
{
  if (blackPawnCount[position % 8] > 0)
  {
   //Doubled Pawn
   score -= 16;
  }

  if (position >= 48 && position <= 55)
  {
   if (square.Piece.AttackedValue == 0)
   {
    blackPawnCount[position % 8] += 200;

    if (square.Piece.DefendedValue != 0)
     blackPawnCount[position % 8] += 50;
   }
  }
  //Pawns in 6th Row that are not attacked are worth more points.
  else if (position >= 40 && position <= 47)
  {
   if (square.Piece.AttackedValue == 0)
   {
    blackPawnCount[position % 8] += 100;

    if (square.Piece.DefendedValue != 0)
     blackPawnCount[position % 8] += 25;
   }
  }

blackPawnCount[position % 8] += 10;

}
}

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.

else if (square.Piece.PieceType == ChessPieceType.Knight)
{
score += KnightTable[index];

//In the end game remove a few points for Knights since they are worth less
if (endGamePhase)
{
score -= 10;
}

}

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.

else if (square.Piece.PieceType == ChessPieceType.Bishop)
{
bishopCount++;

if (bishopCount >= 2)
{
//2 Bishops receive a bonus
score += 10;
}

//In the end game Bishops are worth more
if (endGamePhase)
{
score += 10;
}

score += BishopTable[index];
}

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.

else if (square.Piece.PieceType == ChessPieceType.Rook)
{
insufficientMaterial = false;

if (square.Piece.Moved && castled == false)
{
score -= 10;
}
}

Furthermore we want to discourage Queen movement in the beginning of the game so we give a small penalty if the Queen has moved.

else if (square.Piece.PieceType == ChessPieceType.Queen)
{
insufficientMaterial = false;

if (square.Piece.Moved && !endGamePhase)
{
score -= 10;
}
}

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.

else if (square.Piece.PieceType == ChessPieceType.King)
{
if (square.Piece.ValidMoves.Count < 2)
{
  score -= 5;
}
if (endGamePhase)
{
  score += KingTableEndGame[index];
}
else
{
  score += KingTable[index];

  if (square.Piece.Moved && castled == false)
  {
   score -= 30;
  }
}
}

At the end our method simply returns the score:

return 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.

internal static void EvaluateBoardScore(Board board)

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

board.Score = 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.

bool insufficientMaterial = true;

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.

if (board.StaleMate)
{
    return;
}
if (board.FiftyMoveCount >= 50)
{
    return;
}
if (board.RepeatedMoveCount >= 3)
{
    return;
}

Next we give bonuses and penalties for board level scenarios such as King Checks, Mates and Castles.

if (board.BlackMate)
{
board.Score = 32767;
return;
}
if (board.WhiteMate)
{
board.Score = -32767;
return;
}
if (board.BlackCheck)
{
board.Score += 75;
if (board.EndGamePhase)
board.Score += 10;
}
else if (board.WhiteCheck)
{
board.Score -= 75;
if (board.EndGamePhase)
board.Score -= 10;
}
if (board.BlackCastled)
{
board.Score -= 40;
}
if (board.WhiteCastled)
{
board.Score += 40;
}
//Add a small bonus for tempo (turn)
if (board.WhoseMove == ChessPieceColor.White)
{
board.Score += 10;
}
else
{
board.Score -= 10;
}

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.

byte blackBishopCount = 0;
byte whiteBishopCount = 0;
byte knightCount = 0;

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.

int RemainingPieces = 0;

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.

blackPawnCount = new short[8];
whitePawnCount = new short[8];

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.

for (byte x = 0; x < 64; x++)
{
Square square = board.Squares[x];

if (square.Piece == null)
continue;

//Calculate Remaining Material for end game determination
remainingPieces++;

if (square.Piece.PieceColor == ChessPieceColor.White)
{
  board.Score += EvaluatePieceScore(square, x, board.WhiteCastled, board.EndGamePhase,
   ref whiteBishopCount, ref insufficientMaterial);
}
else if (square.Piece.PieceColor == ChessPieceColor.Black)
{
  board.Score -= EvaluatePieceScore(square, x, board.BlackCastled, board.EndGamePhase,
   ref blackBishopCount, ref insufficientMaterial);
}

if (square.Piece.PieceType == ChessPieceType.Knight)
{
knightCount++;

  if (knightCount > 1)
  {
   insufficientMaterial = false;
  }
}

if ((blackBishopCount + whiteBishopCount) > 1)
{
insufficientMaterial = false;
}
}

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.

if (insufficientMaterial)
{
board.Score = 0;
board.StaleMate = true;
board.InsufficientMaterial = true;
return;
}

if (remainingPieces < 10)
{
board.EndGamePhase = true;

if (board.BlackCheck)
{
board.Score += 10;
}
else if (board.WhiteCheck)
{
board.Score -= 10;
}
}

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.

//Black Isolated Pawns
if (blackPawnCount[0] >= 1 && blackPawnCount[1] == 0)
{
board.Score += 12;
}
if (blackPawnCount[1] >= 1 && blackPawnCount[0] == 0 &&
blackPawnCount[2] == 0)
{
board.Score += 14;
}
if (blackPawnCount[2] >= 1 && blackPawnCount[1] == 0 &&
blackPawnCount[3] == 0)
{
board.Score += 16;
}
if (blackPawnCount[3] >= 1 && blackPawnCount[2] == 0 &&
blackPawnCount[4] == 0)
{
board.Score += 20;
}
if (blackPawnCount[4] >= 1 && blackPawnCount[3] == 0 &&
blackPawnCount[5] == 0)
{
board.Score += 20;
}
if (blackPawnCount[5] >= 1 && blackPawnCount[4] == 0 &&
blackPawnCount[6] == 0)
{
board.Score += 16;
}
if (blackPawnCount[6] >= 1 && blackPawnCount[5] == 0 &&
blackPawnCount[7] == 0)
{
board.Score += 14;
}
if (blackPawnCount[7] >= 1 && blackPawnCount[6] == 0)
{
board.Score += 12;
}

//White Isolated Pawns
if (whitePawnCount[0] >= 1 && whitePawnCount[1] == 0)
{
board.Score -= 12;
}
if (whitePawnCount[1] >= 1 && whitePawnCount[0] == 0 &&
whitePawnCount[2] == 0)
{
board.Score -= 14;
}
if (whitePawnCount[2] >= 1 && whitePawnCount[1] == 0 &&
whitePawnCount[3] == 0)
{
board.Score -= 16;
}
if (whitePawnCount[3] >= 1 && whitePawnCount[2] == 0 &&
whitePawnCount[4] == 0)
{
board.Score -= 20;
}
if (whitePawnCount[4] >= 1 && whitePawnCount[3] == 0 &&
whitePawnCount[5] == 0)
{
board.Score -= 20;
}
if (whitePawnCount[5] >= 1 && whitePawnCount[4] == 0 &&
whitePawnCount[6] == 0)
{
board.Score -= 16;
}
if (whitePawnCount[6] >= 1 && whitePawnCount[5] == 0 &&
whitePawnCount[7] == 0)
{
board.Score -= 14;
}
if (whitePawnCount[7] >= 1 && whitePawnCount[6] == 0)
{
board.Score -= 12;
}

//Black Passed Pawns
if (blackPawnCount[0] >= 1 && whitePawnCount[0] == 0)
{
board.Score -= blackPawnCount[0];
}
if (blackPawnCount[1] >= 1 && whitePawnCount[1] == 0)
{
board.Score -= blackPawnCount[1];
}
if (blackPawnCount[2] >= 1 && whitePawnCount[2] == 0)
{
board.Score -= blackPawnCount[2];
}
if (blackPawnCount[3] >= 1 && whitePawnCount[3] == 0)
{
board.Score -= blackPawnCount[3];
}
if (blackPawnCount[4] >= 1 && whitePawnCount[4] == 0)
{
board.Score -= blackPawnCount[4];
}
if (blackPawnCount[5] >= 1 && whitePawnCount[5] == 0)
{
board.Score -= blackPawnCount[5];
}
if (blackPawnCount[6] >= 1 && whitePawnCount[6] == 0)
{
board.Score -= blackPawnCount[6];
}
if (blackPawnCount[7] >= 1 && whitePawnCount[7] == 0)
{
board.Score -= blackPawnCount[7];
}

//White Passed Pawns
if (whitePawnCount[0] >= 1 && blackPawnCount[1] == 0)
{
board.Score += whitePawnCount[0];
}
if (whitePawnCount[1] >= 1 && blackPawnCount[1] == 0)
{
board.Score += whitePawnCount[1];
}
if (whitePawnCount[2] >= 1 && blackPawnCount[2] == 0)
{
board.Score += whitePawnCount[2];
}
if (whitePawnCount[3] >= 1 && blackPawnCount[3] == 0)
{
board.Score += whitePawnCount[3];
}
if (whitePawnCount[4] >= 1 && blackPawnCount[4] == 0)
{
board.Score += whitePawnCount[4];
}
if (whitePawnCount[5] >= 1 && blackPawnCount[5] == 0)
{
board.Score += whitePawnCount[5];
}
if (whitePawnCount[6] >= 1 && blackPawnCount[6] == 0)
{
board.Score += whitePawnCount[6];
}
if (whitePawnCount[7] >= 1 && blackPawnCount[7] == 0)
{
board.Score += whitePawnCount[7];
}

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.

Currently rated 4.8 by 4 people

Currently 4.75/5 Stars.
1
2
3
4
5

Tags: chess engine, computer chess, board evaluation, chess board evaluation

Chess Bin Engine

<< Previous posts

Created and Maintained by Adam Berent
www.adamberent.com

Computer Chess Information and Resources

Transposition Table and Zobrist Hashing

Quiescence Search and Extensions

Some Performance Optimization Advice

Forsyth–Edwards Notation

Completing the chess engine

Move Searching Alpha Beta Part 2

Performance Reconstruction

Chess Board Evaluation

Free Online Chess

Recent Posts

Vintage Chess Computers

Downloads

Miscellaneous