Bitboard Techniques: Encoding a Chessboard in 64 Bits

Why Represent a Board as Bits

A naive chess board representation is an 8x8 array where each cell stores a piece code or empty. Checking whether a rook can capture something means walking outward one square at a time until you hit a piece or the edge, four separate directions, with branching logic at every step. That is slow when you must do it millions of times per second during a search. A bitboard representation instead uses twelve 64-bit integers for a standard chess position: one for each combination of piece type (pawn, knight, bishop, rook, queen, king) and color (white, black). Bit index n, running from 0 to 63, corresponds to a specific square, typically with bit 0 as a1 and bit 63 as h8, scanning left to right, bottom to top. If white has a knight on square g1, bit 6 of the white-knight bitboard is set to 1; every other bit in that integer is 0. This representation turns board queries into arithmetic. Total occupancy of the board is simply the bitwise OR of all twelve piece bitboards. White's total occupancy is the OR of just white's six bitboards. To find which of a bishop's diagonal target squares actually contain an enemy piece, the engine ANDs the bishop's precomputed attack bitboard with the opponent's occupancy bitboard; every 1 bit remaining in the result is a legal capture square, discovered without inspecting a single square individually. The practical payoff is speed measured in CPU cycles rather than loop iterations. A modern processor executes a 64-bit AND, OR, XOR, or shift in a single cycle, so an operation that would take a dozen or more comparisons in an array-based board collapses into one instruction. Multiply that savings across the millions of positions a strong engine examines per second during a deep search, and the difference between array-based and bitboard-based move generation becomes the difference between a hobby program and a competitive engine. This is also why bitboards are not unique to chess: Othello, checkers, Connect Four, and other fixed-grid games with binary occupancy states borrow the same trick whenever the grid size fits comfortably into a machine word.

Core Bitwise Operations on a Board

Four operations do almost all the work in a bitboard engine, and each maps directly onto a chess concept. AND finds intersections. ANDing a piece's precomputed attack bitboard with the opponent's occupancy bitboard yields exactly the squares that piece can capture on. ANDing a pawn's forward-move bitboard with the empty-squares bitboard (the bitwise complement, NOT, of total occupancy) confirms whether the square ahead is actually free to move into. OR combines sets without losing information, since setting a bit that is already 1 changes nothing. This is how occupancy bitboards are built: OR together all piece bitboards of one color to get that side's occupied squares, then OR both sides together for total occupancy. It is also used to add a piece to a bitboard, by OR-ing in a bitboard with only that one square's bit set. XOR toggles bits, which is exactly what happens when a piece moves: the origin square's bit flips from 1 to 0 and the destination square's bit flips from 0 to 1, both achieved by XOR-ing the piece's bitboard with a bitboard that has only those two bits set. XOR is also how captures update the captured piece's own bitboard, clearing the bit at the destination square. This property makes XOR self-inverting, which is convenient for undoing moves during search: applying the identical XOR a second time restores the original bitboard exactly. Shifts simulate movement in a direction. Shifting white's pawn bitboard left by 8 bit positions (since each rank is 8 bits wide) produces every square a pawn could advance to, before checking for blockers or promotion. Diagonal pawn captures use shifts of 7 or 9, with a mask applied first to prevent bits from wrapping around the board edge from the a-file to the h-file or vice versa, an artifact of packing a two-dimensional board into a one-dimensional bit string. Beyond these four, engines rely on two more primitives: population count (counting how many bits are set, useful for material counting and mobility scoring) and bit-scan (finding the index of a particular set bit), which is where the De Bruijn sequence trick, covered later in this article, becomes essential.

The Sliding-Piece Problem

Knights, kings, and pawns have fixed, short-range move patterns: a knight's attacks from any given square are always the same fixed set of offsets, so its full set of possible attack bitboards, one per starting square, can be precomputed once and stored in a 64-entry table with zero further work at runtime. Rooks, bishops, and queens are different because they slide until they hit either the edge of the board or a blocking piece, friendly or enemy. A rook on d4 with nothing in its way can reach the entire d-file and 4th rank; the same rook with a pawn on d6 can only reach d5 and d6 upward before the blocker stops it. The set of legal target squares therefore depends not just on the rook's position but on the full pattern of occupied squares along its rank and file, called the occupancy. Naively, this means recomputing legal moves by ray-casting outward square by square every single time, checking each square for a blocker before continuing, which reintroduces exactly the kind of loop-heavy computation bitboards were meant to eliminate. The number of possible blocker configurations relevant to a rook is large: up to 2 to the 12th power for a rook near the board's center (12 relevant squares along its rank and file, excluding the edges since the edge itself is always a valid stopping point regardless of occupancy). Storing a precomputed answer for every possible occupancy pattern, for every square, for both rook and bishop, is feasible in principle, since the totals run into a few hundred thousand table entries, well within a modern engine's memory budget. The remaining problem is purely algorithmic: given an arbitrary 64-bit occupancy bitboard, how do you convert the relevant blocker bits into a compact index into that precomputed table, quickly and without collisions that would return the wrong answer? That question is exactly what magic bitboards were invented to answer, and it is the subject of the next section.

Magic Bitboards: Hashing Occupancy to an Index

The magic bitboard technique solves the sliding-piece lookup problem with a single multiplication. For each square and each sliding piece type, the engine precomputes a bitboard mask of the squares whose occupancy actually matters for that square, called the relevant occupancy mask, which deliberately excludes the board's outer edge in that direction since a slide always stops there regardless of what occupies it. Given a real board position, the engine first extracts only the bits from the actual occupancy bitboard that fall within this relevant mask, using an AND operation. This masked occupancy is then multiplied by a specially chosen 64-bit constant, the magic number, and the top bits of that 64-bit product are extracted with a right shift. The result is a small integer, small enough to serve directly as an array index into a precomputed table of attack bitboards for that square. What makes a magic number magic is that, for the specific limited set of occupancy patterns that are actually reachable given that square's relevant mask, the multiplication spreads the input bits across the top bits of the product in a way that avoids collisions, or in practice, in a way where any collisions that do occur happen only between occupancy patterns that map to the identical legal-move result anyway, making the collision harmless. Finding such constants historically required random search: generate a candidate 64-bit number, test it against every possible relevant occupancy pattern for that square, and check whether the resulting indices ever collide destructively; if they do, discard the candidate and try another. This brute-force search reliably finds working magics within seconds of computer time, and once found, they are fixed constants baked into the engine's source code forever after, since the search only needs to happen once, at engine-development time, not during actual play. The payoff at runtime is dramatic. Computing a rook or bishop's full legal-move bitboard, accounting for every possible blocker, becomes: one AND to mask relevant occupancy, one multiply by the magic constant, one shift to extract the index, and one array lookup. Four fast operations replace what would otherwise be a variable-length ray-casting loop, and because there is no branching based on board content, this sequence executes at a predictable, pipeline-friendly speed on modern CPUs, which matters enormously when it happens billions of times during a deep search.

De Bruijn Sequences: Finding the Lowest Set Bit Instantly

Bitboard engines constantly need to answer a narrower question: given a 64-bit integer with some bits set, which square does the single lowest set bit correspond to? This comes up whenever the engine iterates over the individual squares in a bitboard, for instance, walking through every square a piece attacks one at a time to generate a distinct move for each. A naive approach tests bit 0, then bit 1, then bit 2, and so on until it finds a 1, which is a loop of up to 64 iterations in the worst case. A classic bit trick speeds up finding the lowest set bit itself: computing bitboard AND with its own two's-complement negation isolates just the lowest set bit into its own 64-bit value, with every other bit cleared, in one operation. That leaves a second problem: given this isolated single-bit value, which of the 64 possible positions is it, expressed as a plain integer index rather than a bit pattern? This is where the De Bruijn sequence comes in. A De Bruijn sequence of order k over a binary alphabet is a cyclic sequence of length 2 to the power k in which every possible substring of length k appears exactly once as the sequence is read with wraparound. For 64-bit bit-scanning, engines use a specific 64-bit De Bruijn constant of order 6, since 2 to the 6th power equals 64. The remarkable property is this: if you take the isolated single-bit value, multiply it by this De Bruijn constant, and then right-shift the 64-bit product by 58 bits (keeping only the top 6 bits), the resulting 6-bit number is a unique index between 0 and 63, and that index feeds directly into a small 64-entry lookup table that has been precomputed once to map each of those 64 possible index values to the actual square number of the original bit. The reason this works is that multiplying by a well-constructed De Bruijn constant causes each of the 64 possible single-bit inputs to shift the constant's bit pattern by a different, unique amount, so the top 6 bits of the product end up different for every possible input position, exactly the perfect-hash property a De Bruijn sequence guarantees by its combinatorial construction. The entire operation, isolate the lowest bit, multiply, shift, and look up, takes a small constant number of machine instructions regardless of where the set bit happens to be, replacing a variable-length loop with fixed, predictable, branch-free execution, precisely the same design goal that motivates magic bitboards for sliding pieces.

Frequently asked questions

Try it live

Everything above runs in your browser — open Bitboard Techniques: Encoding a Chessboard in 64 Bits and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.