Move Generation

Introduction

Move generation stands as a cornerstone component of any chess program, orchestrating the intricate dance of pieces across the board. Because this module handles the complexities of legal move generation, it is crucial that we define a carefully crafted architecture that ensures accurate calculations and keeps the code far away from crumbling under the weight of its own complexity. In this devlog, we delve deep into the inner workings of the move generation module’s architecture, dissecting its components and the rationale behind design choices.

Code Architecture

The general structure for this module is the following:

Let’s explain each block from top to bottom.

Move

The Move class is a simple data container that represents a move in the board. It holds a rank and file for the starting and destination squares. It also holds a flag that specifies whether we are performing a special move or just a regular one. Since each type of move has its rules and technicalities, this will be helpful later to implement specialized logic for each one. The move flag is implemented with the MoveFlag enumeration type.

Adding a field that referred to the piece that would move was considered. However, when performing a legal move on the board, the piece that’s moving is not relevant. The only required information is the start and destination squares, and the type of move we are performing. Therefore, it was omitted from this data structure.

Piece enums

Two enumeration types are defined for pieces: PieceType and PieceColor. These enums are used across the program to standardize and simplify how classes talk about piece characteristics. They will be highly used as method parameters to return different results depending on the piece color and piece type provided.

The option of holding both color and type on the same enum was considered. This alternative is illustrated in this video [1]. However, this information was split into two different enums to be more clear and explicit when writing the code.

Notice that we added a NONE flag to both enums. The intention of this flag is to find and correct bugs where the piece type or piece color is not initialized. This way, we ensure these fields are always set up from the beginning [2].

Piece

The Piece abstract class generalizes the data and behavior of pieces.

Pieces are defined by their color, type, and where they are located on the board (rank and file). A position field is added to hold a bitboard representing the piece position. This facilitates calculations of moves.

The getMoves() abstract method receives a board configuration and it returns a bitboard representing moves a piece can perform on the given board. Derived classes implement this method providing the details on how they can move. This method considers only regular moves and captures, excluding special moves like en-passant, castling, and such.

MoveGenerator

This class will be responsible for generating legal moves based on the basic rules implemented in the Piece class, the current state of the board, and other special rules (castling, en-passant, promotion). The algorithm ensures king safety at all times, meaning that it makes sure no king is in check after any move.

The generateMoves() method receives a board configuration and returns an array of legal moves for the given color.

Board

The Board class is responsible for keeping, updating, and sharing information about the board’s current state. It allows other classes to change the board by applying moves, adding pieces, or removing them.

The MoveGenerator class and Piece instances will heavily use this interface to retrieve information about the board so they can calculate moves appropriately. As mentioned before, PieceColor and PieceType enums are used to tailor the information provided.

Board Data Structures

Two important data structures store the current state and support the board’s functionality.

The first data structure is a Dictionary 3 which maps piece color and piece type (keys) to pieces currently placed on the board(values). This allows fast access to pieces with specific characteristics without the need to scan the whole board.

The second data structure is a Quadrille [4] that represents the position of pieces on the board. This data structure is used along with the Move class to apply moves on the board and change the pieces’ position property. Moves are made by directly indexing the matrix with the rank and file provided by the Move object instance. Here’s some pseudocode to exemplify this approach:

makeMove(move) {
        //if there's a piece in destination
        let pieceInDestination = getPieceOnRankFile(move.endRank, move.endFile);
        if (pieceInDestination !== null) {
            //capture it
            capturePiece(move.endRank, move.endFile);
        }

        //move piece
        let pieceToMove = getPieceOnRankFile(move.startRank, move.startFile);
        pieceToMove.position = RankFileToBitboard(rank,file);
        removePiece(move.startRank, move.startFile);
        addPiece(pieceToMove, move.endRank, move.endFile);
    }

    getPieceOnRankFile(rank,file){
        return board.read(rank,file);
    }
    addPiece(piece,rank,file){
        return board.fill(rank,file, piece);
    }
    removePiece(rank,file){
        return board.clear(rank,file);
    }

Keep in mind that this matrix is used just for making moves, not generating them. As we said in previous entries, we will use bitboards to do most calculations to generate legal moves.

Why using a matrix?

We could argue that it is possible to use the piece type to access the required piece object in the Dictionary and then change its position property.

However, this will involve adding an extra field in the Move class, which is not ideal. Also, the board might have several pieces of the same type, so we would have to do some tricky logic to pinpoint exactly which piece is going to move.

Another solution would be to add the piece object directly in the Move class and forget about finding the piece on the board. Nonetheless, the Move class will be too aware of the Piece_** class, which is not necessary at this point.

An important principle when designing code is to hide as much information as possible and avoid coupling classes together [2]. By creating a matrix that holds the pieces in their current spot, we avoid adding more information to the Move class, we hide implementation details of the Piece class, and we simplify the logic to pinpoint the piece we want to move.

Move Generation

The Board class has a reference to all pieces on the board. Likewise, pieces extensively use methods from Board to calculate their moves. After all, pieces need to know the board configuration and placement of other pieces to be able to calculate how they can move.

Furthermore, the Board class holds a reference to an instance of MoveGenerator. Board serves as a middleman between this class and other modules to generate moves through the generateMoves(PieceColor) method. Likewise, the MoveGenerator class uses methods from the Board class to calculate moves.

You might be wondering: “Why not do it the other way around? Why not have external classes call MoveGenerator directly and pass a board object instance?” This idea would look like this:

instead of:

Indeed, the first option is better because Board has no knowledge of MoveGenerator, removing the circular relation between both classes and reducing coupling. Actually, this was the idea that originally went into the design.

However, this approach was discarded for the reasons we’ll see in the following sections.

Board Methods

One last tweak…

Let’s take a look at the Board class again:

Looks neat, right? Well, there are two aspects of the class that we have to address.

Poor encapsulation

If we look at the methods provided by the Board class interface, we notice that this class is too open (or a dirty snitch!) about the internal workings of the Move Generation module.

Bitboards are an example of this. They are a low-level [5] data type that is meant to be used only for facilitating calculations when generating moves. They are not as intuitive and easy to use as other common data types like String or Number. Considering that the Board class is intended to provide information about the board to any class that requires it, bitboards are an implementation detail that shouldn’t be exposed to higher-level clients.

The same happens with methods that make use of the Piece class. Piece objects also deal with bitboards and contain details that won’t be required outside the Move Generation module.

We have to remake the Board class so we can hide these implementation details from the rest of the codebase.

Inconsistent abstraction

This problem arises as a consequence of the previous one. On one hand, we have some methods of the Board class that work with complex low-level structures and are intended to be used by the Move Generation module (e.g getOccupied(), getEmpty(), addPiece(), removePiece()). On the other hand, other methods work with lighter, simpler data types and are intended to be used by higher-level classes (draw(), print(), makeMove()). The interface is clearly split into two different parts: a low-level abstraction that deals with implementation details, and a higher-level abstraction that interacts with the rest of the program.

We have to separate these parts into two single consistent abstractions.

The Cure

To resolve these issues, we’re going to create two classes and distribute data and methods appropriately.

Alt text
Creating an abstraction of a complex system. Taken from [6]

In our case, that would look like this:

It’s important to remark that BoardImplementation will act as an immutable object that holds the state of the board at a particular moment of the game. Like as if we had taken a picture of the board at some point and kept that picture unaltered. For this reason, every time there’s a change in the board as a result of making a move, Board will create a new BoardImplementation instance and point to it. The main purpose of this is to avoid creating duplicated methods to update the state of the board in both classes.

To be honest, BoardImplementation instances will actually be semi-immutable. For the purpose of calculating moves, we need to be able to remove pieces from the BoardImplementation instance temporarily. We’ll see why in the following devlogs. But apart from this case, BoardImplementation should maintain the same internal state since its creation.

On another note, going back to why the MoveGenerator class is at the bottom of the architecture, it’s evident that MoveGenerator needs access to the implementation details provided by BoardImplementation, which is encapsulated behind Board. Hence, Board has to hold a reference to MoveGenerator to grant access to the BoardImplementation instance. It’s the only way to connect these two classes without exposing the BoardImplementation class to the rest of the program.

Some other aspects worth mentioning about this approach are:

  • Both classes hold a matrix of pieces. However, Board holds a simpler version of pieces symbolized by string keys. Check Quadrille’s chess keys [4].
  • We have removed the cyclical relation between Board and MoveGenerator.
  • print() is kept for both classes for debugging purposes.

Final Architecture

Other alternatives considered

This section is a quick overview of additional alternatives considered for the architecture that were ultimately discarded. You can skip this section if you desire.

Move Generation inside Board

A simple option to add move generation functionality would be to let Board implement all the logic necessary to calculate moves. After all, Board masters the information about pieces and how they are arranged on the board.

However, this option has a drawback. It puts too many responsibilities on the Board class. First, it would be responsible for updating and reporting the state of the board. And second, it would be responsible for generating legal moves.

The first of the SOLID principles is the Single-Responsability principle: “Gather together the things that change for the same reasons. Separate those things that change for different reasons”[7]. Generating moves and dealing with the state of the board are two different concerns that should be separated into different classes. Focusing unrelated tasks under the same roof makes for a class with poor cohesion and low maintainability.

Pawn structure

An interesting approach to represent and manipulate pawns is to treat all of them as a single entity. This is called a pawn structure and it is illustrated in this video [8]. However, since we are operating on multiple pawns at once, finding which pawn is able to perform a certain move might become ambiguous. For the sake of simplicity, there’ll be one object for each pawn.

Your turn!

As I said in a previous devlog, my solution is nowhere near being the “correct” or the “perfect” one. There are still plenty of things I don’t feel totally sure about and that might be subject to change in the future.

That’s just the nature of software development. You never just sit in your chair, think for a couple of minutes, and come up with the most brilliant and creative solution that has ever existed or been dreamt of in the history of human insanity.

The picture of the software designer deriving his design in a rational, error-free way from a statement of requirements is quite unrealistic. No system has ever been developed in that way, and probably none ever will. - David Parnas Paul Clements [4]

A tidy way of summarizing these attributes of design is to say that design is “emergent.” Designs don’t spring fully formed directly from someone’s brain. They evolve and improve through design reviews, informal discussions, experience writing the code itself, and experience revising the code. - Steve McConnell [4]

Success is the progressive realization of a worthy goal or ideal. - Earl Nightingale

So it’s time you take a deep dive into creating the architecture of your own program. I know it might be daunting at first, but remember, you’ll refine it over time. Just start with something right now! You can also prototype some ideas in code and then, with the knowledge of how the implementation will look like, tackle the architecture.

References