Solving a Childhood Mystery: How BASIC Games Learned to Win

[greentec]

Hello HN!

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.

[kragen]

BTW David Ahl has placed all of his work, including this book, into the public domain https://blog.adafruit.com/2022/06/16/david-ahl-places-all-hi... and so we can link to the Hexapawn page in the original book https://dn790005.ca.archive.org/0/items/Basic_Computer_Games...

Unfortunately I do not know of an online source for the Korean edition that so inspired the original poster.

[JLemay]

The 1970s saw the birth of many foundational algorithms and concepts in machine learning, with research focusing on decision tree algorithms, clustering, and ensemble methods. I believe one of the first decision tree algorithms was created in 1973, crazy how early it all started!

[aa-jv]

In the 80's I apprenticed under a greybeard programmer who gave me all the shitty network code to write, while he experimented with neural networks instead of writing "old school" error correction logic for said network code.

I'm grateful for his bikeshedding, because it made me a network programmer and led to a fine career building Internet service providers, but I'll never forget his frustration .. "the computer is simply not big enough, we need to build a bigger computer" .. I wonder where he is these days. Hopefully retired.

[louthy]

Ah, the memories of inputting listings from magazines and books like these, only to find that I’d have one character wrong and the whole thing would fail (and I didn’t know enough to fix it).

The vibe coding of its day! :D

[lubujackson]

I was a programmer a decade before my first Hello World!

[ryoshu]

Using Norton Utilities 1.0's hex editor to read and change save files for Moria :)

[Mountain_Skies]

There was an article in 'The Rainbow' about the tic-tac-toe bead method of machine learning. For some reason, that particular method stuck in my head long after most other things I read in computer magazines of the time faded away. Maybe due to both the simplicity of tic-tac-toe and of the algorithm itself.

[diggernet]

> As an aside, line 511 is entered when it fails to find matching values with the current game state for all 19 boards and flipped boards. It seems like it was originally intended to be a comment using the REM command like 511 REM REMEMBER THE TERMINATION OF THIS LOOP IS IMPOSSIBLE, but perhaps that part was omitted during editing, so it just starts with REMEMBER.

Actually, that line does start with "511 REM". There was no requirement for REM to be followed by a space.

[greentec]

I didn't realize that! Thanks for the clarification.

[jgalt212]

PDF of Gardner's Scientific American article on HEXAPAWN.

https://people.csail.mit.edu/brooks/idocs/GardnerHexapawn.pd...

[jerf]

Matt Parker did a video about a physical implementation of MENACE as part of a museum display for a day: https://www.youtube.com/watch?v=R9c-_neaxeU

[michalpleban]

So basically it has a table of all possible moves, and after losing a game, it deletes a move that led to the defeat? Then why not simply have a smaller table of moves right from the start, with losing moves already removed?

[glimshe]

Because that wouldn't help readers understand how the computer learns with this simple algorithm.

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

[firesteelrain]

How would it learn without playing against the person already?

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.

[reverendsteveii]

this makes me want to rewrite the unbeatable tic tac toe algorithm I wrote back in high school so that instead of starting optimized it just walks through potential game states and eliminates them as it loses.