|
a chess engine for one PowerPC 604e [ home | fractals | archaeology | language model | chess | neural net ] Deep Blue beat Garry Kasparov in 1997 with a 30-node RS/6000 SP and 480 custom chess chips, searching about 200 million positions a second. This is the single-node answer. Lite Blue is a chess engine I wrote for obsidian, this one 250 MHz PowerPC 604e: the same alpha-beta spirit, one processor and no chips, searching about 33,000 positions a second. Where Deep Blue won by searching more nodes than a human, Lite Blue has to win its strength back by searching better ones, because the silicon is simply not there. The name is a joke about the scale, and it is an honest one.
Everything runs on obsidian itself. It is written in portable C89 and builds unmodified with XL C 5.0.2 and GCC 2.95.3, on the machine and off it. All the numbers below were measured on the 604e.
How it is built. The position is a 0x88 mailbox, not bitboards: the 604e is a 32-bit machine with no fast 64-bit integer path, so the usual bitboard advantage inverts here. The search is classic negamax alpha-beta with iterative deepening, quiescence search, null-move pruning, late-move reductions, principal-variation search and killer/history ordering - not MCTS, which would starve on one scalar core. The transposition table entries are packed into exactly 16 bytes so a table sized to the 604e's 1 MiB L2 cache fits without spilling to DRAM. The evaluation is hand-tuned: material, piece-square tables, a tapered king, a pawn-shield king-safety term and pawn structure; a small learned evaluation is the next experiment, not the first. CorrectnessMove generation is validated with perft against the standard test positions, with the incremental Zobrist key recomputed and compared at every internal node. Position 3 runs to depth 6 - 11,030,083 nodes - and matches exactly. The identical perft and search node counts under XL C and GCC are further evidence that the engine is deterministic and free of undefined behaviour. Measured on the 604e
A game it played against itself (500 ms a move, searching 5-8 ply):
Measured improvements Changes are measured with a match harness: two engine builds play the same set of 512 opening positions with both colours, and the score gives an Elo difference (about +/-30 at that sample size). Against 1.0.0, the king-safety term (1.1.0) is worth about +50 Elo, and pawn structure (1.2.0) about +35. Search pruning and null-move, by contrast, landed in the noise - a reminder that a measured number beats a guess. What this is notLite Blue is roughly club strength, not a giant. Its evaluation is hand-tuned - material, piece-square tables, a tapered king, a pawn-shield king-safety term and pawn structure - so it now castles instead of walking its king up the board, but there is still no opening book, no tablebases and no endgame knowledge beyond king activity. It is honest about being symbolic alpha-beta search; nothing here is learned, and I make no claim that it is. FilesVersion 1.2.1 - liteblue-1.2.1.tar.gz (source, MIT licence; also at github.com/nfinit/liteblue) NOTES.md (design and measurements), PLAYING.md (how to play), search.c, board.c, movegen.c, eval.c, tt.c, liteblue.c (UCI), Makefile. |