Bitboards

When we looked at the 0x88 representation, we took a square-centric view of the board: an array indexed by square, where each entry told us which piece, if any, sat there. Bitboards take the opposite, piece-centric view. A chess board has exactly 64 squares, and a 64-bit integer has exactly 64 bits, so we can dedicate one bitboard to a single fact about the board, “which squares hold a white knight”, and let each bit stand for one square: 1 if the fact is true there, 0 if not. It sounds almost too simple to be useful, but it turns out that expressing the board this way lets us answer questions about whole sets of squares at a time, often in a single operation, which is why many strong modern engines are built on bitboards.

type Bitboard uint64

A board’s piece placement isn’t one bitboard but a small collection of them: one per piece type per color (white pawns, white knights, and so on), plus a few derived ones we’ll build as we go. Each individual bitboard answers a yes/no question for all 64 squares at once.

Mapping Squares to Bits#

Before we can set any bits we need to agree on which bit means which square. We’ll use the most common convention, little-endian rank-file mapping: bit 0 is a1, bit 1 is b1, on up to bit 7 for h1, then bit 8 wraps up to a2, and so on to bit 63 for h8. In other words the square index is rank*8 + file, with both rank and file zero indexed¹.

func square(rank, file int) int {
    return rank*8 + file
}

Laid out as a board, with rank 8 on top the way we’d see it from white’s side, the bit indices look like this:

Since the index is just rank*8 + file, every board direction becomes a fixed offset on it. Going up one rank always adds 8, and going one file to the right always adds 1; going down or left subtracts the same amounts. These offsets hold before we account for the edges of the board, where moving “right” off the h-file has to be handled specially, as we’ll see when we generate moves.

Setting, Clearing, and Testing Squares#

The three fundamental single-square operations are setting a bit, clearing it, and testing it. Each one starts from a mask with a single bit set at the square we care about, which we’ll build with a small helper.

// bit returns a bitboard with only the given square set.
func bit(sq int) Bitboard { return 1 << sq }

func (b Bitboard) get(sq int) bool       { return b&bit(sq) != 0 }
func (b Bitboard) set(sq int) Bitboard   { return b | bit(sq) }
func (b Bitboard) clear(sq int) Bitboard { return b &^ bit(sq) }

Setting a square is an OR with the mask, which forces that one bit to 1 and leaves the rest untouched. Testing is an AND with the mask: the result is non-zero exactly when the bit was already set. Clearing uses Go’s AND-NOT operator &^, which is worth pausing on². b &^ bit(sq) keeps every bit of b except the one in the mask, clearing that square whether or not it was set, without disturbing anything else. Note that set and clear have value receivers, so they return a modified copy rather than changing the bitboard in place; you use them as b = b.set(sq), not b.set(sq) on its own.

Set-Wise Operations#

Everything so far has manipulated a single square, which a plain array could do just as well. The reason bitboards earn their keep is the operations that touch every square at once. Because a bitboard is just an integer, the bitwise operators combine two of them square by square in a single operation.

Say we’re holding one bitboard per color for every piece a side owns. The set of all occupied squares is their union, an OR. The empty squares are its complement, a NOT. And the squares where white could capture something are the intersection of white’s attacks with black’s pieces, an AND.

occupied := white | black
empty    := ^occupied
captures := whiteAttacks & black

Each of these is a single operation that answers a question about all 64 squares simultaneously. A straightforward array implementation would need a loop for every one of them. This is the whole pitch for bitboards in miniature: reframe a question about the board as a question about sets, and a single bitwise operator answers it.

Counting and Iterating#

Two questions come up constantly: how many squares are in a set, and which ones. Both are handled by the math/bits package, whose functions compile to dedicated hardware instructions on CPUs that support them and fall back to efficient software otherwise, so we never have to loop over 64 bits by hand.

Counting the bits in a set, the population count, is a single call. It answers questions like how many pawns a side has, or how many squares appear in an attack set. Counting how many pieces attack a particular square is a two-step version of the same idea: first build a bitboard of those attackers, then count its bits.

import "math/bits"

func (b Bitboard) count() int { return bits.OnesCount64(uint64(b)) }

Iterating the individual squares in a set, sometimes called serialization, is the more interesting one. The set operations keep everything as whole-board bitboards, but eventually we have to come back down to individual squares to do anything with them: a bitboard of a piece’s target squares, for instance, has to become one move per square that the engine can actually play and search. To pull the squares back out we repeatedly find the lowest set bit, use its index, and clear it, until nothing is left.

func (b Bitboard) squares() []int {
    var out []int
    for b != 0 {
        sq := bits.TrailingZeros64(uint64(b))
        out = append(out, sq)
        b &= b - 1
    }
    return out
}

bits.TrailingZeros64 returns the number of trailing zero bits, which is exactly the index of the lowest set bit³. The trick that drives the loop forward is b &= b - 1, which clears that lowest set bit and nothing else. Subtracting one flips the lowest set bit to 0 and turns every zero below it into a 1; ANDing that back against the original wipes out the lowest set bit and the borrow, leaving everything above untouched.

b         = 0110 1000
b - 1     = 0110 0111
b & (b-1) = 0110 0000

The lowest set bit, at index 3, is gone and the higher bits survive. Each iteration removes exactly one set bit, so the loop runs once per member of the set rather than once per square on the board.

Generating Moves by Shifting#

Now for the operation that makes bitboards worth the trouble: generating moves. The idea is that shifting a bitboard slides every piece on it in the same direction at once. Recall that up a rank is a left shift by 8. So every white pawn’s single push forward is one shift, and intersecting with the empty squares keeps only the pushes that aren’t blocked.

singlePush := (pawns << 8) & empty

That one expression computes the single pushes for all of white’s pawns together. Double pushes reuse the result: shift the single pushes forward again, keep the ones that land on empty squares, and restrict the targets to the fourth rank so that only pawns that started on their home square qualify.

rank4 := Bitboard(0x00000000FF000000)
doublePush := (singlePush << 8) & empty & rank4

The Wraparound Problem#

Vertical shifts are clean because moving up or down a file can only ever run off the top or bottom of the board, where the bits simply fall out of the 64-bit integer. Horizontal and diagonal shifts are trickier. When we shift left across a file boundary, a piece on the h-file doesn’t fall off the edge, it reappears on the a-file one rank up, because those squares are adjacent bit indices. This is the bitboard equivalent of the off-board problem the 0x88 mask solved for us in the array world, and we solve it the same way: with a mask that deletes the squares a legal move could never reach.

The masks we need are whole files. A file is one bit per rank, eight bits spaced eight apart, and we can build the rest by shifting the a-file mask sideways.

const (
    fileA Bitboard = 0x0101010101010101
    fileB Bitboard = fileA << 1
    fileG Bitboard = fileA << 6
    fileH Bitboard = fileA << 7
)

White’s pawn captures show the pattern at its simplest. A capture toward the h-file is an up-and-right step, a shift by 9; a capture toward the a-file is up-and-left, a shift by 7. After each shift we clear the file the move could only have reached by wrapping around the edge.

attacks := ((pawns << 9) & ^fileA) | ((pawns << 7) & ^fileH)

A pawn on the h-file has no up-and-right capture, and the ^fileA mask⁴ deletes the bogus one that wrapped onto the a-file. The up-and-left mask is the mirror image.

Knight Attacks#

Knights are the showpiece. A knight has eight target squares, each a distinct combination of rank and file offsets, and each one is a shift paired with a file mask that removes its particular wraparound. Moves that cross two files can wrap onto two files’ worth of squares, so those need a two-file mask.

func knightAttacks(knights Bitboard) Bitboard {
    notAB := ^(fileA | fileB)
    notGH := ^(fileG | fileH)

    var attacks Bitboard
    attacks |= (knights << 17) & ^fileA // up 2, right 1
    attacks |= (knights << 15) & ^fileH // up 2, left 1
    attacks |= (knights << 10) & notAB  // up 1, right 2
    attacks |= (knights << 6) & notGH   // up 1, left 2
    attacks |= (knights >> 6) & notAB   // down 1, right 2
    attacks |= (knights >> 10) & notGH  // down 1, left 2
    attacks |= (knights >> 15) & ^fileA // down 2, right 1
    attacks |= (knights >> 17) & ^fileH // down 2, left 1
    return attacks
}

The function takes a bitboard of knights rather than a single square, and because every step is a set operation it computes the combined attacks of all of them at once. Pass it a board with one knight and you get that knight’s targets; pass it both of a side’s knights and you get their union, for the same eight shifts and no loop. For knights, intersect the attack set with empty to find the non-capturing destinations and with the enemy pieces to find the captures.

Attacks, Pseudo-Legal, and Legal#

It’s worth being precise about what these functions actually produce. knightAttacks returns an attack set: every square the knights bear on, which is what you need for captures and for questions like whether a king is in check. Pawns are the only piece whose ordinary capture pattern (the diagonal captures) differs from its ordinary movement (the pushes), which is why we computed the two separately⁵.

An aggregate attack set like this is not a move list, and the difference matters once you feed more than one piece through at a time. The union of both knights’ attacks tells you every square attacked by some knight, which is exactly right for a query like whether a square is defended. But it has thrown away which knight reached which square, and if two knights attack the same square those two distinct moves have collapsed into a single bit. To generate the actual moves, each needing a source square as well as a destination, you serialize the pieces instead: walk the knight bitboard one square at a time and compute that single knight’s attacks on its own.

What none of this accounts for is whether a move leaves your own king in check. Moves derived purely from a piece’s movement rules, ignoring that constraint, are called pseudo-legal; filtering out the ones that expose the king leaves the legal moves the engine may actually play. That filtering is a separate step. One common approach is to make the move and test whether the king is attacked; some engines instead use check, pin, and evasion masks to generate legal moves more directly.

Conclusion#

Bitboards flip the board on its side: instead of asking each square what it holds, we keep one 64-bit set per fact and let bitwise operations answer questions about all 64 squares at once. Occupancy is an OR, empty squares a NOT, capture targets an AND, piece counts a population count, and the combined attack map of a whole army of knights or pawns takes only a handful of shifts and masks. The masks that stop moves from wrapping around the edge play the same role the 0x88 mask did in the square-centric representation, just from the piece-centric side.

The one thing we’ve sidestepped is sliding pieces. Rooks, bishops, and queens travel until something blocks them, so their moves depend on the occupancy of the squares in between, which a fixed shift can’t capture. A common answer is magic bitboards, an occupancy-indexed lookup that maps a piece’s square and the surrounding occupancy to its precomputed attack set. It isn’t the only approach to sliding attacks, but it’s a natural next step from here. As always, the chess programming wiki has far more depth on all of it.