6 ms·

Solving a Childhood Mystery: How BASIC Games Learned to Win

73 points by greentec 1y ago

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.

deleted 1y ago
[deleted]
michalpleban 1y ago
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 1y ago
  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.
  - michalpleban 1y ago
    OK, that makes sense - the game has a better playability if it starts on an average level and "learns" over time.
    - kragen 1y ago
      No, that's not why. The comment you're replying to gave a different reason that it was done that way. That comment explained, twice, that it's not merely, or even primarily, to improve the game's playability; it was to serve as an executable demonstration of the matchbox learning algorithm. 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.
      - zahlman 1y ago
        > Martin Gardner's popularization of Donald Michie's work on the algorithm. I remember reading this, but for the life of me I can't recall what the title of the book was. ISTR it also had a chapter exploring multi-dimensional spaces, in particular the problem of packing hyperspheres into hypercubes.
        kragen 1y ago
        I can't keep his book titles straight.
  - ljf 1y ago
    I would have previously agreed (that there is nothing quite like it these days) - but my son is now part of an online games coding club. They start off assembling ready made 'Scratch' instructions, and playing at tweaking them. In later lessons they then start to write their own Scratch recipes, before moving to Python libraries then writing Python directly. So far I've been really impressed with the materials, then tutors and the games they've made. For what he has learnt, and the support they also provide outside of the lessons, £50 a month feels pretty cheap.
    - glimshe 1y ago
      Forgive me, but I don't think scratch is all that good - my son did it too. I never liked these super simplified approaches to computing because I don't think they are necessary. Scratch wouldnt be that useful in the 80s. BASIC, despite its flaws, was both simple and powerful. You could code in the same language as many pros from the get go.
      - ljf 1y ago
        Yeah Scratch has a lot of limitations - but as an introduction to the concepts, it has been amazing. Watching him be able to build a game that he enjoyed on day one, then by maybe 6 lessons later to be using Python - has been great. I'm not a coder so it is not something I could help with (I play with Arduino etc. but I don't know python). But getting the early simple lessons to explain how changing variables affects the game, and how to run things in sequence, has been really powerful for him.
        glimshe 1y ago
        You can learn a lot from Scratch, that's for sure. I'm not saying it's bad, it's actually a decent learning tool. But I think it's a step back from BASIC. You could code a ton of fairly decent games, utilities and even full applications in BASIC. While that's theoretically possible in Scratch, it's a lot more cumbersome. Scratch feels more like a puzzle game than a real programming language. BASIC, especially the later, better dialects, could do it all. With 2 very understandable lines: 10 PRINT "glimshe rulez!" 20 GOTO 10 You could teach that the computer is under your command and you can ask it to do work for you nonstop. It teaches a bit of I/O, program sequence and loops. No stupid "main" functions, indentation nonsense, cryptic library includes or cumbersome drag-and-drop. The simplicity of the code above is one of the treasures of computing history. 90% or more of humanity can quickly understand these two lines and I super disagree with Dijkstra about BASIC. It was at the same time a teaching tool and a professional programming language (although, arguably, not amazing at that).
- firesteelrain 1y ago
  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.
- deleted 1y ago
  [deleted]
Mountain_Skies 1y ago
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.
mlvljr 1y ago
[dead]
kragen 1y ago
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-his-classic-computing-publications-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_Microcomputer_Edition_1978_Creative_Computing/Basic_Computer_Games_Microcomputer_Edition_1978_Creative_Computing.pdf#page=98 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.
louthy 1y ago
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 1y ago
  I was a programmer a decade before my first Hello World!
- ryoshu 1y ago
  Using Norton Utilities 1.0's hex editor to read and change save files for Moria :)
JLemay 1y ago
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 1y ago
  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.
jerf 1y ago
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 https://www.youtube.com/watch?v=R9c-_neaxeU
diggernet 1y ago
> 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 1y ago
  I didn't realize that! Thanks for the clarification.
jgalt212 1y ago
PDF of Gardner's Scientific American article on HEXAPAWN. https://people.csail.mit.edu/brooks/idocs/GardnerHexapawn.pdf https://people.csail.mit.edu/brooks/idocs/GardnerHexapawn.pd...
reverendsteveii 1y ago
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.

73 points by greentec 1y ago

deleted 1y ago

[deleted]

michalpleban 1y ago

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 1y ago
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.
- michalpleban 1y ago
  OK, that makes sense - the game has a better playability if it starts on an average level and "learns" over time.
  - kragen 1y ago
    No, that's not why. The comment you're replying to gave a different reason that it was done that way. That comment explained, twice, that it's not merely, or even primarily, to improve the game's playability; it was to serve as an executable demonstration of the matchbox learning algorithm. 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.
    - zahlman 1y ago
      > Martin Gardner's popularization of Donald Michie's work on the algorithm. I remember reading this, but for the life of me I can't recall what the title of the book was. ISTR it also had a chapter exploring multi-dimensional spaces, in particular the problem of packing hyperspheres into hypercubes.
      - kragen 1y ago
        I can't keep his book titles straight.
- ljf 1y ago
  I would have previously agreed (that there is nothing quite like it these days) - but my son is now part of an online games coding club. They start off assembling ready made 'Scratch' instructions, and playing at tweaking them. In later lessons they then start to write their own Scratch recipes, before moving to Python libraries then writing Python directly. So far I've been really impressed with the materials, then tutors and the games they've made. For what he has learnt, and the support they also provide outside of the lessons, £50 a month feels pretty cheap.
  - glimshe 1y ago
    Forgive me, but I don't think scratch is all that good - my son did it too. I never liked these super simplified approaches to computing because I don't think they are necessary. Scratch wouldnt be that useful in the 80s. BASIC, despite its flaws, was both simple and powerful. You could code in the same language as many pros from the get go.
    - ljf 1y ago
      Yeah Scratch has a lot of limitations - but as an introduction to the concepts, it has been amazing. Watching him be able to build a game that he enjoyed on day one, then by maybe 6 lessons later to be using Python - has been great. I'm not a coder so it is not something I could help with (I play with Arduino etc. but I don't know python). But getting the early simple lessons to explain how changing variables affects the game, and how to run things in sequence, has been really powerful for him.
      - glimshe 1y ago
        You can learn a lot from Scratch, that's for sure. I'm not saying it's bad, it's actually a decent learning tool. But I think it's a step back from BASIC. You could code a ton of fairly decent games, utilities and even full applications in BASIC. While that's theoretically possible in Scratch, it's a lot more cumbersome. Scratch feels more like a puzzle game than a real programming language. BASIC, especially the later, better dialects, could do it all. With 2 very understandable lines: 10 PRINT "glimshe rulez!" 20 GOTO 10 You could teach that the computer is under your command and you can ask it to do work for you nonstop. It teaches a bit of I/O, program sequence and loops. No stupid "main" functions, indentation nonsense, cryptic library includes or cumbersome drag-and-drop. The simplicity of the code above is one of the treasures of computing history. 90% or more of humanity can quickly understand these two lines and I super disagree with Dijkstra about BASIC. It was at the same time a teaching tool and a professional programming language (although, arguably, not amazing at that).
firesteelrain 1y ago
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.
deleted 1y ago
[deleted]

Mountain_Skies 1y ago

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.

mlvljr 1y ago

[dead]

kragen 1y ago

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-his-classic-computing-publications-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_Microcomputer_Edition_1978_Creative_Computing/Basic_Computer_Games_Microcomputer_Edition_1978_Creative_Computing.pdf#page=98 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.

louthy 1y ago

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 1y ago
I was a programmer a decade before my first Hello World!
ryoshu 1y ago
Using Norton Utilities 1.0's hex editor to read and change save files for Moria :)

JLemay 1y ago

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 1y ago
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.

jerf 1y ago

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 https://www.youtube.com/watch?v=R9c-_neaxeU

diggernet 1y ago

> 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 1y ago
I didn't realize that! Thanks for the clarification.

jgalt212 1y ago

PDF of Gardner's Scientific American article on HEXAPAWN. https://people.csail.mit.edu/brooks/idocs/GardnerHexapawn.pdf https://people.csail.mit.edu/brooks/idocs/GardnerHexapawn.pd...

reverendsteveii 1y ago

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.