Move Searching Alpha Beta Part 2

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

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

The code below can be divided into 3 sections.

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

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

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

Now onto the main Alpha Beta Root Method:

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

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

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

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

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

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

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

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

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

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

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

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

   succ.Positions.Add(board);
  }
 }

 succ.Positions.Sort(Sort);

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

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

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

 int currentBoard = 0;

 alpha = -400000000;

 succ.Positions.Sort(Sort);

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

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

  pos.Score = value;

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

 }

 return bestBoard.LastMove;
}

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

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

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

Want to skip to the end, download the full chess engine source code on GitHub