Algorithms are a hot topic of conversation, as Facebook, er, Meta, finds itself criticized for employing algorithms that promote anger and strife for the purpose of increasing customer engagement with the website.
But it is difficult to drill into algorithms to see exactly how they work, especially very complex social media algorithms. The magnitude of this challenge is illustrated by University of Calgary researchers John Aycock and Tara Copplestone’s paper, “The Art, Science, and Engineering of Programming."
The paper examines an Atari 2600 console game from 1982 called “Entombed.” This vertically scrolling game generated a maze in real time as the player progressed through catacombs, but the algorithm that creates the solvable maze on the fly using the Atari’s minimal computing resources has modern programmers scratching their heads.
The game’s manual introduces it like this: “You and your team of archeologists have fallen into ‘the catacombs of the zombies.’ The longer you survive, the faster you have to move.”
As a reminder, the Atari 2600 console, like the Apple II and Commodore 64 PCs, was powered by a MOS Technologies 6507 processor. It ran at 1.19 MHz and had 128 bytes of RAM on a MOS 6532 RAM, I/O, and Timer (RIOT) chip. Bytes. Not gigabytes, megabytes, or even kilobytes. The game cartridges brought with them 4 kilobytes of ROM that held the game.
The 2600’s last chip was a Television Interface Adapter. As Aycock and Copplestone explain, “A 2600 programmer had to structure their code to render the display on a line by line basis and repeat that for every single video frame.”
Working within these constraints demanded that the game generate a new maze on the fly every time because there was no space to store an existing maze design. Indeed, the paper explains that “The programming challenges are noted by former 2600 programmers in interviews. John Harris said ‘The way the machine had to be programmed was so obscure and so challenging that you had to write extremely optimal code.’”
So optimal, it seems, that in the case of the maze-generating algorithm, no one can figure out how the table that creates it works today. Programmer Paul Allen Newell remembers its creation this way: ‘Duncan and I went out for a beer and ended up coming up with this “problem” of wondering whether one could generate an endless maze that always had a solution and that ‘We worked out the algorithm and [...] I spent a weekend coding something up.’”
Newell’s colleague Steve Sidley remembers it this way: ‘The basic maze generating routine had been partially written by a stoner who had left. I contacted him to try and understand what the maze-generating algorithm did. He told me it came upon him when he was drunk and whacked out of his brain, he coded it up in assembly overnight before he passed out, but now could not for the life of him remember how the algorithm worked.’”
It is no surprise to Sidley that today’s engineers don’t know how the game’s maze is generated because he couldn’t figure it out at the time. “It was a mystery to me too,” he said. “I couldn’t unscramble it. I just used it to generate the new [maze] row at the bottom of the screen.”