Chess engine code – laying the groundwork

This article is part of a series – the contents page is here.

In the last article we covered the very basic theory of a chess engine.  Time to write some code!  Before we can get to the interesting stuff we need to lay the groundwork with a few elementary types and enums.  You can see all of these in the ChessElements.ts file.  The main ones are PieceType, BoardSquare, Board and GameMove.

BoardResources

Often when we build a new system, an important design goal is extensibility.  We want to avoid code that depends on the intimate details of the requirements, because we know that there is a high chance of those details changing.  For this reason “premature optimization” is usually considered a bad idea.  The small performance improvement you get is often completely negated by the extra work needed to maintain the code when the requirements change.

Well, our chess-playing system is not like that at all.  The rules of the game are set in stone.  We are absolutely justified in assuming that the board will always be 8 by 8, for example.  On the other hand, performance is our biggest enemy, since the search tree is so vast.  If we can shave a millisecond off the evaluation function by making intricate use of the fact that the number of pieces on the board can never increase then we should do it!

With this in mind we define the BoardResources class to hold a bunch of objects that act a bit like flyweights.  For example, we create 64 BoardSquare objects and place them in BoardResources.squares.  This gives us a quick, global, way for every board to refer to the object representing the e5 square.  The pieces array gives us the one-and-only object representing a white pawn and so on.

Board

The Board class represents a single position.  Walking the search tree means using moves to manipulate boards, so that manipulation is a performance critical task.

The Board class’s design has one key principle: Boards are immutable.  Applying a move to a board gives you a brand new board, which makes Board.applyMove() one of the most important methods in the code.

Immutable objects are great because they’re easy to reason about (they can’t change, after all).  But the price is that applying a move means cloning the Board to get a fresh copy that we can then update with the move.  To make the clone as fast as possible, Board stores its pieces in a one-dimensional array of numbers called squares.  Of course, in chess it’s much more natural to think of the squares as being a two-dimensional array, so there are helper functions to translate the square indexes (for example, to translate between “b2” and the index value 9).  Outside of the Board class most of the code doesn’t need to know about our one-dimensional indexes.

Board has one more vital property: the flag isWhiteToMove.  This is true when it is White’s turn to move and false when it is Black’s turn.  The last thing applyMove does is to flip this value.

MoveGenerator

The MoveGenerator class contains static functions that generate the pieces’ potential moves – the raw material for our search.  There’s one for each type of piece, for example here’s the signature for the knight-move function:

public static getPotentialKnightMoves(board: Chess.Board, fromSquare: Chess.BoardSquare, findKingCaptureOnly?: boolean): Chess.GameMove[] {
...
}

This function takes a Board and a square.  It starts by looking at Board.isWhiteToMove to find out who is moving.  It assumes that that square contains a knight of that colour!  The getPotentialMoves functions return all the legal moves that a piece could make from that square, with a few caveats:

  1. It doesn’t take checks into consideration.  So some of the moves that it generates might be illegal because they might put (or leave) the mover’s king in check.
  2. It includes ‘theoretical king captures’, where the moving piece captures the opponent’s king.  Such moves are of course invalid, but they are the key to identifying check situations.  These ‘moves’ are identified by the presence of the GameMove.isTheoreticalKingCapture flag.
  3. We want to know when a piece attacks an empty square (for positional evaluation purposes).  For most pieces we get this information from the potential moves, but pawns are a special case.  A list of legal pawn moves won’t tell us when a pawn attacks an empty square.  So the getPotentialPawnMoves function has an extra option to serve up ‘moves’ that are flagged as ‘pawn attacks’.

Notice the findKingCaptureOnly parameter.  If this is set to true then the function operates in a different mode, where it is simply trying to answer the question: are there any theoretical king captures?  Obviously in this mode the function runs more quickly.

Board.getPotentialMoves

The last building block that we need is to generate all the moves for a position.  The Board.getPotentialMoves function simply runs through all the pieces belonging to the moving player and calls each piece’s move generator function.  Put them all together and you’ve got your potential moves, but to figure out whether a potential move is legal you must generate all of the opponent’s potential replies to that move and see if any of them are ‘king captures.’  If there is at least one king capture then the move is illegal because it would put (or leave) the mover in check.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s