Bitboards

A bitboard is a number that represents a grid: each bit encodes one cell (1 = filled, 0 = empty). With this encoding, common grid operations—like making a move or testing win patterns—reduce to standard bitwise operations.

In super‑strong C++ NNUE chess engines like Stockfish and Obsidian, bitboards use fast 64‑bit math. Here we use JavaScript BigInt for the same encoding and arbitrarily large boards—but vanilla Quadrille operations are consistently faster than equivalent BigInt bitwise ops in JS.

Layered 3×3 Bitboard Tic-Tac-Toe

The sketch below implements standard 3×3 Tic-Tac-Toe using two Quadrilles: player1 and player2. Each move updates the current player’s layer; win detection converts each layer to a bitboard and checks against predefined win patterns.

// Bit patterns for all winning 3-in-a-row configurations
const patterns = [
  0b111000000n, // Rows
  0b000111000n,
  0b000000111n,
  0b100100100n, // Columns
  0b010010010n,
  0b001001001n,
  0b100010001n, // Diagonals
  0b001010100n
];

let player1;
let player2;
let resetButton;
let winner;

Quadrille.cellLength = 100;
const x = 'X', o = 'O';

function setup() {
  createCanvas(3 * Quadrille.cellLength, 3 * Quadrille.cellLength);
  textAlign(CENTER, CENTER);
  resetButton = createButton('reset game');
  resetButton.position(10, height + 10);
  resetButton.mousePressed(resetGame);
  document.oncontextmenu = () => false;
  resetGame();
}

function draw() {
  background(0);
  drawQuadrille(player1);
  drawQuadrille(player2);
  if (winner) {
    textSize(32);
    fill('white');
    text(`${winner} wins!`, width / 2, height / 2);
    noLoop();
  }
}

function mousePressed() {
  // Ignore clicks if game is over
  if (winner) return;
  // Determine current and opponent players
  const current = player1.order <= player2.order ? player1 : player2;
  const opponent = current === player1 ? player2 : player1;
  // Determine clicked cell coordinates
  const row = current.mouseRow;
  const col = current.mouseCol;
  // Check bounds and ensure both layers are empty
  if (current.isValid(row, col) && current.isEmpty(row, col) && opponent.isEmpty(row, col)) {
    current.fill(row, col, current === player1 ? x : o);
    // Check for win or restart on draw
    winner = checkWinner();
    if (!winner && player1.order + player2.order === 9) resetGame();
  }
}

function resetGame() {
  player1 = createQuadrille(3, 3);
  player2 = createQuadrille(3, 3);
  winner = undefined;
  loop();
}

function checkWinner() {
  const b1 = player1.toBigInt();
  const b2 = player2.toBigInt();
  // A win occurs if any pattern is fully matched by a player's bitboard
  return patterns.some(p => (b1 & p) === p) && 'Player 1' ||
         patterns.some(p => (b2 & p) === p) && 'Player 2';
}

Winning Patterns

In a 3×3 board, there are nine bits—one per cell—arranged in row-major, top-to-bottom, left-to-right order. For instance, 0b111000000n (which equals 448n) marks the top row: the first three bits are 1, the rest 0. Concretely, 2⁸ + 2⁷ + 2⁶ = 256 + 128 + 64 = 448—the sum of powers of two where the bit is set. All win patterns are listed below.

const patterns = [
  0b111000000n, // Rows
  0b000111000n,
  0b000000111n,
  0b100100100n, // Columns
  0b010010010n,
  0b001001001n,
  0b100010001n, // Diagonals
  0b001010100n
];

The interactive sketch below visualizes these win patterns in real time. Use the dropdown to select a win pattern and inspect its bitboard value. Each cell is labeled with its power of 2, showing exactly how the number is constructed.

Win Detection with Bitwise Matching

A win occurs when the player’s bitboard matches a predefined win pattern. This is checked with the bitwise AND test:

where $b$ is the player’s bitboard (from toBigInt) and $p$ is a win pattern. In words: all bits required by the pattern are already set in the player’s bitboard.

Because the test compares against a fixed pattern, every winning pattern—covering all positions and orientations—must be predefined. For example, (player.toBigInt() & selectedPattern) === selectedPattern triggers a win, and here the sketch changes the background from indigo to magenta to illustrate the match:

(click to (un)set the player marker ⨂)

The same rule applies to any player: win if (b & p) === p for some pattern p in patterns.

function checkWinner() {
  const b1 = player1.toBigInt();
  const b2 = player2.toBigInt();
  // A win occurs if any pattern is fully matched by a player's bitboard
  return patterns.some(p => (b1 & p) === p) && 'Player 1' ||
         patterns.some(p => (b2 & p) === p) && 'Player 2';
}

Bitboard Quadrille API

Below are the essential helpers you’ll use most often with bitboards:

• toBigInt() — Converts a Quadrille to a BigInt where 1-bits mark every non-null cell. Mapping is row-major across the grid.
• bitIndex — Maps a cell (row, col) to a 0-based bit position in the bitboard. Useful for building single-move masks: 1n << bitIndex.
• bitCell — Inverse of bitIndex: given a bit position (or single-bit mask), returns the corresponding { row, col } cell.
• createQuadrille(width, height, bigint, value) — Builds a grid from a bitboard: every 1-bit becomes value in the new Quadrille.
• clear(bitboard) — Clears all cells whose bits are 1 in the provided mask.
• fill(bitboard, value) — Fills all cells whose bits are 1 in the provided mask with value.

References

• Tic-Tac-Toe — Classic grid game used here to illustrate patterns and checks.
• Bitboard (Wikipedia) — Compact state encoding widely used in board-game engines.

Further Reading

• Bitwise toolkit used with bitboards: & (AND) for matching patterns, | (OR) to add moves, ^ (XOR) for toggles, ~ (NOT) for masks, <</>> for shifting patterns or single-bit masks.
• Pattern Matching (Computer Science) — Symbolic vs. structural comparisons.
• Bitwise operators in JavaScript — Reference for BigInt-aware bitwise operators.