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