Solving a Childhood Mystery: How BASIC Games Learned to Win

As a teenager, I had this BASIC Computer Games book with a game called HEXAPAWN. Lines 900-970 were just cryptic numbers that made no sense to me. Finally figured it out decades later.

Turns out it's machine learning from the 1970s! The AI learns by literally deleting bad moves from an array. After losing ~10 games, it becomes unbeatable. Just 19 board states, no neural networks, no fancy algorithms.

Martin Gardner (who wrote about it) also mentioned MENACE - a tic-tac-toe learning machine made with matchboxes and beads. Same principle, physical implementation.

Made a JavaScript version if anyone wants to try. The AI really does get better.

Solving a Childhood Mystery: How BASIC Games Learned to Win
sublevelgames.github.io

People bought the book to not only play, but also learn from simple games. There's nothing quite like it nowadays.

It gives a sense of intelligence the way it’s played now but it’s a simple algorithm.

Eventually the computer runs out of things to remove and it has to give up.

The blog post explained that the game derived from Martin Gardner's popularization of Donald Michie's work on the algorithm.

The output of the program also outlines the algorithm, using a series of PRINT statements.

Finally, the explanatory text in the book also explains the algorithm, in somewhat more depth.

Like many of the games in the book, it had a didactic purpose. It's not about improving playability.