Board Representation

Introduction

Board representation is an ongoing topic in the chess programming community. Programmers, scientists, and hobbyists are constantly looking for new representations that make their programs better, faster, or more intuitive.

Board as a matrix

The first approach most of us will think of is to represent the board as a matrix of values. This is a very intuitive representation because the chessboard is just like a matrix: a squared arrangement of spaces that contains values. In this case, our values are chess pieces. To read or modify the state of the chessboard, we have to index an element of the matrix directly or traverse the matrix with a loop.

Alt text
Board representated as a matrix. Pieces are represented by their initial

However, historically the hardware in which chess programs were executed had limited memory and processing power. For that reason, developers couldn’t afford big data structures or algorithms that had to iterate through the whole matrix several times [1]. Matrices were then discarded because they consume more memory than regular data types and they usually involve working with nested loops, which are not efficient in performance and can be difficult to manipulate with all the indexes and array limits.

 Consequently, data structures that prove to be lightweight and simple to manipulate were predominantly used.

Board as a bitboard

The reasoning behind bitboards is to imagine that each bit of a binary number is arranged spatially. The way we arrange those bits depends on what we want to represent with the binary number.

Alt text
Binary number arranged spatially in different ways

To represent a chessboard, we’ll use a 64-bit binary number whose bits are spatially arranged in an 8x8 matrix, just like a chessboard.

Alt text
Bitboard representation of chessboard

With this configuration, each square of the board is linked to one bit of a binary number. Therefore, each square can have one of two values: zero or one. This means bitboards can store information on binomial properties of the board that are different for each square. In other words, bitboards allow us to ask a question to each square about its state with two possible answers. For example, we can set up a bitboard that asks the question: “Is the square empty?” with one meaning “yes” and zero meaning “no”.

This comes in handy to easily represent various properties that make up the state of the game. For example, we can create a bitboard that tells us which squares are occupied by white pieces:

Alt text
Bitboard of squares occupied by white pieces

We can create a bitboard that represents the squares that are attacked by a black Queen placed in D5:

Alt text
Bitboard of black queen’s attacks

We can create a bitboard of all the squares the white king cannot move because it’ll be in check:

Alt text
Bitboard of forbidden squares for white king

As you can see, bitboards are versatile to store different types of information.

And remember, a bitboard is not a matrix of numbers, it is just a single number. Let’s take the example of the queen in D5. If we convert the binary number to the decimal system, we get the number 9.386.671.504.487.645.697. It’s a big number, but still just a number. Therefore, a couple of bitboards that represent the entire game are more space-efficient than matrices that hold complex objects inside.

Calculations with a matrix

Let’s say we want to know which squares contain white pieces that are being attacked by black pieces on an arbitrary board. If we use a Matrix representation, the pseudocode to accomplish this will be:

let board = new Matrix(8,8);
let attackedSquares = [];//squares with white pieces attacked by black pieces
//iterate board
for(rank = 0; rank < MAX_RANK; rank++){
  for(file = 0; file < MAX_FILE; file++){
    //if there's a black piece
    let piece = board[rank][file];
    if(piece !== null && piece.color === PieceColor.Black){
      //get piece attacks
      let attacks = piece.getAttacks();
      //iterate attacks
      for(attackedRank = 0; attackedRank < MAX_RANK; attackedRank++){
        for(attackedFile = 0; attackedFile < MAX_FILE; attackedFile++){
          let attackedPiece = attacks[attackedRank][attackedFile];
          //if attacked piece is a white piece
          if(attackedPiece !== null && 
          attackedPiece.color === PieceColor.White){
            //add attacked square to list
            let square = {
              rank: attackedRank,
              file: attackedFile
              }
            attackedSquares.push(square);
          }
        }
      }
    }
  }
}

class Piece{
  getAttacks(){
    //returns matrix with pieces being attacked by this piece.
  }
}

As we can see, the code is long and complex. Also, it is not efficient because it needs to iterate through arrays multiple times. On top of that, we can expect the code will become more complex as we add more conditions to the problem.

Calculations with bitboards

The biggest advantage bitboards bring to the table is the efficiency and simplicity with which we can manipulate them with bitwise operators. Bitwise operators apply operations to numbers bit by bit. This is useful because we can change every bit of the bitboard in a single statement without needing to loop through it. You can learn more about bitwise operations here [2].

Going back to the previous example, we can easily solve the problem with bitboards and some bitwise operations:

let board = new Matrix(8,8);
let attackedSquares = 0n; //bitboard with squares occupied by white pieces being attacked by black pieces
let whitePieces = getWhitePieces();//bitboard with square occupied by white pieces

//iterate board
for(rank = 0; rank < MAX_RANK; rank++){
  for(file = 0; file < MAX_FILE; file++){
    let piece = board[rank][file];
    //if there's a black piece
    if(piece !== null && piece.color === PieceColor.Black){
      //get attacks
      let attacks = piece.getAttacks();
      //get intersection between attacks and white pieces
      let whitePiecesAttacked = whitePieces & attacks;
      //add intersection to attacked
      attackedSquares = attackedSquares | whitePiecesAttacked;
    }
  }
}

class Piece{
  getAttacks(){
    //returns bitboard with pieces being attacked by this piece.
  }
}

As we can see, the logic has simplified significantly, going from an intricated loop to a few statements. Also, this time more conditions just mean adding extra bitboards to the equation. The only thing we need to worry about is building the bitboards correctly.

Additionally, bitwise operators are supported natively by most modern processors. This means that they are executed really fast compared to iterative statements.

Hands on!

The intention of this explanation isn’t to say that matrices are the wrong solution at all. In software development, there are multiple equally correct ways to achieve the same result. Each strategy brings some upsides and downsides and it is the developer’s responsibility to select the solution that suits best the requirements of the project. It can also depend on your personal preference. Matrices might be more intuitive to you than bitboards, and that’s totally valid. You are free to choose whatever makes you sleep better at night.

Actually, as I said in this post introduction, there are tons of new representations that have come to life over the years that might be even better than what we have discussed here. I encourage you to be curious and take a look at these new developments. Check [1] and [3].

Exercise  Search for the latest board representations available, understand how they work, and decide which you want to implement for your game.

References