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 with 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);
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;
}
}
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 72 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.
Want to skip to the end, download the full chess engine source code on GitHub