Guide to Programming a Chess Engine

 

This document is a product of a rather rash decision in mid 2008 to learn to program my own Chess Game, hence began my journey into the art of computer chess.  Over the last 2 years I have made some significant progress.  I have learned quite a bit about the art of Computer Chess and amazingly I managed to build a reasonable strong chess engine.  This Document is dedicated to recording the development of my Chess Game as well as the field of Computer Chess in general

 

Table of Contents

Project Goals   2

Goal 1   2

Goal 2   2

Goal 3   3

Goal 4   3

Goal 5   3

Goal 6   3

Choice of Programming Language   3

Chess Piece Representation    3

Constructors  5

Methods  6

Chess Board Square   8

Chess Board Representation    8

Row    9

Column   9

Properties  9

Constructors  10

Copy Constructor:  11

Board Movement  12

En Passant  13

Castling   14

Chess Piece Moves   17

Chess Piece Valid Moves   29

Parent:  31

Child:  32

Move Content   41

Starting the chess engine   45

Generating a Starting Chess Position   47

Piece Square Table   47

Chess Board Evaluation    49

Chess Piece Evaluation   50

On to the code  50

Search for Mate   63

Move Searching and Alpha Beta    65

Min Max & Negamax   65

Evaluate Moves  68

Move Searching Alpha Beta Part 2   72

Quiescence Search and Extensions   74

Horizon Affect  74

Quiescence Search   75

Extensions  75

Forsyth–Edwards Notation    79

Why is FEN useful to us?   79

The implementation of Forsyth–Edwards Notation   79

Examples:  80

Forsyth–Edwards Notation Code  80

Some Performance Optimization Advice   90

Finding Performance Gains  90

Further Performance Gains:  91

Performance Reconstruction Phase Two    92

Transposition Table and Zobrist Hashing    92

The problems  93

Implementation   93

Zobrist Hashing   93

Collisions  94

Transposition Table Contents  94

Replacement Schemes  95

Table Lookup   95

 

 

Project Goals

 

Goal 1

Create a chess game that was capable of consistently winning games against me.

Status: Achieved as of August 18, 2008. 

Goal 2 

Defeat Chess Titans at level 10, the free Chess Game that comes with Windows Vista.

Status: Achieved as of November 7th, 2009 although not consistently

Goal 3 

Interface with WinBoard, the open source chess board.  This is necessary to submit my Chess Engine to most Computer Chess tournaments. 

Status: Achieved as of December 18th 2009:

Goal 4 

Enter a computer chess tournament and beat someone’s chess engine. 

Status: Acheived as of April 5th 2010, Entered WBEC Ridderkerk's 18th Edition Tournament and beat more than one chess engine.

Goal 5 

Defeat Little Chess Partner , the free Java Chess Game from the nice people at Lokasoft.

Status: October 28th 2008, tied based on three move repetition

Goal 6

Create Mobile Chess Game (iOS & Android)

Status: Acheived as of October 20th 2016,

Choice of Programming Language

 

For my implementation of the Chess Game I selected C# mainly because it is a computer language that:

 

Š      I know best and work with every day.

Š      I would like to improve my skills in.

Š      Should be around for a while giving the project a longer life. 

 

There are however negative aspects to my choice.  C# cannot compete with C or assembly language in terms of performance.   This will means that a chess engine created in C# will probably be slightly slower in move searches compared to the same chess engine created in a programming language that compiles into machine code.

 

I have read sites that claim that the .NET framework is just as efficient and quick as unmanaged C++.  However I am skeptical at best.  I have seen a managed C# program choke on things that C++ would breeze through.  Maybe some of this has to do with implementation or optimization.  However I am a firm believer that optimized C++ unmanaged executable will usually be faster then optimized C# managed executable. 

 

As proof I would like to submit the fact that it has been years since the introduction of C# and yet the Windows OS is still entirely written in unmanaged code… even notepad.

 

However I stated before my goal is not to make the best Chess Engine that ever existed, just a fairly good one.  I believe the C# programming language will serve that purpose.

Chess Piece Representation

 

The first 2 tasks in creating a chess engine are the description of the Chess Board and the Chess Pieces.  This page I will discuss my C# representation of the Chess Piece. 

Throughout the chess engine many decisions will have to be made based on 2 concepts.  The chess piece type and it’s color.  For this purpose I have declared two enumerated types, chess piece color and chess piece type:

 

public enum ChessPieceColor

{

    White,

    Black

}

 

public enum ChessPieceType

{

    King,

    Queen,

    Rook,

    Bishop,

    Knight,

    Pawn,

    None

}

 

Originally these two enumerated types were located inside the Chess Piece class, however I later realized that these constructs must be available to assemblies outside of the chess engine, and therefore must be made public.  Since I found that internal classes perform faster than public classes, the only way to make my Chess Piece class internal is to remove the enumerated types out of the Chess Piece class.

The next concept that will be required is the idea of a Chess Board position.  This will be needed in order to list valid moves for a chess piece inside the Chess Piece class.  In the current version of my chess engine, board position coordinates are stored as a single byte, 0 for A8 and 63 for A1.

Originally I stored chess board positions as a set of two bytes.  The first byte was used to represent the column and second byte for the row.  This made my chess engine easier to understand but cost me approximately 30% more in performance.

The class representing my Chess Pieces will be declared as internal sealed:

 

internal sealed class Piece

 

During my performance testing I found that the sealed and internal keywords improved speed significantly.  I also found that private methods and objects perform much faster so I strongly suggest using the private keyword as much as possible. 

To make descriptions of my chess pieces easier and more strongly typed, I will be using the above defined enumerated types as representations of the chess piece color and type.

 

internal ChessPieceColor PieceColor;

internal ChessPieceType PieceType;

 

The next line of code will describe the piece value used in the evaluation of positions.  Obviously each piece type will have a different value; a Queen is worth more than a pawn etc.

 

internal short PieceValue;

 

In order to keep track the value of pieces that are currently attacking and defending this chess piece we will declare the following 2 variables:

 

internal short AttackedValue;

internal short DefendedValue;

 

Each piece will have what I call the Piece Action Value, this is the value added or subtracted from the score when the chess piece is either attacking or defending another chess piece.  Different chess piece types will have different action values.  This follows the logic that it is better to risk a pawn than it is to risk a queen.

 

internal short PieceActionValue;

 

The next line describes if the chess piece is currently selected on the board by the user.  This will help later when coding a graphical user interface.

 

internal bool Selected;

 

The following variable desribes if our chess piece has been moved.  This will be very usefull in the evaluation function where we can give penalties or bonueses if the chess piece has not yet made a move.

 

internal bool Moved;

 

Each piece will also contain a list of valid moves, or board positions that the piece can move too. 

 

internal Stack<byte> ValidMoves;

 

Constructors 

 

There are 2 constructors in the Chess Piece class

 

Copy Constructor, which is needed during move generation.

 

internal Piece(Piece piece)

{

    PieceColor = piece.PieceColor;

    PieceType = piece.PieceType;

    Moved = piece.Moved;

    PieceValue = piece.PieceValue;

   

    if (piece.ValidMoves != null)

        LastValidMoveCount = piece.ValidMoves.Count;                     

}

 

Constructor used to initiate the chess board with chess pieces.

 

internal Piece(ChessPieceType chessPiece, ChessPieceColor chessPieceColor)

{

    PieceType = chessPiece;

    PieceColor = chessPieceColor;

 

    ValidMoves = new Stack<byte>();

    PieceValue = CalculatePieceValue(PieceType);

}

 

Methods

 

Calculate Piece Value and is used during object construction to calculate and record the chess piece’s value.

 

private static short CalculatePieceValue(ChessPieceType pieceType)

{

    switch (pieceType)

    {

        case ChessPieceType.Pawn:

            {

                return 100;

               

            }

        case ChessPieceType.Knight:

            {

                return 320;

            }

        case ChessPieceType.Bishop:

            {

                return 325;

            }

        case ChessPieceType.Rook:

            {

                return 500;

            }

 

        case ChessPieceType.Queen:

            {

                return 975;

            }

        case ChessPieceType.King:

            {

                return 32767;

            }

        default:

            {

                return 0;

            }

    }

}

 

The Piece Action value, the added or subtracted from the score when the chess piece is either attacking or defending another chess piece is also calculated on construction, using the following method:

 

private static short CalculatePieceActionValue(ChessPieceType pieceType)

{

    switch (pieceType)

    {

        case ChessPieceType.Pawn:

            {

                return 6;

            }

        case ChessPieceType.Knight:

            {

                return 3;

            }

        case ChessPieceType.Bishop:

            {

                return 3;

            }

        case ChessPieceType.Rook:

            {

                return 2;

            }

        case ChessPieceType.Queen:

            {

                return 1;

            }

        case ChessPieceType.King:

            {

                return 1;

            }

        default:

            {

                return 0;

            }

    }

}

 

Note that the above method is designed to encourage the computer to protect and attack using the lower valued pieces first. 

 


 

Chess Board Square

 

In this post I will discuss the chess board square representation.  Before we can discuss the chess board we need to model how each of the chess board squares will be represented on our board.

The chess board square will be declared as an internal struct.  I have found that small structs seem to perform better then small classes.  Also making objects internal or even better private, tends to increase performance.

 

internal struct Square

 

Each chess board square can contain a chess piece.

 

internal Piece Piece;

 

Each Board Square will also have the following copy constructor that will copy the chess piece from the copied chess board square or set the chess piece to null, signifying that the current square is empty.

 

internal Square(Piece piece)

{

    Piece = new Piece(piece);

}

Chess Board Representation

 

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.

 

Chess Piece Moves

 

This post at one point discussed the Chess Piece Motion Class.  I have since then divided the code from this class into two separate classes. 

 

Piece Moves 

Piece Valid Moves

 

This post will discuss Piece Moves class.  This class is responsible for providing all available chess piece moves regardless of the state of the chess board.  The information stored in this class will not change throughout the game play so it is static and calculated only once before the game starts.  Having a set of possible moves for any chess piece at any position allows us to later to generate only the valid moves for each chess piece based on the current state of the board. 

 

The Chess Piece Moves listing will contain a Valid Move Set struct.  This struct will be used to store a set of moves available from a single position.

 

internal struct PieceMoveSet

{

    internal readonly List<byte> Moves;

 

    internal PieceMoveSet(List<byte> moves)

    {

        Moves = moves;

    }

}

 

Furthermore we will need some additional array to store all the above move sets for every position on the board.

 

For example KnightMoves[0]. Moves will return a Knight Moves available from position 0 or A8.  KnightMoves[63] will return all of the possible moves for position 63 or H1.

Some chess pieces can move in a single direction for an undefined number of squares until they reach the end of the board or another chess piece.  For this purpose moves sets for some pieces are divided into several arrays, each describing a move in a certain direction.  This makes it easier to manage these movements in the Chess Piece Valid Moves Class by having the ability to loop through each array until a chess piece or the end of the board is reached and no further.

One other explanation is required around the Total Moves arrays.  Example there is an array called KnightTotalMoves.  This array will hold the number of moves available for every position on the chess board.  This is a performance related addition as it allows me to replace all my foreach loops with regular for loops.  It’s a small performance gain (1%-2%) but they all add up.

 

internal struct MoveArrays

{

    internal static PieceMoveSet[] BishopMoves1;

    internal static byte[] BishopTotalMoves1;

   

    internal static PieceMoveSet[] BishopMoves2;

    internal static byte[] BishopTotalMoves2;

 

    internal static PieceMoveSet[] BishopMoves3;

    internal static byte[] BishopTotalMoves3;

    internal static PieceMoveSet[] BishopMoves4;

    internal static byte[] BishopTotalMoves4;

    internal static PieceMoveSet[] BlackPawnMoves;

    internal static byte[] BlackPawnTotalMoves;

    internal static PieceMoveSet[] WhitePawnMoves;

    internal static byte[] WhitePawnTotalMoves;

    internal static PieceMoveSet[] KnightMoves;

    internal static byte[] KnightTotalMoves;

    internal static PieceMoveSet[] QueenMoves1;

    internal static byte[] QueenTotalMoves1;

    internal static PieceMoveSet[] QueenMoves2;

    internal static byte[] QueenTotalMoves2;

    internal static PieceMoveSet[] QueenMoves3;

    internal static byte[] QueenTotalMoves3;

    internal static PieceMoveSet[] QueenMoves4;

    internal static byte[] QueenTotalMoves4;

    internal static PieceMoveSet[] QueenMoves5;

    internal static byte[] QueenTotalMoves5;

    internal static PieceMoveSet[] QueenMoves6;

    internal static byte[] QueenTotalMoves6;

    internal static PieceMoveSet[] QueenMoves7;

    internal static byte[] QueenTotalMoves7;

    internal static PieceMoveSet[] QueenMoves8;

    internal static byte[] QueenTotalMoves8;

    internal static PieceMoveSet[] RookMoves1;

    internal static byte[] RookTotalMoves1;

    internal static PieceMoveSet[] RookMoves2;

    internal static byte[] RookTotalMoves2;

    internal static PieceMoveSet[] RookMoves3;

    internal static byte[] RookTotalMoves3;

    internal static PieceMoveSet[] RookMoves4;

    internal static byte[] RookTotalMoves4;

    internal static PieceMoveSet[] KingMoves;

    internal static byte[] KingTotalMoves;

}

 

To make use of the above structs we will declare a static class called Piece Moves:

 

internal static class PieceMoves

To make life a bit easier, we will add a helper method called Position.  This method will accept a chess board column and row, and return a single byte representing the chess board position.  Usually we would not want to use a method like this because it will slow things down.  However this method is only used when the Chess Engine starts when super fast performance is not really all that necessary.

 

private static byte Position(byte col, byte row)

{

    return (byte)(col + (row * 8));

}

 

Initiate Chess Piece Motion Class is called only once in the Chess Engine Constructor.  It will construct all of the arrays and call the methods responsible for populating the Move Set arrays will all of the moves for each position on the board for each chess piece.

 

internal static void InitiateChessPieceMotion()

{

    MoveArrays.WhitePawnMoves = new PieceMoveSet[64];

    MoveArrays.WhitePawnTotalMoves = new byte[64];

 

    MoveArrays.BlackPawnMoves = new PieceMoveSet[64];

    MoveArrays.BlackPawnTotalMoves = new byte[64];

    MoveArrays.KnightMoves = new PieceMoveSet[64];

    MoveArrays.KnightTotalMoves = new byte[64];

    MoveArrays.BishopMoves1 = new PieceMoveSet[64];

    MoveArrays.BishopTotalMoves1 = new byte[64];

    MoveArrays.BishopMoves2 = new PieceMoveSet[64];

    MoveArrays.BishopTotalMoves2 = new byte[64];

    MoveArrays.BishopMoves3 = new PieceMoveSet[64];

    MoveArrays.BishopTotalMoves3 = new byte[64];

    MoveArrays.BishopMoves4 = new PieceMoveSet[64];

    MoveArrays.BishopTotalMoves4 = new byte[64];

    MoveArrays.RookMoves1 = new PieceMoveSet[64];

    MoveArrays.RookTotalMoves1 = new byte[64];

    MoveArrays.RookMoves2 = new PieceMoveSet[64];

    MoveArrays.RookTotalMoves2 = new byte[64];

    MoveArrays.RookMoves3 = new PieceMoveSet[64];

    MoveArrays.RookTotalMoves3 = new byte[64];

    MoveArrays.RookMoves4 = new PieceMoveSet[64];

    MoveArrays.RookTotalMoves4 = new byte[64];

    MoveArrays.QueenMoves1 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves1 = new byte[64];

    MoveArrays.QueenMoves2 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves2 = new byte[64];

    MoveArrays.QueenMoves3 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves3 = new byte[64];

    MoveArrays.QueenMoves4 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves4 = new byte[64];

    MoveArrays.QueenMoves5 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves5 = new byte[64];

    MoveArrays.QueenMoves6 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves6 = new byte[64];

    MoveArrays.QueenMoves7 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves7 = new byte[64];

    MoveArrays.QueenMoves8 = new PieceMoveSet[64];

    MoveArrays.QueenTotalMoves8 = new byte[64];

    MoveArrays.KingMoves = new PieceMoveSet[64];

    MoveArrays.KingTotalMoves = new byte[64];

   

    SetMovesWhitePawn();

    SetMovesBlackPawn();

    SetMovesKnight();

    SetMovesBishop();

    SetMovesRook();

    SetMovesQueen();

    SetMovesKing();

}

 

Set Moves methods are responsible for populating the Move Arrays with the moves available for each chess piece from a given position.  I am not going to explain this much further.  These methods basically add some predetermined positions to the arrays defined above.  Again performance is not really all that key here, since these methods run only once when the Chess Engine starts.

 

private static void SetMovesBlackPawn()

{

    for (byte index = 8; index <= 55; index++)

    {

        var moveset = new PieceMoveSet(new List<byte>());

       

        byte x = (byte)(index % 8);

        byte y = (byte)((index / 8));

       

        //Diagonal Kill

        if (y < 7 && x < 7)

        {

            moveset.Moves.Add((byte)(index + 8 + 1));

            MoveArrays.BlackPawnTotalMoves[index]++;

        }

        if (x > 0 && y < 7)

        {

            moveset.Moves.Add((byte)(index + 8 - 1));

            MoveArrays.BlackPawnTotalMoves[index]++;

        }

       

        //One Forward

        moveset.Moves.Add((byte)(index + 8));

        MoveArrays.BlackPawnTotalMoves[index]++;

 

        //Starting Position we can jump 2_        if (y == 1)

        {

            moveset.Moves.Add((byte)(index + 16));

            MoveArrays.BlackPawnTotalMoves[index]++;

        }

        MoveArrays.BlackPawnMoves[index] = moveset;

    }

}

private static void SetMovesWhitePawn()

{

    for (byte index = 8; index <= 55; index++)

    {

        byte x = (byte)(index % 8);

        byte y = (byte)((index / 8));

        var moveset = new PieceMoveSet(new List<byte>());

      

        //Diagonal Kill_

        if (x < 7 && y > 0)

        {

            moveset.Moves.Add((byte)(index - 8 + 1));

            MoveArrays.WhitePawnTotalMoves[index]++;

        }

        if (x > 0 && y > 0)

        {

            moveset.Moves.Add((byte)(index - 8 - 1));

            MoveArrays.WhitePawnTotalMoves[index]++;

        }

        //One Forward_ 

        moveset.Moves.Add((byte)(index - 8));

        MoveArrays.WhitePawnTotalMoves[index]++;

        //Starting Position we can jump 2_

        if (y == 6)

        {

            moveset.Moves.Add((byte)(index - 16));

            MoveArrays.WhitePawnTotalMoves[index]++;

        }

        MoveArrays.WhitePawnMoves[index] = moveset;

    }

}

private static void SetMovesKnight()

{

    for (byte y = 0; y < 8; y++)

    {

        for (byte x = 0; x < 8; x++)

        {

            byte index = (byte)(y + (x * 8));

            var moveset = new PieceMoveSet(new List<byte>());

           

            byte move;

            if (y < 6 && x > 0)

            {

                move = Position((byte)(y + 2), (byte)(x - 1));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y > 1 && x < 7)

            {

                move = Position((byte)(y - 2), (byte)(x + 1));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y > 1 && x > 0)

            {

                move = Position((byte)(y - 2), (byte)(x - 1));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y < 6 && x < 7)

            {

                move = Position((byte)(y + 2), (byte)(x + 1));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y > 0 && x < 6)

            {

                move = Position((byte)(y - 1), (byte)(x + 2));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y < 7 && x > 1)

            {

                move = Position((byte)(y + 1), (byte)(x - 2));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            if (y > 0 && x > 1)

            {

                move = Position((byte)(y - 1), (byte)(x - 2));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

           

            if (y < 7 && x < 6)

            {

                move = Position((byte)(y + 1), (byte)(x + 2));

                if (move < 64)

                {

                    moveset.Moves.Add(move);

                    MoveArrays.KnightTotalMoves[index]++;

                }

            }

            MoveArrays.KnightMoves[index] = moveset;

        }

    }

}

private static void SetMovesBishop()

{

    for (byte y = 0; y < 8; y++)

    {

        for (byte x = 0; x < 8; x++)

        {

            byte index = (byte)(y + (x * 8));

            var moveset = new PieceMoveSet(new List<byte>());

            byte move;

            byte row = x;

            byte col = y;

            while (row < 7 && col < 7)

            {

                row++;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.BishopTotalMoves1[index]++;

            }

            MoveArrays.BishopMoves1[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row < 7 && col > 0)

            {

                row++;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.BishopTotalMoves2[index]++;

            }

            MoveArrays.BishopMoves2[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0 && col < 7)

            {

                row--;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.BishopTotalMoves3[index]++;

            }

            MoveArrays.BishopMoves3[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0 && col > 0)

            {

                row--;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.BishopTotalMoves4[index]++;

            }

            MoveArrays.BishopMoves4[index] = moveset;

        }

    }

}

private static void SetMovesRook()

{

    for (byte y = 0; y < 8; y++)

    {

        for (byte x = 0; x < 8; x++)

        {

            byte index = (byte)(y + (x * 8));

            var moveset = new PieceMoveSet(new List<byte>());

            byte move;

            byte row = x;

            byte col = y;

            while (row < 7)

            {

                row++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.RookTotalMoves1[index]++;

            }

            MoveArrays.RookMoves1[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0)

            {

                row--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.RookTotalMoves2[index]++;

            }

            MoveArrays.RookMoves2[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (col > 0)

            {

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.RookTotalMoves3[index]++;

            }

            MoveArrays.RookMoves3[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (col < 7)

            {

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.RookTotalMoves4[index]++;

            }

            MoveArrays.RookMoves4[index] = moveset;

        }

    }

}

private static void SetMovesQueen()

{

    for (byte y = 0; y < 8; y++)

    {

        for (byte x = 0; x < 8; x++)

        {

            byte index = (byte)(y + (x * 8));

            var moveset = new PieceMoveSet(new List<byte>());

            byte move;

            byte row = x;

            byte col = y;

            while (row < 7)

            {

                row++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves1[index]++;

            }

            MoveArrays.QueenMoves1[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0)

            {

                row--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves2[index]++;

            }

            MoveArrays.QueenMoves2[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (col > 0)

            {

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves3[index]++;

            }

            MoveArrays.QueenMoves3[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (col < 7)

            {

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves4[index]++;

            }

            MoveArrays.QueenMoves4[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row < 7 && col < 7)

            {

                row++;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves5[index]++;

            }

            MoveArrays.QueenMoves5[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row < 7 && col > 0)

            {

                row++;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves6[index]++;

            }

            MoveArrays.QueenMoves6[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0 && col < 7)

            {

                row--;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves7[index]++;

            }

            MoveArrays.QueenMoves7[index] = moveset;

            moveset = new PieceMoveSet(new List<byte>());

            row = x;

            col = y;

            while (row > 0 && col > 0)

            {

                row--;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.QueenTotalMoves8[index]++;

            }

            MoveArrays.QueenMoves8[index] = moveset;

        }

    }

}

private static void SetMovesKing()

{

    for (byte y = 0; y < 8; y++)

    {

        for (byte x = 0; x < 8; x++)

        {

            byte index = (byte)(y + (x * 8));

            var moveset = new PieceMoveSet(new List<byte>());

            byte move;

            byte row = x;

            byte col = y;

            if (row < 7)

            {

                row++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (row > 0)

            {

                row--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (col > 0)

            {

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (col < 7)

            {

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (row < 7 && col < 7)

            {

                row++;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (row < 7 && col > 0)

            {

                row++;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            row = x;

            col = y;

            if (row > 0 && col < 7)

            {

                row--;

                col++;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

 

            row = x;

            col = y;

            if (row > 0 && col > 0)

            {

                row--;

                col--;

                move = Position(col, row);

                moveset.Moves.Add(move);

                MoveArrays.KingTotalMoves[index]++;

            }

            MoveArrays.KingMoves[index] = moveset;

        }

    }

}

 

This concludes the Chess Piece Moves class. 

 

 

Chess Piece Valid Moves

 

Originally the code in this post was part of the Chess Piece Motion class.  However since I posted the original code I have divided that class into 2 separate classes.  Chess Piece Moves and Chess Piece Valid moves which is discussed here.

 

This class will be responsible for dynamically figuring out only the valid moves for the current chess board and assigning only the valid moves to each chess piece.  This class will also figure out what pieces are attacking each other, is the king in check, has en passant occurred and assign the information to each piece for the purpose of score evaluation.

 

The Chess Piece Valid Moves class will be declared as follows:

 

internal static class PieceValidMoves

 

To help us understand what is board squares are being attacked we will defina 2 arrays.  One for storing board squares attacked by White, and one for Black.  These arrays are crucial in figuring out things like valid moves for a king, since kings cannot move onto a square that is currently attacked by an opponent.

 

 

internal static bool[] BlackAttackBoard;

internal static bool[] WhiteAttackBoard;

 

Furthermore we can't correctly check for the kings valid moves until we examine all other chess pieces.  This is due to the fact that we won't know if the chess board square is attacked if we don't look at every single chess piece first.  For this reason when we come across a king during our analysis, we don't analyze its possible moves but rather store its position for later analysis.  The following 2 variables are used to store that information.

 

 

private static byte BlackKingPosition;

private static byte WhiteKingPosition;

 

The Analyze Move method will perform a deep analysis or examination of the move itself and its effect on the chess board.  For example this method will record an En Passant scenario as well as recording Checks and Kills.  The Analyze Move method will return true if the move is considered not blocked (not resulting in a kill or blocked by another chess piece of the same color).  Similarly it will return false if the move is blocked and movement cannot continue past this position.  This is very important since this return value will be used to end a loop of moves in a certain direction.  This method is called for all chess pieces other than pawns and kings.

 

private static bool AnalyzeMove(Board board, byte dstPos, Piece pcMoving)

{

    //If I am not a pawn everywhere I move I can attack

    if (pcMoving.PieceColor == ChessPieceColor.White)

    {

        WhiteAttackBoard[dstPos] = true;

    }

    else

    {

        BlackAttackBoard[dstPos] = true;

    }

 

    //If there no piece there I can potentialy kill just add the move and exit_

    if (board.Squares[dstPos].Piece == null)

    {

        pcMoving.ValidMoves.Push(dstPos);

        return true;

    }

    Piece pcAttacked = board.Squares[dstPos].Piece;

    //if that piece is a different color_

    if (pcAttacked.PieceColor != pcMoving.PieceColor)

    {

        pcAttacked.AttackedValue += pcMoving.PieceActionValue;

        //If this is a king set it in check 

        if (pcAttacked.PieceType == ChessPieceType.King)

        {

            if (pcAttacked.PieceColor == ChessPieceColor.Black)

            {

                board.BlackCheck = true;

            }

            else

            {

                board.WhiteCheck = true;

            }

        }

        else

        {

            //Add this as a valid move_

            pcMoving.ValidMoves.Push(dstPos);

        }

 

        //We don't continue movement past this piece_

        return false;

    }

    //Same Color I am defending_

    pcAttacked.DefendedValue += pcMoving.PieceActionValue;

    //Since this piece is of my kind I can't move there_

    return false;

}

 

Pawns behave slightly differently than regular pieces in that not all of their moves can result in a kill.  A move straight ahead cannon result in a kill while a diagonal move can.  For this reason, there are two separate methods to analyze pawn moves.   One Parent that loops through all available pawn moves and one child that analyzes each move at a time.

 

Parent:

 

private static void CheckValidMovesPawn(List<byte> moves, Piece pcMoving,

          byte srcPosition,

          Board board, byte count)

{

 for (byte i = 0; i < count; i++)

 {

  byte dstPos = moves[i];

 

  if (dstPos%8 != srcPosition%8)

  {

   //If there is a piece there I can potentialy kill_

   AnalyzeMovePawn(board, dstPos, pcMoving);

   if (pcMoving.PieceColor == ChessPieceColor.White)

   {

    WhiteAttackBoard[dstPos] = true;

   }

   else

   {

    BlackAttackBoard[dstPos] = true;

   }

  }

   // if there is something if front pawns can't move there_

  else if (board.Squares[dstPos].Piece != null)

  {

   return;

  }

  //if there is nothing in front of me (blocked == false)_

  else

  {

   pcMoving.ValidMoves.Push(dstPos);

  }

 }

}

 

Child:

 

private static void AnalyzeMovePawn(Board board, byte dstPos, Piece pcMoving)

{

    //Because Pawns only kill diagonaly we handle the En Passant scenario specialy

    if (board.EnPassantPosition > 0)

    {

        if (pcMoving.PieceColor != board.EnPassantColor)

        {

            if (board.EnPassantPosition == dstPos)

            {

                //We have an En Passant Possible

                pcMoving.ValidMoves.Push(dstPos);

 

                if (pcMoving.PieceColor == ChessPieceColor.White)

                {

                    WhiteAttackBoard[dstPos] = true;

                }

                else

                {

                    BlackAttackBoard[dstPos] = true;

                }

            }

        }

    }

    Piece pcAttacked = board.Squares[dstPos].Piece;

    //If there no piece there I can potentialy kill_

    if (pcAttacked == null)

        return;

    //Regardless of what is there I am attacking this square_

    if (pcMoving.PieceColor == ChessPieceColor.White)

    {

        WhiteAttackBoard[dstPos] = true;

        //if that piece is the same color_

        if (pcAttacked.PieceColor == pcMoving.PieceColor)

        {

            pcAttacked.DefendedValue += pcMoving.PieceActionValue;

            return;

        }

        //else piece is different so we are attacking_

        pcAttacked.AttackedValue += pcMoving.PieceActionValue;

        //If this is a king set it in check 

        if (pcAttacked.PieceType == ChessPieceType.King)

        {

            board.BlackCheck = true;

        }

        else

        {

            //Add this as a valid move_

            pcMoving.ValidMoves.Push(dstPos);

        }

    }

    else

    {

        BlackAttackBoard[dstPos] = true;

        //if that piece is the same color_

        if (pcAttacked.PieceColor == pcMoving.PieceColor)

        {

            return;

        }

        //If this is a king set it in check 

        if (pcAttacked.PieceType == ChessPieceType.King)

        {

            board.WhiteCheck = true;

        }

        else

        {

            //Add this as a valid move_

            pcMoving.ValidMoves.Push(dstPos);

        }

    }

    return;

}

 

Check Valid Moves King Castle Method handles the complicated castling scenarios by examining the chess board squares between the king and the rook to make sure they are empty, not attacked and that the rook and king are both in their starting positions.

 

private static void GenerateValidMovesKingCastle(Board board, Piece king)

{

 if (king == null)

 {

  return;

 }

 

 if (king.Moved)

 {

  return;

 }

 if (king.PieceColor == ChessPieceColor.White &&

  board.WhiteCastled)

 {

  return;

 }

 if (king.PieceColor == ChessPieceColor.Black &&

  board.BlackCastled)

 {

  return;

 }

 if (king.PieceColor == ChessPieceColor.Black &&

  board.BlackCheck)

 {

  return;

 }

 if (king.PieceColor == ChessPieceColor.White &&

  board.WhiteCheck)

 {

  return;

 }

 

 //This code will add the castleling move to the pieces available moves_

 if (king.PieceColor == ChessPieceColor.White)

 {

  if (board.WhiteCheck)

  {

   return;

  }

  if (board.Squares[63].Piece != null)

  {

   //Check if the Right Rook is still in the correct position_

   if (board.Squares[63].Piece.PieceType == ChessPieceType.Rook)

   {

    if (board.Squares[63].Piece.PieceColor == king.PieceColor)

    {

     //Move one column to right see if its empty_

     if (board.Squares[62].Piece == null)

     {

      if (board.Squares[61].Piece == null)

      {

       if (BlackAttackBoard[61] == false &&

        BlackAttackBoard[62] == false)

       {

        //Ok looks like move is valid lets add it_

        king.ValidMoves.Push(62);

        WhiteAttackBoard[62] = true;

       }

      }

     }

    }

   }

  }

  if (board.Squares[56].Piece != null)

  {

   //Check if the Left Rook is still in the correct position_

   if (board.Squares[56].Piece.PieceType == ChessPieceType.Rook)

   {

    if (board.Squares[56].Piece.PieceColor == king.PieceColor)

    {

     //Move one column to right see if its empty_

     if (board.Squares[57].Piece == null)

     {

      if (board.Squares[58].Piece == null)

      {

       if (board.Squares[59].Piece == null)

       {

        if (BlackAttackBoard[58] == false &&

         BlackAttackBoard[59] == false)

        {

         //Ok looks like move is valid lets add it_

         king.ValidMoves.Push(58);

         WhiteAttackBoard[58] = true;

        }

       }

      }

     }

    }

   }

  }

 }

 else if (king.PieceColor == ChessPieceColor.Black)

 {

  if (board.BlackCheck)

  {

   return;

  }

  //There are two ways to castle, scenario 1:_ 

  if (board.Squares[7].Piece != null)

  {

   //Check if the Right Rook is still in the correct position_

   if (board.Squares[7].Piece.PieceType == ChessPieceType.Rook

    && !board.Squares[7].Piece.Moved)

   {

    if (board.Squares[7].Piece.PieceColor == king.PieceColor)

    {

     //Move one column to right see if its empty

     if (board.Squares[6].Piece == null)

     {

      if (board.Squares[5].Piece == null)

      {

       if (WhiteAttackBoard[5] == false && WhiteAttackBoard[6] == false)

       {

        //Ok looks like move is valid lets add it_

        king.ValidMoves.Push(6);

        BlackAttackBoard[6] = true;

       }

      }

     }

    }

   }

  }

  //There are two ways to castle, scenario 2:_

  if (board.Squares[0].Piece != null)

  {

   //Check if the Left Rook is still in the correct position_

   if (board.Squares[0].Piece.PieceType == ChessPieceType.Rook &&

    !board.Squares[0].Piece.Moved)

   {

    if (board.Squares[0].Piece.PieceColor ==

     king.PieceColor)

    {

     //Move one column to right see if its empty_

     if (board.Squares[1].Piece == null)

     {

      if (board.Squares[2].Piece == null)

      {

       if (board.Squares[3].Piece == null)

       {

        if (WhiteAttackBoard[2] == false &&

         WhiteAttackBoard[3] == false)

        {

         //Ok looks like move is valid lets add it_

         king.ValidMoves.Push(2);

         BlackAttackBoard[2] = true;

        }

       }

      }

     }

    }

   }

  }

 }

}

 

The last method in this class is the only non-private method in this listing.  The Generate Valid Moves method will be called directly by the chess engine to create valid moves for each chess board it examines.  This method will loop through all chess pieces on the chess board and examine each possible move based on the chess piece’s position.  Please note that we have already calculated each pieces move in the Chess Piece Moves class for every single position on the chess board.  We now just have to figure out which one of those moves is valid and what their results will be.  While we are looping through all of the chess pieces we also collect some information such as how many pawns are in each file, how many pawns are isolated.  At the end of this method we will sum up this information and store it on the Chess Board.

 

internal static void GenerateValidMoves(Board board)

{

 // Reset Board

 board.BlackCheck = false;

 board.WhiteCheck = false;

 

 WhiteAttackBoard = new bool[64];

 BlackAttackBoard = new bool[64];

 //Generate Moves_

 for (byte x = 0; x < 64; x++)

 {

  Square sqr = board.Squares[x];

  if (sqr.Piece == null)

   continue;

  sqr.Piece.ValidMoves = new Stack<byte>(sqr.Piece.LastValidMoveCount);

  switch (sqr.Piece.PieceType)

  {

   case ChessPieceType.Pawn:

    {

     if (sqr.Piece.PieceColor == ChessPieceColor.White)

     {

      CheckValidMovesPawn(MoveArrays.WhitePawnMoves[x].Moves, sqr.Piece, x,

           board,

           MoveArrays.WhitePawnTotalMoves[x]);

      break;

     }

     if (sqr.Piece.PieceColor == ChessPieceColor.Black)

     {

      CheckValidMovesPawn(MoveArrays.BlackPawnMoves[x].Moves, sqr.Piece, x,

           board,

           MoveArrays.BlackPawnTotalMoves[x]);

      break;

     }

     break;

    }

   case ChessPieceType.Knight:

    {

     for (byte i = 0; i < MoveArrays.KnightTotalMoves[x]; i++)

     {

      AnalyzeMove(board, MoveArrays.KnightMoves[x].Moves[i], sqr.Piece);

     }

     break;

    }

   case ChessPieceType.Bishop:

    {

     for (byte i = 0; i < MoveArrays.BishopTotalMoves1[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.BishopMoves1[x].Moves[i],

          sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.BishopTotalMoves2[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.BishopMoves2[x].Moves[i],

          sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.BishopTotalMoves3[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.BishopMoves3[x].Moves[i],

          sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.BishopTotalMoves4[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.BishopMoves4[x].Moves[i],

          sqr.Piece) ==

       false)

      {

       break;

      }

     }

     break;

    }

   case ChessPieceType.Rook:

    {

     for (byte i = 0; i < MoveArrays.RookTotalMoves1[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.RookMoves1[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.RookTotalMoves2[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.RookMoves2[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.RookTotalMoves3[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.RookMoves3[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.RookTotalMoves4[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.RookMoves4[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     break;

    }

   case ChessPieceType.Queen:

    {

     for (byte i = 0; i < MoveArrays.QueenTotalMoves1[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves1[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves2[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves2[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves3[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves3[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves4[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves4[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves5[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves5[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves6[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves6[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves7[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves7[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     for (byte i = 0; i < MoveArrays.QueenTotalMoves8[x]; i++)

     {

      if (

       AnalyzeMove(board, MoveArrays.QueenMoves8[x].Moves[i], sqr.Piece) ==

       false)

      {

       break;

      }

     }

     break;

    }

   case ChessPieceType.King:

    {

     if (sqr.Piece.PieceColor == ChessPieceColor.White)

     {

      WhiteKingPosition = x;

     }

     else

     {

      BlackKingPosition = x;

     }

     break;

    }

  }

 }

 

 if (board.WhoseMove == ChessPieceColor.White)

 {

  GenerateValidMovesKing(board.Squares[BlackKingPosition].Piece, board,

          BlackKingPosition);

  GenerateValidMovesKing(board.Squares[WhiteKingPosition].Piece, board,

          WhiteKingPosition);

 }

 else

 {

  GenerateValidMovesKing(board.Squares[WhiteKingPosition].Piece, board,

          WhiteKingPosition);

  GenerateValidMovesKing(board.Squares[BlackKingPosition].Piece, board,

          BlackKingPosition);

 }

 

 //Now that all the pieces were examined we know if the king is in check_

 GenerateValidMovesKingCastle(board, board.Squares[WhiteKingPosition].Piece);

 GenerateValidMovesKingCastle(board, board.Squares[BlackKingPosition].Piece);

}

 

This concludes the Chess Piece Valid Moves class. 

 

Move Content

 

In our Chess Engine we will need to describe movement as it occurs.  This will be useful to keep track move history, the best move at each search level or even the result of our Alpha Beta Search.

The Move Content class has 2 major components.  The first component describes the moving chess piece(s). The second component describes the chess piece taken or captured during the move. 

These two components described as 2 structs:

 

public struct PieceMoving

{

 public byte DstPosition;

 public bool Moved;

 public ChessPieceColor PieceColor;

 public ChessPieceType PieceType;

 public byte SrcPosition;

 

 public PieceMoving(ChessPieceColor pieceColor, ChessPieceType pieceType, bool moved,

        byte srcPosition, byte dstPosition)

 {

  PieceColor = pieceColor;

  PieceType = pieceType;

  SrcPosition = srcPosition;

  DstPosition = dstPosition;

  Moved = moved;

 }

 public PieceMoving(PieceMoving pieceMoving)

 {

  PieceColor = pieceMoving.PieceColor;

  PieceType = pieceMoving.PieceType;

  SrcPosition = pieceMoving.SrcPosition;

  DstPosition = pieceMoving.DstPosition;

  Moved = pieceMoving.Moved;

 }

 public PieceMoving(ChessPieceType pieceType)

 {

  PieceType = pieceType;

  PieceColor = ChessPieceColor.White;

  SrcPosition = 0;

  DstPosition = 0;

  Moved = false;

 }

}

 

 

 

public struct PieceTaken

{

 public bool Moved;

 public ChessPieceColor PieceColor;

 public ChessPieceType PieceType;

 public byte Position;

 

 public PieceTaken(ChessPieceColor pieceColor, ChessPieceType pieceType, bool moved,

       byte position)

 {

  PieceColor = pieceColor;

  PieceType = pieceType;

  Position = position;

  Moved = moved;

 }

 public PieceTaken(ChessPieceType pieceType)

 {

  PieceColor = ChessPieceColor.White;

  PieceType = pieceType;

  Position = 0;

  Moved = false;

 }

}

 

The Move Content class itself makes use of the above 2 structs by declaring them into 3 fields:

 

Š      PieceMoving MovingPiecePrimary – The primary piece that has moved.

Š      PieceMoving MovingPieceSecondary; - The secondary piece that has moved.  This is usually null unless a king has castled.  In this case the primary Piece would be the king and the secondary piece would be the rook.

Š      PieceTaken TakenPiece – The chess piece that was capture or taken during the move.

 

The other fields like Score, Pawn Promoted and En Passant Occurred are self explanatory.  However the last method ToString requires a bit of an explanation.

The Move Content class will be used to generate Portable Game Notation (PGN) string of the game.  For this reason I overwrote the ToString() method for the class so that it will return a portion of the PGN string for the move that has occurred.

 

public new string ToString()

{

    string value = "";

 

    var srcCol = (byte) (MovingPiecePrimary.SrcPosition%8);

    var srcRow = (byte)(8 - (MovingPiecePrimary.SrcPosition / 8));

    var dstCol = (byte) (MovingPiecePrimary.DstPosition%8);

    var dstRow = (byte) (8 - (MovingPiecePrimary.DstPosition/8));

    if (MovingPieceSecondary.PieceType == ChessPieceType.Rook)

    {

        if (MovingPieceSecondary.PieceColor == ChessPieceColor.Black)

        {

            if (MovingPieceSecondary.SrcPosition == 7)

            {

                value += "O-O";

            }

            else if (MovingPieceSecondary.SrcPosition == 0)

            {

                value += "O-O-O";

            }

        }

        else if (MovingPieceSecondary.PieceColor == ChessPieceColor.White)

        {

            if (MovingPieceSecondary.SrcPosition == 63)

            {

                value += "O-O";

            }

            else if (MovingPieceSecondary.SrcPosition == 56)

            {

                value += "O-O-O";

            }

        }

    }

    else

    {

        value += GetPgnMove(MovingPiecePrimary.PieceType);

        switch (MovingPiecePrimary.PieceType)

        {

            case ChessPieceType.Knight:

                value += GetColumnFromInt(srcCol + 1);

                value += srcRow;

                break;

            case ChessPieceType.Rook:

                value += GetColumnFromInt(srcCol + 1);

                value += srcRow;

                break;

            case ChessPieceType.Pawn:

                if (srcCol != dstCol)

                {

                    value += GetColumnFromInt(srcCol + 1);

                }

                break;

        }

        if (TakenPiece.PieceType != ChessPieceType.None)

        {

            value += "x";

        }

        value += GetColumnFromInt(dstCol + 1);

        value += dstRow;

        if (PawnPromoted)

        {

            value += "=Q";

        }

    }

    return value;

}

 

Notice: Since the Move Content class and all its components will be used to display information outside of the chess engine like the user interface all the Move Content components and the class itself were declared as public. 

The above ToString() method requires a few helper methods that convert objects to strings:

 

private static string GetColumnFromInt(int column)

{

    switch (column)

    {

        case 1:

            return "a";

        case 2:

            return "b";

        case 3:

            return "c";

        case 4:

            return "d";

        case 5:

            return "e";

        case 6:

            return "f";

        case 7:

            return "g";

        case 8:

            return "h";

        default:

            return "Unknown";

    }

}

 

private static string GetPgnMove(ChessPieceType pieceType)

{

    switch (pieceType)

    {

        case ChessPieceType.Bishop:

            return "B";

        case ChessPieceType.King:

            return "K";

        case ChessPieceType.Knight:

            return "N";

        case ChessPieceType.Queen:

            return "Q";

        case ChessPieceType.Rook:

            return "R";

        default:

            return "";

    }

}

 

This concludes the Move Content class.

 

Starting the chess engine

 

Bringing it all together, starting the chess engine.

This post will bring all of the previous sections together in the discussion of the chess engine class.  At this time I will assume that you have already read the previous sections related to Chess Board Square, Chess Board and Chess Piece Representation as well as the Chess Piece Moves and Chess Piece Valid Moves.  Today I will not provide a complete chess engine listing because we have not yet discussed move searching and Chess Board Evaluation.  However at the end of this section we will have a basic chess engine that can:

 

1.     Track chess piece locations on the chess board

2.     Provide a list of valid moves for each chess piece, including en passant and castling

3.     Track whose move it is.

4.     Track move history.

5.     Setup a starting chess board.

 

This in theory once we create a graphical user interface this skeleton chess engine would allow you to play a two human player chess game.

Chess Engine class is declared as public sealed

 

 

public sealed class Engine

 

Chess Engine class will contain 3 members that will represent the current chess board, previous chess board whose move it currently is.  Previous Chess Board will store the last chess board prior to the last move.  Please notice that the Previous Chess Board member will potentially give us easy undo functionality.

 

 

internal Board ChessBoard;

internal Board PreviousChessBoard;

 

public ChessPieceColor WhoseMove

{

    get { return ChessBoard.WhoseMove; }

    set { ChessBoard.WhoseMove = value; }

}

 

The constructor is a bit complicated as it performs the following actions:

      Instantiate above members and set the initial move to White

      Initiate Chess Piece Motion (Pre-calculate all possible moves for all pieces on all chess board squares possible)

      Assign Chess pieces to the chess board in the starting position of a standard chess game.

      Generate valid moves for the chess pieces in their current positions.

 

public Engine()

{

    ChessBoard = new Board();

    MoveHistory = new Stack<MoveContent>();

 

    RegisterStartingBoard();

    ChessBoard.WhoseMove = ChessPieceColor.White;   

   

    ChessPieceMoves.InitiateChessPieceMotion();

    PieceValidMoves.GenerateValidMoves(ChessBoard);

}

 

Notice the Constructor uses a method called Register Starting Board.  This method constructs all the chess pieces necessary for the starting chess board and registers them with the chess board object.

In the above code a helper method was used called Register Piece. This method assigns the created chess piece to the desired location on the chess board.

 

 

private void RegisterPiece(byte boardColumn, byte boardRow, ChessPiece Piece)

{

    byte position = (byte)(boardColumn + (boardRow * 8));    

 

    ChessBoard.Squares[position].Piece = Piece;

    return;

}

 

The remaining method that I will indroduce today is the MovePiece method.  This code will allow you to move chess pieces around the chess board.  The method will return true if the move was successful and false if the move was not valid.

 

public bool MovePiece(byte sourceColumn, byte sourceRow,

         byte destinationColumn, byte destinationRow)

{

 byte srcPosition = (byte)(sourceColumn + (sourceRow * 8));

 byte dstPosition = (byte)(destinationColumn + (destinationRow * 8));

 

 Piece Piece = ChessBoard.Squares[srcPosition].Piece;

 PreviousChessBoard = new Board(ChessBoard);

 

 Board.MovePiece(ChessBoard, srcPosition, dstPosition, PromoteToPieceType);

 PieceValidMoves.GenerateValidMoves(ChessBoard);

 

 //If there is a check in place, check if this is still true;_ 

 if (Piece.PieceColor == ChessPieceColor.White)

 {

  if (ChessBoard.WhiteCheck)

  {

   //Invalid Move_

   ChessBoard = new Board(PreviousChessBoard);

   PieceValidMoves.GenerateValidMoves(ChessBoard);

   return false;

  }

 }

 else if (Piece.PieceColor == ChessPieceColor.Black)

 {

  if (ChessBoard.BlackCheck)

  {

   //Invalid Move_

   ChessBoard = new Board(PreviousChessBoard);

   PieceValidMoves.GenerateValidMoves(ChessBoard);

   return false;

  }

 }

 MoveHistory.Push(ChessBoard.LastMove);

 return true;

}

 

Generating a Starting Chess Position

 

At this point we it would be nice if we were able to add some chess pieces to our chess board.  Originally I wrote a method that would declare 32 chess pieces and assign them to the correct chess board square.  However eventually I wanted to implement FEN notation into my chess engine.  FEN notation is an easy way to describe chess board positions.  It is somewhat of a standard in computer chess circles.  Hence once I implemented a method that can read a FEN string and setup the chess board based on the FEN string values, I had an easy way to create my starting chess position. 

 

ChessBoard = new Board("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");

 

The full source code for the FEN methods can be found on the FEN Section

 

To summarize, our chess engine class contains the current chess board (Board ChessBoard) as well as a copy of the chess board as it looked prior to the last move (Board PreviousChessBoard).  The Chess Engine knows whose move it currently is (ChessPiece.ChessPieceColor WhoseMove).  The constructor of the Chess Engine creates all the chess pieces required for a standard chess game and registers them with the chess board using the Register Piece method.  The chess engine constructor will also Initiate Chess Piece Motion and Assign valid moves to each chess piece based on the pieces current position and the board layout.  Moving chess pieces around the board is handled by the MovePiece method.

 

Piece Square Table

 

Today I want to discuss the Piece Square Table

Originally the piece square tables were declared in a separate class that was used by the Evaluation function.  However I found that it is more efficient to save the extra method calls and perform the piece square table lookups directly in the evaluation function. 

 

Hence I have modified this post to simply describe the piece square table and the logic behind the numbers assigned to each position.

 

As I have already stated the piece square tables are used chess board Evaluation class to score points based on the current position of the chess piece.  The main idea behind this code is that certain positions for chess pieces are better than others.  Fox example it is better for knights to stay away from the edge of the board.  Pawns should control the center of the board and advance forward. 

I have decided not to create a piece square table for every single chess piece.  I have omitted Queens and Rooks.  I could not find good enough positional tactical advantages for Rooks and Queens to warrant the performance cost of a table lookup for each of their positions.

 

Here are the piece square tables used by my chess engine:

 

Pawns are encouraged to stay in the center and advance forward:

 

private static readonly short[] PawnTable = new short[]

{

     0,  0,  0,  0,  0,  0,  0,  0,

    50, 50, 50, 50, 50, 50, 50, 50,

    10, 10, 20, 30, 30, 20, 10, 10,

     5,  5, 10, 27, 27, 10,  5,  5,

     0,  0,  0, 25, 25,  0,  0,  0,

     5, -5,-10,  0,  0,-10, -5,  5,

     5, 10, 10,-25,-25, 10, 10,  5,

     0,  0,  0,  0,  0,  0,  0,  0

};

 

Knights are encouraged to control the center and stay away from edges to increase mobility:

 

private static readonly short[] KnightTable = new short[]

{

    -50,-40,-30,-30,-30,-30,-40,-50,

    -40,-20,  0,  0,  0,  0,-20,-40,

    -30,  0, 10, 15, 15, 10,  0,-30,

    -30,  5, 15, 20, 20, 15,  5,-30,

    -30,  0, 15, 20, 20, 15,  0,-30,

    -30,  5, 10, 15, 15, 10,  5,-30,

    -40,-20,  0,  5,  5,  0,-20,-40,

    -50,-40,-20,-30,-30,-20,-40,-50,

};

 

Bishops are also encouraged to control the center and stay away from edges and corners:

 

private static readonly short[] BishopTable = new short[]

{

    -20,-10,-10,-10,-10,-10,-10,-20,

    -10,  0,  0,  0,  0,  0,  0,-10,

    -10,  0,  5, 10, 10,  5,  0,-10,

    -10,  5,  5, 10, 10,  5,  5,-10,

    -10,  0, 10, 10, 10, 10,  0,-10,

    -10, 10, 10, 10, 10, 10, 10,-10,

    -10,  5,  0,  0,  0,  0,  5,-10,

    -20,-10,-40,-10,-10,-40,-10,-20,

};

 

Kings have 2 piece square tables, one for the end game and one for the middle game.  During the middle game kings are encouraged to stay in the corners, while in the end game kings are encouraged to move towards the center.

 

private static readonly short[] KingTable = new short[]

{

  -30, -40, -40, -50, -50, -40, -40, -30,

  -30, -40, -40, -50, -50, -40, -40, -30,

  -30, -40, -40, -50, -50, -40, -40, -30,

  -30, -40, -40, -50, -50, -40, -40, -30,

  -20, -30, -30, -40, -40, -30, -30, -20,

  -10, -20, -20, -20, -20, -20, -20, -10,

   20,  20,   0,   0,   0,   0,  20,  20,

   20,  30,  10,   0,   0,  10,  30,  20

};

 

private static readonly short[] KingTableEndGame = new short[]

{

    -50,-40,-30,-20,-20,-30,-40,-50,

    -30,-20,-10,  0,  0,-10,-20,-30,

    -30,-10, 20, 30, 30, 20,-10,-30,

    -30,-10, 30, 40, 40, 30,-10,-30,

    -30,-10, 30, 40, 40, 30,-10,-30,

    -30,-10, 20, 30, 30, 20,-10,-30,

    -30,-30,  0,  0,  0,  0,-30,-30,

    -50,-30,-30,-30,-30,-30,-30,-50

};

 

The above tables are used during the evaluation method to lookup the positional values to help calculate the chess board score.

Here is an example of how the above tables would be used to lookup a value for a white pawn position:

 

score += PawnTable[position];

 

And here is the code to perform the same lookup for a black pawn:

 

byte index = (byte)(((byte)(position + 56)) - (byte)((byte)(position / 8) * 16));

 

score += PawnTable[index];

 

 

Chess Board Evaluation

 

From what information I could gather on the internet, it seems that most experts agree that the evaluation function of a chess engine has the greatest capability to dictate the strength of your chess game. Rybka, currently considered to be the top computer chess engine in the world, is not famous for its search speed but rather for its advanced chess board evaluation written by an international chess master.  Furthermore the evaluation function can make your move searching faster by allowing your chess engine to search better moves first.

 

Unfortunately for you Rybka’s evaluation function is not available.  To make things worse I am not considered by anyone to be a chess master.

 

Chess Piece Evaluation

 

As seen in the Chess Piece Class, the following values are assigned to chess pieces:

 

Pawn     100_   

Knight   320_   

Bishop   325_   

Rook     500_   

Queen    975_   

King     32767

 

About the numbers.

 

Writing your chess board evaluation method, think about the numbers as percentages of a pawn.  In my chess engine a pawn is worth 100 points.  If you award 10 points to a tactical position you are telling the chess engine that this position is worth 1/10th of a pawn.  The problem can arise when a move combines several tactical advantages for the moving side and several tactical penalties for the opponent.  This can result in unnecessary pawn sacrifice for set of minor tactical advantages.  When writing your evaluation function always keep this in mind.

 

The Chess Board Score is represented by a signed integer.  The higher the score the better it is for White.  The lower the score the better it is for black.  Using a single integer makes everything a bit faster since I can always just reference one variable.

 

For example if the value of a single pawn is 100 points and there was only one single black pawn on the chess board the score would be -100.  If there were two pawns, one white and one black the score would be 0.  If white had 2 pawns and black 1 pawn the score would be 100. 

 

On to the code

 

Chess Bin Board evaluation is implemented as a static class with two static methods. 

 

internal static class Evaluation

 

We first declare our Piece Square Tables discussed in the previous post:

 

 

private static readonly short[] PawnTable = new short[]

{

  0,  0,  0,  0,  0,  0,  0,  0,

 50, 50, 50, 50, 50, 50, 50, 50,

 10, 10, 20, 30, 30, 20, 10, 10,

  5,  5, 10, 27, 27, 10,  5,  5,

  0,  0,  0, 25, 25,  0,  0,  0,

  5, -5,-10,  0,  0,-10, -5,  5,

  5, 10, 10,-25,-25, 10, 10,  5,

  0,  0,  0,  0,  0,  0,  0,  0

};

 

private static readonly short[] KnightTable = new short[]

{

 -50,-40,-30,-30,-30,-30,-40,-50,

 -40,-20,  0,  0,  0,  0,-20,-40,

 -30,  0, 10, 15, 15, 10,  0,-30,

 -30,  5, 15, 20, 20, 15,  5,-30,

 -30,  0, 15, 20, 20, 15,  0,-30,

 -30,  5, 10, 15, 15, 10,  5,-30,

 -40,-20,  0,  5,  5,  0,-20,-40,

 -50,-40,-20,-30,-30,-20,-40,-50,

};

private static readonly short[] BishopTable = new short[]

{

 -20,-10,-10,-10,-10,-10,-10,-20,

 -10,  0,  0,  0,  0,  0,  0,-10,

 -10,  0,  5, 10, 10,  5,  0,-10,

 -10,  5,  5, 10, 10,  5,  5,-10,

 -10,  0, 10, 10, 10, 10,  0,-10,

 -10, 10, 10, 10, 10, 10, 10,-10,

 -10,  5,  0,  0,  0,  0,  5,-10,

 -20,-10,-40,-10,-10,-40,-10,-20,

};

private static readonly