In 2003, Alvin Albrecht wrote a Minesweeper for the TS2068 in C, built with z88dk. Porting the Windows game to a Z80 was the easy half.
The half he cared about was getting the computer to play it well, and to play it honestly: every move reasoned from the numbers on the board, never from the mines hidden underneath.
He sent along a note on how he got there, and it reads like a tour of three roads, two of them dead ends. The first was a probabilistic model, abandoned as too complicated.
The second was tidier: treat each revealed number as a linear equation, the squares around it summing to the mine count, and solve the whole system by Gaussian elimination. The trouble is that a square is either a mine or it isn’t, one or zero, and ordinary elimination is happy to hand you a one-half. The arithmetic doesn’t know the rules of the game.
So Alvin turned to Boolean algebra, where one and zero are the only values on offer. Each revealed number becomes a statement listing every mine arrangement consistent with it — a “2” with three unknown neighbors allows three of them — and exactly one is true.
As more squares open, their statements get ANDed together, and contradictory arrangements cancel. Now and then a square is a mine in every arrangement that survives, which means it is a mine, full stop. In one of his examples a square is forced exactly this way; as Alvin put it, the math doesn’t lie.
When nothing is forced, the same expression yields the odds on each square, so the program guesses safely rather than blindly.
The part that makes me sit up is how he handled the Boolean side: reduced ordered binary decision diagrams. ROBDDs are a workhorse of hardware verification, the reduced ordered form introduced by Randal Bryant in 1986 — not the sort of thing one expects to meet inside a 1983 home computer.
Alvin reckoned his was the first time anyone had run them on an 8-bit machine.