0x88 Chess Board Representation

In chess programming, there are many different ways of representing the chess board. The 0x88 board representation is a square centric¹ way of representing the board using an array of length 128. Square centric approaches represent the board from the perspective of the squares rather than the pieces. The 0x88 in the name comes from the usefulness of the 0x88 (1000 1000 in binary) bitmask in important operations which we’re going to explore.

type board struct {
    data [128]byte
}

Something to note about this representation is that we are allocating 128 squares even though a traditional chess board has only 64 squares. Why are we representing our board with 128 squares (16x8)? Wouldn’t it be simpler if we represented the board with just 64 squares (8x8)? Let’s try to understand why this representation could be useful.

Board Structure

First, let’s understand how positions work in our board representation since we have more available squares than valid squares. As a refresher, rank represents the rows of a chess board, and file the columns. Since we’re viewing the 128 bytes of our board as a 16x8 grid that means that the width of our board expands beyond the boundary of valid positions.

The table above shows the hexadecimal index of each piece of the board with 00 representing the bottom-left of the board from white’s perspective and 77 the top-right. Note that our rank and file are zero indexed since that’s how we’ll be representing them internally. As you can see above, the right half of the board is essentially garbage data since the points there don’t map to valid positions on the board. We’re not actually storing any meaningful data at these locations.

Let’s look at how we can implement some basic functions that make working with the board easier.

func getIndex(rank int, file int) int {
    return (rank << 4) | file
}

func getFile(index int) int {
    return index & 7
}

func getRank(index int) int {
    return index >> 4
}

// This is the magic of the 0x88 representation
func isValidSquare(index int) bool {
    return (index & 0x88) == 0
}

To understand how these operations work, let’s take a look at look at how our indices² look in binary.

This table illustrates a couple of interesting properties of the 0x88 representation. The upper 4 bits represent the rank and the lower 4 bits represent the file. The most significant bit of both the file and the rank are never set in any of these valid board positions. Also, the extra padding in this representation makes it so that the bits representing the nth rank are equal to the bits representing the nth file!

Retrieving Index

Understanding how we get the index from a rank and file in this representation is simple enough. Our rank has 16 squares so we multiply by 16 to get to the start of the target row and then we add the file to get to the target column. We can achieve the same thing through bit manipulation by shifting the rank left by 4 (equivalent to multiplying by 2^4) and then setting the bits used for the file with the OR operator (equivalent to adding since the bits used for the file are empty after shifting left). Let’s look at an example using of getting the index of rank 5, file 3

rank      = 0000 0101 (decimal 5)
rank << 4 = 0101 0000 (decimal 80)
file      = 0000 0011 (decimal 3)
OR        = 0101 0011 (decimal 83)

Retrieving File

Now let’s look back at the operation for retrieving the file from an index. Earlier we defined this as index & 7. Since 7 in binary is 111, this operation is essentially just retrieving the 3 lowest bits of our index since those are the ones that represent our file. We don’t need to get the most significant bit of the file since it’s never set for valid board positions. Let’s take a look at an example using rank 7, file 6.

    0111 0110 (decimal 118)
AND 0000 0111 (decimal 7)
  = 0000 0110 (decimal 6)

Retrieving Rank

Great, now let’s take a quick look at how we retrieve the rank. We know that we essentially just need the 4 most significant bits with no other bits set. We saw earlier we can do this with index >> 4. This operation just shifts our binary 4 bits to the right³. Let’s extract the rank from our previous example.

       0111 0110 (decimal 118)
>> 4 = 0000 0111 (decimal 7)

Valid Board Position

Those are great, and help us work with our board easier, but the important part (and one of the reasons we might do this in the first place) of this representation is how efficient it is for us to check if a given index is valid board position. Earlier we observed that, for valid board positions, the most significant bit of the rank and file are never set. The binary representation for any rank or file above or below our board would require that one or both of the most significant bits of our rank and file to be set. To check if a position is valid we can just check to make sure that neither of those bits are set! To extract both of those bits we can use the 0x88 mask (1000 1000 in binary) that this representation gets its name from. We can express this operation as (index & 0x88) == 0. Let’s look at both a valid (rank 5, file 6) and invalid (rank 8, file 7) example.

isValidSquare(0101 0110) // Rank 5, File 6
    0101 0110
AND 1000 1000
  = 0000 0000
Result equals 0 -> VALID

isValidSquare(1000 0111) // Rank 8, File 7
    1000 0111
AND 1000 1000
  = 1000 0000
Result doesn't equals 0 -> INVALID

Conclusion

In chess programming, a large amount of time can be spent on the move generation step. The beauty of the 0x88 representation is that it helps us accomplish the task of checking whether the position of a generated move is on the board without having to calculate and compare against row and column bounds when we’re trying to quickly generate the available legal moves using offsets. Since some chess engine prioritize speed over memory the 0x88 representation can potentially be a good choice when compared to a more traditional 8x8 representation. There are other more efficient board representations that you can read about on the chess programming wiki.