I listened to the champion's lecture — and won with a 2 MB bitmask

At Progmeistars there was a tournament of computer programs: each round had a game, and the contestants’ programs played it against each other. My entry for the 11th tournament played “matrix poker”: a 5×5 board, 25 cards with digits 0–4, players take turns placing them, and each owns five lines plus a diagonal that score like poker hands. My program played greedily for most of the game — improving its own lines and spoiling the opponent’s — and switched to a full search for the last seven cards. The comment at the top of the source says it all: “the computer beat me.”

One of the teachers won these tournaments again and again. One day he gave a lecture on how to write such programs properly — minimax and how to make the search fast.

I listened, took his advice into the next tournament — and won the 12th Tournament of Computer Programs in 2003.

The game was played on an 8×6 board. Players took turns covering neighbouring cells with strips — mostly two cells long, plus three strips of three; the game ended when no free space was left. Full search over that board was out of reach, so the plan was to cheat the size of the problem:

1. Get rid of the three-cell strips early, so that only two-cell moves remain.
2. Split the board in two. Once the middle columns are filled, the left and right halves are independent games, each 4×6 — just 2²⁴, about 16 million, possible positions.
3. Precompute every half. For each of those 16 million positions the program knew, under the opponent’s best play, whether the number of remaining moves was even or odd. One bit per position: the whole table fit in a 2 MB file of bitmasks.
4. Play by parity. With two independent halves, the right move is the one that makes the combined parity work out in your favour — a lookup, not a search.

The matches were run by hand: the teacher started two programs on two computers and carried the moves from one to the other. What surprised him most was that by the second or third move my program was already announcing, with near certainty, that it would win.

What stayed with me: the best optimisation is often not a faster search but a different representation — split the problem into independent parts and precompute what never changes.