A Deep Dive Into NES Tetris

Tetris AI

Back in 1989, Nintendo released Tetris for the NES. This detailed article first explains the mechanics of how Tetris works, then builds an AI to play the game.

To understand the mechanics of the game, the ROM source was explored. Since the NES was based of the MOS 6502 microprocessor, this involves looking at the 6502 assembly. The article details how the blocks (called Tetriminos) are created and how they move across the screen. The linear feedback shift register used for random number generation is examined. Even details of the legal screen and demo mode are explained.

After the tour through how Tetris works, an algorithm for the AI is presented. This AI is implemented in Lua inside of the FCEUX NES/Famicom emulator. It works by evaluating all of the possible places to put each new Tetrimino, and choosing the best based on a number of criteria. The weighting for each criterion was determined by using a particle swarm optimization.

The source for both the Lua version and a Java version of the code is available with the article. Everything you need to run the AI is available for free, except the Tetris ROM. If you’re interested in how 8 bit games were built, this dissection is a great read.

[via Reddit]

Comments

  1. Chris says:

    I suggest reading the rest of this guy’s site. It is wonderful source of interesting reading. Nice find.

  2. cooperised says:

    A really interesting approach. I like the reverse engineering aspect. An AI that exploited the (presumably not crypto-grade) RNG to guess which shape was coming next would be really cool.

    BTW, you mean ‘the weighting for each criterion’ – criterea is the plural.

  3. Mike Lu says:

    Those “classic” games have loads of programming shortcuts that led to various glitches. I’d like to see a detailed analysis of Chip’s Challenge, which has peculiar bugs suggesting peculiar programming.

  4. rj says:

    To think that all the AI effort of bastet could just be replaced with alternating S/Z tetrominos!

    One very minor erratum in his document: the colors in his palette reference are slightly off. (Colors 0x20 and 0x30 are identical; color 0x3D is untinted grey and not purplish; color 0x0D is out of gamut/blacker than black)

  5. 1.21Gigawatts says:

    Now I want to fire up my NES system when I get home from work. Play a little Tetris, maybe a little Duck Hunt. The system and cartridges need a contact cleaning though. Haven’t touched Final Fantasy in 20 years and still haven’t finished the game. Maybe I’ll pull it out.

    • Rob says:

      I regret not having space for a CRT television… Duck Hunt doesn’t work on a LCD… and the NES Gun is so lonely sitting there next to the controllers.

      • Krusty says:

        I just turned my Zapper into a nice laser pointer, with a USB charger and battery built into the handle :)

      • Jonathan Wilson says:

        I am surprised no-one has come up with a gun that was both compatible with the NES (and how its gun works) and with LCD TVs. Or does the way the NES talks to the gun mean that you cant make an LCD compatible gun that the games would be able to correctly talk to?

        • Blue Footed Booby says:

          You’re underestimating how down-to-the-metal it all was.

          The gun worked by reading the brightness of what it’s pointed at. This is why the screen flashed when you shot: ducks turned white, everything not shootable turned black.

          The trick is in how it determined *which* shootable object you hit. It took advantage of the set way CRTs fill in the picture, scanning from left to right and top to bottom. Because of this, you could tell what you’d hit by *when* the pixels turned white.

          You might see where this is going: the gun itself is an entirely dumb photo sensor. It doesn’t “talk” to the system at all, at least not in the sense of having a protocol that can be reverse engineered.

          • Kevin says:

            The NES gun don’t use scanning, only the later systems does. As I said in my other post the big problem is probably the slowness of LCD TV:s and this would be solvable by reprogramming the games.

        • Kevin says:

          The NES gun works by checking if it’s pointed to a black or white target, the same time as you pull the trigger the screen changes briefly (you’ll notice the screen flashes) and makes the target one color and the surrounding area the other. LCD TV:s either aren’t that fast or not bright enough, I would guess the first is the biggest problem.

          Newer gun systems (SNES, PlayStation) use the scanning of the video signal and can get the exact pixel at which the gun is pointing but this doesn’t work on LCD:s because of the lack of scanning, LCD:s display the full frame at once.

        • It has to do with the interlaced picture of a crt, and the progressive scan of modern displays.

  6. 911Ducktail says:

    ” Meaning, the number of frames that it takes the player to position a piece actually affects which piece comes up next.”

    Wow, whole new way to look at droughts…..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,441 other followers