Entropy Lost: Nintendo’s Not-So-Random Sequence of 32, 767 Bits
Authors: 
Trang Ngo, Aaron WilliamsAuthors Info & Claims
Article No.: 65, Pages 1 - 10
Abstract
Early video games didn’t have hardware support for random number generation, so developers used software-based RNG. We show that hundreds of games in the Nintendo Famicom / NES library regenerate the same pseudorandom sequence of 32, 767 bits, although the machine code for doing so comes in more than one hundred variants. We identified the disparate implementations using a simple regular expression that matches the following “fingerprint” of operations: LDA, AND, STA, LDA, AND, EOR, CLC, BEQ, SEC, ROR. These instructions implement a classic 15-bit linear feedback shift register associated with x15 + x7 + 1 (i.e., tap the 15th and 7th bits). However, many games devoted more memory to the LFSR’s state. For example, Donkey Kong (1983) used 8 bytes (or 8 · 8 = 64 bits), The Legend of Zelda (1986) used 13 bytes, and Super Mario Bros. 3 (1988) used 9 bytes. In each case, additional entropy is lost by a simple programming error: the bits are shifted in the wrong direction.
References
[1]
Abbas Alhakim, Evan Sala, and Joe Sawada. 2021. Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions. Theoretical Computer Science 852 (2021), 73–77.
[2]
Abbas M Alhakim. 2010. A simple combinatorial algorithm for de Bruijn sequences. The American Mathematical Monthly 117, 8 (2010), 728–732.
[3]
Matt Alt. 2020. The Designer Of The NES Dishes The Dirt On Nintendo’s Early Days. https://www.kotaku.com.au/2020/07/the-designer-of-the-nes-dishes-the-dirt-on-nintendos-early-days/.
[4]
Internet Archive. 2020. [No-Intro] Nintendo - Nintendo Entertainment System. https://archive.org/details/nointro.nes.
[5]
John Aycock. 2016. Retrogame Archeology: Exploring Old Computer Games (1st ed.). Springer, New York, NY, USA.
[6]
Pradipto Banerjee and Michael Filaseta. 2010. On a polynomial conjecture of Pál Turán. Acta Arith 143, 3 (2010), 239–255.
[7]
John Adrian Bondy, Uppaluri Siva Ramachandra Murty, 1976. Graph theory with applications. Vol. 290. Macmillan London.
[8]
Ben Cameron, Aysu Gündoğan, and Joe Sawada. 2022. Cut-Down de Bruijn Sequences. arXiv preprint arXiv:2205.02815(2022).
[9]
Joseph DiMuro. 2019. Classifying rotationally-closed languages having greedy universal cycles. The electronic journal of combinatorics26 (2019), P1.35. Issue 1.
[10]
Patrick Baxter Dragon, Oscar I Hernandez, Joe Sawada, Aaron Williams, and Dennis Wong. 2018. Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. European Journal of Combinatorics 72 (2018), 1–11.
[11]
Patrick Baxter Dragon, Oscar I Hernandez, and Aaron Williams. 2016. The grandmama de Bruijn sequence for binary strings. In LATIN 2016: Theoretical Informatics. Springer, 347–361.
[12]
Michael Filaseta. 2014. Is Every Polynomial with Integer Coefficients Near an Irreducible Polynomial?Elemente der Mathematik 69, 3 (2014), 130–143.
[13]
Michael Filaseta and Michael Mossinghoff. 2012. The distance to an irreducible polynomial, II. Math. Comp. 81, 279 (2012), 1571–1585.
[14]
Harold Fredricksen and James Maiorana. 1978. Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Mathematics 23, 3 (1978), 207–210.
[15]
Daniel Gabric and Joe Sawada. 2022. Investigating the discrepancy property of de Bruijn sequences. Discrete Mathematics 345, 4 (2022), 112780.
[16]
Daniel Gabric, Joe Sawada, Aaron Williams, and Dennis Wong. 2018. A framework for constructing de Bruijn sequences via simple successor rules. Discrete Mathematics 341, 11 (2018), 2977–2987.
[17]
Daniel Gabric, Joe Sawada, Aaron Williams, and Dennis Wong. 2019. A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles. IEEE Transactions on Information Theory 66, 1 (2019), 679–687.
[18]
Petar Gaydarov and Konstantin Delchev. 2015. Combinatorial Computations on an Extension of a Problem by Pál Turán. Serdica Journal of Computing(2015), 257–268.
[19]
Solomon W. Golomb. 1981. Shift Register Sequences(1 ed.). Aegean Park Press.
[20]
Mark Hendrikx, Sebastiaan Meijer, Joeri Van Der Velden, and Alexandru Iosup. 2013. Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications 9, 1(2013), 1–22.
[21]
Cees JA Jansen, Wouter G Franx, and Dick E Boekee. 1991. An efficient algorithm for the generation of DeBruijn cycles. IEEE Transactions on Information Theory 37, 5 (1991), 1475–1478.
[22]
Thomas Jentzsch. 2017. Pitfall!x256 (was: Pitfall!x16). https://atariage.com/forums/topic/267046-pitfallx256-was-pitfallx16.
[23]
Donald E Knuth. 2005. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations. Addison-Wesley Professional.
[24]
Donald E Knuth and Len Shustek. 2021. Let’s not dumb down the history of computer science. Commun. ACM 64, 2 (2021), 33–35.
[25]
Gilbert Lee, Frank Ruskey, and Aaron Williams. 2007. Hamming distance from irreducible polynomials over . Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (Jan. 2007). https://doi.org/10.46298/dmtcs.3550
[26]
Monroe H Martin. 1934. A problem in arrangements. Bull. Amer. Math. Soc. 40, 12 (1934), 859–864.
[27]
Damien McFerran. 2018. Feature: Shining A Light On Ikegami Tsushinki, The Company That Developed Donkey Kong. https://www.nintendolife.com/news/2018/02/feature_shining_a_light_on_ikegami_tsushinki_the_company_that_developed_donkey_kong.
[28]
Mike Mika. 2013. Why I hacked Donkey Kong for my daughter. Wired, March 11(2013).
[29]
Nick Montfort and Ian Bogost. 2009. Racing the beam: The Atari video computer system. Mit Press.
[30]
Nick Morgan. 2012. Easy 6502 Simulator. https://skilldrick.github.io/easy6502/simulator.html.
[31]
Trang Q. Ngo. 2020. Python implementation of Dr. Mario algorithms. https://github.com/trangqngo/Dr-Mario-virus-generation.
[32]
nightmareci. 2012. Dr. Mario virus placement. https://tetrisconcept.net/threads/dr-mario-virus-placement.2037.
[33]
nightmareci. 2013. Dr. Mario. https://tetris.wiki/Dr._Mario.
[34]
Robert Xiao (nneonneo). 2015. bgrep. https://github.com/nneonneo/bgrep.
[35]
Frank Ruskey, Carla Savage, and Terry Min Yih Wang. 1992. Generating necklaces. Journal of Algorithms 13, 3 (1992), 414–430.
[36]
Frank Ruskey, Joe Sawada, and Aaron Williams. 2012. De Bruijn sequences for fixed-weight binary strings. SIAM Journal on Discrete Mathematics 26, 2 (2012), 605–617.
[37]
Joe Sawada, Aaron Williams, and Dennis Wong. 2016. Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles. The electronic journal of combinatorics(2016), P1–24.
[38]
Joe Sawada, Aaron Williams, and Dennis Wong. 2016. A surprisingly simple de Bruijn sequence construction. Discrete Mathematics 339, 1 (2016), 127–131.
[39]
Joe Sawada, Aaron Williams, and Dennis Wong. 2017. A simple shift rule for k-ary de Bruijn sequences. Discrete Mathematics 340, 3 (2017), 524–531.
[40]
Noor Shaker, Julian Togelius, and Mark J Nelson. 2016. Procedural content generation in games. Springer.
[41]
Wayne Stahnke. 1973. Primitive binary polynomials. Mathematics of computation 27, 124 (1973), 977–980.
[42]
Brett Stevens and Aaron Williams. 2014. The coolest way to generate binary strings. Theory of Computing Systems 54, 4 (2014), 551–577.
[43]
taotao54321. 2018. NES Dr.Mario hand simulator. https://gist.github.com/taotao54321/4ec019a251fdd8f9759fa8a8b5439559.
[44]
Sam Trenholme. 2013. Alternate Pitfall maps. https://www.samiam.org/blog/20130617.html.
[45]
Aaron Williams. 2019. Dr. Mario Puzzle Generation: Theory, Practice, & History (Famicom/NES). In The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games. 128–129.
[46]
Aaron Williams. 2022. Nintendo’s Not-So-Random Sequence. https://gitlab.com/combinatronics/nintendos-not-so-random-sequence.
Index Terms
- Entropy Lost: Nintendo’s Not-So-Random Sequence of 32, 767 Bits
Recommendations
Classic Nintendo games are (computationally) hard
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros. 1-3, The Lost Levels, and Super Mario World; ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2022
664 pages
ISBN:9781450397957
DOI:10.1145/3555858
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 November 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
FDG22
FDG22: 17th International Conference on the Foundations of Digital Games
September 5 - 8, 2022
Athens, Greece
Acceptance Rates
Overall Acceptance Rate 152 of 415 submissions, 37%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 46Total Downloads
- Downloads (Last 12 months)22
- Downloads (Last 6 weeks)3
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format