The BBC has posted a story, The mysterious origins of an uncrackable video game, which describes the investigation by two Game Archaeologists into the Atari 2600 game "Entombed".
The article is a narration of the story outlined in the abstract: Entombed: An archaeological examination of an Atari 2600 game (DOI: https://doi.org/10.22152/programming-journal.org/2019/3/4) and full article (pdf):
The Atari 2600 was an extremely limited device with 128 bytes of RAM, a scaled down version of the venerable 6502 processor called the 6507 which had only 13 address liness restricting it to 8 kB of addressable memory, no interrupt processing, and it had no frame buffer, so each line of pixels to be displayed had to be calculated in real time — racing the beam — so being limited to exactly 76 machine cycles per line. The paper succinctly puts it: "Given that 6507 instructions all take two or more cycles, there was no room for inefficiency."
As if that were not enough of a challenge, there were no libraries in ROM, all code had to be hand-crafted. No programmer documentation meant that to even get started programming, one had to reverse engineer how the 2600 even worked.
The word "uncrackable" in the title is not of the crypto flavor one would normally assume, but instead of the "How did they come up with that?" variety. Specifically: create a scrolling maze that had a path through it, all with the aforementioned hardware limitations.
The part that defies understanding is how did the programmer ever conceive of — and go about implementing — an algorithm that only needed to know the values of 5 neighboring pixels and a 32-entry lookup table?
| c | d | e | |||
| a | b | X |
In this case a pixel was either on (1=wall) or off (0=no wall).
Given the values of a, b, c, d, and e: compute the value of X: wall, no wall, or random().
The actual journal article goes into considerable depth as to how they deduced this code and even went so far as to write Python code to implement it which they included in an appendix.
As the BBC put it:
It seems straightforward, but the thing is, no-one can work out how the table was made.
Aycock and Copplestone have tried retro-engineering the table. They looked for patterns in the values to try and reveal how it was designed, but this was to no avail. Whatever the programmer did, it was a stroke of mild genius. Every time the game is played, a reliably navigable maze is pumped out. Were the table’s values random or even slightly different, the maze would likely fail to be drawn with a playable path through it. It just seems impossible to explain.
[...] The best guess the pair have is that the programmer behind the maze algorithm must have manually fine-tuned the table values until the game worked as desired, but that still doesn’t really explain the logic behind it.
(Score: 3, Interesting) by zugedneb on Wednesday September 25 2019, @08:16AM (6 children)
I know many of u read the site, so some mey remember it...
Anyways, in the old days, there was a guy who had to make a program for some sort of card playing machine at casino, and the actual code was encoded mechanincally onto a spinning wheel. Not harddrive.
Sombody later got a job to transfer that particular code to electronics, if i remember correct, but could not in the beginning understand how it worked.
Later, he seys, he found that the actual rotation time of the wheel was a part of the code, so certain loops or conditions did not have to bee terminated, but fell of the edge naturally, and the code continued from a different part of the wheel, depending on the conditions...
The words he used was "The light nearly blindid me when it came..." or some such...
Anyways, he was impressed as hell...
I can not give link, since this wasy some years ago...
old saying: "a troll is a window into the soul of humanity" + also: https://en.wikipedia.org/wiki/Operation_Ajax
(Score: 5, Informative) by gringer on Wednesday September 25 2019, @08:54AM (3 children)
http://www.catb.org/~esr/jargon/html/story-of-mel.html [catb.org]
Ask me about Sequencing DNA in front of Linus Torvalds [youtube.com]
(Score: 1) by zugedneb on Wednesday September 25 2019, @09:08AM (1 child)
I got "some parts" wrong, but i think it is at _least_ 15 years ago i read that story, more likely 20...
I was just plain text then, not in form of poetry, but whatever...
I wish i saved all the old anecdotes i read in the old days of the net... They are difficult to find nowdays...
Thanks =)
old saying: "a troll is a window into the soul of humanity" + also: https://en.wikipedia.org/wiki/Operation_Ajax
(Score: 3, Interesting) by choose another one on Wednesday September 25 2019, @09:47AM
> I got "some parts" wrong, but i think it is at _least_ 15 years ago i read that story, more likely 20...
I first read it over 30yrs ago, along with Real Programmers Don't Use Pascal, but I knew instantly from your first post what you were referring to.
I admit that I have however had to refresh my memory a few times over the decades to prevent fading - it's amazing how prescient those long ago humorists were:
(Score: 2) by hendrikboom on Thursday September 26 2019, @01:08AM
Reminds me of the Bendix G15-D. Also a main memory is a drum machine. Only all the registers were on the drum, too. The contents of the drum were constantly being read and rewritten as the drum revolved, so it functioned as a delay line -- the delay being one drum revolution. Well, not quite, because the read and write heads weren't in the same location. In between those read and write heads were another pair of heads to copy the registers onto and off of the drum, but these were spaced so the delay between writing and reading was the time for one machine work or two or four to pass by.
I completely recognized the every-instruction-is-a-jump situation. One interesting difference -- there were also instructions that ran continuously from the moment they were read for a specified period of time. one of these was multiply. It used shifting and adding continuously until the product was ready.
(Score: 0) by Anonymous Coward on Wednesday September 25 2019, @04:27PM (1 child)
I remember when DOS games were clocked to a particular CPU clock speed. Using them on later/faster CPUs caused them to run too fast.
(Score: 2) by istartedi on Wednesday September 25 2019, @10:10PM
IIRC, that was the idea behind the "turbo" switch on some PCs from that era. It wasn't something for conserving power then boosting when you needed computational speed. It was for syncing games.
Appended to the end of comments you post. Max: 120 chars.
(Score: 2) by FatPhil on Wednesday September 25 2019, @08:41AM (4 children)
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Interesting) by choose another one on Wednesday September 25 2019, @09:23AM (3 children)
Probably right. Problem is that with hardware complexity these days trial-and-error or calculate-all-possibilities is off the table from the start, but the tech archaeologists forget that when you've finished marvelling at how limited and constrained hardware was in the past you need to revisit those assumptions when looking at software designed to run on it - terribly constrained and limited also means try-every-way is a feasible design method.
There is also an element of survivor bias - we look at the best of the past and marvel at how good the creators were, forgetting that we only have the best to look at because the vast majority of failed stuff has long since been lost forgotten erased destroyed re-purposed or painted over. Look at all those massive cathedrals still standing after so many centuries - those medieval stone masons must have been geniuses...
(Score: 2) by FatPhil on Wednesday September 25 2019, @10:26AM (2 children)
After I posted my prior comment I realised that I should have equated the wide-eyed reaction to the table-driven algorithm, not being able to work out the simple rules behind it, as being similar to those who look at life on earth and say "Irreducible complexity! There must be some intelligent designer behind this!". Nope, just a stoner (read the paper) who just threw something random together that worked just well enough to be a playable game. It's as bad a design as the eyeball (blind spots because the sensor's back-to-front), or metabolism of lipids (break it apart, pack it together, break that apart, pack it together again, break it apart again...), or putting the fun hole between the piss hole and the shit hole (and the fun switch on the far side of the piss hole, so there's no avoiding the piss hole), or ... .
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by Bot on Wednesday September 25 2019, @08:43PM
If it is irreducible complexity, you gotta find a model to reduce it. It is not a theological problem. Creationists and atheists make it so, but it isn't, because the hypothetical God is not bound by time, so it can theoretically obtain the desired outcome from a freely evolving mechanism instead of creating it with an ad hoc intervention. In other words, creation vs evolution is meaningless in the hypothetical dimension of God. If that seem strange, consider an arrow of time t and a banal function of t, f(t) = 2t. You know every value because you are not bound by t. You don't need to travel over t to plot it. You know it for every possible value already. Such is God wrt time.
Account abandoned.
(Score: 2) by choose another one on Wednesday September 25 2019, @08:43PM
> The builders certainly learnt what flying buttresses are for. Namely keeping your walls vertical.
Probably by trial and error again - not by carefully calculating force lines. Buttresses (non flying) would have been used when walls started to bow, build em taller and wider until wall stops bowing. Flying buttresses were for the gothic taller-thinner look and maybe to save some stone, someone figured that the most important bit was the top and the outside (having figured how far up and out was needed) so why not save some stone by making it half an arch. Or something like that :-)
(Score: 3, Funny) by Anonymous Coward on Wednesday September 25 2019, @10:05AM
From the BBC link about this
'..And he claimed it had been the work of a programmer who developed it while not entirely sober: “He told me it came upon him when he was drunk and whacked out of his brain.”..'
Ah!, programming when drunk, that blessed altered state when all sorts of fun things can happen...
I won't say my best code has been written whilst inebriated, but some of the more interesting stuff most definitely was, and I won't even count the number of times I'd retired to the pub, had a couple of pints, then scurried back to work to fix a coding issue which had been bothering me for a bit as the solution had just occurred to me (sometimes as the actual lines of code scrolling in front of my eyes as some sort of blizzare Matrix style overlay..and this was way before that film came out) then, obviously, made my way back to the pub...
Oh, the things I've drunkenly coded over the decades...Howling (but efficient) HC11 assembly, sozzled 68k assembly, pissed Perl (and you thought sober Perl was unreadable...), meroculous Matlab, legless Lisp, plastered Pascal, paraletic Python, crapulous C...
(Score: -1) by MyOpinion on Wednesday September 25 2019, @11:43AM (1 child)
2600, the first computer discovered to grow on trees.
Man had to figure out how it works all by himself.
Truth is like a Lion: you need not defend it; let it loose, and it defends itself. https://discord.gg/3FScNwc
(Score: 2) by Pino P on Wednesday September 25 2019, @01:20PM
From the point of view of third-party devs, the 2600 did grow on trees, as Atari sure as 💩 didn't want to spill the beans about how to use the TIA. The closest analogy I can draw is the manufacturer of a chipset or peripheral for Windows PCs that doesn't cooperate with contributors to Linux, X Window System, CUPS, or SANE.
(Score: 0) by Anonymous Coward on Wednesday September 25 2019, @12:04PM (3 children)
Do they have a college degree in that yet?
(Score: 0) by Anonymous Coward on Wednesday September 25 2019, @03:43PM (2 children)
No idea about the degree, but with some sleuthing it may be possible to find someone still alive that was at Atari back then. Why not look for the answer directly, rather than all this dramatic "mystery" stuff? I have one friend who worked there, he's over 65, but hardly retired--sent him a link to the BBC article, maybe he knows someone...
Pretty early on there were pirates that copied games and sold them around the world. Atari was on to them--clever things were done in the software and hardware to make the games hard to copy, and/or easy to demonstrate to a court that a game had been copied directly, not re-programmed in a "clean room".
(Score: 2) by All Your Lawn Are Belong To Us on Wednesday September 25 2019, @05:06PM (1 child)
I knew someone who knew somebody in that trade. He had a case full of PROM chips (dunno if EPROM or EEPROM) and an open circuit board with a socket with a locking lever. Chip-into-socket-lock-then-insert. Dad came home the afternoon we were playing on our 2600 and said we couldn't do it anymore since he was afraid the nonstandard connector would screw up the cartrdige retriever socket by widening it. He was probably right. So I'd go over to his place. I had maybe 10-15 or so cartridges by the end of playing with our 2600. He had dozens.
This sig for rent.
(Score: 0) by Anonymous Coward on Wednesday September 25 2019, @06:46PM
Of course, glad to hear that you were "just asking for a friend"(grin).
I had an EPROM writer too, when I was doing some game testing for Atari. I'd get updated code by ftp, burn the EPROM, insert in the game and test. This was a large arcade game, not a 2600 game...
The EPROMS they gave me were UV erasable, had a window over the chip. There were official eraser machines, but it was easy enough to take off the sticker and leave outdoors in the sun for a few hours (on a dry day).
(Score: 3, Informative) by istartedi on Wednesday September 25 2019, @10:23PM
Thank-you for providing a better summary than any other site so far. I had originally envisioned this as a game with a 2d maze that scrolled in all four directions. It was far simpler than that. For a better understanding of what the programmer was dealing with, a video of actual game play. [youtube.com] is useful.
I still don't understand what governs the parts of the maze that appear and disappear. Another interesting aspect of the game is that there are "stranded" black areas on the sides; but it's all good because the player is never there. What's more, it's symmetrical. It only scrolls in one direction, and they use the mirror image to double the size. They really were pulling some tricks here.
Appended to the end of comments you post. Max: 120 chars.
(Score: 2) by KritonK on Thursday September 26 2019, @08:48AM
Not completely reliably navigable, as there are times where you apparently have to dig [youtube.com] yourself out [youtube.com] of a dead end.