game-solver

A chess engine looks for a good move in a given time. A solver looks for something else: the exact value of the position, under the assumption that nobody makes another mistake. These are two trades, and the second only returns an answer once it has proved it.

Two games run today: tic-tac-toe, which fits in a handful of nodes, and Connect 4, which is the real target. The method is a memoised negamax alpha-beta, compiled to WebAssembly from AssemblyScript and spread across a pool of workers, one per core, one column each, with a JavaScript fallback if WASM is missing. Each possible move then gets its exact label: wins, loses, or draws.

That is where combinatorics makes itself felt. Analysing the empty Connect 4 position costs about ten minutes, which is untenable in an interface: per-move analysis therefore only starts at the seventh move played, and before that the solver settles for a safe heuristic, play the centre and never enter a losing line. The budget is capped at eight million nodes per worker.

Correctness is not judged by eye on this kind of program: test positions are checked against Pascal Pons’ reference solver, which gives the attested value. A solver that is silently wrong is more troubling than a mediocre engine, since it claims to prove.