Bitboard Representation in Connect Four and Othello

A bitboard representation is a high-performance data structure that models a board game state using binary integers, where each individual bit corresponds to a specific cell on the board. In games like Connect Four and Othello (Reversi), bitboards replace multi-dimensional arrays by encoding the presence of game pieces as 1s and empty cells as 0s across 64-bit integers. This approach allows game engines to evaluate board states, validate rules, generate legal moves, and detect winning lines simultaneously using low-level bitwise operations that execute in a single CPU cycle.

How Bitboards Map the Board

In a computer board game, the physical grid is mapped directly to the binary positions of an unsigned integer.

  • Othello: An \(8 \times 8\) grid contains 64 cells, perfectly matching a standard 64-bit integer (uint64_t). A full game state typically requires two bitboards: one for the black pieces and one for the white pieces. Bit 0 represents the top-left cell \((A1)\), while bit 63 represents the bottom-right cell \((H8)\).
  • Connect Four: A standard grid is 7 columns by 6 rows (42 cells). Engines commonly map this into a 64-bit integer by allocating 7 bits per column (6 playable rows plus 1 sentinel overflow row). The extra row prevents pieces from wrapping around horizontally during bit-shift calculations. One bitboard tracks the current player's pieces, and a second bitboard tracks all occupied spaces to represent the board's physical layout.
Connect Four 7x7 Bit Index Mapping:
.  .  .  .  .  .  .   (Sentinel Row: 6, 13, 20, 27, 34, 41, 48)
5 12 19 26 33 40 47   (Row 6)
4 11 18 25 32 39 46   (Row 5)
3 10 17 24 31 38 45   (Row 4)
2  9 16 23 30 37 44   (Row 3)
1  8 15 22 29 36 43   (Row 2)
0  7 14 21 28 35 42   (Row 1 - Bottom)

Evaluating Winning Lines with Bitwise Operations

Evaluating winning lines (such as four-in-a-row in Connect Four) traditionally requires nested loops to inspect neighboring cells. With bitboards, the binary number system enables parallel evaluation across the entire board at once using bit-shifts and bitwise AND (&) operations.

In a column-major Connect Four bitboard where adjacent vertical cells have an index difference of 1 and adjacent horizontal cells have a difference of 7:

  • Vertical: Shift of \(1\)
  • Horizontal: Shift of \(7\)
  • Diagonal (Bottom-Left to Top-Right): Shift of \(8\) (\(7 + 1\))
  • Diagonal (Top-Left to Bottom-Right): Shift of \(6\) (\(7 - 1\))

To detect four consecutive pieces in any direction, a bitboard algorithm computes the intersection of shifted patterns:

bool check_win(uint64_t board) {
    int shifts[] = {1, 7, 8, 6}; // Vertical, Horizontal, Diagonals
    
    for (int i = 0; i < 4; i++) {
        int shift = shifts[i];
        // Step 1: Find pairs of two adjacent pieces
        uint64_t pairs = board & (board >> shift);
        
        // Step 2: Check if two adjacent pairs overlap to make four in a row
        if ((pairs & (pairs >> (2 * shift))) != 0) {
            return true; // Winning line detected
        }
    }
    return false;
}

Binary Arithmetic Step-by-Step

  1. First Shift (board >> shift): Aligns each piece with its immediate neighbor in the chosen direction.
  2. First Conjunction (board & (board >> shift)): Produces a bitboard containing a 1 only at positions that represent the start of an adjacent pair (\(2\) in a row).
  3. Second Shift (pairs >> (2 * shift)): Moves the detected pairs by two positions along the same direction vector.
  4. Second Conjunction (pairs & (pairs >> (2 * shift))): Checks if two separate pairs overlap. If any bit remains 1, four consecutive pieces exist in that direction. If the resulting integer is non-zero, the game is won.

Line Evaluation and Flips in Othello

In Othello, bitboards evaluate ray-casting operations in eight directions to determine legal moves and piece flipping without checking cells one by one:

  1. Directional Shifts: The engine shifts the player's bitboard by \(1\) (east/west), \(8\) (north/south), \(7\), or \(9\) (diagonals).
  2. Opponent Masking: The shifted bits are masked with the opponent's bitboard using & to find sequences of opposing pieces.
  3. Continuous Propagation: The engine repeatedly shifts and masks up to 6 times to track lines of bounded opponent discs.
  4. Anchor Intersection: An intersection with an empty square or an existing friendly piece identifies either a legal placement or the exact pieces that must be inverted using a bitwise XOR (^) operation.

By substituting conditional branching and nested iteration with native binary operations, bitboard representations execute move generation and win detection in constant \(O(1)\) time complexity.