DEV Community

SEN LLC
SEN LLC

Posted on

A 3.7 KB Othello Engine: Bitboards in Rust, Raw WASM, No wasm-bindgen

#rust #webassembly #gamedev

Othello legal-move generation is seven lines of bitboard bitwise ops. I knew this existed; I'd never actually written it. So I built a Reversi engine in Rust, compiled it to raw WebAssembly without wasm-bindgen, and ended up with a 3.7 KB .wasm that plays a credible game against you in the browser.

Rust/WASM Reversi. Dark green 8x8 board with the four center disks, four gold dots showing Black's legal opening moves, status line

📦 GitHub: https://github.com/sen-ltd/reversi-wasm
🔗 Demo: https://sen.ltd/portfolio/reversi-wasm/

Stack summary:

  • Rust, no_std, zero heap allocations
  • Raw WebAssembly.instantiate — no wasm-bindgen, no generated JS glue
  • Vanilla JS + HTML + CSS for the board UI
  • Alpha-beta negamax AI, configurable depth 1–5
  • Final wasm: 3,717 bytes

Bitboards: two u64s carry the entire game

The board is two bitboards, one per color:

static mut BLACK: u64 = 0;
static mut WHITE: u64 = 0;
Enter fullscreen mode Exit fullscreen mode

Bit row * 8 + col — so bit 0 is a1 (top-left) and bit 63 is h8 (bottom-right). Starting position:

const INIT_WHITE: u64 = (1u64 << 27) | (1u64 << 36); // d4, e5
const INIT_BLACK: u64 = (1u64 << 28) | (1u64 << 35); // e4, d5
Enter fullscreen mode Exit fullscreen mode

State is 17 bytes total: two u64s + one byte of turn flag. Legal moves, application of a move, evaluation, all become bitwise operations on these two numbers.

Direction shifts

Each of Othello's eight directions becomes a one-line function:

const NOT_A_FILE: u64 = 0xFEFEFEFEFEFEFEFE; // all bits except column 0
const NOT_H_FILE: u64 = 0x7F7F7F7F7F7F7F7F; // all bits except column 7

fn n(x: u64)  -> u64 { x >> 8 }                       // north
fn s(x: u64)  -> u64 { x << 8 }                       // south
fn e(x: u64)  -> u64 { (x & NOT_H_FILE) << 1 }        // east
fn w(x: u64)  -> u64 { (x & NOT_A_FILE) >> 1 }        // west
fn ne(x: u64) -> u64 { (x & NOT_H_FILE) >> 7 }        // NE (up-right)
fn nw(x: u64) -> u64 { (x & NOT_A_FILE) >> 9 }        // NW (up-left)
fn se(x: u64) -> u64 { (x & NOT_H_FILE) << 9 }        // SE (down-right)
fn sw(x: u64) -> u64 { (x & NOT_A_FILE) << 7 }        // SW (down-left)
Enter fullscreen mode Exit fullscreen mode

The file masks applied before the shift prevent column wraparound — a bit in column 7 shifted right by 1 would otherwise appear in column 0 of the next row. Row overflow takes care of itself because shifting pushes bits off the ends into oblivion.

Legal moves in seven lines

The definition of an Othello legal move: "a square, empty, reached from one of my disks through a run of one-or-more opponent disks in any direction."

In bitboard form, one direction:

fn legal_moves_dir(me: u64, opp: u64, empty: u64, shift: Shift) -> u64 {
    let mut run = shift(me) & opp;          // opp disks adjacent to me
    run |= shift(run) & opp;                 // extend further
    run |= shift(run) & opp;
    run |= shift(run) & opp;                 // max run is 6 (middle 6 of 8)
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    shift(run) & empty                        // the empty square past the run
}
Enter fullscreen mode Exit fullscreen mode

Seven lines, zero branches. The OR'd run variable accumulates all opponent-disk positions reachable from me along this direction; the final shift(run) & empty picks out squares that extend one past the run and are empty — i.e., legal moves.

All eight directions get OR'd together:

fn legal_moves(me: u64, opp: u64) -> u64 {
    let empty = !(me | opp);
    let mut moves = 0u64;
    for shift in DIRECTIONS {
        moves |= legal_moves_dir(me, opp, empty, shift);
    }
    moves
}
Enter fullscreen mode Exit fullscreen mode

This returns a u64 where every set bit is a legal move square. The JS side takes that u64 and uses it to draw the gold hint dots.

Applying a move: the same pattern, different terminator

Computing which opponent disks flip when I play at pos:

fn flips_dir(pos: u64, me: u64, opp: u64, shift: Shift) -> u64 {
    let mut run = shift(pos) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    run |= shift(run) & opp;
    // If the run terminates at one of our disks, flip everything in between.
    if shift(run) & me != 0 { run } else { 0 }
}
Enter fullscreen mode Exit fullscreen mode

Structurally identical to legal-move detection. The only change: check if the run lands on me (sandwich complete, flip) versus empty (open terminus, no flip).

OR across directions → flips_total → apply:

let new_me  = me | pos | flips;
let new_opp = opp & !flips;
Enter fullscreen mode Exit fullscreen mode

That's the entire move-application logic.

AI: negamax + alpha-beta

Othello is a determinate, two-player, zero-sum, perfect-information game — textbook minimax territory. Negamax with alpha-beta pruning:

fn negamax(me: u64, opp: u64, depth: u32, mut alpha: i32, beta: i32) -> (i32, u64) {
    if depth == 0 { return (evaluate(me, opp), 0); }

    let moves = legal_moves(me, opp);
    if moves == 0 { /* handle pass / terminal */ }

    let mut best_score = i32::MIN + 1;
    let mut best_move = 0u64;
    let mut bits = moves;
    while bits != 0 {
        let mv = bits & bits.wrapping_neg();     // extract lowest set bit
        bits ^= mv;
        let flips = flips_total(mv, me, opp);
        let new_me  = me | mv | flips;
        let new_opp = opp & !flips;
        let (s, _) = negamax(new_opp, new_me, depth - 1, -beta, -alpha);
        let score = -s;
        if score > best_score { best_score = score; best_move = mv; }
        if score > alpha       { alpha = score; }
        if alpha >= beta       { break; }
    }
    (best_score, best_move)
}
Enter fullscreen mode Exit fullscreen mode

bits & bits.wrapping_neg() is the Brian Kernighan/LSB isolation trick — extracts the lowest set bit, which we then XOR off. The entire move enumeration is allocation-free.

Evaluation is the classic position weight table + mobility:

const WEIGHTS: [i32; 64] = [
    100, -25,  10,   5,   5,  10, -25, 100,
    -25, -50,  -1,  -1,  -1,  -1, -50, -25,
     10,  -1,   3,   2,   2,   3,  -1,  10,
      5,  -1,   2,   1,   1,   2,  -1,   5,
      5,  -1,   2,   1,   1,   2,  -1,   5,
     10,  -1,   3,   2,   2,   3,  -1,  10,
    -25, -50,  -1,  -1,  -1,  -1, -50, -25,
    100, -25,  10,   5,   5,  10, -25, 100,
];
Enter fullscreen mode Exit fullscreen mode

Corners are +100, X-squares (diagonal adjacents to corners) are -50 because occupying them too early lets the opponent take the corner. Add a 5-points-per-legal-move mobility term. Result: the AI plays corner-hunting, X-square-avoiding, mobility-aware Othello at depth 4.

Why skip wasm-bindgen

wasm-bindgen is lovely when you need to pass strings and structs across the Rust/JS boundary. My engine's API is:

#[no_mangle] pub extern "C" fn reset();
#[no_mangle] pub extern "C" fn legal_moves_bits() -> u64;
#[no_mangle] pub extern "C" fn apply_move(pos: u32) -> u32;
#[no_mangle] pub extern "C" fn ai_choose_move(depth: u32) -> u32;
#[no_mangle] pub extern "C" fn black_discs() -> u64;
#[no_mangle] pub extern "C" fn white_discs() -> u64;
Enter fullscreen mode Exit fullscreen mode

Pure POD, no references, no strings. The JS side just calls the exports:

const res = await fetch('./assets/reversi.wasm');
const { instance } = await WebAssembly.instantiate(await res.arrayBuffer(), {});
const engine = instance.exports;

engine.reset();
const legal = engine.legal_moves_bits();  // returns a BigInt for u64
engine.apply_move(pos);
const ai = engine.ai_choose_move(4);
Enter fullscreen mode Exit fullscreen mode

No generated .js glue file, no import maps, no npm dependencies. The .wasm is all there is.

Release profile + no_std

Cargo.toml release profile is what squeezes 3.7 KB out of the binary:

[profile.release]
opt-level = 3
lto = true
codegen-units = 1
panic = "abort"
strip = true
Enter fullscreen mode Exit fullscreen mode

Plus #![no_std] and #![no_main] drop the entire std runtime. You provide your own panic handler:

#[cfg(not(test))]
#[panic_handler]
fn panic(_: &PanicInfo) -> ! { loop {} }
Enter fullscreen mode Exit fullscreen mode

The #[cfg(not(test))] exists because cargo test needs std (test's own harness is built on std), and std already defines panic_handler. The conditional lets the same source file build both ways:

#![cfg_attr(not(test), no_std)]
#![cfg_attr(not(test), no_main)]
Enter fullscreen mode Exit fullscreen mode

I want cargo test to work so I can run unit tests on the pure game logic without needing a browser.

Tests as the bug-catcher

Seven unit tests covering:

  • Initial position has 4 disks, 2-2
  • Black's opening has exactly four legal moves (d3, c4, f5, e6)
  • Playing d3 flips d4 (3 black, 1 white, white's turn)
  • An illegal move returns 0 and doesn't change state
  • AI at depth 2 returns a legal move from the starting position
  • AI takes a corner when only that move is available
  • Pass fails when legal moves exist

I wrote the direction-shift mask (NOT_A_FILE vs NOT_H_FILE) wrong on the first try and the "opening has four legal moves" test caught it in 200 ms. Bitboard bugs are merciless — an off-by-one file mask wraps bits across rows and the whole game gets surreal — but they also tend to fail catastrophically the moment you test them, which is great for fast iteration.

Takeaways

  1. Othello is a showcase for bitboards. Seven lines of shift-and-AND give you legal moves in all eight directions, and the same structure does disc flipping.
  2. Raw WASM is viable for POD-only APIs. WebAssembly.instantiate is three lines; you don't need a toolchain pipeline for a small, pure engine.
  3. no_std + strip = true + panic = abort cuts Rust binaries by an order of magnitude when you don't need the runtime.
  4. #[cfg(not(test))] on your panic handler lets you dual-build: wasm-no_std for the browser, std-with-tests for cargo.
  5. BigInt is your friend on the JS side: wasm u64 exports come back as BigInt, so use (legal & (1n << BigInt(i))) !== 0n for bit testing.

Repository: https://github.com/sen-ltd/reversi-wasm

Top comments (0)