SOLVING THE UNSOLVABLE: IMPOSSIBLE PROBLEMS AND ATARI 2600 CODE REUSE
Channel: European Association of Archaeologists
Date: 2020-10-15

In developing methodology for archaeogaming, it is important to have exemplars of techniques that work for analyzing digital artifacts, but it is equally important to understand the limitations of techniques. For example, analyzing retrogame code by reverse engineering is typically presented as a fait accompli, a successful endeavor. But this belies the fact that there are questions that arise when reverse engineering code whose answers are either provably impossible or computationally hard to find. Furthermore, there can be a fine line between easy and incredibly hard problems.
For concreteness, we consider the practice of programmers reusing code in Atari 2600 games: tracing common fragments of code from one game to others. Given a single chosen code fragment, this is a straightforward task to automate, as we have done for a distinctive code fragment in the 1982 game Entombed. On the other hand, identifying and tracing all common code fragments automatically is a problem impossible to precisely answer; we explain why this is such a hard problem. We tackle this problem heuristically instead, using a novel approach to look for all common code fragments in a corpus of 1,897 Atari 2600 games. This involves building analysis tools, visualizing the results, and interpreting key instances of discovered code reuse. Our technique can be generalized to other game platforms. We also show how our solution can potentially lead to automated identification of “interesting” code, which would make it possible to direct analysis to distinctive areas of code in a game corpus rather than rely on serendipity and laborious manual analysis.

Author(s): Aycock, John (University of Calgary)