The Go Program That Taught Chess Engines to Remember

In 1970 a graduate student named Albert Zobrist wrote a technical report with a flat, forgettable title — A New Hashing Method with Application for Game Playing — and folded into it was the trick that half the world’s board-game engines now run on. He wasn’t thinking about chess. He was writing a program to play Go, and he needed a fast answer to a question the game asks constantly: have I seen this exact board before?

Go’s rules forbid recreating an earlier whole-board position (that’s the ko and superko business). A 19×19 board has 361 points, each empty, black, or white, and comparing full boards point-by-point is slow. Zobrist’s move: hand every (point, colour) pair a random 64-bit number, and let a position’s fingerprint be the XOR of all its stones’ numbers.

import random
random.seed(1)
SIZE = 9
# a random 64-bit key per (point, colour); 0 = black, 1 = white
Z = [[random.getrandbits(64) for _ in range(2)] for _ in range(SIZE * SIZE)]

def toggle(h, point, colour):     # place OR remove: XOR is its own inverse
    return h ^ Z[point][colour]

h = 0
h = toggle(h, 40, 0)              # black plays the centre point, tengen
h = toggle(h, 41, 1)              # white answers to the right
print(hex(h))
h = toggle(h, 41, 1)              # white gets captured: same XOR erases it
print(hex(h))

The good behaviour falls out of XOR being its own inverse. Placing a stone folds its key into the hash; capturing that same stone folds the identical key back out, and you land exactly where you started — no rescanning the board, just one integer operation.

const std = @import("std");

pub fn main() void {
    var prng = std.Random.DefaultPrng.init(1);
    const rand = prng.random();
    var z: [81][2]u64 = undefined;            // a key per (point, colour)
    for (&z) |*point| for (point) |*colour| {
        colour.* = rand.int(u64);
    };

    var h: u64 = 0;
    h ^= z[40][0];                            // black on tengen, the centre
    h ^= z[41][1];                            // white answers to the right
    std.debug.print("{x}\n", .{h});
    h ^= z[41][1];                            // capture white: the XOR undoes it
    std.debug.print("{x}\n", .{h});
}

Look at the second line of each run: once white is lifted off, the hash returns to what it was with only black on tengen. Same 64 bits whether you reached that shape by playing one stone or by playing three and capturing two.

I’m glossing over one cost — two different positions can collide on the same 64-bit value. With decent random keys the odds are minuscule, and engines take the gamble because a transposition-table lookup becomes a single integer compare instead of a board scan.

Sitting at the goban tonight, I watched a group lose its last liberty and come off the board. Three stones gone, and the position was suddenly one I’d have recognized a few moves earlier. That’s the operation Zobrist built for: the stones came off, and the number slid back to where it had been.