Move Searching and Alpha Beta

by aberent 11. February 2009 06:50

Out of all of the computer chess programming concepts I discussed on this website I found move searching to be the most complicated for me to understand, and the most time consuming to write. Until this point all of the concepts of writing a chess engine were easy to understand. Most developers will figure out some way of representing chess pieces, chess board and movement. However I found that move searching is not like that. Reinventing the wheel by writing your own move search algorithm is just not a good idea. There are algorithms that you just have to implement for your engine to have a shot at searching enough moves to simulate even average chess playing.

Min Max & Negamax

Probably like most people starting to program a chess engine I started by looking at implementing the Min Max algorithm. The idea is fairly simple, I look at all my moves I can make, evaluate them and make the best move. Then I do the same for the opponent from his point of view.

This led me to some really crappy code that did not really work very well. Actually what I found out later is that min max works by going deep into the furthest leaf of the search tree and working backwards. That’s not the same thing as going from the top down because what ended up being a spectacular move 5 nodes down could have been a really crappy move at the beginning. A good example of this is a chess piece sacrifice to get a check mate. So I look to all the possibilities of every move I can make along with all of the moves my opponent can make work backwards and I choose the root move that will get me the best score at the end.

private static int MinMax(Board examineBoard, byte depth)
{
if (depth == 0)
{
   //Evaluate Score
  Evaluation.EvaluateBoardScore(examineBoard);
  //Invert Score to support Negamax
  return SideToMoveScore(examineBoard.Score, examineBoard.WhoseMove);
}

List<Position> positions = EvaluateMoves(examineBoard, depth);

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;
  }
}

int bestScore = -32767;

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 = -MinMax(board, (byte)(depth-1));

  if (value > bestScore)
  {
   bestScore = (int)value;
  }
}

return bestScore;
}

The above Mix-Max implementation is not actually used anywhere in my chess engine, however I wanted to make sure it is we understand how it works before we move to the actual implementation of Alpha Beta.

The first point I would like to make about the above code is that the algorithm is recursive. It will call itself up to its furthest leaf and then return the score back to each parent branch so that the branch can evaluate which leaf was the best back as many levels as we decide are needed.

The second point on the above Min-Max implementation is related to the depth variable. It will set the limit of how far should our algorithm search. This is often referred to as ply. One ply equals one move by either side. So if we set our algorithm depth to 1 ply the Min Max algorithm would simple search one move deep and return the best move available to the current side. A depth 2 or ply 2 search would search each possible move and each possible response to every move.

Furthermore the above algorithm is actually a variation of Min-Max often called Negamax because as mentioned above it always looks for the maximizing score rather than having to branches looking for either the maximum or minimum value depending on the chess piece color moving.

There is however a trick to implementing Negamax. The issue is that the algorithm has to always look for the highest score, so we will need a helper method to help us out here by inverting the score for black.

private static int SideToMoveScore(int score, ChessPieceColor color)
{
if (color == ChessPieceColor.Black)
return -score;

return score;
}

This above method is key, since without it your algorithm would not return the best move for black but rather the worst, highest scored.

If we you had tried to implemented this algorithm in your chess engine you would find that move searching was probably very slow. It was probably ok down to ply 3 or 4

Alpha Beta

The next evolution of my search algorithm was Alpha Beta. It took me of weeks reading articles on min max and alpha beta trying to fully grasp exactly was has to be coded and why it works.

The main idea behind Alpha Beta is the fact that we don’t need to search every possible move. Some moves just do not make sense.

Let’s imagine your opponent has 5 bags of items. You get to keep one of the items from one of the 5 bags. You get to choose the bag, however your opponent will get to choose which item you get. Your opponent does not want to give away his valuable items so he will choose the one that is least valuable to you. So you must choose the bag where the least valuable item is more valuable than the least valuable item in all of the other bags.

So let’s say you open the first bag and you look inside. You see a gold ring, a diamond and a shovel. You know your opponent is not going to give you the gold ring or the diamond. If you choose the first bag you will end up with a shovel. The shovel is the least valuable item in that bag you remember that for later.

So you look into the second bag and you see a laptop computer. This is more valuable than a shovel, so you keep looking. However the second item is a clump of dirt. Dirt is less valuable than a shovel. So you don’t need to keep looking through the other items in that bag, because you know that whatever else you find in the bag even if it is more valuable you will just end up with dirt. Instead you can move on to the next bag and keep looking for something better than a shovel.

This is how alpha beta works. You stop looking for responses to your move (bag) when you find one that has a worst result than the worst result from your previous move. The name Alpha Beta refers to the two variables that you will pass around the algorithm that will keep the best scores for you and your opponent (The Shovel)

The main advantage of Alpha Beta is that it is free. It does not affect the quality of the moves made by the computer. It simply discards moves that would not have been considered anyways.

One additional note I would like to make is that Alpha Beta works best when the moves are sorted in the order of best first. If we think of our example above it is in our best interest to find the bag with the shovel first before finding the bag with the clump of dirt. If you had found the clump of dirt first you would still have to look through all the other items in the second bag.

For this purpose it is in our best interest to sort the moves prior to trying Alpha Beta. For that we need to declare a few methods.

Evaluate Moves

Evaluate Moves is a pseudo move generator and an evaluation function combined. It organizes all the valid moves for a position into a list of positions and assigns them a score based on a very basic evaluation. We don’t use this evaluation score to make any serious decisions we just use it to sort our moves. You may be tempted to use your regular chess board evaluation function here. This would improve sorting quite a bit, however a full evaluation is slow and there would be allot of wasted effort because you don’t need the actual score of the chess board until you get to depth 0 (the last ply you are going to look at). In my tests I found that doing a simple sort based on a score resulting from Most Valuable Vitim Least Valuable Attacker, performs quite well. Basically the idea is that you want to try a pawn attacking a queen before you try a queen attacking a pawn. I achieve this by subtracting the values of the attacker and defender. This generates lots of node cut-offs. In addition to MVV/LVA I add some small easy evaluation points for castling moves and Piece Action Value.

Evaluate Moves stores its results in a List of Positions.

private struct Position
{
internal byte SrcPosition;
internal byte DstPosition;
internal int Score;
}

Evaluate Moves also requires a helper sort method.

private static int Sort(Position s2, Position s1)
{
return (s1.Score).CompareTo(s2.Score);
}

The actual Evaluate Moves method loops through all of the chess pieces on the board and records the source position and destination position of the move along its pseudo score.

private static List<Position> EvaluateMoves(Board board)
{

//We are going to store our result boards here
List<Position> positions = new List<Position>();

for (byte x = 0; x < 64; x++)
{
Piece piece = board.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 != board.WhoseMove)
   continue;

  //For each valid move for this piece
  foreach (byte dst in piece.ValidMoves)
  {
   Position move = new Position();

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

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

   //If the move is a capture add it's value to the score
   if (pieceAttacked != null)
   {
    move.Score += pieceAttacked.PieceValue;

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

   if (!piece.Moved)
   {
    move.Score += 10;
   }

move.Score += piece.PieceActionValue;

   //Add Score for Castling
   if (!board.WhiteCastled && board.WhoseMove == ChessPieceColor.White)
   {

    if (piece.PieceType == ChessPieceType.King)
    {
     if (move.DstPosition != 62 && move.DstPosition != 58)
     {
      move.Score -= 40;
     }
     else
     {
      move.Score += 40;
     }
    }
    if (piece.PieceType == ChessPieceType.Rook)
    {
     move.Score -= 40;
    }
   }

   if (!board.BlackCastled && board.WhoseMove == ChessPieceColor.Black)
   {
    if (piece.PieceType == ChessPieceType.King)
    {
     if (move.DstPosition != 6 && move.DstPosition != 2)
     {
      move.Score -= 40;
     }
     else
     {
      move.Score += 40;
     }
    }
    if (piece.PieceType == ChessPieceType.Rook)
    {
     move.Score -= 40;
    }
   }

positions.Add(move);
}
}

return positions;
}

Now for the actual implementation of Alpha Beta.

In our chess engine we need to introduce the concept of the variables alpha and beta. These will be used during our recursive search to affectively keep the leaf score during our search. This will allow us to make the decision of whether or not we need to continue or we can cut the search short and return.

• Alpha will be the current best score for this leaf.
• Beta will be the best score for the upper leaf thus far or the opponent’s best score for positions already searched.

If Alpha > Beta, meaning my move is better than my opponents other best move thus far we have reached the scenario where searching other moves are not relevant because a Shovel is better than clump of dirt.

Here is the Alpha Beta code from my chess engine

private static int AlphaBeta(Board examineBoard, byte depth, int alpha, int beta)
{
nodesSearched++;

if (examineBoard.FiftyMove >= 50 || examineBoard.RepeatedMove >= 3)
return 0;

if (depth == 0)
{
  //Evaluate Score
  Evaluation.EvaluateBoardScore(examineBoard);
  //Invert Score to support Negamax
  return SideToMoveScore(examineBoard.Score, examineBoard.WhoseMove);
}

List<Position> positions = EvaluateMoves(examineBoard);

    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;
   }
  }

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

  if (value >= beta)
  {
   // Beta cut-off
   return beta;
  }
  if (value > alpha)
  {
   alpha = value;
  }
}

return alpha;
}

As you see this code is almost identical to the Min-Max code above with the exception of move sorting as well as the Alpha and Beta variables. Furthermore if we do find a cut-off (alpha > beta) then we simply return beta as the best score.

Initially the Alpha Beta method is called with Alpha being the smallest possible integer and Beta being the highest possible integer. This ensures that we search at least one move all the way down to its last ply before performing any cut-offs. In the next post I will discuss how to make that initial Alpha Beta call from my chess engine and some of the other modifications of Alpha Beta that will improve its speed and accuracy.

Currently rated 5.0 by 5 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: alpha beta, min max, negamax, move pruning, alpha, beta, move sorting, min-max, minmax, alpha-beta, alphabeta

Chess Bin Engine

Search for Mate

by aberent 2. January 2009 06:34

Before we can discus move searching and the Alpha Beta algorithm we need a way to check for check mates. This method will actually be located in our static Search class. This method will loop through all of the moves for all the chess pieces on the board and see if they actually have a valid move. If they do then we are not in a check mate situation. If there aren’t any valid moves for this board position that we know that this is either a check mate (if the king is in check) or a stale mate.

This method is very expensive to execute so we only call it if there is a check on any king on the board or if there are 0 possible moves. I will explain in more detail in my Alpha Beta method.

The Search for Mate method returns true if a check mate or stale mate is found. The actual values of type of mate and side mated are stored in the three reference variables passed into the method.

internal static bool SearchForMate(ChessPieceColor movingSide, Board examineBoard, ref bool blackMate, ref bool whiteMate, ref bool staleMate)
{
bool foundNonCheckBlack = false;
bool foundNonCheckWhite = false;

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 != movingSide)
   continue;

  //For each valid move for this piece
  foreach (byte dst in sqr.Piece.ValidMoves)
  {

//We make copies of the board and move so we don't change the original
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);

   if (board.BlackCheck == false)
   {
    foundNonCheckBlack = true;
   }
   else if (movingSide == ChessPieceColor.Black)
   {
    continue;
   }

   if (board.WhiteCheck == false )
   {
    foundNonCheckWhite = true;
   }
   else if (movingSide == ChessPieceColor.White)
   {
    continue;
   }
  }
}

if (foundNonCheckBlack == false)
{
  if (examineBoard.BlackCheck)
  {
   blackMate = true;
   return true;
  }
  if (!examineBoard.WhiteMate && movingSide != ChessPieceColor.White)
  {
   staleMate = true;
   return true;
  }
}

if (foundNonCheckWhite == false)
{
  if (examineBoard.WhiteCheck)
  {
   whiteMate = true;
   return true;
  }
  if (!examineBoard.BlackMate && movingSide != ChessPieceColor.Black)
  {
   staleMate = true;
   return true;
  }
}

return false;
}

The Search for Mate method is also used in your Chess Engine Make Move method which will check if the last move made by the human player caused a check mate. This will be done every time a player makes a move.

That’s it for this post. If you have any questions feel free to email me or post a comment below. Chances are if you have a question, other people might have it too.

Currently rated 5.0 by 1 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: alpha beta, check mate, stale mate, mate checkmate, stalemate, search, check mate search, find check mate

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

Piece Square Table

by aberent 26. September 2008 03:17

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:

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
};

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

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,
};

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

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,
};

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.

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 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:

score += PawnTable[position];

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

byte index = (byte)(((byte)(position + 56)) - (byte)((byte)(position / 8) * 16));

score += PawnTable[index];

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.

Currently rated 4.5 by 2 people

Currently 4.5/5 Stars.
1
2
3
4
5

Tags: piece square table, computer chess, computer chess engine, chess engine, chessbin

Chess Bin Engine

Starting the chess engine

by aberent 17. September 2008 04:52

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

public sealed class Engine

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.

internal Board ChessBoard;
internal Board PreviousChessBoard;

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

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.

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

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

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

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.

private void RegisterPiece(byte boardColumn, byte boardRow, ChessPiece Piece)
{
byte position = (byte)(boardColumn + (boardRow * 8));

ChessBoard.Squares[position].Piece = Piece;

return;
}

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.

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;
}

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.

ChessBoard = new Board("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");

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.

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

Tags: chess engine, computer chess

Chess Bin Engine

Move Content

by aberent 15. September 2008 03:20

In our Chess Engine we will need to describe movement as it occurs. This will be useful to keep track move history, the best move at each search level or even the result of our Alpha Beta Search.

The Move Content class has 2 major components. The first component describes the moving chess piece(s). The second component describes the chess piece taken or captured during the move.

These two components described as 2 structs:

public struct PieceMoving
{
public byte DstPosition;
public bool Moved;
public ChessPieceColor PieceColor;
public ChessPieceType PieceType;
public byte SrcPosition;

public PieceMoving(ChessPieceColor pieceColor, ChessPieceType pieceType, bool moved,
        byte srcPosition, byte dstPosition)
{
  PieceColor = pieceColor;
  PieceType = pieceType;
  SrcPosition = srcPosition;
  DstPosition = dstPosition;
  Moved = moved;
}

public PieceMoving(PieceMoving pieceMoving)
{
  PieceColor = pieceMoving.PieceColor;
  PieceType = pieceMoving.PieceType;
  SrcPosition = pieceMoving.SrcPosition;
  DstPosition = pieceMoving.DstPosition;
  Moved = pieceMoving.Moved;
}

public PieceMoving(ChessPieceType pieceType)
{
  PieceType = pieceType;
  PieceColor = ChessPieceColor.White;
  SrcPosition = 0;
  DstPosition = 0;
  Moved = false;
}
}

public struct PieceTaken
{
public bool Moved;
public ChessPieceColor PieceColor;
public ChessPieceType PieceType;
public byte Position;

public PieceTaken(ChessPieceColor pieceColor, ChessPieceType pieceType, bool moved,
       byte position)
{
  PieceColor = pieceColor;
  PieceType = pieceType;
  Position = position;
  Moved = moved;
}

public PieceTaken(ChessPieceType pieceType)
{
  PieceColor = ChessPieceColor.White;
  PieceType = pieceType;
  Position = 0;
  Moved = false;
}
}

The Move Content class itself makes use of the above 2 structs by declaring them into 3 fields:

PieceMoving MovingPiecePrimary – The primary piece that has moved.

PieceMoving MovingPieceSecondary; - The secondary piece that has moved. This is usually null unless a king has castled. In this case the primary Piece would be the king and the secondary piece would be the rook.

PieceTaken TakenPiece – The chess piece that was capture or taken during the move.

The other fields like Score, Pawn Promoted and En Passant Occurred are self explanatory. However the last method ToString requires a bit of an explanation.

The Move Content class will be used to generate Portable Game Notation (PGN) string of the game. For this reason I overwrote the ToString() method for the class so that it will return a portion of the PGN string for the move that has occurred.

public new string ToString()
{
string value = "";

    var srcCol = (byte) (MovingPiecePrimary.SrcPosition%8);
    var srcRow = (byte)(8 - (MovingPiecePrimary.SrcPosition / 8));
    var dstCol = (byte) (MovingPiecePrimary.DstPosition%8);
    var dstRow = (byte) (8 - (MovingPiecePrimary.DstPosition/8));

    if (MovingPieceSecondary.PieceType == ChessPieceType.Rook)
    {
        if (MovingPieceSecondary.PieceColor == ChessPieceColor.Black)
        {
            if (MovingPieceSecondary.SrcPosition == 7)
            {
                value += "O-O";
            }
            else if (MovingPieceSecondary.SrcPosition == 0)
            {
                value += "O-O-O";
            }
        }
        else if (MovingPieceSecondary.PieceColor == ChessPieceColor.White)
        {
            if (MovingPieceSecondary.SrcPosition == 63)
            {
                value += "O-O";
            }
            else if (MovingPieceSecondary.SrcPosition == 56)
            {
                value += "O-O-O";
            }
        }
    }
    else
    {
        value += GetPgnMove(MovingPiecePrimary.PieceType);

        switch (MovingPiecePrimary.PieceType)
        {
            case ChessPieceType.Knight:
                value += GetColumnFromInt(srcCol + 1);
                value += srcRow;
                break;
            case ChessPieceType.Rook:
                value += GetColumnFromInt(srcCol + 1);
                value += srcRow;
                break;
            case ChessPieceType.Pawn:
                if (srcCol != dstCol)
                {
                    value += GetColumnFromInt(srcCol + 1);
                }
                break;
        }

        if (TakenPiece.PieceType != ChessPieceType.None)
        {
            value += "x";
        }

value += GetColumnFromInt(dstCol + 1);

value += dstRow;

        if (PawnPromoted)
        {
            value += "=Q";
        }
    }

return value;
}

Notice: Since the Move Content class and all its components will be used to display information outside of the chess engine like the user interface all the Move Content components and the class itself were declared as public.

The above ToString() method requires a few helper methods that convert objects to strings:

private static string GetColumnFromInt(int column)
{
    switch (column)
    {
        case 1:
            return "a";
        case 2:
            return "b";
        case 3:
            return "c";
        case 4:
            return "d";
        case 5:
            return "e";
        case 6:
            return "f";
        case 7:
            return "g";
        case 8:
            return "h";
        default:
            return "Unknown";
    }
}

private static string GetPgnMove(ChessPieceType pieceType)
{
    switch (pieceType)
    {
        case ChessPieceType.Bishop:
            return "B";

case ChessPieceType.King:
return "K";

case ChessPieceType.Knight:
return "N";

case ChessPieceType.Queen:
return "Q";

        case ChessPieceType.Rook:
            return "R";
        default:
            return "";
    }
}

This concludes the Move Content class. If you want to get started on creating your own chess engine download my C# Chess Game Starter Kit.

Currently rated 5.0 by 1 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: move content, move history, source move, destination move, chess piece moves

Chess Bin Engine

Chess Piece Valid Moves

by aberent 10. September 2008 12:31

Originally the code in this post was part of the Chess Piece Motion class. However since I posted the ordinal code I have divided that class into 2 separate classes. Chess Piece Moves and Chess Piece Valid moves which is discussed here.

This class will be responsible for dynamically figuring out only the valid moves for the current chess board and assigning only the valid moves to each chess piece. This class will also figure out what pieces are attacking each other, is the king in check, has en passant occurred and assign the information to each piece for the purpose of score evaluation.

The Chess Piece Valid Moves class will be declared as follows:

internal static class PieceValidMoves

To help us understand what is board squares are being attacked we will defina 2 arrays. One for storing board squares attacked by White, and one for Black. These arrays are crucial in figuring out things like valid moves for a king, since kings cannot move onto a square that is currently attacked by an opponent.

internal static bool[] BlackAttackBoard;
internal static bool[] WhiteAttackBoard;

Furthermore we can't correctly check for the kings valid moves until we examine all other chess pieces. This is due to the fact that we won't know if the chess board square is attacked if we don't look at every single chess piece first. For this reason when we come across a king during our analysis, we don't analyze its possible moves but rather store its position for later analysis. The following 2 variables are used to store that information.

private static byte BlackKingPosition;
private static byte WhiteKingPosition;

The Analyze Move method will perform a deep analysis or examination of the move itself and its effect on the chess board. For example this method will record an En Passant scenario as well as recording Checks and Kills. The Analyze Move method will return true if the move is considered not blocked (not resulting in a kill or blocked by another chess piece of the same color). Similarly it will return false if the move is blocked and movement cannot continue past this position. This is very important since this return value will be used to end a loop of moves in a certain direction. This method is called for all chess pieces other than pawns and kings.

private static bool AnalyzeMove(Board board, byte dstPos, Piece pcMoving)
{
    //If I am not a pawn everywhere I move I can attack
    if (pcMoving.PieceColor == ChessPieceColor.White)
    {
        WhiteAttackBoard[dstPos] = true;
    }
    else
    {
        BlackAttackBoard[dstPos] = true;
    }

    //If there no piece there I can potentialy kill just add the move and exit
    if (board.Squares[dstPos].Piece == null)
    {
        pcMoving.ValidMoves.Push(dstPos);

return true;
}

Piece pcAttacked = board.Squares[dstPos].Piece;

    //if that piece is a different color
    if (pcAttacked.PieceColor != pcMoving.PieceColor)
    {
        pcAttacked.AttackedValue += pcMoving.PieceActionValue;

        //If this is a king set it in check
        if (pcAttacked.PieceType == ChessPieceType.King)
        {
            if (pcAttacked.PieceColor == ChessPieceColor.Black)
            {
                board.BlackCheck = true;
            }
            else
            {
                board.WhiteCheck = true;
            }
        }
        else
        {
            //Add this as a valid move
            pcMoving.ValidMoves.Push(dstPos);
        }

        //We don't continue movement past this piece
        return false;
    }
    //Same Color I am defending
    pcAttacked.DefendedValue += pcMoving.PieceActionValue;

//Since this piece is of my kind I can't move there
return false;
}

Pawns behave slightly differently then regular pieces in that not all of their moves can result in a kill. A move straight ahead cannon result in a kill while a diagonal move can. For this reason there are two separate methods to analyze pawn moves. One Parent that loops through all available pawn moves and one child that analyzes each move at a time.

Parent:

private static void CheckValidMovesPawn(List<byte> moves, Piece pcMoving,
          byte srcPosition,
          Board board, byte count)
{
for (byte i = 0; i < count; i++)
{
  byte dstPos = moves[i];

  if (dstPos%8 != srcPosition%8)
  {
   //If there is a piece there I can potentialy kill
   AnalyzeMovePawn(board, dstPos, pcMoving);

   if (pcMoving.PieceColor == ChessPieceColor.White)
   {
    WhiteAttackBoard[dstPos] = true;
   }
   else
   {
    BlackAttackBoard[dstPos] = true;
   }
  }
   // if there is something if front pawns can't move there
  else if (board.Squares[dstPos].Piece != null)
  {
   return;
  }
   //if there is nothing in front of me (blocked == false)
  else
  {
   pcMoving.ValidMoves.Push(dstPos);
  }
}
}

Child:

private static void AnalyzeMovePawn(Board board, byte dstPos, Piece pcMoving)
{
    //Because Pawns only kill diagonaly we handle the En Passant scenario specialy
    if (board.EnPassantPosition > 0)
    {
        if (pcMoving.PieceColor != board.EnPassantColor)
        {
            if (board.EnPassantPosition == dstPos)
            {
                //We have an En Passant Possible
                pcMoving.ValidMoves.Push(dstPos);

                if (pcMoving.PieceColor == ChessPieceColor.White)
                {
                    WhiteAttackBoard[dstPos] = true;
                }
                else
                {
                    BlackAttackBoard[dstPos] = true;
                }
            }
        }
    }

Piece pcAttacked = board.Squares[dstPos].Piece;

    //If there no piece there I can potentialy kill
    if (pcAttacked == null)
        return;

    //Regardless of what is there I am attacking this square
    if (pcMoving.PieceColor == ChessPieceColor.White)
    {
        WhiteAttackBoard[dstPos] = true;

        //if that piece is the same color
        if (pcAttacked.PieceColor == pcMoving.PieceColor)
        {
            pcAttacked.DefendedValue += pcMoving.PieceActionValue;
            return;
        }
        //else piece is different so we are attacking
        pcAttacked.AttackedValue += pcMoving.PieceActionValue;

        //If this is a king set it in check
        if (pcAttacked.PieceType == ChessPieceType.King)
        {
            board.BlackCheck = true;
        }
        else
        {
            //Add this as a valid move
            pcMoving.ValidMoves.Push(dstPos);
        }
    }
    else
    {
        BlackAttackBoard[dstPos] = true;

        //if that piece is the same color
        if (pcAttacked.PieceColor == pcMoving.PieceColor)
        {
            return;
        }

        //If this is a king set it in check
        if (pcAttacked.PieceType == ChessPieceType.King)
        {
            board.WhiteCheck = true;
        }
        else
        {
            //Add this as a valid move
            pcMoving.ValidMoves.Push(dstPos);
        }
    }

return;
}

Check Valid Moves King Castle Method handles the complicated castling scenarios by examining the chess board squares between the king and the rook to make sure they are empty, not attacked and that the rook and king are both in their starting positions.

private static void GenerateValidMovesKingCastle(Board board, Piece king)
{
if (king == null)
{
return;
}

if (king.Moved)
{
  return;
}
if (king.PieceColor == ChessPieceColor.White &&
  board.WhiteCastled)
{
  return;
}
if (king.PieceColor == ChessPieceColor.Black &&
  board.BlackCastled)
{
  return;
}
if (king.PieceColor == ChessPieceColor.Black &&
  board.BlackCheck)
{
  return;
}
if (king.PieceColor == ChessPieceColor.White &&
  board.WhiteCheck)
{
  return;
}

//This code will add the castleling move to the pieces available moves
if (king.PieceColor == ChessPieceColor.White)
{
  if (board.WhiteCheck)
  {
   return;
  }

  if (board.Squares[63].Piece != null)
  {
   //Check if the Right Rook is still in the correct position
   if (board.Squares[63].Piece.PieceType == ChessPieceType.Rook)
   {
    if (board.Squares[63].Piece.PieceColor == king.PieceColor)
    {
     //Move one column to right see if its empty
     if (board.Squares[62].Piece == null)
     {
      if (board.Squares[61].Piece == null)
      {
       if (BlackAttackBoard[61] == false &&
        BlackAttackBoard[62] == false)
       {
        //Ok looks like move is valid lets add it
        king.ValidMoves.Push(62);
        WhiteAttackBoard[62] = true;
       }
      }
     }
    }
   }
  }

  if (board.Squares[56].Piece != null)
  {
   //Check if the Left Rook is still in the correct position
   if (board.Squares[56].Piece.PieceType == ChessPieceType.Rook)
   {
    if (board.Squares[56].Piece.PieceColor == king.PieceColor)
    {
     //Move one column to right see if its empty
     if (board.Squares[57].Piece == null)
     {
      if (board.Squares[58].Piece == null)
      {
       if (board.Squares[59].Piece == null)
       {
        if (BlackAttackBoard[58] == false &&
         BlackAttackBoard[59] == false)
        {
         //Ok looks like move is valid lets add it
         king.ValidMoves.Push(58);
         WhiteAttackBoard[58] = true;
        }
       }
      }
     }
    }
   }
  }
}
else if (king.PieceColor == ChessPieceColor.Black)
{
  if (board.BlackCheck)
  {
   return;
  }

  //There are two ways to castle, scenario 1:
  if (board.Squares[7].Piece != null)
  {
   //Check if the Right Rook is still in the correct position
   if (board.Squares[7].Piece.PieceType == ChessPieceType.Rook
    && !board.Squares[7].Piece.Moved)
   {
    if (board.Squares[7].Piece.PieceColor == king.PieceColor)
    {
     //Move one column to right see if its empty

     if (board.Squares[6].Piece == null)
     {
      if (board.Squares[5].Piece == null)
      {
       if (WhiteAttackBoard[5] == false && WhiteAttackBoard[6] == false)
       {
        //Ok looks like move is valid lets add it
        king.ValidMoves.Push(6);
        BlackAttackBoard[6] = true;
       }
      }
     }
    }
   }
  }
  //There are two ways to castle, scenario 2:
  if (board.Squares[0].Piece != null)
  {
   //Check if the Left Rook is still in the correct position
   if (board.Squares[0].Piece.PieceType == ChessPieceType.Rook &&
    !board.Squares[0].Piece.Moved)
   {
    if (board.Squares[0].Piece.PieceColor ==
     king.PieceColor)
    {
     //Move one column to right see if its empty
     if (board.Squares[1].Piece == null)
     {
      if (board.Squares[2].Piece == null)
      {
       if (board.Squares[3].Piece == null)
       {
        if (WhiteAttackBoard[2] == false &&
         WhiteAttackBoard[3] == false)
        {
         //Ok looks like move is valid lets add it
         king.ValidMoves.Push(2);
         BlackAttackBoard[2] = true;
        }
       }
      }
     }
    }
   }
  }
}
}

The last method in this class is the only non private method in this listing. The Generate Valid Moves method will be called directly by the chess engine to create valid moves for each chess board it examines. This method will loop through all chess pieces on the chess board and examine each possible move based on the chess piece’s position. Please note that we have already calculated each pieces move in the Chess Piece Moves class for every single position on the chess board. We now just have to figure out which one of those moves is valid and what their results will be. While we are looping through all of the chess pieces we also collect some information such as how many pawns are in each file, how many pawns are isolated. At the end of this method we will sum up this information and store it on the Chess Board.

internal static void GenerateValidMoves(Board board)
{
// Reset Board
board.BlackCheck = false;
board.WhiteCheck = false;

WhiteAttackBoard = new bool[64];
BlackAttackBoard = new bool[64];

//Generate Moves
for (byte x = 0; x < 64; x++)
{
Square sqr = board.Squares[x];

if (sqr.Piece == null)
continue;

sqr.Piece.ValidMoves = new Stack<byte>(sqr.Piece.LastValidMoveCount);

  switch (sqr.Piece.PieceType)
  {
   case ChessPieceType.Pawn:
    {
     if (sqr.Piece.PieceColor == ChessPieceColor.White)
     {
      CheckValidMovesPawn(MoveArrays.WhitePawnMoves[x].Moves, sqr.Piece, x,
           board,
           MoveArrays.WhitePawnTotalMoves[x]);
      break;
     }
     if (sqr.Piece.PieceColor == ChessPieceColor.Black)
     {
      CheckValidMovesPawn(MoveArrays.BlackPawnMoves[x].Moves, sqr.Piece, x,
           board,
           MoveArrays.BlackPawnTotalMoves[x]);
      break;
     }

     break;
    }
   case ChessPieceType.Knight:
    {
     for (byte i = 0; i < MoveArrays.KnightTotalMoves[x]; i++)
     {
      AnalyzeMove(board, MoveArrays.KnightMoves[x].Moves[i], sqr.Piece);
     }

     break;
    }
   case ChessPieceType.Bishop:
    {
     for (byte i = 0; i < MoveArrays.BishopTotalMoves1[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.BishopMoves1[x].Moves[i],
          sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.BishopTotalMoves2[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.BishopMoves2[x].Moves[i],
          sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.BishopTotalMoves3[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.BishopMoves3[x].Moves[i],
          sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.BishopTotalMoves4[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.BishopMoves4[x].Moves[i],
          sqr.Piece) ==
       false)
      {
       break;
      }
     }

     break;
    }
   case ChessPieceType.Rook:
    {
     for (byte i = 0; i < MoveArrays.RookTotalMoves1[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.RookMoves1[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.RookTotalMoves2[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.RookMoves2[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.RookTotalMoves3[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.RookMoves3[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.RookTotalMoves4[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.RookMoves4[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }

     break;
    }
   case ChessPieceType.Queen:
    {
     for (byte i = 0; i < MoveArrays.QueenTotalMoves1[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves1[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves2[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves2[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves3[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves3[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves4[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves4[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves5[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves5[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves6[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves6[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves7[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves7[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }
     for (byte i = 0; i < MoveArrays.QueenTotalMoves8[x]; i++)
     {
      if (
       AnalyzeMove(board, MoveArrays.QueenMoves8[x].Moves[i], sqr.Piece) ==
       false)
      {
       break;
      }
     }

     break;
    }
   case ChessPieceType.King:
    {
     if (sqr.Piece.PieceColor == ChessPieceColor.White)
     {
      WhiteKingPosition = x;
     }
     else
     {
      BlackKingPosition = x;
     }

     break;
    }
  }
}

if (board.WhoseMove == ChessPieceColor.White)
{
  GenerateValidMovesKing(board.Squares[BlackKingPosition].Piece, board,
          BlackKingPosition);
  GenerateValidMovesKing(board.Squares[WhiteKingPosition].Piece, board,
          WhiteKingPosition);
}
else
{
  GenerateValidMovesKing(board.Squares[WhiteKingPosition].Piece, board,
          WhiteKingPosition);
  GenerateValidMovesKing(board.Squares[BlackKingPosition].Piece, board,
          BlackKingPosition);
}

//Now that all the pieces were examined we know if the king is in check
GenerateValidMovesKingCastle(board, board.Squares[WhiteKingPosition].Piece);
GenerateValidMovesKingCastle(board, board.Squares[BlackKingPosition].Piece);
}

This concludes the Chess Piece Valid Moves class.

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

Currently rated 5.0 by 2 people

Currently 5/5 Stars.
1
2
3
4
5

Tags: chess piece motion, valid moves, chess piece moves, moves, motion, chess motion, computer chess, move generator

Chess Bin Engine

<< Previous posts Next posts >>

Created and Maintained by Adam Berent
www.adamberent.com

Computer Chess Information and Resources

Move Searching and Alpha Beta

Search for Mate

Performance Reconstruction

Chess Board Evaluation

Piece Square Table

Starting the chess engine

Move Content

Chess Piece Valid Moves

Free Online Chess

Recent Posts

Vintage Chess Computers

Downloads

Miscellaneous