Like climbing Everest without oxygen

September 24, 2019 3:58 AM

Digital archaeologists John Aycock and Tara Copplestone investigate the Atari 2600 game Entombed; running it under emulation and disassembling the machine code, only to find that nobody understands how the game's maze generation algorithm works. The algorithm, which runs in the limited space of the 2600 (where storing pre-made mazes would not have been viable), leans heavily on idiosyncrasies elsewhere in the code and is driven by a mysterious lookup table, manages to avoid generating any unsolvable mazes; rewriting the algorithm in Python shed no light on it. The original developer of the algorithm was unreachable, but coworkers recount him having been “a stoner” who came up with the logic while “drunk and whacked out of his brain” and coded it before passing out.

Aycock and Copplestone's paper, Entombed: An archaeological examination of an Atari 2600 game, is here.

posted by acb (46 comments total)

The original developer of the algorithm was unreachable, but coworkers recount him having been “a stoner” who came up with the logic while “drunk and whacked out of his brain” and coded it before passing out.

Obviously the solution to dealing with this kind of legacy code is, as always, to recreate the original dev environment as faithfully as possible.
posted by srboisvert at 4:15 AM on September 24, 2019 [77 favorites]

I’ve read enough creepypastas to know this is the premise for a creepypasta
posted by ejs at 4:37 AM on September 24, 2019 [43 favorites]

My sobriety and straight edge lifestyle are holding me back in this arena of endeavor.
posted by jadepearl at 4:38 AM on September 24, 2019 [3 favorites]

I wonder whether there's a mathematics breakthrough waiting there, and whether some mathematician will pick up this paper, do some digging, and end up winning the Fields Medal on the strength of some decades-old drug-influenced 6502 assembly language.
posted by acb at 4:54 AM on September 24, 2019 [10 favorites]

I dunno how true this will for anyone who ISN'T an assembly-language geek, but the article itself is fascinating. With 128 bytes of RAM, and their own home-rolled random number generator (which had a bug that may or may not have been intentionally introduced for this specific purpose), they managed to build an algorithm for building provably-solvable mazes. That algorithm was used for years, and the same buggy RNG found its way into a bunch of other contemporary games because it was so damned clever.

Also, every developer who has been doing this for more than about six months knows all too well the feeling of reading through a block of code, wondering "what clever asshole thought THIS was a good idea?" and then seeing that they're actually the original author.
posted by Mayor West at 5:01 AM on September 24, 2019 [45 favorites]

I wonder whether there's a mathematics breakthrough waiting there, and whether some mathematician will pick up this paper, do some digging, and end up winning the Fields Medal on the strength of some decades-old drug-influenced 6502 assembly language.

This sometimes happens! John Carmack famously came up with a magic number that basically enabled modern 3D gaming (0x5f3759df). There are probably other examples of this that I will remember after I have my coffee!

Seeing how programmer handled processor-intensive gaming with almost zero resources often surfaces some incredibly clever hacks; I love that they've brought an archaeology Ph.D into the fold to help investigate this.
posted by Mayor West at 5:06 AM on September 24, 2019 [15 favorites]

According to Atari design engineer, Al Alcorn, when Atari was on tour promoting the device, a Sears representative asked what the developers were smoking when they invented it. With that, a technician stepped forward holding up a lit joint.

I'm just sayimg this sort of thing isn't totally unprecedented. There was a lot of overlap between hippie/stoner and computer culture in the early days.
posted by Western Infidels at 5:22 AM on September 24, 2019 [9 favorites]

The paper includes the inexplicable table. Now that this has gotten mainstream attention, I think a lot more people are going to try their hand at working it out.

Also, if you have any interest in the Atari 2600, I *highly* recommend Montfort & Bogost's book Racing the Beam.
posted by cheshyre at 5:27 AM on September 24, 2019 [8 favorites]

please please please please tell me the original dev's name is Doug Forcett
posted by lazaruslong at 5:42 AM on September 24, 2019 [31 favorites]

> John Carmack famously came up with a magic number that basically enabled modern 3D gaming (0x5f3759df).

That linked article is really neat but it says that Carmack denied authorship and that Greg Walsh created it.
posted by ardgedee at 5:45 AM on September 24, 2019 [19 favorites]

If you follow enough of the maps precisely enough in the real world, they take you to Carcosa.

“Not upon us, oh King, not upon us!”
posted by GenjiandProust at 6:04 AM on September 24, 2019 [11 favorites]

As a programmer these are often either the most frustrating or satisfying type of projects I’ve been assigned. When you figure it out; it’s pure joy. When you fail; frustrating.
posted by interogative mood at 6:13 AM on September 24, 2019 [1 favorite]

As a non-technical, non-programmer type, I love reading stuff like this. It makes me wish I had become a technical, programmer type.
posted by slogger at 6:15 AM on September 24, 2019 [2 favorites]

LDA #$45 ;hehe
posted by sydnius at 6:20 AM on September 24, 2019 [2 favorites]

Better programming through chemistry!
posted by rmd1023 at 6:26 AM on September 24, 2019 [3 favorites]

I’m sorry but is this not just the plot of House of Leaves
posted by quiet coyote at 7:17 AM on September 24, 2019 [10 favorites]

I've seen code in a Cobol program that calculates figures for invoices. This was very old code and the program had been modified many times by many people, but there was always an added comment just prior to the code which said basically the same in every case.
The comment being : I cannot work out how this works, but it does, so I am not going to touch it.

I added another!! after spending a couple of days trying to work it out.
The original author was (apparently) a smart arse that was often drunk, and had "left" the company.
posted by Burn_IT at 7:40 AM on September 24, 2019 [6 favorites]

There was a lot of overlap between hippie/stoner and computer culture in the early days.

There was a lot of overlap between West Coast microcomputer / home computer / PC culture (which I'd include consoles like the Atari as part of, because it was architecturally similar to a home computer at the time) and hippie/stoner culture. And Emtombed is definitely an artifact of that culture. But there is and was a whole separate software development tradition and associated culture, largely but not exclusively from the East Coast, which was more buttoned-down, more academic, arguably more slow-moving, and centered on developing software for midrange and larger computers. (I suspect the MIT AI Lab still went through its fair share of weed, though, and I bet the pocket protector crowd were no strangers to the occasional three-martini lunch, but who knows.)

The rapid uptake of PCs brought 'West Coast tech' culture into the spotlight, and for better or worse 'startup culture' keeps it there, but I think there's often too much focus on it as the platonic ideal of tech, when in reality it's often a startlingly inefficient way of working. A lot of the 1970s microcomputer programmers spent, in retrospect, a shitload of time reinventing wheels that people in white shirts and pocket protectors had invented, prototyped, published papers on, and sometimes abandoned as dead ends long prior.

It doesn't lead to as much fun 'code archaeology', though, and I'm not against having fun or anything. But just to compare, if you want to see how an IBM programmer would have handled a PRNG implementation, you can just read the IBM Systems Journal paper describing one of the canonical implementations. (Whether you read it drunk or sober is left as an exercise for the reader.)
posted by Kadin2048 at 8:32 AM on September 24, 2019 [8 favorites]

I've seen code in a Cobol program that calculates figures for invoices. This was very old code and the program had been modified many times by many people, but there was always an added comment just prior to the code which said basically the same in every case. The comment being : I cannot work out how this works, but it does, so I am not going to touch it.

I'm an old, old nerd, but even I see comments like this and I'm like: "Ha ha! Cobol!" And then I'm like: "Oh shit. Cobol."
posted by The Bellman at 8:32 AM on September 24, 2019 [11 favorites]

Like climbing Everest without oxygen

So, the Wim Hof method of coding?
posted by filthy light thief at 8:48 AM on September 24, 2019

i mean they were clearly hoffing something
posted by cortex at 8:49 AM on September 24, 2019 [1 favorite]

She says this is an example of a classic conundrum in archaeology. “I think there’s this assumption that when we find things, we know what they are – if we pull a spearhead out of the ground, we know what it is,” she says. “[But] more often than not, we have no idea what’s happening.”

Sometimes I wonder whether the designation of "religious or ritual object" comes from this conundrum. "What's this thing?" "Dunno, which means it must be mystical."
posted by clawsoon at 9:04 AM on September 24, 2019 [2 favorites]

There's a version playable in your browser over at archive.org.
posted by vverse23 at 9:10 AM on September 24, 2019 [2 favorites]

It's not quite the same thing, but there's a whole lot of fascinating video game excavation and archaeology over at The Cutting Room Floor. It's amazing how many old games had things fully built but access removed right before release (the original NES Tetris had a two player competitive mode shipped on the cartridge) or shipped with uncompiled source code on ROM/disk/CD, or even had messages to hackers (like the one in Donkey Kong inviting anyone disassembling the game to call the developer, complete with phone number).

Slightly more on-topic, there are some absolutely fascinating breakdowns of 'kill screens' in some old games (Dig Dug, Galaga, Ms. Pac Man). The coolest thing about these is not only does Don Hodges break down the code and explain why the bugs appear, he then patches the code within the constraints on the original hardware!
posted by fader at 9:31 AM on September 24, 2019 [4 favorites]

Intoxication is not incapacitation.
posted by Mental Wimp at 9:48 AM on September 24, 2019 [5 favorites]

a lot of overlap between hippie/stoner and computer culture in the early days.

As a long time resident of Silicon Valley and the Seattle coding communities, that overlap still exists. A lot more get-rich-quick folks and careerists nowadays, but the stoners are here keeping shit running.

Ol Grandpa Abehammerb will now return to waiting for the next major Linux fleet goof up at ye old company.
posted by Abehammerb Lincoln at 9:50 AM on September 24, 2019 [3 favorites]

But there is and was a whole separate software development tradition and associated culture, largely but not exclusively from the East Coast, which was more buttoned-down, more academic, arguably more slow-moving, and centered on developing software for midrange and larger computers.

Also, weren't a lot of Mormons early adopters of computer technology? I imagine that their coding culture kept well clear of the 60s counterculture.
posted by acb at 9:51 AM on September 24, 2019

Intoxication is not incapacitation.

Specifically, for me, drinking some tequila while working would prevent me from overthinking and over-engineering problems. I could just focus on getting a problem solved and working, even if it was messy.

Now that I think about it, decreased tequila consumption may have led to me despising software development.
posted by bonje at 10:00 AM on September 24, 2019 [2 favorites]

That linked article is really neat but it says that Carmack denied authorship and that Greg Walsh created it.

D'oh! Teach me to link anything before coffee. You're totally right, it was Greg Walsh's amazing discovery, not Carmack.
posted by Mayor West at 10:22 AM on September 24, 2019 [1 favorite]

Sometimes I wonder whether the designation of "religious or ritual object" comes from this conundrum. "What's this thing?" "Dunno, which means it must be mystical."

cf. Motel of the Mysteries
posted by The Tensor at 10:58 AM on September 24, 2019 [5 favorites]

OMG The Tensor... I remember seeing that in a Readers Digest or some such when I was 10 or 11 or so (based on date). It was hilarious.

I totally suffer from the sole programmer of the department and just eventually started assuming the code I read was actually something that I wrote long ago. It's weird going from "who's this idiot" to "ok, I'm starting to get the gist" to "fuck, that's old me" and it's still sorta the same thing I'd do if I had to do it again. I should really learn to at least put a note to my future self to give me a bit of warning.

I once wrote this tool (named 'grok' natch) that would do everything that a dozen other tools would do. Of course it was something of a Forth-like DSL using the arguments. Of course I couldn't actually document or explain how it worked to my co-workers and thus had to keep maintaining the other dozen tools. Such a shame, it was awesome but unexplainable.

This harkens back to The Jargon file story of some old hacker using how fast the rotating drum of memory could turn to do timing on I/O functions. Don't wait, just jump to an instruction that will take the right amount of time to reach and the data will be waiting when you get there. Too Clever For Their Own Good.
posted by zengargoyle at 11:44 AM on September 24, 2019 [1 favorite]

The Jargon file story of some old hacker

I will not stand by and hear Mel, a Real Programmer described thusly.
posted by Mr. Bad Example at 12:23 PM on September 24, 2019 [12 favorites]

This sort of thing pleases me immensely; would that all hacking were so innocent.

(What does it cost to lure a dope-smoking Unix guru to Dayton?)
posted by praemunire at 4:18 PM on September 24, 2019

If you like mazes and retro computing and exhaustive discussions of how both are intertwined with mythology, history and popular culture, I recommend Nick Montfort's 10 PRINT CHR$(205.5+RND(1));:GOTO 10.
posted by some little punk in a rocket at 7:13 PM on September 24, 2019 [3 favorites]

This reminds me of NASA's weird antennae that were designed through evolutionary algorithms.
posted by porpoise at 7:43 PM on September 24, 2019

D'oh! Teach me to link anything before coffee.

No need! We've removed the need to link!
posted by hexaflexagon at 7:51 PM on September 24, 2019

Specifically, for me, drinking some tequila while working would prevent me from overthinking and over-engineering problems. I could just focus on getting a problem solved and working, even if it was messy.

Code drunk, refactor sober.
posted by acb at 1:25 AM on September 25, 2019 [4 favorites]

For a detailed account of the prehistory of the personal computer and how the counter-culture was integral to the birth of the PC, read What the Doormouse Said.
The vision that lead to the PC started after WW2. In 1945 Vannevar Bush published a paper titled "As We May Think" about the Memex concept, a conceptual design for a personal automated information system.
Shortly after "As We May Think" was originally published, Douglas Engelbart read it, and with Bush's visions in mind, commenced work that would later lead to the invention of the mouse. Ted Nelson, who coined the terms "hypertext" and "hypermedia", was also greatly influenced by Bush's essay.
Many key players were in the area around Stanford University and there was overlap between the emerging computer technology and the emerging counter-culture, including the use of drugs. The anti-Viet Nam war movement also had a major impact.
Xerox PARC, Apple and IBM did not create the PC from scratch. The fundamental concepts were being invented in what is now Silicon Valley starting in the 1950s. Sex, drugs and rock and roll were a part of the mix.
posted by Metacircular at 1:51 AM on September 25, 2019 [2 favorites]

For a detailed account of the prehistory of the personal computer and how the counter-culture was integral to the birth of the PC, read What the Dormouse Said.

Seconded.
posted by acb at 2:49 AM on September 25, 2019

(What does it cost to lure a dope-smoking Unix guru to Dayton?)

$20, same as in town.
posted by Gelatin at 6:57 AM on September 25, 2019 [2 favorites]

Here's the table as a graphic.

The article oversells it a little I think, the algorithm produces nice paths, but there are fairly regular dead ends that are part of the gameplay. It's still cool that it works so well, but the paper has unblown my mind a bit.
posted by lucidium at 10:04 AM on September 25, 2019 [1 favorite]

Honestly, it feels like a simplified Conways Game of Life. I mean, it's actually simplified, but it has a similar cellular automata feel, only draws down instead of iterating on the same cells. It's clearer if you play the game linked above, and certainly very clever.

Re: The inverse square stuff above: previously and an attached article from said previous.
posted by lkc at 10:59 AM on September 25, 2019

Obviously the solution to dealing with this kind of legacy code is, as always, to recreate the original dev environment as faithfully as possible.

WORKSFORME
posted by mikelieman at 11:19 AM on September 25, 2019 [1 favorite]

Honestly, the table itself doesn't seem all that inexplicable. If you look at all the cases where the a and b bits are not both set and squint, it looks like it depends only on bits c,d,e with some random sprinkled in. If you try there non random version of that, it quickly creates completely filled rows, then alternates filled and empty rows. To prevent that, check bits a and b and if both are set, you might be filling the whole row, so do something different. The make some cells random for variety.
posted by eruonna at 11:42 AM on September 25, 2019 [2 favorites]

And (I think I've done this correctly send help) here's a graph.
posted by lucidium at 12:03 PM on September 25, 2019 [1 favorite]

I'm annoyed that they completely omitted how they transfered the ROM chip data to a modern system, which makes me suspect that they did, in fact, not do it at all.

I suspect they simply downloaded the ROM file from a romsite somewhere on the internet, and assumed it would match the content of the cart in their possession. That's not proper archaeology.

That being said, it is an impressive analysis, but I hope future research in other titles do it the "proper" way by dumping the ROM content of the actual cartridges in question.
posted by ymgve at 5:12 PM on September 26, 2019