Move Searching Alpha Beta Part 2

by aberent 14. April 2009 05:15

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

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

The code below can be divided into 3 sections.

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

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

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

Now onto the main Alpha Beta Root Method:

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

Board bestBoard = new Board(short.MinValue);

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

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

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

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

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

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

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

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

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

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

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

succ.Positions.Add(board);
}
}

succ.Positions.Sort(Sort);

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

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

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

int currentBoard = 0;

alpha = -400000000;

succ.Positions.Sort(Sort);

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

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

pos.Score = value;

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

}

return bestBoard.LastMove;
}

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

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

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

return depth;
}

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

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

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

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

Chess Bin Engine

Performance Reconstruction Phase Two

by aberent 3. April 2009 23:06

This is the second re-design I am doing on the ChessBin Chess Engine. You can read all about the first one here, so you don’t make the same mistakes as me. I guess that is what you get for re-inventing the wheel. At least I am still having fun.

This re-construction is related to how my chess engine stores the chess board. Currently the chess board is described as a two dimensional array. This way with a column and row you can locate any square on the board. This is makes my chess engine easy to understand but slow.

The new design will modify the chess board to be a single array of 64 squares. This makes it necessary to refer to board positions via an index. An index of 0 will locate the top left most square on the board and an index of 63 will locate the bottom right one. This also allows me to drop the entire Position struct as it is no longer necessary to describe the position by two bytes.

The new version of my ChessBin chess engine that I am currently testing is about 25% faster due to these changes.

I will be modifying each of the posts and the development kit over the next few weeks. Stay tuned for updates.

Updated April 22nd 2009, I have finished updating all of the posts and the Chess Game Development Kit.

Be the first to rate this post

Currently 0/5 Stars.
1
2
3
4
5

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

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 Representation

by aberent 29. August 2008 03:22

Prior to Reading this post I suggest reviewing the pages explaining the Board Square and Chess Piece classes.

The chess board class is again declared as internal sealed to improve performance.

internal sealed class Board

Our chess board will contain 64 board squares represented by an array of [64] items.

Originally I used a multidimensional array [][]. This way I can reference board position by columns and rows. Although this made my code easier to understand, it also made move searching approximately 30%

internal Square[] Squares;

At this point I would like to explain some simple concepts related to how we represent a chess board using the above 64 item array of board squares. Array item 0 will represent the top left most square on the board (A8). Array item 63 will represent the bottom right most square on the board, H1.

0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

When dealing with a single index to reference chess board positions there are certain things that one must know to make life easier. For example how do you know that two positions are both on the same row or column? There is an easy trick to figure that out.

Row

To figure out the row of a position you divide the position by 8 and take the integer portion of the result. For example position 63 divided by 8 is 7.875 which equals row 7. Position 3 divided by 8 is 0.375 so 0. In C# by casting to an integer you will always get just the integer portion of the number, hence:

Row = (int)(position / 8)

Column

To figure out the column of a position you use the modulus operator by performing position modulus 8. For example position 24 modulus 8 is column 0. Position 15 modulus 8 is 7, hence

Column = position % 8

Armed with these two concepts we can convert any position on our 64 square board to a column and row.

Properties

The next property is the Board Score. This is implemented as an internal integer. The score works by increasing better positions for White and decreasing for better positions for Black. Hence in our search methods Black is always trying to find boards with the lowest score and White with the highest.

internal int Score;

The next set of properties that contain information related to king checks and mates. True if white king is in check, false if not etc.

internal bool BlackCheck;
internal bool BlackMate;
internal bool WhiteCheck;
internal bool WhiteMate;
internal bool StaleMate;

The next two variables are counters that allow us to keep track of the two tie scenarios related to the 50 move rule and the 3 move repetitions rule. If the fifty move count reaches 50 or repeat move count reaches 3 we know that a tie has occurred.

internal byte FiftyMove;
internal byte RepeatedMove;

The two following flags are used to track if any of the two sides have castled. This information is needed for the evaluation function to give bonus scores for castling and the move generator to allow for castling to occur if the circumstance is correct.

internal bool BlackCastled;
internal bool WhiteCastled;

The next flag tracks if the board is in the middle game or end game state. This is determined later on by the amount of pieces remaining on the board in the Evaluation Function. If the chess board is in an end game state certain behaviors will be modified to increase king safety and mate opportunities.

internal bool EndGamePhase;

The board will also keep track of the last move that occurred. This is implemented as a Move Content class which we will discuss later.

internal MoveContent LastMove;

The next flags relate to the EnPassant rule, which was actually a bit of a pain to implement. For now all we need to know is that our board will contain 2 pieces of information related to EnPassant.

1. Which side has last made a move that can cause an EnPassant (Which side moved the pawn 2 spots).

internal ChessPieceColor EnPassantColor;

2. The Board Square of the EnPassant position, which is the position directly behind the pawn that moved 2 spots.

internal byte EnPassantPosition;

The Board will keep track of whose move it is

internal ChessPieceColor WhosMove;

As well as how many moves have occurred.

internal int MoveCount;

Constructors

The Board class with have 4 constructors as follows:

Default Constructor:

internal Board()
{
Squares = new Square[64];

    for (byte i = 0; i < 64; i++)
    {
        Squares[i] = new Square();
    }

LastMove = new MoveContent();
}

Copy Constructor:

internal Board(Board board)
{
Squares = new Square[64];

    for (byte x = 0; x < 64; x++)
    {
        if (board.Squares[x].Piece != null)
        {
            Squares[x] = new Square(board.Squares[x].Piece);
        }
    }
    EndGamePhase = board.EndGamePhase;

FiftyMove = board.FiftyMove;
RepeatedMove = board.RepeatedMove;

WhiteCastled = board.WhiteCastled;
BlackCastled = board.BlackCastled;

    BlackCheck = board.BlackCheck;
    WhiteCheck = board.WhiteCheck;
    StaleMate = board.StaleMate;
    WhiteMate = board.WhiteMate;
    BlackMate = board.BlackMate;
    WhosMove = board.WhosMove;
    EnPassantPosition = board.EnPassantPosition;
    EnPassantColor = board.EnPassantColor;

Score = board.Score;

LastMove = new MoveContent(board.LastMove);

MoveCount = board.MoveCount;
}

Constructor that allows to pass in the default Score. This is useful during move searching where we can initially construct the best Board we found so far to something ridiculous like int.MinValue

internal Board(int score) : this()
{
Score = score;
}

Constructor that will accept an array of Board Squares

private Board(Square[] squares)
{
Squares = new Square[64];

    for (byte x = 0; x < 64; x++)
    {
        if (squares[x].Piece != null)
        {
            Squares[x].Piece = new Piece(squares[x].Piece);
        }
    }
}

As you may have noticed above the copy constructor is actually quite meaty. There are too many fields to copy and this has a performance impact during move generation. For this reason I created another method called Fast Copy. The idea here is that during move generation some fields will get overwritten anyways, so I don’t really care what the previous values of these fields were. The Fast Copy method will copy only the values that must persist from one board to another during move generation.

internal Board FastCopy()
{
Board clonedBoard = new Board(Squares);

    clonedBoard.EndGamePhase = EndGamePhase;
    clonedBoard.WhoseMove = WhoseMove;
    clonedBoard.MoveCount = MoveCount;
    clonedBoard.FiftyMove = FiftyMove;
    clonedBoard.BlackCastled = BlackCastled;
    clonedBoard.WhiteCastled = WhiteCastled;
    return clonedBoard;
}

Board Movement

The following listings are a set of methods that will help us with chess piece movement on our board. Before we can actually write the main movement method, we need to handle all of the special scenarios such as pawn promotion, en passant and castling. These helper methods basically have a set of hard coded positions and some logic that states, if I am in this position and this piece type, do something different. Else the move will be handled by the main move method.

Pawn Promotion

The Promote Pawns method will check for the destination position of the pawn and promote it to a Queen Piece. Most Chess programs allow the user to choose the piece they promote the pawn too; however in most cases I don’t see why you would not choose a queen anyways. Furthermore choosing the queen always simplifies the implementation for now.

private static bool PromotePawns(Board board, Piece piece, byte dstPosition,
                  ChessPieceType promoteToPiece)
{
    if (piece.PieceType == ChessPieceType.Pawn)
    {
        if (dstPosition < 8)
        {
            board.Squares[dstPosition].Piece.PieceType = promoteToPiece;
            return true;
        }
        if (dstPosition > 55)
        {
            board.Squares[dstPosition].Piece.PieceType = promoteToPiece;
            return true;
        }
    }

return false;
}

En Passant

The Record En Passant method sets the En Passant flag if the piece currently moving is a pawn that moves 2 squares.

private static void RecordEnPassant(ChessPieceColor pcColor, ChessPieceType pcType,
        Board board, byte srcPosition, byte dstPosition)
{
    //Record En Passant if Pawn Moving
    if (pcType == ChessPieceType.Pawn)
    {
        //Reset FiftyMoveCount if pawn moved
        board.FiftyMove = 0;

int difference = srcPosition - dstPosition;

        if (difference == 16 || difference == -16)
        {
            board.EnPassantPosition = (byte)(dstPosition + (difference / 2));
            board.EnPassantColor = pcColor;
        }
    }
}

Set En Passant Move Method will move the En Passant piece and kill the advanced pawn based on the En Passant flags of the board and the destination move requested.

private static bool SetEnpassantMove(Board board, byte dstPosition,
                    ChessPieceColor pcColor)
{
    //En Passant
    if (board.EnPassantPosition == dstPosition)
    {
        //We have an En Passant Possible
        if (pcColor != board.EnPassantColor)
        {
            int pieceLocationOffset = 8;

            if (board.EnPassantColor == ChessPieceColor.White)
            {
                pieceLocationOffset = -8;
            }

dstPosition = (byte)(dstPosition + pieceLocationOffset);

Square sqr = board.Squares[dstPosition];

            board.LastMove.TakenPiece =
                new PieceTaken(sqr.Piece.PieceColor, sqr.Piece.PieceType,
                        sqr.Piece.Moved, dstPosition);

            board.Squares[dstPosition].Piece = null;

            //Reset FiftyMoveCount if capture
            board.FiftyMove = 0;

            return true;
        }
    }

return false;
}

Castling

The next Method will move the Rook to its correct position if castling is requested.

private static void KingCastle(Board board, Piece piece,
         byte srcPosition, byte dstPosition)
{
    if (piece.PieceType != ChessPieceType.King)
    {
        return;
    }

    //Lets see if this is a casteling move.
    if (piece.PieceColor == ChessPieceColor.White &&
           srcPosition == 60)
    {
        //Castle Right
        if (dstPosition == 62)
        {
            //Ok we are casteling we need to move the Rook
            if (board.Squares[63].Piece != null)
            {
                board.Squares[61].Piece = board.Squares[63].Piece;
                board.Squares[63].Piece = null;
                board.WhiteCastled = true;
                board.LastMove.MovingPieceSecondary =
                 new PieceMoving(board.Squares[61].Piece.PieceColor,
                     board.Squares[61].Piece.PieceType,
                          board.Squares[61].Piece.Moved, 63, 61);
                board.Squares[61].Piece.Moved = true;
                return;
            }
        }
        //Castle Left
        else if (dstPosition == 58)
        {
            //Ok we are casteling we need to move the Rook
            if (board.Squares[56].Piece != null)
            {
                board.Squares[59].Piece = board.Squares[56].Piece;
                board.Squares[56].Piece = null;
                board.WhiteCastled = true;
                board.LastMove.MovingPieceSecondary =
                  new PieceMoving(board.Squares[59].Piece.PieceColor,
                            board.Squares[59].Piece.PieceType,
                                 board.Squares[59].Piece.Moved, 56, 59);
                board.Squares[59].Piece.Moved = true;
                return;
            }
        }
    }
    else if (piece.PieceColor == ChessPieceColor.Black &&
           srcPosition == 4)
    {
        if (dstPosition == 6)
        {
            //Ok we are casteling we need to move the Rook
            if (board.Squares[7].Piece != null)
            {
                board.Squares[5].Piece = board.Squares[7].Piece;
                board.Squares[7].Piece = null;
                board.BlackCastled = true;
                board.LastMove.MovingPieceSecondary =
                    new PieceMoving(board.Squares[5].Piece.PieceColor,
                             board.Squares[5].Piece.PieceType,
                                  board.Squares[5].Piece.Moved, 7, 5);
                board.Squares[5].Piece.Moved = true;
                return;
            }
        }
            //Castle Left
        else if (dstPosition == 2)
        {
            //Ok we are casteling we need to move the Rook
            if (board.Squares[0].Piece != null)
            {
                board.Squares[3].Piece = board.Squares[0].Piece;
                board.Squares[0].Piece = null;
                board.BlackCastled = true;
                board.LastMove.MovingPieceSecondary =
                   new PieceMoving(board.Squares[3].Piece.PieceColor,
                            board.Squares[3].Piece.PieceType,
                                 board.Squares[3].Piece.Moved, 0, 3);
                board.Squares[3].Piece.Moved = true;
                return;
            }
        }
    }

return;
}

This is the actual Move Method, where each piece is moved, captured. The logic here basically boils down to, recording the move, and assigning the moving piece to the new square, while clearing the old one. This method also calls the helper movement methods we have just listed above to handle the more complex scenarios such as castling, pawn promotion and En Passant.

internal static MoveContent MovePiece(Board board, byte srcPosition,
                    byte dstPosition,
                    ChessPieceType promoteToPiece)
{
    Piece piece = board.Squares[srcPosition].Piece;

//Record my last move
board.LastMove = new MoveContent();

//Add One to FiftyMoveCount to check for tie.
board.FiftyMove++;

    if (piece.PieceColor == ChessPieceColor.Black)
    {
        board.MoveCount++;
    }

    //En Passant
    if (board.EnPassantPosition > 0)
    {
        board.LastMove.EnPassantOccured =
              SetEnpassantMove(board, dstPosition, piece.PieceColor);
    }

    if (!board.LastMove.EnPassantOccured)
    {
        Square sqr = board.Squares[dstPosition];

        if (sqr.Piece != null)
        {
            board.LastMove.TakenPiece =
                  new PieceTaken(sqr.Piece.PieceColor, sqr.Piece.PieceType,
                                       sqr.Piece.Moved, dstPosition);
            board.FiftyMove = 0;
        }
        else
        {
            board.LastMove.TakenPiece =
                  new PieceTaken(ChessPieceColor.White, ChessPieceType.None,
                          false, dstPosition);

        }
    }

    board.LastMove.MovingPiecePrimary =
              new PieceMoving(piece.PieceColor, piece.PieceType,
                      piece.Moved, srcPosition, dstPosition);

//Delete the piece in its source position
board.Squares[srcPosition].Piece = null;

    //Add the piece to its new position
    piece.Moved = true;
    piece.Selected = false;
    board.Squares[dstPosition].Piece = piece;

    //Reset EnPassantPosition
    board.EnPassantPosition = 0;

    //Record En Passant if Pawn Moving
    if (piece.PieceType == ChessPieceType.Pawn)
    {
       board.FiftyMove = 0;
       RecordEnPassant(piece.PieceColor, piece.PieceType,
                board, srcPosition, dstPosition);
    }

    board.WhoseMove = board.WhoseMove == ChessPieceColor.White
              ? ChessPieceColor.Black
              : ChessPieceColor.White;

KingCastle(board, piece, srcPosition, dstPosition);

    //Promote Pawns
    if (PromotePawns(board, piece, dstPosition, promoteToPiece))
    {
        board.LastMove.PawnPromoted = true;
    }
    else
    {
        board.LastMove.PawnPromoted = false;
    }

    if ( board.FiftyMove >= 50)
    {
        board.StaleMate = true;
    }

return board.LastMove;
}

If you compile this listing along with the Chess Piece, Move Content and Board Square classes you should have all the necessary code for declaring and moving pieces around the board. Of course you still don't have a graphical chess board or the move generator.

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 board, board, computer chess, board representation, chess board representation

Chess Bin Engine

Created and Maintained by Adam Berent
www.adamberent.com

Computer Chess Information and Resources

Move Searching Alpha Beta Part 2

Performance Reconstruction Phase Two

Performance Reconstruction

Chess Board Representation

Free Online Chess

Recent Posts

Vintage Chess Computers

Downloads

Miscellaneous