Description
only bid if you’ve read the pdf
Unformatted Attachment Preview
A1: Entombed
The paper “Entombed: An archaeological examination of an Atari 2600 game”, by John
Aycock and Tara Copplestone, https://programming-journal.org/2019/3/4/ got some play in the
news with articles like, “The mysterious origins of an uncrackable video game,” by Chris
Baraniuk, 22nd Sept 2019, which says: https://www.bbc.com/future/article/20190919-the-mazepuzzle-hidden-within-an-early-video-game
Released in 1982, Entombed was far from a best-seller and today it’s largely forgotten. But recently, a
computer scientist and a digital archaeologist decided to pull apart the game’s source code to investigate how
it was made. [Youtube video of the game: https://www.youtube.com/watch?v=oIR8IT493_Y]
… It turned out that the maze is generated in a sequence. The game needs to decide, as it draws each new
square of the maze, whether it should draw a wall or a space for the game characters to move around in. Each
square should therefore be “wall” or “no wall” – “1” or “0” in computer bits. The game’s algorithm decides this
automatically by analysing a section of the maze. It uses a five-square tile that looks a little like a Tetris piece.
This tile determines the nature of the next square in each row.
How? That’s the fascinating part. The fundamental logic that determines the next square is locked in a table of
possible values written into the game’s code. Depending on the values of the five-square tile, the table tells
the game to deposit either wall, no wall or a random choice between the two. 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 abnormality of the table was just quite striking,” says Copplestone. 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.”
For Aycock, the as-yet unsolved mystery of the table
lingers uncomfortably. “The struggle I have as a scientist
is, I think that there should be some logical way that this
will all make sense and there really doesn’t seem to be.”
The best guess the pair have is that the programmer
behind the maze algorithm must have manually finetuned the table values until the game worked as desired,
but that still doesn’t really explain the logic behind it.
Here are illustrations from Aycock &
Copplestone. There are some special
cases for starting on the left and the
mirror symmetry in the middle, but
basically the game scans left to right and
chooses blank (0), wall (1), or random by
looking at two bits to the left
and three above:
These bits index into a truth table of 2! = 32 rows to
generate the next bit X. Aycock and Copplestone call it a
“mystery table,” but most of it is easy to explain. You will make a slightly
different table of 2! = 32 rows and compare it with the mystery table.
Note:
Consider how each bit – wall (1) or blank (0) – relates to its four neighbors
above, below, left and right. For X, bits b and d are two of those neighbors.
2. Rule 2×2: For a good “Entombed” maze, you want to avoid generating a
2×2 blank (all 0s), a 2×2 block (all 1s), or a 2×2 checkerboard.
1)
Give a logic formula in b,c,d that tests if there is a danger that X may
complete one of these 2×2 patterns, and a way to set X so that it does
not. Even if you start by making formulas for each possible 2×2, try to
simplify them — you can fill in these blanks with very short formulas.
if _____________ then assign X= ____
2)
What is the one exception to your Rule 2×2 in the mystery table?
(It allows the checkerboard 2×2 the player is headed toward in Fig. 5.)
For the pattern _______, the game assigns X to a random bit, rather than to ____.
3. Rule Nbr: To avoid an isolated wall or blank, every bit should match at
least one of its four neighbors. If a neighbor of X does not already have a
matching neighbor among a,b,c,d,e, let’s make X be the match.
1)
Give a logic formula in a,b,c,d,e to test if b needs X as a match.
2)
Give logic formulas in a,b,c,d,e to test if d needs X as a match.
3)
if _____________ then assign = .
if _____________ then assign = .
Argue that there can be no conflict between the two Rule Nbr cases: that if ≠ it will
never try to assign both = 0 and = 1.
4. The Key Exception: In the remaining patterns, it should be OK to choose X randomly,
since Rule 2×2 eliminates the unwanted 2×2 patterns and Rule Nbr sets those that need X
as a neighbor.
1)
2)
What is the exception that is not random in the mystery table?
For the pattern _______, the game assigns X to ___, rather than to a random bit.
Explain why the game may be better when that value identified in 4.1 is not random,
but fixed. You’ll probably also reference your Rule 2×2.
Purchase answer to see full
attachment
