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 solve 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 75 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.
Want to skip to the end, download the full chess engine source code on GitHub