MOCHI¹ has gained a move generator! For every possible chess position, the move generator can find all valid moves.

Unsurprisingly, handling pawns were the trickiest part: they move in a different way than they take, they promote to another piece when they reach the farthest rank and there is the infamous en passant rule (yes, en passant memes are a thing²).

However, surprisingly, the code was correct almost on the first try! There were just two easy to fix logic bugs in the castling code. An earlier version of the code allowed castling despite the rook being taken before (d’oh) and I’ve had a wrong extra condition on squares that must not be attacked.

Talking about correctness… how do I know the code is (likely) correct?

It turns out there is a strategy called PERFT. From the chess programming wiki³:

Perft, (performance test, move path enumeration)
a debugging function to walk the move generation tree of strictly legal moves to count all the leaf nodes of a certain depth, which can be compared to predetermined values and used to isolate bugs.

The chess programming wiki has PERFT results for six sample positions⁴. I’ve computed all of them to depth 6⁵: that’s a whopping 19 319 136 242 positions and the numbers all match the known results!

Performance is also sort of decent (about 2M positions per second on a single server thread). High-performance move generators reach a lot more, but given my naive implementation this is better than what I expected :)