Applying Artificial Intelligence to Nintendo Tetris

For those lacking the persistence, patience and time necessary to master Nintendo Tetris, I created an AI to play it for you. Finally, you can experience level 30 and beyond. You can witness the score max out while the line, level and statistics counters wraparound indefinitely. Find out what colors appear in levels higher than any human has ever reached. Discover how long it can go.

Preliminaries

To run the AI, you'll need FCEUX, the all-in-one NES/Famicom emulator. The AI was developed for FCEUX 2.2.2, the most recent version at the time of this writing.

You'll also need the Nintendo Tetris ROM file (USA version). Google might be able to help you to track it down.

Download

Run

From the menu bar, select File | Open ROM... In the Open File dialog box, select the Nintendo Tetris ROM file and press Open. The game will launch.

From the menu bar, select File | Lua | New Lua Script Window... From the Lua Script window, enter the path to NintendoTetrisAI.lua or hit the Browse button to navigate to it. Finally, press Run.

The Lua script will direct you to the first menu screen. Leave the game type as A-Type, but feel free to change the music using the arrow keys. On slower computers, the music may play choppy; you might want to disable it completely. Press Start (Enter) to advance to the next menu screen. In the second menu, you can change the starting level using the arrow keys. Press Start to begin the game. The AI will take over from there.

From the second menu screen, after you select the level, if you hold down gamepad button A (use Config | Input... to modify the keyboard mapping) and press Start, the resulting starting level will be 10 plus the selected value. The highest starting level is 19.

Configuration

To make it play faster, open the Lua script in a text editor. Toward the top of the file, you'll find the following line.

The Mechanics of Nintendo Tetris

Representing Tetriminos

Each Tetrimino (tetri-mee-noh) has a single-character name that resembles its shape.

The designers of Nintendo Tetris arbitrarily ordered the Tetriminos into the sequence shown above. The pieces are depicted in the spawn orientations and the arrangement produces a nearly symmetric image, which might explain why they chose this ordering. The index into the sequence provides each Tetrimino with a unique numerical type ID. The sequence and the type IDs are important at a programmatic level, but it also manifests itself in the order of the pieces displayed in the statistics area (see below).

The 19 orientations of Tetriminos used by Nintendo Tetris are encoded in a table located at $8A9C within NES memory. Each piece is represented as a sequence of 12 bytes that can be broken down into triples, (Y, tile, X), describing each square within the piece. Hex coordinate values above $7F represent negative integers ($FF = −1 and $FE = −2).

    ; Y0 T0 X0  Y1 T1 X1  Y2 T2 X2  Y3 T3 X3
                        
8A9C: 00 7B FF  00 7B 00  00 7B 01  FF 7B 00  ; 00: T up
8AA8: FF 7B 00  00 7B 00  00 7B 01  01 7B 00  ; 01: T right
8AB4: 00 7B FF  00 7B 00  00 7B 01  01 7B 00  ; 02: T down (spawn)
8AC0: FF 7B 00  00 7B FF  00 7B 00  01 7B 00  ; 03: T left

8ACC: FF 7D 00  00 7D 00  01 7D FF  01 7D 00  ; 04: J left
8AD8: FF 7D FF  00 7D FF  00 7D 00  00 7D 01  ; 05: J up
8AE4: FF 7D 00  FF 7D 01  00 7D 00  01 7D 00  ; 06: J right
8AF0: 00 7D FF  00 7D 00  00 7D 01  01 7D 01  ; 07: J down (spawn)

8AFC: 00 7C FF  00 7C 00  01 7C 00  01 7C 01  ; 08: Z horizontal (spawn)
8B08: FF 7C 01  00 7C 00  00 7C 01  01 7C 00  ; 09: Z vertical

8B14: 00 7B FF  00 7B 00  01 7B FF  01 7B 00  ; 0A: O (spawn)

8B20: 00 7D 00  00 7D 01  01 7D FF  01 7D 00  ; 0B: S horizontal (spawn)
8B2C: FF 7D 00  00 7D 00  00 7D 01  01 7D 01  ; 0C: S vertical

8B38: FF 7C 00  00 7C 00  01 7C 00  01 7C 01  ; 0D: L right
8B44: 00 7C FF  00 7C 00  00 7C 01  01 7C FF  ; 0E: L down (spawn)
8B50: FF 7C FF  FF 7C 00  00 7C 00  01 7C 00  ; 0F: L left
8B5C: FF 7C 01  00 7C FF  00 7C 00  00 7C 01  ; 10: L up

8B68: FE 7B 00  FF 7B 00  00 7B 00  01 7B 00  ; 11: I vertical
8B74: 00 7B FE  00 7B FF  00 7B 00  00 7B 01  ; 12: I horizontal (spawn)
        
8B80: 00 FF 00  00 FF 00  00 FF 00  00 FF 00  ; 13: Unused

There is one unused entry at the bottom of the table potentially providing the means of adding an extra orientation. However, in various parts of the code, $13 indicates that the active Tetrimino's orientation ID is not assigned a value.

The square coordinates are re-expressed in decimal below to make it easier to read.

-- { { X0, Y0 }, { X1, Y1 }, { X2, Y2 }, { X3, Y3 }, },

   { { -1,  0 }, {  0,  0 }, {  1,  0 }, {  0, -1 }, },  -- 00: T up
   { {  0, -1 }, {  0,  0 }, {  1,  0 }, {  0,  1 }, },  -- 01: T right
   { { -1,  0 }, {  0,  0 }, {  1,  0 }, {  0,  1 }, },  -- 02: T down (spawn)
   { {  0, -1 }, { -1,  0 }, {  0,  0 }, {  0,  1 }, },  -- 03: T left

   { {  0, -1 }, {  0,  0 }, { -1,  1 }, {  0,  1 }, },  -- 04: J left
   { { -1, -1 }, { -1,  0 }, {  0,  0 }, {  1,  0 }, },  -- 05: J up
   { {  0, -1 }, {  1, -1 }, {  0,  0 }, {  0,  1 }, },  -- 06: J right
   { { -1,  0 }, {  0,  0 }, {  1,  0 }, {  1,  1 }, },  -- 07: J down (spawn)

   { { -1,  0 }, {  0,  0 }, {  0,  1 }, {  1,  1 }, },  -- 08: Z horizontal (spawn) 
   { {  1, -1 }, {  0,  0 }, {  1,  0 }, {  0,  1 }, },  -- 09: Z vertical

   { { -1,  0 }, {  0,  0 }, { -1,  1 }, {  0,  1 }, },  -- 0A: O (spawn)

   { {  0,  0 }, {  1,  0 }, { -1,  1 }, {  0,  1 }, },  -- 0B: S horizontal (spawn)
   { {  0, -1 }, {  0,  0 }, {  1,  0 }, {  1,  1 }, },  -- 0C: S vertical

   { {  0, -1 }, {  0,  0 }, {  0,  1 }, {  1,  1 }, },  -- 0D: L right
   { { -1,  0 }, {  0,  0 }, {  1,  0 }, { -1,  1 }, },  -- 0E: L down (spawn)
   { { -1, -1 }, {  0, -1 }, {  0,  0 }, {  0,  1 }, },  -- 0F: L left
   { {  1, -1 }, { -1,  0 }, {  0,  0 }, {  1,  0 }, },  -- 10: L up

   { {  0, -2 }, {  0, -1 }, {  0,  0 }, {  0,  1 }, },  -- 11: I vertical
   { { -2,  0 }, { -1,  0 }, {  0,  0 }, {  1,  0 }, },  -- 12: I horizontal (spawn)

Above, a white square marks the center of the matrix, the pivot point for piece rotation.

The orientation ID (the table index) is displayed in hexadecimal in the upper-right of each matrix. And, a mnemonic invented for this discussion appears in the upper-lefts. The lower-case u, r, d, l, h and v are short for up, right, down, left, horizontal and vertical respectively. It's easier to refer to Jd rather than $07, for instance.

Tetriminos I, S and Z could have been designed to have 4 distinct orientations, but the creators of Nintendo Tetris decided to limit them to 2. Also, Zv and Sv are not perfect mirrors of each other. Both were produced via counterclockwise rotation resulting in an imbalance.

The orientation table also contains the tile values for each square within each oriented piece. However, a close inspection reveals that the values are all the same among Tetrimino type.

T	J	Z	O	S	L	I
7B	7D	7C	7B	7D	7C	7B

Tiles $7B, $7C and $7D are located directly below, "ATIS", in the word, "STATISTICS". They are the 3 types of squares from which Tetriminos are built.

If you are wondering, the ostriches and penguins are from the B-Type endings, a topic further discussed below.

Below is the result of modifying the ROM to change $7B to $29, the tile directly below character P in the pattern table, for all T orientations.

The heart tiles remain in the playfield even after the modified T locks into place. As discussed further below, this means that the playfield stores the actual tile index values from the played Tetriminos.

The game programmers provided the means of using 4 separate tiles for each piece as opposed to just one consistent square type. It's a useful feature that could be used to re-skin the game. There are plenty of empty spaces within the pattern table for new tiles that could give each Tetrimino a unique look.

The square coordinates are just as easy to manipulate. For example, below is a modified version of the first 4 triples in the orientation table.

8A9C: FE 7B FE  FE 7B 02  02 7B FE  02 7B 02  ; 00: T up

   { { -2, -2 }, {  2, -2 }, { -2,  2 }, {  2,  2 }, },  -- 00: T up

When the disjoint Tetrimino is moved around, its squares are restricted to the boundaries of the playfield and they cannot pass through previously locked pieces. Also, the game prohibits rotation to this orientation if it would result in a square outside of the playfield bounds or if it would cause a square to overlap a locked square.

The disjoint Tetrimino locks into place when any of its squares are supported. And, when it locks, its floating squares remain floating.

The game treats the disjoint Tetrimino as it would any other normal piece. It reveals that there is no additional table containing piece metadata. For example, a table could have been used that stores the bounding-box dimensions of each orientation for playfield perimeter collision testing. But, no such table is used. Instead, the game simply performs tests on all 4 squares just prior to manipulating a piece.

In addition, the square coordinates can be any values; they are not restricted to [−2, 2]. Of course, values far outside of that range will yield unusable pieces that may not even fit in the playfield. More importantly, as discussed later, when a piece locks in place, the mechanism that clears out completed lines only scans row offsets −2 to 1 about the piece origin; a square with a y-coordinate outside of that range will go undetected at that time.

Rotating Tetriminos

In the graphical depiction of the orientation table, rotation involves moving from a matrix to one of the matrices directly to its left or right, wrapping around the row if necessary. That concept is encoded in a table at $88EE.

             ; CCW  CW
88EE: 03 01  ;  Tl  Tr
88F0: 00 02  ;  Tu  Td
88F2: 01 03  ;  Tr  Tl
88F4: 02 00  ;  Td  Tu
88F6: 07 05  ;  Jd  Ju
88F8: 04 06  ;  Jl  Jr
88FA: 05 07  ;  Ju  Jd
88FC: 06 04  ;  Jr  Jl
88FE: 09 09  ;  Zv  Zv
8900: 08 08  ;  Zh  Zh
8902: 0A 0A  ;  O   O
8904: 0C 0C  ;  Sv  Sv
8906: 0B 0B  ;  Sh  Sh
8908: 10 0E  ;  Lu  Ld
890A: 0D 0F  ;  Lr  Ll
890C: 0E 10  ;  Ld  Lu
890E: 0F 0D  ;  Ll  Lr
8910: 12 12  ;  Ih  Ih
8912: 11 11  ;  Iv  Iv

To make this clearer, each column above was transposed to a row in the table below.

	Tu	Tr	Td	Tl	Jl	Ju	Jr	Jd	Zh	Zv	O	Sh	Sv	Lr	Ld	Ll	Lu	Iv	Ih
Counterclockwise	Tl	Tu	Tr	Td	Jd	Jl	Ju	Jr	Zv	Zh	O	Sv	Sh	Lu	Lr	Ld	Ll	Ih	Iv
Clockwise	Tr	Td	Tl	Tu	Ju	Jr	Jd	Jl	Zv	Zh	O	Sv	Sh	Ld	Ll	Lu	Lr	Ih	Iv

The mnemonics in the headers across the top can be interpreted as an index into the sequence or a key into a map. For instance, a counterclockwise rotation of Tu produces Tl, where as a clockwise rotation of Tu produces Tr.

The rotation table encodes chained sequences of orientation IDs and consequentially, it is possible to modify entries such that rotation will have the effect of transforming one Tetrimino type into another. That technique could potentially be used to take advantage of the unused row in the orientation table.

88AB: LDA $0042
88AD: STA $00AE    ; originalOrientationID = orientationID; 

88AF: CLC
88B0: LDA $0042
88B2: ASL
88B3: TAX          ; index = 2 * orientationID;

88B4: LDA $00B5    
88B6: AND #$80     ; if (not just pressed button A) {
88B8: CMP #$80     ;   goto aNotPressed;
88BA: BNE $88CF    ; }

88BC: INX          
88BD: LDA $88EE,X    
88C0: STA $0042    ; orientationID = rotationTable[index + 1];

88C2: JSR $948B    ; if (new orientation not valid) {
88C5: BNE $88E9    ;   goto restoreOrientationID;
                   ; }

88C7: LDA #$05     
88C9: STA $06F1    ; play rotation sound effect;
88CC: JMP $88ED    ; return;

aNotPressed:

88CF: LDA $00B5
88D1: AND #$40     ; if (not just pressed button B) {
88D3: CMP #$40     ;   return;
88D5: BNE $88ED    ; }

88D7: LDA $88EE,X  
88DA: STA $0042    ; orientationID = rotationTable[index];
 
88DC: JSR $948B    ; if (new orientation not valid) {                  
88DF: BNE $88E9    ;   goto restoreOrientationID;
                   ; }

88E1: LDA #$05
88E3: STA $06F1    ; play rotation sound effect;
88E6: JMP $88ED    ; return;

restoreOrientationID:

88E9: LDA $00AE                
88EB: STA $0042    ; orientationID = originalOrientationID;

88ED: RTS          ; return;

For counterclockwise rotation, the index of the rotation table is computed by doubling the orientation ID. Adding 1 to that produces the index for clockwise rotation.

The x-coordinate, the y-coordinate and the orientation ID of the Tetrimino in play are stored at $0040, $0041 and $0042 respectively.

The code uses a temporary variable to backup the orientation ID. Later, after modifying the orientation, the code verifies that all 4 squares are within the bounds of the playfield and that none them overlap a previously locked square (the validation code is at $948B, beyond the snippet above). If the new orientation is invalid, it restores back to the original, preventing the player from rotating.

Including the D-pad, the NES controller has 8 buttons and the state of each is represented by a bit of $00B6.

7	6	5	4	3	2	1	0
A	B	Select	Start	Up	Down	Left	Right

For example, $00B6 will contain $81 for as long as the player holds down A and Left.

On the other hand, $00B5 reports when buttons are pressed; the bits of $00B5 remain set for only one iteration of the game loop (1 rendered frame). The code uses $00B5 to respond to A and B. Each of them need to be released before they can be used again.

$00B5 and $00B6 are mirrors of $00F5 and $00F6 respectively. Code in subsequent sections uses these addresses interchangeably.

Spawning Tetriminos

The Nintendo Tetris playfield consists of a matrix with 22 rows and 10 columns such that the top 2 rows are hidden from the player.

As seen in the snippet below, when a Tetrimino is spawned, it is always positioned at coordinates (5, 0) within the playfield.

98BA: LDA #$00
98BC: STA $00A4
98BE: STA $0045
98C0: STA $0041  ; Tetrimino Y = 0
98C2: LDA #$01
98C4: STA $0048                           
98C6: LDA #$05        
98C8: STA $0040  ; Tetrimino X = 5

None of the spawn matrices have squares above the origin. Meaning, when a Tetrimino is spawned, all 4 of its squares are immediately visible to the player. However, if the player quickly rotates the piece before it has an opportunity to drop, part of the piece could be hidden temporarily in the first 2 rows of the playfield.

In fact, normally, we think of game over as when the pile reaches the top. But, this is not entirely correct. The game actually ends when it is no longer possible to spawn the next piece. That is, all four cells of the playfield corresponding to the spawned Tetrimino's square positions must be empty before the piece can be introduced. A piece can be locked in place such that some of its squares end up in negatively numbered rows without ending the game; however, in Nintendo Tetris, negatively numbered rows are an abstraction that only applies to the active Tetrimino. After a piece is locked, only the squares in rows 0 and above are recorded in the playfield. Conceptually, it is as if the negatively number rows are automatically cleared after lock occurs. But, in reality, the game simply doesn't store the data, potentially truncating away the upper part of pieces.

The 20×10 visible region of the playfield is stored at $0400 in row-major order, each byte containing a background tile value. Empty cells are denoted by tile $EF, a solid black square.

Three lookup tables are used during spawning. Given an arbitrary orientation ID, the table at $9956 provides the spawn orientation ID for the associated Tetrimino type.

9956: 02 02 02 02  ; Td
995A: 07 07 07 07  ; Jd
995E: 08 08        ; Zh
9960: 0A           ; O
9961: 0B 0B        ; Sh
9963: 0E 0E 0E 0E  ; Ld
9967: 12 12        ; Ih

Tu	Tr	Td	Tl	Jl	Ju	Jr	Jd	Zh	Zv	O	Sh	Sv	Lr	Ld	Ll	Lu	Iv	Ih
Td	Td	Td	Td	Jd	Jd	Jd	Jd	Zh	Zh	O	Sh	Sh	Ld	Ld	Ld	Ld	Ih	Ih

993B: 00 00 00 00  ; T
993F: 01 01 01 01  ; J
9943: 02 02        ; Z
9945: 03           ; O
9946: 04 04        ; S
9948: 05 05 05 05  ; L
994C: 06 06        ; I

Tu	Tr	Td	Tl	Jl	Ju	Jr	Jd	Zh	Zv	O	Sh	Sv	Lr	Ld	Ll	Lu	Iv	Ih
T	T	T	T	J	J	J	J	Z	Z	O	S	S	L	L	L	L	I	I

Picking Tetriminos

Nintendo Tetris uses a 16-bit Fibonacci linear feedback shift register (LFSR) as a pseudorandom number generator (PRNG). The 16-bit value is stored big-endian at $0017–$0018. It is seeded to $8988, an arbitrary number.

80BC: LDX #$89
80BE: STX $0017    
80C0: DEX
80C1: STX $0018

Each successive pseudorandom number is generated by treating the value as a 17-bit number and setting the highest bit to the result of XORing bits 1 and 9 together. Then, the value is right shifted, tossing away the lowest bit.

AB47: LDA $00,X
AB49: AND #$02
AB4B: STA $0000  ; extract bit 1

AB4D: LDA $01,X
AB4F: AND #$02   ; extract bit 9

AB51: EOR $0000
AB53: CLC
AB54: BEQ $AB57   
AB56: SEC        ; XOR bits 1 and 9 together

AB57: ROR $00,X   
AB59: INX        
AB5A: DEY        ; right shift
AB5B: BNE $AB57  ; shifting in the XORed value

AB5D: RTS        ; return

Interestingly, the subroutine above was parameterized such that the caller can specify the width of the shift register and where to find it in memory. However, the same parameters are used throughout, suggesting that the developers may have borrowed this code from somewhere else.

For anyone who wants to repurpose it further, the algorithm is expressed in Java below.

int generateNextPseudorandomNumber(int value) {
  int bit1 = (value >> 1) & 1;
  int bit9 = (value >> 9) & 1;
  int leftmostBit = bit1 ^ bit9;
  return (leftmostBit << 15) | (value >> 1);
}

int generateNextPseudorandomNumber(int value) {
  return ((((value >> 9) & 1) ^ ((value >> 1) & 1)) << 15) | (value >> 1);
}

This PRNG repeatedly and deterministically generates 32,767 distinct values, each cycle starting with the original seed. That is one less than half of the possible numbers that can fit in the register and any value within that set can serve as the seed. Many of the values outside of the set will produce a chain that eventually leads to a number within the set. However, some starting numbers ultimately produce an endless sequence of zeros.

To gain a rough impression of this PRNG’s performance, I generated the visualization below of the values it produces based on a suggestion from RANDOM.ORG.

The image was created by treating the PRNG as a generator of pseudorandom bits rather than 16-bit integer numbers. Each pixel was colored based on the value in bit 0. The image is 128×256, covering the full sequence.

Aside from the faint bands across the top and left sides, it has the appearance of randomness. No obvious patterns manifest themselves.

From power on, the PRNG continually scrambles the register, executing at least once per frame. Not only does this occur on the title screen and the menu screens, it happens while Tetriminos are falling between spawns. Meaning, the number of frames that it takes the player to position a piece actually affects which piece comes up next. Essentially, the game taps directly into the inherent randomness of the human interfaced with it.

9907: INC $001A    ; spawnCount++;

9909: LDA $0017    ; index = high byte of randomValue;

990B: CLC
990C: ADC $001A    ; index += spawnCount;

990E: AND #$07     ; index &= 7;

9910: CMP #$07     ; if (index == 7) {
9912: BEQ $991C    ;   goto invalidIndex;
                   ; }

9914: TAX          
9915: LDA $994E,X  ; newSpawnID = spawnTable[index];

9918: CMP $0019    ; if (newSpawnID != spawnID) {
991A: BNE $9938    ;   goto useNewSpawnID;
                   ; }

invalidIndex:

991C: LDX #$17
991E: LDY #$02
9920: JSR $AB47    ; randomValue = generateNextPseudorandomNumber(randomValue);

9923: LDA $0017    ; index = high byte of randomValue;

9925: AND #$07     ; index &= 7;

9927: CLC
9928: ADC $0019    ; index += spawnID;

992A: CMP #$07
992C: BCC $9934
992E: SEC
992F: SBC #$07
9931: JMP $992A    ; index %= 7;

9934: TAX
9935: LDA $994E,X  ; newSpawnID = spawnTable[index];

useNewSpawnID:

9938: STA $0019    ; spawnID = newSpawnID;

993A: RTS          ; return;

The program maintains a count at $001A of the number of pieces spawned since power on. It is incremented by the first line of the subroutine and because it is a 1-byte counter, it loops back to 0 every 256 spawns. Since the counter is not reset between games, prior play history actually contributes to the piece selection process. This is another way that the game takes advantage of the player for a source of randomness.

The subroutine transforms the high byte of the pseudorandom number ($0017) into Tetrimino type and it uses that as an index into a table located at $994E to convert the type into a spawn orientation ID.

994E: 02  ; Td
994F: 07  ; Jd
9950: 08  ; Zh
9951: 0A  ; O
9952: 0B  ; Sh
9953: 0E  ; Ld
9954: 12  ; Ih

The first step of the transformation involves adding the spawn count to the high byte. A mask is applied to retain only the lower 3 bits. If the result is not 7, then it is a valid Tetrimino type and if it is not the same as the previously selected piece, then it is used as an index into the spawn table. Otherwise, the next pseudorandom number is generated and a mask is applied to retain the lower 3 bits of the high byte before adding the prior spawn orientation ID. Finally, a modulo operation is performed to obtain a valid Tetrimino type, which is used as an index into the spawn table.

Since the processor does not directly support modulo, the operator is emulated by repeatedly subtracting 7 until the result is less than 7. Modulo is applied to the sum of the masked high byte and the prior spawn orientation ID. The maximum value of that sum is 25. Hence, at most, it requires 3 iterations to reduce that to the remainder 4.

At the start of each game, the spawn orientation ID ($0019) is initialized to Tu ($00), a value potentially used at $9928 during the first spawn.

Using the prior spawn orientation ID in the sum as opposed to the prior Tetrimino type introduces a bias because the spawn orientation ID values are not evenly distributed. This is illustrated in the table below.

$00	$02	$07	$08	$0A	$0B	$0E	$12
0	2	0	1	3	4	0	4
1	3	1	2	4	5	1	5
2	4	2	3	5	6	2	6
3	5	3	4	6	0	3	0
4	6	4	5	0	1	4	1
5	0	5	6	1	2	5	2
6	1	6	0	2	3	6	3
7	2	0	1	3	4	0	4

Each cell contains a Tetrimino type produced by adding a spawn orientation ID (column) to a 3-bit value (row) and then applying modulo 7 to the sum. Each row contains duplicates because $07 and $0E are both evenly divisible by 7 and $0B and $12 have a common remainder. Rows 0 and 7 are the same because they are 7 apart.

There are 56 possible input combinations and if the resultant Tetrimino types were evenly distributed, the expectation is that in the table above each type should appear exactly 8 times. But, as shown below, that is not the case.

T and S appear more frequently and L and I less frequently. But, the biased code that uses the prior spawn orientation ID is not executed every time that the subroutine is called.

Type	Frequency
T	9
J	8
Z	8
O	8
S	9
L	7
I	7

Assume that the PRNG actually produces a sequence of uniformly distributed statistically independent values. That is actually a fair assumption considering how the game attempts to appropriate randomness from the human player. Adding the spawn count at $990C will not affect the distribution because the count increases uniformly between calls. The application of a bit mask at $990E is equivalent to applying modulo 8, which also does not affect the distribution. Consequentially, the check at $9910 jumps to invalidIndex 1/8 of the time. And, the chance of arriving at the check at $9918 that compares the newly selected piece against the prior piece is 7/8 where the probability of a match is 1/7. This means that there is additional chance of 7/8 × 1/7 = 1/8 of it ending up at invalidIndex. Overall, there is a 25% chance of using the biased code and a 75% chance of using code that picks Tetriminos uniformly.

In a set of 224 spawned Tetriminos, the mathematical expectation is 32 instances of each type. But, the code will actually produce the following distribution.

Meaning, in clearing 90 rows and reaching level 9, the player will encounter one additional T and S and one fewer L and I than statistically expected.

Apparently, at least in Nintendo Tetris, there is some truth behind the notation that the I Tetrimino never shows up when you need it.

Type	Frequency
T	33
J	32
Z	32
O	32
S	33
L	31
I	31

Type	Probability
T	14.73%
J	14.29%
Z	14.29%
O	14.29%
S	14.73%
L	13.84%
I	13.84%

Shifting Tetriminos

Nintendo Tetris provides Delayed Auto Shift (DAS). Pressing Left or Right immediately shifts the active Tetrimino 1 cell horizontally. While, holding down one of those direction buttons causes the game to automatically shift the piece every 6 frames after an initial delay of 16 frames.

89AE: LDA $0040  
89B0: STA $00AE  ; originalX = tetriminoX;

89B2: LDA $00B6  ; if (pressing down) { 
89B4: AND #$04   ;   return;
89B6: BNE $8A09  ; } 

89B8: LDA $00B5  ; if (just pressed left/right) {
89BA: AND #$03   ;   goto resetAutorepeatX;
89BC: BNE $89D3  ; }

89BE: LDA $00B6  ; if (not pressing left/right) {
89C0: AND #$03   ;   return;  
89C2: BEQ $8A09  ; }

89C4: INC $0046  ; autorepeatX++;
89C6: LDA $0046  ; if (autorepeatX < 16) {
89C8: CMP #$10   ;   return; 
89CA: BMI $8A09  ; }
 
89CC: LDA #$0A
89CE: STA $0046  ; autorepeatX = 10;
89D0: JMP $89D7  ; goto buttonHeldDown;       

resetAutorepeatX:

89D3: LDA #$00
89D5: STA $0046  ; autorepeatX = 0;

buttonHeldDown:
 
89D7: LDA $00B6  ; if (not pressing right) {
89D9: AND #$01   ;   goto notPressingRight;
89DB: BEQ $89EC  ; }

89DD: INC $0040  ; tetriminoX++;
89DF: JSR $948B  ; if (new position not valid) {
89E2: BNE $8A01  ;   goto restoreX;
                 ; }

89E4: LDA #$03
89E6: STA $06F1  ; play shift sound effect;
89E9: JMP $8A09  ; return;

notPressingRight:

89EC: LDA $00B6  ; if (not pressing left) {
89EE: AND #$02   ;   return;
89F0: BEQ $8A09  ; }

89F2: DEC $0040  ; tetriminoX--;
89F4: JSR $948B  ; if (new position not valid) {
89F7: BNE $8A01  ;   goto restoreX;
                 ; }

89F9: LDA #$03
89FB: STA $06F1  ; play shift sound effect;
89FE: JMP $8A09  ; return;

restoreX:

8A01: LDA $00AE  
8A03: STA $0040  ; tetriminoX = originalX;

8A05: LDA #$10          
8A07: STA $0046  ; autorepeatX = 16;

8A09: RTS        ; return;

Similar to the rotation code, a temporary variable is used to backup the x-coordinate in case the new position turns out to be invalid.

Also, note that a check prevents shifting the piece while the player is pressing Down.

Dropping Tetriminos

The speed at which Tetriminos automatically drop is a function of the level. The speeds are encoded as rendered frames per drop in a table located at $898E. Since the NES runs at 60.0988 frames/sec, the period between drops and the speed can be computed.

The table only contains 30 entries. Above level 29, the frames per drop is locked at 1.

An integer number of frames per drop is not a very granular way of representing speed. As shown in the chart below, speed increases exponentially with level. In fact, level 29 is twice as fast as level 28.

Level	Frames/drop	Period (sec/drop)	Speed (drops/sec)
0	48	.799	1.25
1	43	.715	1.40
2	38	.632	1.58
3	33	.549	1.82
4	28	.466	2.15
5	23	.383	2.61
6	18	.300	3.34
7	13	.216	4.62
8	8	.133	7.51
9	6	.100	10.02
10–12	5	.083	12.02
13–15	4	.067	15.05
16–18	3	.050	20.03
19–28	2	.033	30.05
29+	1	.017	60.10

At 1 frame/drop, the player has at most 1/3 of a second to position the piece once it starts moving. At that drop speed, the DAS does not permit the piece to reach the edges of the playfield before lock, quickly ending the game for most humans. However, some players, most notably Thor Aackerlund, overcome the DAS by rapidly vibrating the D-pad. From the shift code above, as long as the horizontal direction button is released exactly every other frame, it is possible to shift the Tetrimino at half the rate that it drops on levels 29 and above. That is the theoretical maximum, but any vibration of the thumb above 3.75 presses/sec will overcome the initial 16 frame delay.

If a timed automatic drop and a player controlled soft drop (pressing Down) coincide within the same frame, the effect is not cumulative. Either or both of those events will cause the piece to advance downward exactly one cell in that frame.

8914: LDA $004E    ; if (autorepeatY > 0) {
8916: BPL $8922    ;   goto autorepeating;
                   ; } else if (autorepeatY == 0) {
                   ;   goto playing;
                   ; }

                   ; game just started
                   ; initial Tetrimino hanging at spawn point 

8918: LDA $00B5    ; if (not just pressed down) { 
891A: AND #$04     ;   goto incrementAutorepeatY;
891C: BEQ $8989    ; }

                   ; player just pressed down ending startup delay

891E: LDA #$00     
8920: STA $004E    ; autorepeatY = 0;
8922: BNE $8939    

playing:

8924: LDA $00B6    ; if (left or right pressed) {
8926: AND #$03     ;   goto lookupDropSpeed;
8928: BNE $8973    ; }

                   ; left/right not pressed

892A: LDA $00B5    
892C: AND #$0F     ; if (not just pressed only down) {
892E: CMP #$04     ;   goto lookupDropSpeed;
8930: BNE $8973    ; }

                   ; player exclusively just presssed down

8932: LDA #$01
8934: STA $004E    ; autorepeatY = 1;

8936: JMP $8973    ; goto lookupDropSpeed;

autorepeating:

8939: LDA $00B6   
893B: AND #$0F     ; if (down pressed and not left/right) {
893D: CMP #$04     ;   goto downPressed;
893F: BEQ $894A    ; }  

                   ; down released

8941: LDA #$00    
8943: STA $004E    ; autorepeatY = 0
8945: STA $004F    ; holdDownPoints = 0
8947: JMP $8973    ; goto lookupDropSpeed;

downPressed:

894A: INC $004E    ; autorepeatY++;
894C: LDA $004E
894E: CMP #$03     ; if (autorepeatY < 3) {
8950: BCC $8973    ;   goto lookupDropSpeed;
                   ; }

8952: LDA #$01   
8954: STA $004E    ; autorepeatY = 1;

8956: INC $004F    ; holdDownPoints++;

drop:

8958: LDA #$00     
895A: STA $0045    ; fallTimer = 0;

895C: LDA $0041   
895E: STA $00AE    ; originalY = tetriminoY;

8960: INC $0041    ; tetriminoY++;
8962: JSR $948B    ; if (new position valid) {
8965: BEQ $8972    ;   return;
                   ; }

                   ; the piece is locked

8967: LDA $00AE  
8969: STA $0041    ; tetriminoY = originalY;

896B: LDA #$02   
896D: STA $0048    ; playState = UPDATE_PLAYFIELD;
896F: JSR $9CAF    ; updatePlayfield();
 
8972: RTS          ; return;

lookupDropSpeed:

8973: LDA #$01     ; tempSpeed = 1;

8975: LDX $0044    ; if (level >= 29) {
8977: CPX #$1D     ;   goto noTableLookup;
8979: BCS $897E    ; }
  
897B: LDA $898E,X  ; tempSpeed = framesPerDropTable[level];
 
noTableLookup:

897E: STA $00AF    ; dropSpeed = tempSpeed;

8980: LDA $0045    ; if (fallTimer >= dropSpeed) {
8982: CMP $00AF    ;   goto drop;
8984: BPL $8958    ; }

8986: JMP $8972    ; return;

incrementAutorepeatY:

8989: INC $004E    ; autorepeatY++;
898B: JMP $8972    ; return;

The frames-per-drop table is referenced at label lookupDropSpeed. As mentioned above, the speed defaults to 1 drop/frame when the level is 29 or higher.

The fallTimer ($0045) triggers a drop when it reaches the dropSpeed ($00AF). The fallTimer is incremented at $8892, outside of the snippet above. It is reset to 0 upon an automatic or soft drop.

The variable autorepeatY ($004E) is initialized to $0A (at $8739), which is interpreted as −96. The condition at the very top causes an opening entry delay. The very first Tetrimino remains suspended at the spawn location until autorepeatY is incremented to 0, which takes 1.6 seconds. However, pressing down during this phase immediately sets autorepeatY to 0. Interestingly, it is possible to shift and rotate during the opening entry delay without cancelling it.

autorepeatY is incremented if Down is held. When it reaches 3, a soft drop happens and autorepeatY is set to 1. Consequentially, the initial soft drop requires 3 frames, but from there it repeats every other frame.

In addition, autorepeatY will advance from 0 to 1 only if the game detects that the player just pressed Down (via $00B5) as opposed to detecting that Down is held. This is significant because autorepeatY is reset to 0 when a Tetrimino is spawned (at $98E8), providing an important feature: if the player soft drops a piece into lock and he inadvertently continues to keep Down held through the subsequent spawn, which is a common occurrence at higher levels, it will not cause the new piece to soft drop. To convey that intension, the player must release Down before subsequently reusing it.

Soft drops can potentially increase the score. holdDownPoints ($004F) is incremented for each drop, but it is reset to 0 when Down is released. As a result, to gain points, the Tetrimino needs to be soft dropped into lock. Any brief soft drop that might occur prior along the way in positioning the piece will not contribute to the score. The score is updated at $9BFE and holdDownPoints is reset to 0 shortly afterward at $9C2F.

A check that prevents the player from soft dropping while shifting complicates gaining points. It means that the final move must be down.

When a drop occurs, tetriminoY ($0041) is backed up to originalY ($00AE). If the new position created by incrementing tetriminoY turns out to be invalid (it either pushed through the floor of the playfield or it overlapped other existing squares), then the Tetrimino was actually supported in the prior position. In that event, tetriminoY is restored and the piece is considered locked. This means that the lock delay—the maximum number of frames that a Tetrimino waits while supported before locking—is equal to the drop delay.

Slides and Spins

The Nintendo Tetris Instruction Booklet contains an illustrated lesson on how to slide:

A slide involves shifting across the surface of other pieces or across the floor of the playfield usually with the intension of positioning a piece under an overhang. It is possible to slide until the fall timer reaches the drop speed at which point the piece will lock. Below is an animated example.

On the other hand, spins rotate pieces into spaces unreachable by any other means (see below).

Like slides, spins would not be possible without lock delay. But, spins also exploit the way that the game manipulates pieces. Prior to moving or rotating a piece, the game verifies that all of the Tetrimino's squares when repositioned are situated on empty cells within the bounds of the playfield. That check, which is listed below, does not inhibit rotation through adjacent solid blocks.

948B: LDA $0041     
948D: ASL           
948E: STA $00A8
9490: ASL
9491: ASL           
9492: CLC
9493: ADC $00A8
9495: ADC $0040
9497: STA $00A8 

9499: LDA $0042     
949B: ASL
949C: ASL
949D: STA $00A9
949F: ASL           
94A0: CLC
94A1: ADC $00A9     
94A3: TAX          ; index = 12 * orientationID;
94A4: LDY #$00

94A6: LDA #$04
94A8: STA $00AA    ; for(i = 0; i < 4; i++) {

94AA: LDA $8A9C,X  ;   squareY = orientationTable[index];
94AD: CLC
94AE: ADC $0041    ;   cellY = squareY + tetriminoY; 
94B0: ADC #$02     ;   if (cellY < -2 || cellY >= 20) {
94B2: CMP #$16     ;     return false;
94B4: BCS $94E9    ;   }

94B6: LDA $8A9C,X
94B9: ASL
94BA: STA $00AB
94BC: ASL
94BD: ASL
94BE: CLC
94BF: ADC $00AB
94C1: CLC
94C2: ADC $00A8
94C4: STA $00AD 

94C6: INX
94C7: INX          ;   index += 2;

94C8: LDA $8A9C,X  ;   squareX = orientationTable[index];
94CB: CLC
94CC: ADC $00AD    
94CE: TAY          ;   cellX = squareX + tetriminoX;
94CF: LDA ($B8),Y  ;   if (playfield[10 * cellY + cellX] != EMPTY_TILE) {
94D1: CMP #$EF     ;     return false;
94D3: BCC $94E9    ;   }

94D5: LDA $8A9C,X
94D8: CLC          
94D9: ADC $0040    ;   if (cellX < 0 || cellX >= 10) { 
94DB: CMP #$0A     ;     return false;
94DD: BCS $94E9    ;   }

94DF: INX          ;   index++;
94E0: DEC $00AA    
94E2: BNE $94AA    ; }

94E4: LDA #$00     
94E6: STA $00A8    
94E8: RTS          ; return true;

94E9: LDA #$FF     
94EB: STA $00A8    
94ED: RTS

As discussed in an earlier section, each row of the orientation table contains 12 bytes; hence, the index into the table is computed by multiplying the active Tetrimino’s orientation ID by 12. As shown below, all of the multiplications in the subroutine are performed via shifts and additions.

index = (orientationID << 3) + (orientationID << 2);  // index = 8 * orientationID + 4 * orientationID;
        
(cellY << 3) + (cellY << 1)  // 8 * cellY + 2 * cellY

Each iteration of the loop offsets the Tetrimino’s position by the relative coordinates of one of the squares from the orientation table to obtain the corresponding playfield cell location. Then, it verifies that the cell coordinates are within the bounds of the playfield and that the cell itself is empty.

94AA: LDA $8A9C,X  ;   squareY = orientationTable[index];
94AD: CLC
94AE: ADC $0041    ;   cellY = squareY + tetriminoY; 
94B0: ADC #$02     ;   if (cellY + 2 >= 22) {
94B2: CMP #$16     ;     return false;
94B4: BCS $94E9    ;   }

In addition to cells of the visible rows, the code treats the cells of the 2 hidden rows above the playfield as legal square positions without using a compound condition. This works because in two's-complement, negative numbers represented by single-byte variables are equivalent to values above 127. In this case, the minimum value of cellY is −2, which is stored as $FE (254 in decimal).

The playfield index is sum of cellY multiplied by 10 and cellX. However, when cellY is −1 ($FF = 255) or −2 ($FE = 254), the product yields −10 ($F6 = 246) and −20 ($EC = 236) respectively. When in range, cellX can be as large as 9, producing a maximum index of 246 + 9 = 255, well past the end of the playfield. However, the game initializes $0400–$04FF to $EF (the empty tile) providing 56 extra bytes of padding.

Oddly, the cellX range check is performed after the playfield cell is examined. But, it will function correctly in either order. The range check also avoids a compound condition as denoted by the revised comments below.

94D5: LDA $8A9C,X
94D8: CLC          
94D9: ADC $0040    ;   if (cellX >= 10) { 
94DB: CMP #$0A     ;     return false;
94DD: BCS $94E9    ;   }

Further examples of spins made possible by the way this code validates positions appear below.

The AI takes advantage of the full range of motion available in Nintendo Tetris including slides and spins.

Level 30 and Beyond

96B8: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

As illustrated below, the pattern table is organized such that tiles $00 to $0F are the glyphs for 0 to F. This means that displaying a digit of a number, decimal or hexadecimal, involves using that digit value directly as the index into the pattern table. In this case, the level values are stored as binary-coded decimal (BCD); each nibble of each byte in the sequence is a tile value.

Unfortunately, the game designers apparently assumed that no one would get past level 29 and consequentially, they decided to put only 30 entries into the table. The strange displayed values are the various bytes beyond. Only a single byte (at $0044) is used for level number, causing the game to slowly cycle through the 256 values shown below.

The first 20 successive values are actually another table that stores the offsets into the playfield for each of the 20 rows.

00	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15
1	16	17	18	19	20	21	22	23	24	25	26	27	28	29	00	0A
2	14	1E	28	32	3C	46	50	5A	64	6E	78	82	8C	96	A0	AA
3	B4	BE	C6	20	E6	20	06	21	26	21	46	21	66	21	86	21
4	A6	21	C6	21	E6	21	06	22	26	22	46	22	66	22	86	22
5	A6	22	C6	22	E6	22	06	23	26	23	85	A8	29	F0	4A	4A
6	4A	4A	8D	07	20	A5	A8	29	0F	8D	07	20	60	A6	49	E0
7	15	10	53	BD	D6	96	A8	8A	0A	AA	E8	BD	EA	96	8D	06
8	20	CA	A5	BE	C9	01	F0	1E	A5	B9	C9	05	F0	0C	BD	EA
9	96	38	E9	02	8D	06	20	4C	67	97	BD	EA	96	18	69	0C
A	8D	06	20	4C	67	97	BD	EA	96	18	69	06	8D	06	20	A2
B	0A	B1	B8	8D	07	20	C8	CA	D0	F7	E6	49	A5	49	C9	14
C	30	04	A9	20	85	49	60	A5	B1	29	03	D0	78	A9	00	85
D	AA	A6	AA	B5	4A	F0	5C	0A	A8	B9	EA	96	85	A8	A5	BE
E	C9	01	D0	0A	A5	A8	18	69	06	85	A8	4C	BD	97	A5	B9
F	C9	04	D0	0A	A5	A8	38	E9	02	85	A8	4C	BD	97	A5	A8

96D6: 00 ;   0
96D7: 0A ;  10
96D8: 14 ;  20
96D9: 1E ;  30
96DA: 28 ;  40
96DB: 32 ;  50
96DC: 3C ;  60
96DD: 46 ;  70
96DE: 50 ;  80
96DF: 5A ;  90
96E0: 64 ; 100
96E1: 6E ; 110
96E2: 78 ; 120
96E3: 82 ; 130
96E4: 8C ; 140
96E5: 96 ; 150
96E6: A0 ; 160
96E7: AA ; 170
96E8: B4 ; 180
96E9: BE ; 190

Since the playfield starts at $0400 and each row contains 10 cells, the address of an arbitrary cell is:

Considering that the processor does not directly support multiplication, that lookup table provides an extremely fast way of obtaining the product.

$0400 + [$96D6 + y] + x

A related table occupies the next 40 bytes. It contains 20 addresses, stored little endian, into nametable 0, the region of VRAM holding background tile values. They are pointers to the rows of the playfield offset by $06.

Lines and Statistics

The number of completed lines and the Tetrimino statistics occupy 2 bytes each at the following locations.

The values are essentially stored as little endian 16-bit packed BCD. For example, a line count of 123 is represented below. The bytes appear right-to-left to order the decimal digits.

Addresses	Count
0050–0051	Lines
03F0–03F1	T
03F2–03F3	J
03F4–03F5	Z
03F6–03F7	O
03F8–03F9	S
03FA–03FB	L
03FC–03FD	I

However, the game designers assumed that none of the values would ever exceed 999. As such, the display logic properly treats the first byte as packed BCD, each nibble serving as a tile value. But, the entire second byte effectively acts the upper decimal digit. Whenever the lower digits rolls over from 99 to 00, the second byte is simply incremented. Ultimately, the second byte cycles through all 256 tiles. Below, you can see this mid-action.

9BA8: INC $0050  ; increment middle-lowest digit pair
9BAA: LDA $0050  
9BAC: AND #$0F    
9BAE: CMP #$0A   ; if (lowest digit > 9) {
9BB0: BMI $9BC7     
9BB2: LDA $0050   
9BB4: CLC        
9BB5: ADC #$06   ;   set lowest digit to 0, increment middle digit
9BB7: STA $0050   
9BB9: AND #$F0   
9BBB: CMP #$A0   ;   if (middle digit > 9) {
9BBD: BCC $9BC7       
9BBF: LDA $0050     
9BC1: AND #$0F    
9BC3: STA $0050  ;     set middle digit to 0
9BC5: INC $0051  ;     increment highest digit
                 ;   }
                 ; }

Checks are performed on the middle and lowest digits to keep them between 0 and 9. But, the highest digit can be incremented indefinitely.

If the lowest digit is 0 after incrementing the line count, then the player just completed a set of 10 rows and the level number needs to be incremented as well. As you can see in the code that follows, an additional check is performed before incrementing the level.

9BC7: LDA $0050   
9BC9: AND #$0F    
9BCB: BNE $9BFB  ; if (lowest digit == 0) { 
9BCD: JMP $9BD0     

9BD0: LDA $0051     
9BD2: STA $00A9   
9BD4: LDA $0050   
9BD6: STA $00A8  ;   copy digits from $0050-$0051 to $00A8-$00A9

9BD8: LSR $00A9
9BDA: ROR $00A8
9BDC: LSR $00A9
9BDE: ROR $00A8  
9BE0: LSR $00A9  
9BE2: ROR $00A8  ;   treat $00A8-$00A9 as a 16-bit packed BCD value
9BE4: LSR $00A9  ;   and right-shift it 4 times
9BE6: ROR $00A8  ;   this leaves the highest and middle digits in $00A8 

9BE8: LDA $0044     
9BEA: CMP $00A8  ;   if (level < [$00A8]) {
9BEC: BPL $9BFB        

9BEE: INC $0044  ;     increment level
                 ;   }
                 ; }

The second check is related to the selected starting level. To advance to some level X, the player must clear 10X rows regardless of the starting level. For example, if the player starts at level 5, he will remain there until he clears 60 rows, at which point he will advance to level 6. From there, each additional 10 rows will increment the level number.

To perform this check, the completed lines value is copied from $0050–$0051 to $00A8–$00A9. Then, the copy is right-shifted 4 times, which for packed BCD is equivalent to dividing by 10. The lowest decimal digit is discarded and the upper and middle decimal digits shift over one position ending up as the nibbles of $00A8.

However, at $9BEA the level number is directly compared against the packed BCD value in $00A8. A table lookup to convert the BCD value to decimal is missing, an apparent bug. For instance, in the image above, the level number would be compared against $12 (18 in decimal) instead of 12. Consequentially, if the player decided to start at level 17, the level would actually advance at 120 lines because 18 exceeds 17.

The table below depicts the expected number of lines required to advance at each starting level against what actually happens due to the bug.

Expected matches actual for starting levels 0–9. In fact, starting level 9 only works coincidentally; 10–15 also advance at 100 lines because $10 is 16 in decimal. The largest gap between expected and actual is 60 lines.

I suspect that the bug is related to a late stage design change. Take a look at the menu screen that allows the player to select the starting level below.

There is no indication of how to start beyond level 9. But, the Nintendo Tetris Instruction Booklet reveals the secret:

That hidden feature feels like an afterthought. It might have been introduced very close to the target release date, limiting the amount of testing that could be performed.

The starting line check actually contains a second bug related to values going out of range. The code comments are revised below to better convey what is happening at the lower level.

9BE8: LDA $0044     
9BEA: CMP $00A8  ; if (level - [$00A8] < 0) {
9BEC: BPL $9BFB        

9BEE: INC $0044  ;   increment level
                 ; }

The comparison is performed by subtraction and testing the sign of the result. But, a 1-byte signed number is limited to the range −128 to 127. If the difference is less than −128, then it wraps around and the result is a positive number. The concept is conveyed in the further revised comments below.

9BE8: LDA $0044  ; difference = level - [$00A8];   
9BEA: CMP $00A8  ; if (difference < 0 && difference >= -128) {
9BEC: BPL $9BFB        

9BEE: INC $0044  ;   increment level
                 ; }

In evaluating when the difference ends up in that range, consider that the level number wraps around to 0 when it is incremented beyond 255 and $00A8 could potentially contain any value because its upper nibble originates from $0051, which is incremented indefinitely.

These effects collude together to produce periods where the level number erroneously remains constant. The periods occur at regular intervals of 2900 lines starting at 2190 lines and they last for 800 lines. For instance, from 2190 (L90) to 2990 (T90), the level remains as $DB (96), as shown below.

The next period happens from 5090 to 5890, the level fixed at $AD (06). And, during the periods, the color palette also remains the same.

Coloring Tetriminos

The Tetrimino tiles are assigned 4 distinct colors in each level. The colors originate from a table at $984C. Its entries are reused every 10 levels.

984C: 0F 30 21 12  ; level 0
9850: 0F 30 29 1A  ; level 1
9854: 0F 30 24 14  ; level 2
9858: 0F 30 2A 12  ; level 3
985C: 0F 30 2B 15  ; level 4
9860: 0F 30 22 2B  ; level 5
9864: 0F 30 00 16  ; level 6
9868: 0F 30 05 13  ; level 7
986C: 0F 30 16 12  ; level 8
9870: 0F 30 27 16  ; level 9

From left-to-right, the columns of that table correspond to the black, white, blue and red regions in the image below respectively.

The first 2 colors of every entry are black and white. However, the first color is actually ignored; regardless of its value, it is treated as a transparent color through which the solid black background is exposed.

9808: LDA $0064     
980A: CMP #$0A      
980C: BMI $9814     
980E: SEC           
980F: SBC #$0A                          
9811: JMP $980A    ; index = levelNumber % 10;
 
9814: ASL          
9815: ASL
9816: TAX          ; index *= 4;

9817: LDA #$00
9819: STA $00A8    ; for(i = 0; i < 32; i += 16) {

981B: LDA #$3F    
981D: STA $2006    
9820: LDA #$08
9822: CLC
9823: ADC $00A8    
9825: STA $2006    ;   palette = $3F00 + i + 8;

9828: LDA $984C,X  
982B: STA $2007    ;   palette[0] = colorTable[index + 0];

982E: LDA $984D,X  
9831: STA $2007    ;   palette[1] = colorTable[index + 1];

9834: LDA $984E,X  
9837: STA $2007    ;   palette[2] = colorTable[index + 2];

983A: LDA $984F,X
983D: STA $2007    ;   palette[3] = colorTable[index + 3];

9840: LDA $00A8
9842: CLC
9843: ADC #$10
9845: STA $00A8    
9847: CMP #$20
9849: BNE $981B    ; }

984B: RTS          ; return;

The index into the color table is based on the level number modulo 10. The loop copies an entry to the palette tables in VRAM.

Modulo is emulated by repeatedly subtracting 10 until the result is less than 10. Below, the top of the subroutine is listed with revised comments to reflect this.

9808: LDA $0064 ; index = levelNumber;    
980A: CMP #$0A  ; while(index >= 10) {
980C: BMI $9814    
980E: SEC            
980F: SBC #$0A  ;   index -= 10;                      
9811: JMP $980A ; }

However, as discussed in the prior section, comparison involves subtracting and branching based on the sign of the difference. And, a 1-byte signed number is limited to the range −128 to 127. The updated comments below factor in those ideas.

9808: LDA $0064 ; index = levelNumber; 
                ; difference = index - 10;    
980A: CMP #$0A  ; while(difference >= 0 && difference <= 127) {
980C: BMI $9814    
980E: SEC       ;   index -= 10;       
980F: SBC #$0A  ;   difference = index - 10;                    
9811: JMP $980A ; }

9808: LDA $0064 ; index = levelNumber;                 
980A: CMP #$0A  ; while(index >= 10 && index <= 137) {
980C: BMI $9814    
980E: SEC              
980F: SBC #$0A  ;   index -= 10;                       
9811: JMP $980A ; }

This formulation exposes a bug in the code. The modulo operation is completely bypassed for levels 138 and up. Instead, the index is directly assigned to the level number, providing access to the bytes well beyond the end of the color table. This can even result in nearly invisible Tetriminos as shown below.

The colors of all 256 levels are depicted below. The tiles are arranged in 10 columns to reflect the cyclic application of the color table that breaks down at level 138. The row and column headers are in decimal.

Also, as mentioned in the prior section, some levels will not advance until 800 lines are cleared. The colors remain constant throughout those long levels.

Game Mode

The game mode, maintained at $00C0, determines which of the various screens and menus is currently presented to the user.

As demonstrated below, the game contains a cleverly written subroutine that acts as a switch statement via a little endian jump table located directly after the call.

Value	Description
00	Legal Screen
01	Title Screen
02	Game Type Menu
03	Level and Height Menu
04	Play / High Score Screen / Ending / Pause
05	Demo

8161: LDA $00C0  
8163: JSR $AC82  ; switch(gameMode) {
8166: 00 82      ;   case 0: goto 8200;  // Legal Screen
8168: 4F 82      ;   case 1: goto 824F;  // Title Screen
816A: D1 82      ;   case 2: goto 82D1;  // Game Type Menu
816C: D7 83      ;   case 3: goto 83D7;  // Level and Height Menu
816E: 5D 81      ;   case 4: goto 815D;  // Play / High Score Screen / Ending / Pause
8170: 5D 81      ;   case 5: goto 815D;  // Demo
                 ; }

The listing above also reveals the addresses of all the game modes. Note that play and demo mode use the same code.

The subroutine never returns. Instead, the code takes advantage of the return address; it normally points to the instruction immediately following the jump-to-subroutine call (minus 1 byte), but in this case, it points to the jump table. The return address is popped off the stack and stored at $0000–$0001. With the jump table address captured, the code uses the value in the A register as the index and jumps accordingly.

AC82: ASL           
AC83: TAY           
AC84: INY           

AC85: PLA         
AC86: STA $0000      
AC88: PLA           ; pop return address off of stack
AC89: STA $0001     ; and store it at $0000-$0001

AC8B: LDA ($00),Y   
AC8D: TAX           
AC8E: INY           
AC8F: LDA ($00),Y   
AC91: STA $0001     
AC93: STX $0000     
AC95: JMP ($0000)   ; goto Ath 16-bit address
                    ; in table at [$0000-$0001]

The code is able to take advantage of this switching subroutine as long as the indices are all near 0 and there are few or no gaps between the possible cases.

Legal Screen

At the bottom, the screen aptly credits Alexey Pazhitnov (Alexéy Pájitnov) for conceiving, designing and programming the original Tetris. In 1984, while working as a computer engineer at the Dorodnitsyn Computing Centre, a leading research institute of the Russian Academy of Sciences in Moscow, he developed the prototype on an Electronika 60, a Soviet clone of the DEC LSI-11. It was designed for green monochrome text mode, using pairs of brackets [] to represent squares. With the help of 16-year-old high school student Vadim Gerasimov and computer engineer Dmitry Pavlovsky, a few days after its inception, the prototype was ported to the IBM PC with Turbo Pascal under MS DOS. They collectively improved the game over 2 years introducing features such as Tetrimino colors and statistics and more importantly timing and graphics code that would make the game run consistently on the multitude of PC models and clones.

Unfortunately, due nature of the Soviet Union at the time, their attempts to monetize the game failed and they ultimately decided to share the PC version with friends gratis. From there, Tetris spread virally across the country and outward, copied from floppy to floppy. However, since the game was developed by employees of a government institution, it was owned by the state and in 1987, the organization in charge of international trade of electronic technology, Electronorgtechnica (ELORG) became responsible for licensing the game. The V/O abbreviation in the legal screen might be short for, "Version Originale".

A British software company called Andromeda attempted to secure the rights to Tetris and before completing the deal, they sublicensed the game to other vendors, such as the United Kingdom computer game publisher Mirrorsoft. Mirrorsoft, in turn, sublicensed it further to Tengen, a subsidiary of Atari Games. And, Tengen provided Bullet-Proof Software with the rights to develop the game for computers and consoles in Japan, resulting in Tetris for Nintendo's Famicom, the legal screen of which is shown below.

Interestingly, in that version, high school student Vadim Gerasimov is credited as the original designer and programmer.

In seeking the handheld rights for the upcoming Game Boy, Nintendo ended up using Bullet-Proof Software to successfully broker a deal directly with ELORG. In the process, ELORG revised its contract with Andromeda, clarifying that Andromeda acquired computer and arcade rights only. This forced Bullet-Proof Software to pay royalties to ELORG for all the Famicom cartridges it sold since the rights they got from Tengen were bogus. But, by appeasing ELORG, it helped Bullet-Proof Software to ultimately obtain the worldwide console rights for Nintendo.

Bullet-Proof Software sublicensed the handheld rights to Nintendo and they co-developed Game Boy Tetris as shown in the legal screen below.

With the worldwide console rights, Nintendo developed the version of Tetris for the NES discussed in this article. And, Bullet-Proof Software subsequently sublicensed the rights from Nintendo to enable them to continue to sell Famicom cartridges in Japan.

A complex legal battle ensued. Nintendo and Tengen each demanded that the other stop production and sale of their version of the game. Nintendo ultimately prevailed and hundreds of thousands of Tengen Tetris cartridges still in their boxes were scrapped. The judgment also blocked several other companies like Mirrorsoft from manufacturing a console version.

Pazhitnov never received any royalties from ELORG or the Soviet government. However, in 1991, he moved to the United States and in 1996, with backing from Henk Rogers, owner of Bullet-Proof Software, he cofounded The Tetris Company, enabling him to profit from mobile and modern console versions.

As intriguing as it is to view the legal screen as a window into the humble origin of the game and the intellectual properties rights battle that followed, as far as most players are concerned, it is just an annoying screen that takes forever to disappear. The delay is established by 2 counters that tick down in succession from 255 to 0. The first phase is unskippable, but the second phase can be cut short by pressing Start. As such, the legal screen appears for a minimum of 4.25 seconds and up to 8.5 seconds. Though, I imagine that most players give up pressing Start during the first interval forcing them to wait through the whole thing.

The timing of the phases, as well as the rest of the game, is regulated by a non-maskable interrupt handler that is invoked at the start of each vertical blanking interval, the brief period between the rendering of television frames. Meaning, every 16.6393 milliseconds, normal program flow is interrupted by the following code.

8005: PHA        
8006: TXA
8007: PHA        
8008: TYA
8009: PHA        ; save A, X, Y

800A: LDA #$00
800C: STA $00B3
800E: JSR $804B  ; render();

8011: DEC $00C3  ; legalScreenCounter1--;

8013: LDA $00C3  
8015: CMP #$FF   ; if (legalScreenCounter1 < 0) {
8017: BNE $801B  ;   legalScreenCounter1 = 0;
8019: INC $00C3  ; }

801B: JSR $AB5E  ; initializeOAM();

801E: LDA $00B1
8020: CLC
8021: ADC #$01
8023: STA $00B1
8025: LDA #$00
8027: ADC $00B2
8029: STA $00B2  ; frameCounter++;

802B: LDX #$17
802D: LDY #$02
802F: JSR $AB47  ; randomValue = generateNextPseudorandomNumber(randomValue);

8032: LDA #$00
8034: STA $00FD
8036: STA $2005  ; scrollX = 0;
8039: STA $00FC
803B: STA $2005  ; scrollY = 0;  

803E: LDA #$01
8040: STA $0033  ; verticalBlankingInterval = true;

8042: JSR $9D51  ; pollControllerButtons();

8045: PLA
8046: TAY
8047: PLA
8048: TAX
8049: PLA        ; restore A, X, Y

804A: RTI        ; resume interrupted task

The handler starts out by pushing the values of the primary registers onto the stack and popping them off at the end to avoid interfering with the interrupted task. The call to render() updates VRAM, converting memory model representations into something that appears on screen. Next, the handler decrements the first legal screen counter if it is greater than zero. The initializeOAM() call performs a step required by the frame generation hardware. The handler continues by incrementing the frame counter, a 16-bit little endian value stored at $00B1–$00B2, which is used in various places for controlled timing. After which, the next pseudorandom number is generated; as mentioned, this occurs at least once per frame regardless of the mode. At $8040, the vertical blanking interval flag is set to indicate that the handler just executed. Finally, the controller buttons are polled; the behavior of that subroutine is described further in the Demo section.

The verticalBlankingInterval flag is used by the subroutine listed below. It spins until an execution of the interrupt handler occurs.

AA2F: JSR $E000  ; updateAudio();

AA32: LDA #$00
AA34: STA $0033  ; verticalBlankingInterval = false;

AA36: NOP

AA37: LDA $0033  
AA39: BEQ $AA37  ; while(!verticalBlankingInterval) { }

AA3B: LDA #$FF
AA3D: LDX #$02
AA3F: LDY #$02
AA41: JSR $AC6A  ; fill memory page 2 with all $FF's

AA44: RTS        ; return;

That blocking subroutine is used by the 2 timing phases of the legal screen, shown below, which run consecutively.

8236: LDA #$FF
8238: JSR $A459

...

A459: STA $00C3  ; legalScreenCounter1 = 255;

A45B: JSR $AA2F  ; do {
A45E: LDA $00C3  ;   waitForVerticalBlankingInterval();
A460: BNE $A45B  ; } while(legalScreenCounter1 > 0);

A462: RTS        ; return;

823B: LDA #$FF
823D: STA $00A8  ; legalScreenCounter2 = 255;

                 ; do {

823F: LDA $00F5  ;   if (just pressed Start) {
8241: CMP #$10   ;     break;
8243: BEQ $824C  ;   }

8245: JSR $AA2F  ;   waitForVerticalBlankingInterval();

8248: DEC $00A8  ;   legalScreenCounter2--;
824A: BNE $823F  ; } while(legalScreenCounter2 > 0);

824C: INC $00C0  ; gameMode = TITLE_SCREEN;

Demo

The demo presents approximately 80 seconds of pre-recorded gameplay. It takes advantage of the same engine that runs during play as opposed to simply displaying a movie file. Two tables are involved in the reproduction. The first, located at $DF00, stores the following Tetrimino spawn sequence:

T J T S Z J T S Z J S Z L Z J T T S I T O J S Z L Z L I O L Z L I O J T S I T O J

During spawning, the piece is either randomly selected or it is pulled from the table depending on the mode. The switch occurs at $98EB.

98EB: LDA $00C0    
98ED: CMP #$05
98EF: BNE $9903    ; if (gameMode == DEMO) { 

98F1: LDX $00D3   
98F3: INC $00D3       
98F5: LDA $DF00,X  ;   value = demoTetriminoTypeTable[++demoIndex];  

98F8: LSR
98F9: LSR
98FA: LSR
98FB: LSR          
98FC: AND #$07
98FE: TAX          ;   tetriminoType = bits 6,5,4 of value;

98FF: LDA $994E,X     
9902: RTS          ;   return spawnTable[tetriminoType];
                   ; } else {
                   ;   pickRandomTetrimino();
                   ; }

Tetrimino type is extracted from bits 6, 5 and 4 of each byte. Occasionally, this yields a value of $07, an invalid type. However, the spawn table ($994E) used to convert Tetrimino type into orientation ID is actually sandwiched between 2 related tables:

993B: 00 00 00 00  ; T
993F: 01 01 01 01  ; J
9943: 02 02        ; Z
9945: 03           ; O
9946: 04 04        ; S
9948: 05 05 05 05  ; L
994C: 06 06        ; I

994E: 02  ; Td
994F: 07  ; Jd
9950: 08  ; Zh
9951: 0A  ; O
9952: 0B  ; Sh
9953: 0E  ; Ld
9954: 12  ; Ih

9956: 02 02 02 02  ; Td
995A: 07 07 07 07  ; Jd
995E: 08 08        ; Zh
9960: 0A           ; O
9961: 0B 0B        ; Sh
9963: 0E 0E 0E 0E  ; Ld
9967: 12 12        ; Ih

The value $07 causes it to read past the end of the table into the next one, bearing Td ($02).

Due to this effect, this scheme can provide an unlimited yet reproducible sequence of pseudorandom spawn orientation IDs. The code will function given any arbitrary address to a varying byte sequence making it impossible to determine where the table ends. In fact, the sequence at $DF00 may actually be part of something entirely unrelated especially considering that the purpose of the remaining 5 nonzero bits is unclear and that the generated sequence appears to contain repetition.

The index into the table ($00D3) is reset to 0 during demo mode initialization at $872B.

The second demo table contains a recording of the gamepad buttons encoded in pairs of bytes. The bits of the first byte correspond to the asserted buttons.

The second byte stores the number of frames that the button combination was applied.

7	6	5	4	3	2	1	0
A	B	Select	Start	Up	Down	Left	Right

The table spans $DD00–$DEFF, composed of 256 pairs. It is accessed by the subroutine at $9D5B.

9D5B: LDA $00D0    ; if (recording mode) {
9D5D: CMP #$FF     ;   goto recording;
9D5F: BEQ $9DB0    ; }

9D61: JSR $AB9D    ; pollController();
9D64: LDA $00F5    ; if (start button pressed) {
9D66: CMP #$10     ;   goto startButtonPressed;
9D68: BEQ $9DA3    ; }

9D6A: LDA $00CF    ; if (repeats == 0) {
9D6C: BEQ $9D73    ;   goto finishedMove;
                   ; } else {
9D6E: DEC $00CF    ;   repeats--;
9D70: JMP $9D9A    ;   goto moveInProgress;
                   ; }

finishedMove:

9D73: LDX #$00
9D75: LDA ($D1,X)
9D77: STA $00A8    ; buttons = demoButtonsTable[index];

9D79: JSR $9DE8    ; index++;

9D7C: LDA $00CE
9D7E: EOR $00A8
9D80: AND $00A8
9D82: STA $00F5    ; setNewlyPressedButtons(difference between heldButtons and buttons);

9D84: LDA $00A8
9D86: STA $00CE    ; heldButtons = buttons;

9D88: LDX #$00     
9D8A: LDA ($D1,X)
9D8C: STA $00CF    ; repeats = demoButtonsTable[index];

9D8E: JSR $9DE8    ; index++;

9D91: LDA $00D2    ; if (reached end of demo table) {
9D93: CMP #$DF     ;   return;
9D95: BEQ $9DA2    ; }

9D97: JMP $9D9E    ; goto holdButtons;

moveInProgress:

9D9A: LDA #$00
9D9C: STA $00F5    ; clearNewlyPressedButtons();

holdButtons:

9D9E: LDA $00CE
9DA0: STA $00F7    ; setHeldButtons(heldButtons);

9DA2: RTS          ; return;

startButtonPressed:

9DA3: LDA #$DD
9DA5: STA $00D2    ; reset index;

9DA7: LDA #$00
9DA9: STA $00B2    ; counter = 0;

9DAB: LDA #$01
9DAD: STA $00C0    ; gameMode = TITLE_SCREEN;

9DAF: RTS          ; return;

Since the demo buttons table is 512 bytes long, a 2-byte index is required to access it. The index is stored little endian at $00D1–$00D2. It is initialized to the address of the table at $872D and it is incremented via the following code.

                   
9DE8: LDA $00D1
9DEA: CLC        ; increment [$00D1]
9DEB: ADC #$01   ; possibly causing wrap around to 0
9DED: STA $00D1  ; which produces a carry

9DEF: LDA #$00
9DF1: ADC $00D2
9DF3: STA $00D2  ; add carry to [$00D2]

9DF5: RTS        ; return

The programmers actually left in the code for capturing player input, providing a glimpse into the development process and making it possible to replace the demo with an alternate recording. Demo recording mode is enabled when $00D0 is set to $FF. It triggers the following code designed to write to the demo buttons table.

recording:

9DB0: JSR $AB9D    ; pollController();

9DB3: LDA $00C0    ; if (gameMode != DEMO) {
9DB5: CMP #$05     ;   return;
9DB7: BNE $9DE7    ; }

9DB9: LDA $00D0    ; if (not recording mode) {
9DBB: CMP #$FF     ;   return;
9DBD: BNE $9DE7    ; }

9DBF: LDA $00F7    ; if (getHeldButtons() == heldButtons) {
9DC1: CMP $00CE    ;   goto buttonsNotChanged;
9DC3: BEQ $9DE4    ; }

9DC5: LDX #$00
9DC7: LDA $00CE
9DC9: STA ($D1,X)  ; demoButtonsTable[index] = heldButtons;

9DCB: JSR $9DE8    ; index++;

9DCE: LDA $00CF
9DD0: STA ($D1,X)  ; demoButtonsTable[index] = repeats;

9DD2: JSR $9DE8    ; index++;

9DD5: LDA $00D2    ; if (reached end of demo table) {
9DD7: CMP #$DF     ;   return;
9DD9: BEQ $9DE7    ; }

9DDB: LDA $00F7
9DDD: STA $00CE    ; heldButtons = getHeldButtons();

9DDF: LDA #$00
9DE1: STA $00CF    ; repeats = 0;
  
9DE3: RTS          ; return;

buttonsNotChanged:

9DE4: INC $00CF    ; repeats++;

9DE6: RTS          
9DE7: RTS          ; return;

But, the table is stored in PRG-ROM. Attempting to write to it has no effect on the stored data. Instead, each write triggers a bank switch resulting in the trippy effect shown below.

This suggests that the developers were able to execute the program partially or entirely in RAM.

To get around this inconvenience, I created lua/RecordDemo.lua, available in the source zip. After switching to demo recording mode, it redirects table writes to the Lua console. From there, the bytes can be copied and pasted into the ROM.

To record your own demo, first launch FCEUX and load the Nintendo Tetris ROM (File | Open ROM...). Then, open a Lua Script window (File | Lua | New Lua Script Window...) and either browse for the file or type in the path. When ready, press the Run button to begin demo recording mode, followed by a mouse click on the FCEUX window to restore the input focus. You will be able to control the pieces until the buttons table reaches capacity. At that point, the game will automatically return to the Title Screen. Press Stop in the Lua Script window to terminate the script. The recorded data will appear in the Output Console as shown below.

Select the full contents and copy it to the clipboard (Ctrl+C). Then, launch the Hex Editor (Debug | Hex Editor...). From the Hex Editor menu, select View | ROM File followed by File | Goto Address. In the Goto dialog box, enter 5D10 (the location of the demo buttons table in the ROM file) and press Ok. Next, paste the clipboard contents (Ctrl+V).

Finally, from the FCEUX menu, select NES | Reset. If you managed to follow all these steps, then the demo should be replaced by your recorded version.

If you wish to preserve your changes, from the Hex Editor menu, select File | Save Rom As... and enter in a name for the modified ROM file before hitting Save.

The Kill Screen

As discussed above, most players cannot endure the drop speed of level 29, which swiftly brings the game to an end. For this reason, it has become associated with the notation of a kill screen. But, technically, a kill screen prevents the player from advancing due to a bug whereas the rapid drop is actually a feature. The designers were kind enough to let the game continue as long as the player could maintain superhuman speed.

The actual kill screen occurs around 1550 lines. It manifests itself in different ways. Sometimes the game resets. Other times, the screen just goes black. Usually, the game freezes just after clearing a line as shown below. And, these effects are often preceded by random visual artifacts.

The kill screen is the result of a bug in the code that adds points to the score when lines are cleared. The 6-digit score is stored as little endian 24-bit packed BCD and it is located across $0053–$0055. A table is used to convert between number of lines cleared and gained points; each entry is a little endian 16-bit packed BCD value.

9CA5: 00 00  ; 0:    0
9CA7: 40 00  ; 1:   40
9CA9: 00 01  ; 2:  100
9CAB: 00 03  ; 3:  300
9CAD: 00 12  ; 4: 1200

After the total lines count and potentially the level are incremented, a value in that list is multiplied by level number plus one and the result is added to the score. This is nicely conveyed by a table in the Nintendo Tetris Instruction Booklet:

As listed below, that multiplication is emulated by a loop that repeatedly adds the points to the score. It executes when a piece is locked even when no lines are cleared.

9C31: LDA $0044
9C33: STA $00A8
9C35: INC $00A8    ; for(i = 0; i <= level; i++) {

9C37: LDA $0056    
9C39: ASL
9C3A: TAX          
9C3B: LDA $9CA5,X  ;   points[0] = pointsTable[2 * completedLines];

9C3E: CLC
9C3F: ADC $0053
9C41: STA $0053    ;   score[0] += points[0]; 

9C43: CMP #$A0     
9C45: BCC $9C4E    ;   if (upper digit of score[0] > 9) {

9C47: CLC
9C48: ADC #$60
9C4A: STA $0053    ;     upper digit of score[0] -= 10;
9C4C: INC $0054    ;     score[1]++;
                   ;   }

9C4E: INX
9C4F: LDA $9CA5,X  ;   points[1] = pointsTable[2 * completedLines + 1];

9C52: CLC
9C53: ADC $0054
9C55: STA $0054    ;   score[1] += points[1];

9C57: AND #$0F     
9C59: CMP #$0A
9C5B: BCC $9C64    ;   if (lower digit of score[1] > 9) {

9C5D: LDA $0054    
9C5F: CLC          ;     lower digit of score[1] -= 10;
9C60: ADC #$06     ;     increment upper digit of score[1];
9C62: STA $0054    ;   }

9C64: LDA $0054    
9C66: AND #$F0
9C68: CMP #$A0
9C6A: BCC $9C75    ;   if (upper digit of score[1] > 9) { 

9C6C: LDA $0054    
9C6E: CLC
9C6F: ADC #$60
9C71: STA $0054    ;     upper digit of score[1] -= 10;
9C73: INC $0055    ;     score[2]++;
                   ;   }

9C75: LDA $0055
9C77: AND #$0F
9C79: CMP #$0A
9C7B: BCC $9C84    ;   if (lower digit of score[2] > 9) {

9C7D: LDA $0055    
9C7F: CLC          ;     lower digit of score[2] -= 10;
9C80: ADC #$06     ;     increment upper digit of score[2];
9C82: STA $0055    ;   }

9C84: LDA $0055    
9C86: AND #$F0
9C88: CMP #$A0
9C8A: BCC $9C94    ;   if (upper digit of score[2] > 9) {

9C8C: LDA #$99
9C8E: STA $0053         
9C90: STA $0054         
9C92: STA $0055    ;     max out score to 999999;
                   ;   }

9C94: DEC $00A8
9C96: BNE $9C37    ; }

It is unfortunate that the Ricoh 2A03 lacks the binary-coded decimal mode of the 6502; it could have simplified much of the body of the loop. Instead, the addition is carried out stepwise using binary mode. Any digit that exceeds 9 after the addition is adjusted by effectively subtracting 10 and incrementing the digit directly to the left. For instance, $07 + $07 = $0E, which is converted to $14. But, that scheme is not entirely foolproof. For example, $09 + $09 = $12 and the checks are incapable of transforming that into $18. To compensate, none of the decimal digits in the entries of the points table exceed 6. Also, to save a check, the final digit of all the entries is 0.

This long and complicated loop takes time to execute. For high levels, the large number of iterations affects the timing of the game as each frame takes longer than 1/60th of a second to generate. That ultimately leads to the various manifestations of the kill screen.

The AI Lua Script caps the number of iterations of the loop at 30, the maximum value that the game designers expected it to reach, eliminating the kill screen.

Endings

And, the game rewards players who gain significantly high scores with one of five ending animations. The choice of ending is based entirely on the 2 left-most digits of the 6-digit score. As shown below, the player must achieve at least 30,000 points to receive any of the endings.

9A4D: LDA $0075
9A4F: CMP #$03   
9A51: BCC $9A5E  ; if (score[2] >= $03) {

9A53: LDA #$80
9A55: JSR $A459
9A58: JSR $9E3A
9A5B: JMP $9A64  ;   select ending; 
                 ; }

It should be noted that $0060–$007F is a mirror of $0040–$005F. The score is replicated across $0073–$0075.

If that first check passes, the ending animation is selected by the following switch.

             
A96E: LDA #$00
A970: STA $00C4
A972: LDA $0075  ; if (score[2] < $05) {
A974: CMP #$05   ;   ending = 0;
A976: BCC $A9A5  ; }

A978: LDA #$01
A97A: STA $00C4
A97C: LDA $0075  ; else if (score[2] < $07) {
A97E: CMP #$07   ;   ending = 1;
A980: BCC $A9A5  ; }

A982: LDA #$02
A984: STA $00C4
A986: LDA $0075  ; else if (score[2] < $10) {
A988: CMP #$10   ;   ending = 2;
A98A: BCC $A9A5  ; }

A98C: LDA #$03
A98E: STA $00C4
A990: LDA $0075  ; else if (score[2] < $12) {
A992: CMP #$12   ;   ending = 3;
A994: BCC $A9A5  ; }

A996: LDA #$04   ; else {
A998: STA $00C4  ;   ending = 4;
                 ; }

The endings consist of rockets of increasing size launched from a pad neighboring Saint Basil's Cathedral. The fourth ending depicts the Buran spacecraft, the Soviet version of the US Space Shuttle. In the best ending, the cathedral itself rockets up into the air as a UFO hovers over the launch pad. An image of each ending and its associated high score range appear below.

The B-Type game provides a different challenge, which the Nintendo Tetris Instruction Booklet describes as:

If the player successfully clears 25 lines, the game display an ending determined by the starting level. The endings for levels 0–8 consists of animals and objects flying or running across the frame, enigmatically passing behind Saint Basil's Cathedral. The UFO from the best A-Type ending makes an appearance in ending 3. Ending 4 features extinct flying pterosaurs, while ending 7 shows mythical flying dragons. Endings 2 and 6 display flightless birds: running penguins and ostriches respectively. Ending 5 is filled with GOOD blimps, not to be confused with Goodyear blimps. And, multiple Buran spacecraft zoom across the screen in ending 8, even though there was only ever one of them.

The starting height (plus 1) acts as a multiplier, rewarding the player with more animals/objects for the greater difficulty.

The best B-Type ending features a castle ebullient with characters from the Nintendo universe: Princess Peach clapping her hands, Kid Icarus playing the violin, Donkey Kong playing a bass drum, Mario and Luigi dancing, Bowser playing the accordion, Samus playing the cello and Link playing the flute as the domes of Saint Basil's Cathedral rocket up into the air. The starting height establishes the number of these elements revealed during the ending.

The AI can rapidly plow through the 25 lines required by B-Type games at any starting level and height, providing a convenient way to watch any of the endings. It is also fascinating to witness how it deals with large stacks of random blocks.

Endings 0–8 display up to 6 objects moving across the frame. The y-coordinates of the objects are stored in a table located at $A7B7.

A7B7: 98 A8 C0 A8 90 B0  ; 0
A7BD: B0 B8 A0 B8 A8 A0  ; 1
A7C3: C8 C8 C8 C8 C8 C8  ; 2
A7C9: 30 20 40 28 A0 80  ; 3
A7CF: A8 88 68 A8 48 78  ; 4
A7D5: 58 68 18 48 78 38  ; 5
A7DB: C8 C8 C8 C8 C8 C8  ; 6
A7E1: 90 58 70 A8 40 38  ; 7
A7E7: 68 88 78 18 48 A8  ; 8

A77B: 3A 24 0A 4A 3A FF  ; 0
A781: 22 44 12 32 4A FF  ; 1
A787: AE 6E 8E 6E 1E 02  ; 2
A78D: 42 42 42 42 42 02  ; 3
A793: 22 0A 1A 04 0A FF  ; 4
A799: EE DE FC FC F6 02  ; 5
A79F: 80 80 80 80 80 FF  ; 6
A7A5: E8 E8 E8 E8 48 FF  ; 7
A7AB: 80 AE 9E 90 80 02  ; 8

A sequence of signed values at $A771 determines the speed and direction of the objects.

A771: 01  ; 0:  1 
A772: 01  ; 1:  1
A773: FF  ; 2: -1
A774: FC  ; 3: -4
A775: 01  ; 4:  1
A776: FF  ; 5: -1
A777: 02  ; 6:  2
A778: 02  ; 7:  2
A779: FE  ; 8: -1

A7F3: 2C  ; 0: dragonfly
A7F4: 2E  ; 1: dove
A7F5: 54  ; 2: penguin
A7F6: 32  ; 3: UFO
A7F7: 34  ; 4: pterosaur
A7F8: 36  ; 5: blimp
A7F9: 4B  ; 6: ostrich
A7FA: 38  ; 7: dragon
A7FB: 3A  ; 8: Buran

Each object actually consists of 2 sprites with adjacent indices. Add 1 for the second index. For example, the dragon consists of $38 and $39. The tiles for those sprites appear in the pattern tables below.

The center pattern table is the same one discussed above for displaying Tetriminos and the playfield. Interestingly, it contains the full alphabet whereas the others only contain a subset to save space. But, what is more interesting is the airplane and the helicopter sprites in the pattern table on the left; they do not appear in any of the endings or anywhere else in the game. It turns out that the airplane and the helicopter have sprite indices of $30 and $16 respectively and it is possible to modify the table above to see them in action. The results appear below.

Unfortunately, the helicopter skids do not appear, but the main and tail rotors are nicely animated.

2 Player Versus

Nintendo Tetris contains a hidden, unfinished 2 player versus mode that can be enabled by internally setting the number of players ($00BE) to 2. As shown below, 2 playfields appear side-by-side on top of the single player mode background.

No border appears between the playfields because the center region of the background is solid black. The 003 values displayed above the playfields indicate the number of lines cleared by each player. A lone, shared piece preview appears in the same location as it did in single player mode, which unfortunately, coincides with the right playfield. The squares and other tiles are not colored properly. And, when a player loses, the game resets.

Those issues aside, the mode is playable. Each player can independently control the pieces in the corresponding playfield. And, when a player achieves a Double, Triple or Tetris, garbage lines containing a single missing square push up from beneath the opponent's playfield.

The additional playfield is located at $0500. And, $0060–$007F, which is normally a mirror of $0040–$005F, is used for the second player.

A rushed development schedule may have extinguished this attractive feature. Or, it may have been left incomplete due to something more intentional. One of the reasons that Tetris was selected as the pack-in game for the Nintendo Game Boy is that it promoted the Game Link Cable, an accessory that hooked 2 Game Boys together for 2 player versus mode. That cable introduced a social element to the system, encouraging friends to go out and buy a Game Boy to link into the fun. Perhaps Nintendo feared that if the console version of the game provided 2 player versus mode that the promotional power that Tetris had on the Game Boy might actually be weakened.

Music and Sound Effects

Background music is triggered when $06F5 is set to one of the values listed in the table below.

Value	Description
01	Unused title screen music
02	B-Type goal achieved
03	Music-1
04	Music-2
05	Music-3
06	Music-1 allegro
07	Music-2 allegro
08	Music-3 allegro
09	Congratulations screen
0A	Endings
0B	B-Type goal achieved

You can listen to the unused title screen music here. The title screen in the actual game is silent.

Music-2 was inspired by traditional Russian folk songs. And, Music-3 is mysterious, futuristic and mellow; at one point, it was the hold music heard on Nintendo of America’s customer service line.

To help push the player into a state of panic when the height of the pile grows close to the playfield ceiling, a rapid tempo version of the background music ($06–$08) commences.

Notably missing is "Korobeiniki", the well-known theme heard in Game Boy Tetris.

Sound effects are initiated by writing to $06F0 and $06F1 as described in the following table.

Address	Value	Description
06F0	02	Game over curtain
06F0	03	Ending rocket
06F1	01	Menu option select
06F1	02	Menu screen select
06F1	03	Shift Tetrimino
06F1	04	Tetris achieved
06F1	05	Rotate Tetrimino
06F1	06	Level up
06F1	07	Lock Tetrimino
06F1	08	Chirp-chirp
06F1	09	Line clearing
06F1	0A	Line completed

Play States and Render Modes

During play, the current state of the game is represented as an integer at $0048. Most of the time, it is set to $01, indicating that the player is controlling the active Tetrimino. However, when the piece locks, the game steps through states $02 through $08, as listed in the table below.

State	Description
00	Unassign orientation ID
01	Player controls active Tetrimino
02	Lock Tetrimino into playfield
03	Check for completed rows
04	Display line clearing animation
05	Update lines and statistics
06	B-Type goal check
07	Unused
08	Spawn next Tetrimino
09	Unused
0A	Update game over curtain
0B	Increment play state

81B2: LDA $0048
81B4: JSR $AC82  ; switch(playState) {
81B7: 2F 9E      ;   case 00: goto 9E2F;  // Unassign orientationID
81B9: CF 81      ;   case 01: goto 81CF;  // Player controls active Tetrimino
81BB: A2 99      ;   case 02: goto 99A2;  // Lock Tetrimino into playfield
81BD: 6B 9A      ;   case 03: goto 9A6B;  // Check for completed rows
81BF: 39 9E      ;   case 04: goto 9E39;  // Display line clearing animation
81C1: 58 9B      ;   case 05: goto 9B58;  // Update lines and statistics
81C3: F2 A3      ;   case 06: goto A3F2;  // B-Type goal check; Unused frame for A-Type
81C5: 03 9B      ;   case 07: goto 9B03;  // Unused frame; Execute unfinished 2 player mode logic
81C7: 8E 98      ;   case 08: goto 988E;  // Spawn next Tetrimino
81C9: 39 9E      ;   case 09: goto 9E39;  // Unused
81CB: 11 9A      ;   case 0A: goto 9A11;  // Update game over curtain
81CD: 37 9E      ;   case 0B: goto 9E37;  // Increment play state
                 ; }

For state $00, the switch jumps to the following the code that assigns $13 to orientationID, indicating that it is not set.

9E2F: LDA #$13
9E31: STA $0042  ; orientationID = UNASSIGNED;

9E33: RTS        ; return;

The handler is never invoked; however, play state $00 serves as a signal for other parts of the code.

81CF: JSR $89AE  ; shift Tetrimino;
81D2: JSR $88AB  ; rotate Tetrimino;
81D5: JSR $8914  ; drop Tetrimino;

81D8: RTS        ; return;

As discussed in prior sections, the shift, rotate and drop subroutines validate new Tetrimino positions before committing to a move. The only way that a piece can lock at an invalid position is if it spawned on top of an existing piece, ending the game. As listed below, the code for state $02 performs that check.

99A2: JSR $948B  ; if (new position valid) {
99A5: BEQ $99B8  ;   goto updatePlayfield;
                 ; }  

99A7: LDA #$02
99A9: STA $06F0  ; play curtain sound effect;

99AC: LDA #$0A
99AE: STA $0048  ; playState = UPDATE_GAME_OVER_CURTAIN;

99B0: LDA #$F0
99B2: STA $0058  ; curtainRow = -16;

99B4: JSR $E003  ; updateAudio();

99B7: RTS        ; return;

If the locked position is valid, it marks the 4 associated cells of the playfield as solid. Otherwise, it changes to state $0A, the dreaded game over curtain.

The curtain is drawn from the top of the playfield to the bottom, advancing one row every 4 frames. The curtainRow ($0058) is initialized to −16, providing an extra delay of 0.27 seconds between the final lock and the beginning of the animation. At $9A21 in the state $0A code below, the multiplication table, which erroneously gets displayed as level numbers, is accessed to scale curtainRow by 10. Also, as revealed earlier, the code at $9A51 triggers an ending animation if the player's score is at least 30,000 points; otherwise, it waits for Start.

9A11: LDA $0058    ; if (curtainRow == 20) {
9A13: CMP #$14     ;   goto endGame;
9A15: BEQ $9A47    ; }

9A17: LDA $00B1    ; if (frameCounter not divisible by 4) {
9A19: AND #$03     ;   return; 
9A1B: BNE $9A46    ; }

9A1D: LDX $0058    ; if (curtainRow < 0) {
9A1F: BMI $9A3E    ;   goto incrementCurtainRow;
                   ; }  

9A21: LDA $96D6,X  
9A24: TAY          ; rowIndex = 10 * curtainRow;  

9A25: LDA #$00
9A27: STA $00AA    ; i = 0;

9A29: LDA #$13
9A2B: STA $0042    ; orientationID = NONE;

drawCurtainRow:

9A2D: LDA #$4F     
9A2F: STA ($B8),Y  ; playfield[rowIndex + i] = CURTAIN_TILE;
9A31: INY          
9A32: INC $00AA    ; i++;
9A34: LDA $00AA
9A36: CMP #$0A     ; if (i != 10) {
9A38: BNE $9A2D    ;   goto drawCurtainRow;
                   ; }

9A3A: LDA $0058
9A3C: STA $0049    ; vramRow = curtainRow;

incrementCurtainRow:

9A3E: INC $0058    ; curtainRow++;

9A40: LDA $0058    ; if (curtainRow != 20) {
9A42: CMP #$14     ;   return;
9A44: BNE $9A46    ; }

9A46: RTS          ; return;

endGame:

9A47: LDA $00BE    
9A49: CMP #$02
9A4B: BEQ $9A64    ; if (numberOfPlayers == 1) {

9A4D: LDA $0075
9A4F: CMP #$03
9A51: BCC $9A5E    ;   if (score[2] >= $03) {

9A53: LDA #$80
9A55: JSR $A459
9A58: JSR $9E3A
9A5B: JMP $9A64    ;     select ending; 
                   ;   }

9A5E: LDA $00F5    ;   if (not just pressed Start) {
9A60: CMP #$10     ;     return;
9A62: BNE $9A6A    ;   }
                   ; }

9A64: LDA #$00
9A66: STA $0048    ; playState = INITIALIZE_ORIENTATION_ID;
9A68: STA $00F5    ; clear newly pressed buttons;

9A6A: RTS          ; return;

The code ends by setting the play state to $00, but the corresponding handler does not get called since it is game over.

The playfield rows are incrementally copied to VRAM to display them. The index of the current row being copied is held in vramRow ($0049). At $9A3C, vramRow is set to curtainRow, which will ultimately render that row of the curtain visible.

VRAM manipulation occurs during the vertical blanking interval, which is detected by the interrupt handler that was discussed in the Legal Screen section. It invokes the subroutine listed below (denoted as render() in the interrupt handler comments).

804B: LDA $00BD
804D: JSR $AC82  ; switch(renderMode) {
8050: B1 82      ;   case 0: goto 82B1;  // Legal and title screens
8052: DA 85      ;   case 1: goto 85DA;  // Menu screens
8054: 44 A3      ;   case 2: goto A344;  // Congratulations screen
8056: EE 94      ;   case 3: goto 94EE;  // Play and demo
8058: 95 9F      ;   case 4: goto 9F95;  // Ending animation
                 ; }

Render mode is similar to game mode. It is stored at $00BD and it can have one of the following values:

Value	Description
00	Legal and title screens
01	Menu screens
02	Congratulations screen
03	Play and demo
04	Ending animation

952A: JSR $9725  ; copyPlayfieldRowToVRAM();
952D: JSR $9725  ; copyPlayfieldRowToVRAM();
9530: JSR $9725  ; copyPlayfieldRowToVRAM();
9533: JSR $9725  ; copyPlayfieldRowToVRAM();

As shown below, copyPlayfieldRowToVRAM() transfers the playfield row indexed by vramRow to VRAM. If vramRow is greater than 20, the subroutine does nothing.

9725: LDX $0049    ; if (vramRow > 20) { 
9727: CPX #$15     ;   return;
9729: BPL $977E    ; }

972B: LDA $96D6,X  
972E: TAY          ; playfieldAddress = 10 * vramRow;

972F: TXA          
9730: ASL           
9731: TAX
9732: INX          ; high = vramPlayfieldRows[vramRow * 2 + 1];
9733: LDA $96EA,X
9736: STA $2006    
9739: DEX          

973A: LDA $00BE    
973C: CMP #$01
973E: BEQ $975E    ; if (numberOfPlayers == 2) {

9740: LDA $00B9    
9742: CMP #$05
9744: BEQ $9752    ;   if (leftPlayfield) {

9746: LDA $96EA,X      
9749: SEC
974A: SBC #$02
974C: STA $2006    ;     low = vramPlayfieldRows[vramRow * 2] - 2;

974F: JMP $9767    ;   } else {

9752: LDA $96EA,X
9755: CLC
9756: ADC #$0C
9758: STA $2006    ;     low = vramPlayfieldRows[vramRow * 2] + 12;

975B: JMP $9767    ; } else {

975E: LDA $96EA,X  
9761: CLC
9762: ADC #$06     ;     low = vramPlayfieldRows[vramRow * 2] + 6;
9764: STA $2006    ; }

                   ; vramAddress = (high << 8) | low;

9767: LDX #$0A
9769: LDA ($B8),Y  
976B: STA $2007    
976E: INY          ; for(i = 0; i < 10; i++) {
976F: DEX          ;   vram[vramAddress + i] = playfield[playfieldAddress + i];
9770: BNE $9769    ; }

9772: INC $0049    ; vramRow++;
9774: LDA $0049    ; if (vramRow < 20) {
9776: CMP #$14     ;   return;
9778: BMI $977E    ; }

977A: LDA #$20
977C: STA $0049    ; vramRow = 32;

977E: RTS          ; return;

The vramPlayfieldRows table ($96EA) contains the little endian VRAM addresses corresponding to the displayed playfield rows offset by 6 in normal mode and by −2 and 12 for the playfields in the unfinished 2 Player Versus mode. The bytes of that table are part of the list of values erroneously displayed as level numbers beyond level 29. The neighboring low and high bytes of each address are retrieved individually and they are effectively combined into a 16-bit address, which is used in the copy loop.

At the end of the subroutine, vramRow is incremented. If it reaches 20, it is set to 32, indicating that the full copy is completed. As shown above, only 4 rows are copied per frame.

The state $03 handler is responsible for identifying completed rows and removing them from the playfield. Across 4 separate calls, it scans row offsets [−2, 1] about the Tetrimino center (both coordinates of all Tetrimino squares existing within that range). The completed row indices are stored at $004A–$004D; a recorded index of 0 is used to indicate that no completed row was found on that pass. The handler appears below.

9A6B: LDA $0049    
9A6D: CMP #$20     ; if (vramRow < 32) {
9A6F: BPL $9A74    ;   return;
9A71: JMP $9B02    ; } 

9A74: LDA $0041    ; rowY = tetriminoY - 2; 
9A76: SEC          
9A77: SBC #$02     ; if (rowY < 0) {
9A79: BPL $9A7D    ;   rowY = 0;
9A7B: LDA #$00     ; }

9A7D: CLC
9A7E: ADC $0057    
9A80: STA $00A9    ; rowY += lineIndex; 
 
9A82: ASL          
9A83: STA $00A8    
9A85: ASL
9A86: ASL          
9A87: CLC
9A88: ADC $00A8    
9A8A: STA $00A8    ; rowIndex = 10 * rowY;

9A8C: TAY          
9A8D: LDX #$0A                        
9A8F: LDA ($B8),Y  
9A91: CMP #$EF     ; for(i = 0; i < 10; i++) {
9A93: BEQ $9ACC    ;   if (playfield[rowIndex + i] == EMPTY_TILE) {
9A95: INY          ;     goto rowNotComplete;   
9A96: DEX          ;   }   
9A97: BNE $9A8F    ; }

9A99: LDA #$0A
9A9B: STA $06F1    ; play row completed sound effect;

9A9E: INC $0056    ; completedLines++;

9AA0: LDX $0057    
9AA2: LDA $00A9    
9AA4: STA $4A,X    ; lines[lineIndex] = rowY;

9AA6: LDY $00A8
9AA8: DEY                               
9AA9: LDA ($B8),Y     
9AAB: LDX #$0A        
9AAD: STX $00B8
9AAF: STA ($B8),Y    
9AB1: LDA #$00
9AB3: STA $00B8
9AB5: DEY          ; for(i = rowIndex - 1; i >= 0; i--) {
9AB6: CPY #$FF     ;   playfield[i + 10] = playfield[i];  
9AB8: BNE $9AA9    ; }

9ABA: LDA #$EF     
9ABC: LDY #$00
9ABE: STA ($B8),Y  
9AC0: INY          ; for(i = 0; i < 10; i++) {
9AC1: CPY #$0A     ;   playfield[i] = EMPTY_TILE;
9AC3: BNE $9ABE    ; }

9AC5: LDA #$13
9AC7: STA $0042    ; orientationID = UNASSIGNED;

9AC9: JMP $9AD2    ; goto incrementLineIndex;

rowNotComplete:

9ACC: LDX $0057
9ACE: LDA #$00
9AD0: STA $4A,X    ; lines[lineIndex] = 0;

incrementLineIndex:

9AD2: INC $0057    ; lineIndex++;

9AD4: LDA $0057    ; if (lineIndex < 4) {
9AD6: CMP #$04     ;   return;
9AD8: BMI $9B02    ; }

9ADA: LDY $0056
9ADC: LDA $9B53,Y  
9ADF: CLC
9AE0: ADC $00BC
9AE2: STA $00BC    ; totalGarbage += garbageLines[completedLines];

9AE4: LDA #$00
9AE6: STA $0049    ; vramRow = 0;
9AE8: STA $0052    ; clearColumnIndex = 0;

9AEA: LDA $0056   
9AEC: CMP #$04    
9AEE: BNE $9AF5    ; if (completedLines == 4) {
9AF0: LDA #$04     ;   play Tetris sound effect; 
9AF2: STA $06F1    ; }

9AF5: INC $0048    ; if (completedLines > 0) {
9AF7: LDA $0056    ;   playState = DISPLAY_LINE_CLEARING_ANIMATION;
9AF9: BNE $9B02    ;   return;                    
                   ; }

9AFB: INC $0048    ; playState = UPDATE_LINES_AND_STATISTICS;

9AFD: LDA #$07     
9AFF: STA $06F1    ; play piece locked sound effect;

9B02: RTS          ; return;

The vramRow check at the top prevents the handler from executing while playfield rows are being transferred to VRAM (the state $03 handler is invoked every frame). If completed lines are discovered, vramRow is reset to 0 to cause a full transfer.

Unlike play state $0A and the playfield copy subroutine that took advantage of the multiplication table at $96D6, the block starting at $9A82 multiplies rowY by 10 using shifts and addition:

rowIndex = (rowY << 1) + (rowY << 3);  // rowIndex = 2 * rowY + 8 * rowY;

This was done because while rowY is constrained to [0, 20], the multiplication table only covers [0, 19]. The line scan can actually run off the end of the playfield. However, as discussed earlier, the game initializes $0400–$04FF to $EF (the empty tile), providing more than 5 additional empty hidden rows below the playfield floor.

The block starting at $9ADA is part of the unfinished 2 Player Versus mode. As mentioned, clearing lines sends garbage over to the opponent's playfield. The number of garbage lines is determined by a table at $9B53:

9B53: 00  ; no cleared lines
9B54: 00  ; Single
9B55: 01  ; Double
9B56: 02  ; Triple
9B57: 04  ; Tetris

The loop at $9AA6 shifts the material above the completed line down a row. It takes advantage the fact that each row is 10 bytes apart in a contiguous sequence. The loop following it clears the top row.

The line clearing animation occurs during play state $04, but as shown below, it does not happen within the play state handler, which is entirely empty.

Instead, the following branch of render mode $03 is followed during play state $04.

94EE: LDA $0068  
94F0: CMP #$04
94F2: BNE $9522  ; if (playState == DISPLAY_LINE_CLEARING_ANIMATION) {

94F4: LDA #$04
94F6: STA $00B9  ;   leftPlayfield = true;

94F8: LDA $0072
94FA: STA $0052
94FC: LDA $006A
94FE: STA $004A
9500: LDA $006B
9502: STA $004B
9504: LDA $006C
9506: STA $004C
9508: LDA $006D
950A: STA $004D
950C: LDA $0068
950E: STA $0048  ;   mirror values;

9510: JSR $977F  ;   updateLineClearingAnimation();
        
                 ;   ...
                 ; }

The leftPlayfield and mirrored values are for the unfinished 2 Player Versus mode.

The updateLineClearingAnimation() subroutine is listed below. It is invoked every frame, but the condition at the top only enables it to run every fourth frame. On each pass, it loops over the list of completed row indices and it clears 2 columns from those rows, advancing from the center columns outward.

977F: LDA $00B1    ; if (frameCounter not divisible by 4) {
9781: AND #$03     ;   return;
9783: BNE $97FD    ; }

9785: LDA #$00     ; for(i = 0; i < 4; i++) {
9787: STA $00AA    ;   rowY = lines[i];
9789: LDX $00AA    ;   if (rowY == 0) {
978B: LDA $4A,X    ;     continue;
978D: BEQ $97EB    ;   }
                   
978F: ASL
9790: TAY         
9791: LDA $96EA,Y  
9794: STA $00A8    ;   low = vramPlayfieldRows[2 * rowY];

9796: LDA $00BE    ;   if (numberOfPlayers == 2) {
9798: CMP #$01     ;     goto twoPlayers;
979A: BNE $97A6    ;   }

979C: LDA $00A8
979E: CLC
979F: ADC #$06
97A1: STA $00A8    ;   low += 6;

97A3: JMP $97BD    ;   goto updateVRAM;

twoPlayers:

97A6: LDA $00B9    
97A8: CMP #$04
97AA: BNE $97B6    ;   if (leftPlayfield) {

97AC: LDA $00A8
97AE: SEC
97AF: SBC #$02
97B1: STA $00A8    ;     low -= 2;

97B3: JMP $97BD    ;   } else {

97B6: LDA $00A8
97B8: CLC
97B9: ADC #$0C     ;     low += 12; 
97BB: STA $00A8    ;   }

updateVRAM:

97BD: INY          
97BE: LDA $96EA,Y
97C1: STA $00A9       
97C3: STA $2006    
97C6: LDX $0052    ;   high = vramPlayfieldRows[2 * rowY + 1];    
97C8: LDA $97FE,X     
97CB: CLC          ;   rowAddress = (high << 8) | low;
97CC: ADC $00A8       
97CE: STA $2006    ;   vramAddress = rowAddress + leftColumns[clearColumnIndex];
97D1: LDA #$FF
97D3: STA $2007    ;   vram[vramAddress] = 255;

97D6: LDA $00A9 
97D8: STA $2006   
97DB: LDX $0052    ;   high = vramPlayfieldRows[2 * rowY + 1];
97DD: LDA $9803,X  
97E0: CLC          ;   rowAddress = (high << 8) | low;
97E1: ADC $00A8
97E3: STA $2006    ;   vramAddress = rowAddress + rightColumns[clearColumnIndex];
97E6: LDA #$FF 
97E8: STA $2007    ;   vram[vramAddress] = 255;
                   
97EB: INC $00AA
97ED: LDA $00AA
97EF: CMP #$04
97F1: BNE $9789    ; }

97F3: INC $0052    ; clearColumnIndex++;
97F5: LDA $0052    ; if (clearColumnIndex < 5) {
97F7: CMP #$05     ;   return;
97F9: BMI $97FD    ; }

97FB: INC $0048    ; playState = UPDATE_LINES_AND_STATISTICS;

97FD: RTS          ; return;

The 16-bit VRAM address is built up in the same way show in the copy playfield subroutine. However, in this case, it is offset by a column index obtained from the table below.

97FE: 04 03 02 01 00  ; left columns 
9803: 05 06 07 08 09  ; right columns

The clearing animation requires 5 passes. Then, the code advances to the next play state.

The play state $05 handler contains the code discussed in the Lines and Statistics section. The handler ends with this code:

9C9E: LDA #$00
9CA0: STA $0056  ; completedLines = 0;

9CA2: INC $0048  ; playState = B_TYPE_GOAL_CHECK;

9CA4: RTS        ; return;

completedLines is not reset until the end of play state $05, after it is used to update the total lines count and the score. This sequence permits an interesting bug. In demo mode, wait for the game to get a complete line and then quickly press Start before the line clearing animation finishes. The game will return to the title screen, but, if you timed it right, completedLines will retain its value. Next, begin an A-Type game. When the first piece locks, the play state $03 handler will scan for completed rows. It won't record any, but it will leave completedLines unchanged. Finally, when play state $05 executes, the total lines count and the score will go up as if those lines were your own.

The easiest way to do this and the way that will result in the most points is to wait for the demo to get a Tetris (2 of them will occur). As soon as you see the screen flash, press Start.

After launching a new game, the screen actually will continue to flash thanks to the following code that is called by the interrupt handler.

9673: LDA #$3F
9675: STA $2006
9678: LDA #$0E
967A: STA $2006  ; prepare to modify background tile color;

967D: LDX #$00   ; color = DARK_GRAY;

967F: LDA $0056
9681: CMP #$04
9683: BNE $9698  ; if (completedLines == 4) {

9685: LDA $00B1  
9687: AND #$03
9689: BNE $9698  ;   if (frameCounter divisible by 4) {

968B: LDX #$30   ;     color = WHITE;

968D: LDA $00B1
968F: AND #$07
9691: BNE $9698  ;     if (frameCounter divisible by 8) {  

9693: LDA #$09
9695: STA $06F1  ;       play clear sound effect;

                 ;     }
                 ;   }
                 ; }

9698: STX $2007  ; update background tile color;

In fact, if you let the first piece automatically drop all the way to the floor of the playfield, the score will increase even more because holdDownPoints ($004F) will retain its demo value as well. This is true even if the demo did not complete any lines. holdDownPoints is not reset until Down is pressed.

Furthermore, if you press Start during the line clearing animation of a Tetris in demo mode and then you wait for the demo to start again, not only will the demo get credited for the Tetris, its timing will get screwed up. As a result, the demo will actually lose the game. From the game over curtain, you can navigate back to the title screen by pressing Start.

Play state $06 performs the goal check for B-Type games. For A-Type, it is effectively an unused frame.

Play state $07 exclusively contains logic for the unfinished 2 Player Versus mode. For single player mode, it acts as an unused frame.

Play state $09 is unused. And, $0B advances the play state, but it also appears to be unused.

                 ; while(true) {

8138: JSR $8161  ;   branchOnGameMode();

813B: CMP $00A7  ;   if (vertical blanking interval wait requested) {
813D: BNE $8142  ;     waitForVerticalBlankingInterval();  
813F: JSR $AA2F  ;   }

8142: LDA $00C0     
8144: CMP #$05        
8146: BNE $815A  ;   if (gameMode == DEMO) {

8148: LDA $00D2  
814A: CMP #$DF
814C: BNE $815A  ;     if (reached end of demo table) {

814E: LDA #$DD
8150: STA $00D2  ;       reset demo table index;

8152: LDA #$00
8154: STA $00B2  ;       clear upper byte of frame counter;

8156: LDA #$01
8158: STA $00C0  ;       gameMode = TITLE_SCREEN;
                 ;     }
                 ;   }
815A: JMP $8138  ; }

The Algorithm

Overview

Searching for Lock

Consider a simplified version of Tetris where the pieces do not drop automatically. Rather, the only means of advancing downward is manually soft dropping. With timing stripped out of the game, the state of an active Tetrimino can be fully described by its position and orientation. It has a known initial spawn state and the operations that transform one state into another are:

Those operations are only applicable when the squares of the resultant Tetrimino correspond to empty cells within the boundaries of the playfield. When it is impossible to move one step down, the state is considered locked. However, since lock delay is effectively infinite in this simplified Tetris, a locked state can be further transformed by the other operations, permitting slides and spins.

The set of locked states along with the minimal sequence of operations that produce them can be found using breadth-first search (BFS). As described below, it uses a queue to store intermediate states.

{ x, y, rotation, visited, predecessor }

In preparation, the program creates a 3-dimensional array of state objects (20 rows × 10 columns × 4 rotations), initializing x, y and rotation accordingly.

The visited field is marked when a state is enqueued. This is permissible in BFS because each successor increases the total path length by 1. Meaning, it is not possible to produce a successor that would need to be inserted anywhere except the end of the queue to keep it ordered by increasing path length.

The predecessor field points to the state object from which it descends. It is set when a state is enqueued. The spawn state has no predecessor.

The Tetrimino type and the solid blocks present in the playfield ultimately determine the set of lock states discovered during the search. The sequence of moves that generated them can be uncovered (in reverse) by repeatedly following the predecessor links back to the spawn state. When the PLAY_FAST constant at the top of the program is set to true, it skips the predecessors entirely, directly placing the Tetrimino into lock.

The 3-dimensional array of state objects, the queue and the BFS were packaged up into a reusable class. It provides a search method that accepts the playfield (a 2-dimensional array), the Tetrimino type, and a listener. Every time a locked state is found, the playfield is updated by adding the Tetrimino at the corresponding location. Then, the modified playfield along with details of the change is passed to the listener for processing. After the listener returns, the playfield is restored.

The listener is used to chain multiple searchers together, providing the means of finding all possible ways of adding 2 (or more) Tetriminos to the playfield. The first searcher in the chain executes the BFS only once. However, the second searcher executes the BFS every time the first search discovers a locked state. And so on, if there were more searchers in the chain.

The listener of the final searcher rates the modified playfield. When it encounters a playfield better than the ones examined prior, it records the locked state object in use at that time by the first searcher in the chain. Since the first searcher executes the BFS only once, the predecessor fields of its state objects remain valid after the entire search process is complete. Meaning, the final listener effectively captures the pathway that the first Tetrimino must take to ultimately lead to the best playfield configuration.

Evaluation Function

The modified playfield is rated by an evaluation function, a weighted sum of various influential factors. The evaluation function used in this application is based on the function developed by Islam El-Ashi. It uses the following features:

El-Ashi suggested that useful weights could be found using particle swarm optimization (PSO), an algorithm that iteratively improves a population of candidate solutions by imitating the kinds of swarm behavior observed in nature. In this case, each candidate solution is a vector of weights and the fitness of a candidate is determined by playing Tetris; it is the total number of Tetriminos it survived through before reaching game over.

These ideas were applied to the Java version, which is discussed below; it executes outside of FCEUX and it can be configured to play against a non-graphical, in-memory game that runs at a considerably faster rate. After setting up the PSO, I was surprised to find that it did not progress beyond the initial iteration. As it happened, several of the randomly generally candidate solutions were actually playing well. Over a period of days, the size of that set dwindled until there was only 1 remaining. Here are the values of that solution:

The playfields are evaluated by multiplying the factors with their associated weights and adding up the results. A lower evaluation implies a better rating. Since the factors and weights are all positive values, all the factors have an adverse influence; each of them should be minimized. It also means that the best possible rating is 0.

Since these weights were selected by random chance, there must be a very wide range of suitable values. This particular set of numbers and the relative significance it suggests about each factor may be inconsequential. But, scrutinizing them is interesting nonetheless.

The least adverse factor is Total Lines Cleared. The fact that this is even an adverse factor is counterintuitive. But, the primary goal of the AI is survival. It does not aim for a high score. Rather, it plays conservatively, usually clearing lines individually. To score a Double, a Triple or a Tetris, it would have to let the pile grow, which goes against its long term goal.

The next on the list is Total Lock Height. This can be minimized by getting the Tetriminos as close to the floor of the playfield as possible. It’s a basic strategy that contributes to long term survival and short term packing by attracting pieces to the bottom.

The weight assigned to Total Well Cells is bit a surprising because expert players intentionally build deep wells with the goal of scoring repeated Tetrises. But, as mentioned, that’s risky play that goes against the main objective of survival. In addition, the number of well cells provides an indication of pile roughness. A certain level of roughness is beneficial in accommodating certain pieces or piece combinations. But, high roughness is detrimental to tight packing.

Total Column Holes is equal to approximately half of the Total Column Transitions. Those factors can be combined and further folded into the final related factor resulting in the broader and most adverse factor: Total Transitions.

Densely packed regions exhibit few transitions in all directions. Hence, the main strategy driving the AI can be summarized as: pack the pieces as closely together as possible.

Factor	Weight
Total Lines Cleared	1.000000000000000
Total Lock Height	12.885008263218383
Total Well Cells	15.842707182438396
Total Column Holes	26.894496507795950
Total Column Transitions	27.616914062397015
Total Row Transitions	30.185110719279040

Other Factors

Here is a list of some of the other factors that I experimented with while developing the AI:

All of the factors can be adjusted by introducing tunable parameters. For example, instead of simply counting lines cleared, a different weight could be assigned to Singles, Doubles, Triples and Tetrises, mimicking the point system. If more than one simultaneously cleared line really is detrimental to the long term goal of survival, then Singles could be assigned a negative weight where as the others would get positive weights.

Another useful parameter is an offset value. For instance, a pile surface that is completely flat has a column height variance of 0. But, a perfectly flat surface is not accommodating to S and Z and other piece combinations. As such, the variance should be centered about the optimal roughness by subtracting a constant.

The tuned and offset factors can be raised to some power or they can be scaled logarithmically or exponentially, and so on, before computing the weighted sum. All of these possibilities can be treated as additional weights, which can potentially be optimized using methods like PSO.

Many of the factors provide insight into how well the pile would handle additional pieces, such as those dealing with surface roughness, but Total Accommodations, Average Next Evaluation and Average Simulated Play evaluate the modified playfield by actually inserting pieces beyond the 2 known ones. In examining successive pieces, the amount of additional knowledge gained diminishes with depth due to rapid line erasure. Meaning, just as distant past play is not that important, distant future play is not that important either. In fact, if a short sequence of pieces were randomly misplaced, the AI would quickly recover, using the next few pieces to clear out the affected lines. Determining the optimal amount of successive piece analysis will require further research.

Another consideration in the usefulness of a factor is computational cost. Costs are greatly amplified because the evaluation function is invoked for every possible placement of the 2 pieces. Since, the AI should be able to play Tetris in real-time, expensive factors that provide valuable information may have to be sacrificed for more approximate techniques that execute faster.

AI Training

Pathological sequences exist that will end the game regardless of the strategy. The simplest example is an endless alternating sequence of S and Z Tetriminos, which, as demonstrated by the animation below, rapidly pushes the AI over the brink.

Since it can take days to run a candidate AI to completion and multiple runs are required to establish an average, it is completely impractical to use average run length as the metric to drive PSO. Instead, during evaluation, the difficulty of the game can be raised at a controlled rate by increasing the frequency of S and Z, eventually leading into the terminal alternating sequence.

I tried this method of training, but I found that teaching it how to deal with frequent S and Z pieces was actually detrimental to its ability to handle uniformly distributed random pieces.

In an alternative method, inspired by the B-Type game, the line clear rate serves as the metric directing the PSO. The playfield is setup with 10 rows of random garbage blocks and every time a row is cleared, a new garbage row pushes up from the bottom, restoring the pile height. Since the playfield is 10 columns wide and each Tetrimino consists of 4 squares, on average, the AI must clear a line every 2.5 Tetriminos. And, to remove garbage, it must do it even faster.

Unfortunately, this technique also did not improve the performance. One possible reason is that the random holes in garbage do not accurately represent the kind of rows it deals with during actual game play. Also, line clearing is a short-term goal; greedily clearing them out does not necessarily improve long-term survival. Occasionally, lines need to be left intact to deal with certain successive piece combinations.

On his web page, Colin Fahey suggested a different method. He produced histograms depicting the percentage of pieces that locked within each row over sample runs. Interestingly, all the histograms look virtually identical regardless of the number of pieces sampled. From this, he proposed that it should be possible to use curve fitting on any sample run to estimate the statistical expectation of a piece locking in the spawn row and hence, how long the AI would play until game over. I decided to examine this possibility.

Below is a heat map generated from multiple sample runs, collectively consisting of 2,039,900,000 Tetriminos. Each cell is colored based on the percentage of pieces which locked there. The nonlinear palette was selected to enhance visual contrast. It was produced by normalizing the cell values, via dividing by the maximum cell percentage, and then raising that to the 0.19 power (see gamma correction).

The dark orange and red band in rows 17 and 18 indicate where the vast majority of pieces end up. The chartreuse hue below it is a consequence of piece geometry; only 4 of the 7 Tetrimino types can lock in the bottom row. In fact, the lower corners are black, revealing that it is impossible to lock there.

The color across each row is nearly homogenous suggesting that pieces tend to be uniformly distributed horizontally. The slight discontinuities can be explained by observing the histograms of the individual piece types:

T appears to be the most versatile type; its histogram is more uniform than any of the others. The anomalies in J’s histogram are a result of the walls; only Jr and Jl can exist in the side columns, forcing the AI to uses columns 1 and 9 more often to compensate. The same idea applies to L. The histograms of Z and S look nearly identical, highlighting the imbalance that exists because Zv and Sv are not perfect mirrors of each other. O is constrained to a 19×9 playfield and it appears that the AI has a tendency of using O at the sides more often than the center. The I Tetrimino is biased toward the right because of where its origin is located; locking in column 1 is a rarity as a result.

Row	Percent
0	0.0000000000
1	0.0000000000
2	0.0000004902
3	0.0000026472
4	0.0000066180
5	0.0000172557
6	0.0000512280
7	0.0001759400
8	0.0006681210
9	0.0023187901
10	0.0077928820
11	0.0259672043
12	0.0866187068
13	0.2901315751
14	0.9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18	50.0335706162
19	6.0077671454

Row_A/Row_B	Ratio (%)
1/2	0.00
2/3	18.52
3/4	40.00
4/5	38.35
5/6	33.68
6/7	29.12
7/8	26.33
8/9	28.81
9/10	29.76
10/11	30.01
11/12	29.98
12/13	29.85
13/14	29.69
14/15	29.61
15/16	30.84
16/17	37.45
17/18	57.10
18/19	832.81

Rows 16–19 involve pieces interacting with the playfield floor; so, they will be precluded. Rows 0–5 have too few samples to be meaningful. The remaining ratios, pairs 6/7–14/15, are almost identical; their average is 29.24%. It means that probability of the pile growing taller by one row is roughly the same regardless of the height of pile. This makes sense because the rules of Tetris limit interactivity to the top of the pile when it is densely packed.

It is close to a perfectly straight line with a coefficient of determination that is nearly 1. The formula derived from the linear regression shown above provides a y-intercept that suggests that the percentage of pieces in row 0 is approximately 10^−7.459%. The reciprocal of that yields a statistical expectation of 2,877,688,349 Tetriminos or 1,151,075,340 lines until game over.

This assumes that the log₁₀ of the percentage of pieces in each row remains linear all the way down to row 0. However, when the pile nearly reaches the playfield ceiling, the freedom of movement maybe constrained to the point that this property breaks down. Also, locking in row 0 does not necessarily guarantee game over; it is possible to recover as long as there is room to spawn.

Another way to evaluate the strength of an AI is to measure the average number of spawns between full clears of the playfield. A full clear can be achieved in as few as 5 Tetriminos. For instance, among many other possibilities, 5 Os laid side-by-side on the floor of the playfield will do it. In general, since each Tetrimino consists of 4 squares and the playfield is 10 squares wide, the number of spawns between full clears must be a multiple of 5 (because 4×5n = 2×10n).

For this AI, the average number of spawns between full clears is 1181, a relatively small number. Since a full clear is equivalent to restarting the game, a complete run can be thought of as an extremely long series of restarts followed by a quick trip to game over. Like the alternating S-Z sequence above, the pathological sequences that kill it are typically very short.

The histogram below depicts the probability (as a percent) that the AI will achieve a full clear after a specified number of spawns.

The magnitude of the exponent in the formula above determines the rate of decay and presumably the strength of the AI. According to that formula, approximately 0.4% or about 1 in every 253 of the runs that start from an empty playfield will end in a full clear after only 5 Tetriminos.

Contrary to what Fahey proposed, the constants in the linear and exponential fits require a very large sample size before R² approaches 1, making them unsuitable for PSO. But, the constants derived from long runs could be used to optimize an approximation function that produces estimates of the constants from short runs. In a kind of development feedback loop, an optimized approximation function could be used by a PSO that enhances the AI, which could in turn be used to compute new constants to serve as benchmarks for improving the approximation function.

Java Version

About

For developers that are not familiar with Lua, the source zip includes a Java port of the AI. The classes are a nearly line-by-line translation of the closure-based Lua objects.

Packages

AI Classes and Interfaces

The aptly named Tetriminos class describes Tetriminos. It acts like an enum containing constants for all of the Tetrimino types:

public static final int NONE = -1;
public static final int T = 0;
public static final int J = 1;
public static final int Z = 2;
public static final int O = 3;
public static final int S = 4;
public static final int L = 5;
public static final int I = 6;

Tetriminos also contains 2 representations of the orientation table. PATTERNS is a 4-dimensional integer array (type × rotation × square × coordinates) containing the relative square coordinates; the rows are ordered such that within each type the spawn orientation appears first. ORIENTATIONS, the other representation, is a 2-dimenstional array (type × rotation) of Orientation objects. Each Orientation contains the square coordinates as an array of Point objects. It also provides fields describing the range of legal positions for that orientation.

public class Orientation {
  public Point[] squares = new Point[4];
  public int minX;
  public int maxX;
  public int maxY;
  ...
}

public class Point {
  public int x;
  public int y;
  ...
}

The Tetrimino rotation—the second index in both orientation tables—appears in the State objects that are manipulated by the BFS.

public class State {
  public int x;
  public int y;
  public int rotation;
  public int visited;
  public State predecessor; 
  public State next;
  ...
}

Collectively, x, y and rotation describe the position and orientation of a piece. Since the Tetrimino type remains constant from spawn to lock, a field for it is unnecessary.

The Searcher class, which houses the BFS algorithm, creates the complete set of all possible State objects upon construction:

private void createStates() {
  states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4];
  for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) {
    for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) {        
      for(int rotation = 0; rotation < 4; rotation++) { 
        states[y][x][rotation] = new State(x, y, rotation);
      }
    }
  }
}

Although Java provides an ample Collections API, Searcher contains a proprietary queue implementation. The Queue class uses State.next to chain State objects into a linked list. Since all the State objects are pre-allocated and each State may be enqueued at most once, the queue is able to operate in-place, avoiding the overhead of temporary container objects present in generic queue implementations.

public boolean search(int[][] playfield, int tetriminoType, int id) {

  int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1;

  int mark = globalMark++;

  if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) {
    return false;
  }    

  while(queue.isNotEmpty()) {
    State state = queue.dequeue();

    if (maxRotation != 0) {
      addChild(playfield, tetriminoType, mark, state, state.x, state.y, 
          state.rotation == 0 ? maxRotation : state.rotation - 1);
      if (maxRotation != 1) {
        addChild(playfield, tetriminoType, mark, state, state.x, state.y, 
            state.rotation == maxRotation ? 0 : state.rotation + 1);
      }
    }

    addChild(playfield, tetriminoType, mark, state, 
        state.x - 1, state.y, state.rotation);
    addChild(playfield, tetriminoType, mark, state, 
        state.x + 1, state.y, state.rotation);

    if (!addChild(playfield, tetriminoType, mark, state,
        state.x, state.y + 1, state.rotation)) {
      lockTetrimino(playfield, tetriminoType, id, state);
    }
  }

  return true;
}

It seeds the queue with the state of a spawned Tetrimino and then it successively derives children from dequeues states, adding them back to the queue as it sprawls the playfield.

The playfield, containing a mixture of solid and empty cells, the Tetrimino type to spawn and an arbitrary identifier are passed into the search method. As it performs the BFS, the listener is called back every time a lock position is discovered.

public interface ISearchListener {  
  public void handleResult(int[][] playfield, int tetriminoType, 
      int id, State state);
}

The listener receives a modified playfield containing the Tetrimino locked in place. The Tetrimino spawn type and the arbitrary identifier are also passed through. The final parameter is the State where the Tetrimino locked. By following the chain of State.predecessor links, it is possible to recover the pathway all the way back to the spawn State.

State.visited could have been implemented as a boolean; however, that would have entailed the overhead of iterating over all the State objects prior to the search to reset visited to false. Instead, visited is an int, which is compared against a count that is incremented every time search is called.

The addChild method provisionally enqueues successor states. The successor must be within the bounds of the playfield and it must be situated over 4 empty playfield cells. In addition, the successor must be an unvisited State. If the position is legal, addChild returns true, even if the successor failed to be enqueued because it was already visited.

The search method uses the addChild return value to detect if it is possible to spawn. If it cannot spawn, then the pile reached the top and there is no searching to be done; so, it returns false.

The addChild return value is also inspected in the attempt to advance downward one step. If that fails, then the current state represents a lock position, triggering a call to lockTetrimino. The lockTetrimino method modifies the playfield, it calls the listener and then it restores the playfield.

Each row of the playfield array contains 1 extra element that stores the number of solid cells within the row. The element is incremented by lockTetrimino as it sets cells to solid.

When the listener receives the modified playfield, it calls PlayfieldUtil.clearRows to remove completed lines; the method detects them by examining the value in the extra row element. To remove a row, the code takes advantage of the fact that in Java, 2-dimensional arrays are actually arrays-of-arrays; it simply shifts down the row references. PlayfieldUtil contains spare rows and it completes the clear by inserting a reference to one of them at top. Before the shift happens, the index of the row-to-be-cleared is saved in the row’s extra element. Then, the row reference is pushed onto a stack.

The listener eventually calls PlayfieldUtil.restoreRows to undo the changes to the playfield. The steps are undone in reverse order. First, the spare row is retrieved from the top. Then, the completed row is popped off the stack and the index is recovered from the extra element. It is used to shift the row references and to position the removed row back into place. Finally, the extra element is restored by setting it to the playfield width, the number of solid cells in a completed line.

PlayfieldUtil also provides the evaluatePlayfield method, which computes and captures 4 of the evaluation factors into the container class listed below.

public class PlayfieldEvaluation {
  public int holes;
  public int columnTransitions;
  public int rowTransitions;
  public int wells;
}

Governing it all is the AI class. It contains 2 Searcher objects chained together by the listener shown below.

public void handleResult(
    int[][] playfield, int tetriminoType, int id, State state) {

  if (id == 0) {
    result0 = state;
  }

  Orientation orientation 
      = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation];
  int rows = playfieldUtil.clearRows(playfield, state.y);
  int originalTotalRows = totalRows;
  int originalTotalDropHeight = totalDropHeight;
  totalRows += rows;
  totalDropHeight += orientation.maxY - state.y;

  int nextID = id + 1;

  if (nextID == tetriminoIndices.length) {

    playfieldUtil.evaluatePlayfield(playfield, e);

    double fitness = computeFitness();
    if (fitness < bestFitness) {
      bestFitness = fitness;
      bestResult = result0;
    }
  } else {
    searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID);
  }

  totalDropHeight = originalTotalDropHeight;
  totalRows = originalTotalRows;
  playfieldUtil.restoreRows(playfield, rows);
}

The AI class is actually designed to handle any number of Searcher objects, but Nintendo Tetris only provides 1 preview piece. The Searcher objects are stored in an array and the code above serves as a common listener for all of them. The arbitrary identifier passed into the Searcher.search method is actually the index into the array, which is also the search depth. When the listener is invoked, the identifier directs the call to the next Searcher in the chain. If it reached the end of the array, then it evaluates the playfield. And, when it encounters a playfield with a better fitness, it records the locked State from the first Searcher in the chain.

AI provides a search method that accepts a playfield and an array containing the spawn and next Tetriminos types. It returns the State containing the position and rotation where the first Tetrimino should lock. It makes no commitment to the second Tetrimino; on the subsequent call, it will reevaluate everything. If the pile is very high and Searcher chain fails to place both Tetriminos, AI.search will return null.

public State search(int[][] playfield, int[] tetriminoIndices) {

  this.tetriminoIndices = tetriminoIndices;
  bestResult = null;
  bestFitness = Double.MAX_VALUE;

  searchers[0].search(playfield, tetriminoIndices[0], 0);

  return bestResult;
}

Invoking the AI

Since the Java version is not anchored to FCEUX, it can potentially be used in other projects. For those interested integrating the AI into something else, this section covers what that entails.

First, create an instance of AI, an instance of PlayfieldUtil and an array to store the known Tetrimino types. Also, instantiate the playfield by calling PlayfieldUtil.createPlayfield; it returns a 2-dimensional array with the additional column discussed earlier. You’ll probably also require a random number generator.

AI ai = new AI();
PlayfieldUtil playfieldUtil = new PlayfieldUtil();
int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED];
int[][] playfield = playfieldUtil.createPlayfield();
Random random = new Random();

The playfield starts out empty with all cells set to Tetriminos.NONE. If you programmatically fill cells, be sure to set playfield[rowIndex][AI.PLAYFIELD_WIDTH] to the number of solid cells in each row.

Fill the Tetrimino types array with the initial spawn and next types, which are normally selected randomly.

tetriminos[0] = random.nextInt(7);
tetriminos[1] = random.nextInt(7);

Then, pass the playfield and the types array to the AI.search method. It will return the State where the first Tetrimino should lock. If it returns null, then game over is inevitable.

State state = ai.search(playfield, tetriminos);

If you need the pathway from spawn to lock, then pass the State to the AI.buildStateList method.

State[] states = ai.buildStatesList(state);

To update the playfield, pass it to PlayfieldUtil.lockTetrimino along with its type and the State object. That method will automatically clear completed lines.

playfieldUtil.lockTetrimino(playfield, tetriminos[0], state);

Before calling AI.search again, the next Tetrimino needs to be randomly selected.

tetriminos[0] = tetriminos[1];    
tetriminos[1] = random.nextInt(7);

AI ai = new AI();
PlayfieldUtil playfieldUtil = new PlayfieldUtil();
int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED];
int[][] playfield = playfieldUtil.createPlayfield();
Random random = new Random();

tetriminos[0] = random.nextInt(7);
tetriminos[1] = random.nextInt(7);

while(true) {

  // ... print playfield ...

  State state = ai.search(playfield, tetriminos);

  if (state == null) {
    break; // game over
  }

  playfieldUtil.lockTetrimino(playfield, tetriminos[0], state);

  tetriminos[0] = tetriminos[1];    
  tetriminos[1] = random.nextInt(7);
}

Rather than printing out the playfield, there is a more interesting way to view what is going on...

Displaying the Playfield

The TetrisFrame class simulates the visuals of Nintendo Tetris including all the quirks discussed in earlier sections.

To see it in action, launch tetris.gui.Main. As with the Lua version, you can adjust the play speed by modifying a constant at the top of the file.

public static final boolean PLAY_FAST = true;

TetrisFrame provides 4 methods for manipulating the screen. The displayTetrimino method renders the active Tetrimino at the specified coordinates. It accepts a delay parameter, which causes the method to wait for that number of animation frames before returning.

public void displayTetrimino(int type, int rotation, int x, int y, int delay)

The lockTetrimino method fixes a piece into place. The lines counter, the score, the level and the Tetrimino colors will update accordingly, exhibiting the expected peculiar behaviors as the values increase beyond the intended limits. Setting the animate parameter to true enables line clearing animations, flashing the display when a Tetris is achieved. The method will block until animations complete.

public void lockTetrimino(int type, int rotation, int x, int y, boolean animate)

updateStatisticsAndNext increments the stats counter for the newly spawned Tetrimino and it updates the preview piece.

public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino)

The dropTetrimino method will spawn a piece and it will let it drop under gravity, making no attempt to rotate or position it. Main uses it for the final 2 pieces when AI.search returns null. If the animate parameter is true, the game over curtain will come down upon spawn failure. As with the other methods, this one blocks until all animations complete. It returns true only if it is able spawn into the crowded playfield.

public boolean dropTetrimino(int type, boolean animate)

Those 4 methods should be invoked by a worker thread, but the TetrisFrame itself should be created on the Event Dispatch Thread. Refer to the Main class to see how this is done.

For fun, Main uses Randomizer, a class that simulates the biased pseudorandom number generator in Nintendo Tetris.

The tetris.gui.images package contains display related files. tiles.png is the pattern table, containing all the tile graphics. background.dat stores tile ids that collectively make up the background; the data was pulled from $BF3F. And, colors.dat contains the bytes that generate the unusual square colors that manifest themselves starting at level 138.

ImageLoader contains the NES palette table and ImagePane possesses the full set of level display values.

Other Projects

The code could potentially be used in place of a recording for demo mode. In fact, such a demo could be rendered perpetual by taking advantage of how rapidly the AI is able to clear the entire playfield. To accomplish this, the pseudorandom number generator would be seeded with by some arbitary constant, producing a deterministic sequence of Tetriminos. The first 2 Tetriminos of the sequence would be recorded. When the AI achieves a full clear, the next 2 Tetriminos would be compared against the first 2 of sequence. If they match—an event expected every 49 full clears, on the average—then the pseudorandom number generator could be reseeded with the original constant, producing an endless demo loop. The length of the loop could be made very large to obscure the fact that it is a loop at all. And, the demo could start at a random point of the loop, providing a different demo each time.

Another potential use of the AI is for player versus computer mode. In multiplayer Tetris, when a group of rows are cleared simultaneously, garbage rows will push up from the bottom of the opponent’s playfield, lifting it upward. The AI should be able to defend itself against garbage for the same reason it is able to play B-Type games. However, as discussed earlier, the AI plays conservatively, tending to clear single rows at time. Meaning, it will be able to guard against assault, but won’t be able to attack. To provide the means of modifying this behavior, I created an interface called IChildFilter.

public interface IChildFilter {
  public boolean validate(int[][] playfield, int tetriminoType,
      int x, int y, int rotation);
}

AI provides an alternate constructor that accepts an implementation of IChildFilter. When present, IChildFilter.validate serves as an additional check for determining if a child state is legal; if it returns false, then the child is not enqueued.

WellFilter is an implementation of IChildFilter that aims for Tetrises. Like human players, it incrementally builds a well in the right-most column of playfield, row-by-row from the bottom up. As it works on a row, it declines children that that would introduce a square in the right-most column. When a row is completely solid except for the well column, it advances to the row above it. When 4 or more such rows are ready, it will permit an I Tetrimino to fill the well, achieving a Tetris. Also, the pile height is monitored; if it grows too high, WellFilter stops interfering with the AI.

AI ai = new AI(new WellFilter());

WellFilter works, but not very efficiently. It contains a simple heuristic intended to demonstrate the concept. To obtain Tetrises more often will require a more elaborate strategy, perhaps something that could be optimized by PSO.

It is also possible to use child state filtering to generate art. Below is an example of what PatternFilter can do.

PatternFilter builds up images row-by-row from the bottom up similar to how WellFilter functions; however, instead of keeping the right-most column empty, PatternFilter only accepts children that maintain a particular pattern.

The constructor of PatternFilter accepts the name one of the image files in the tetris.gui.patterns package, which it uses as a template. Each 20×10 image contains black and white pixels corresponding to cells of the playfield.

AI ai = new AI(new PatternFilter("tetriminos"));

Below is one more. If you squint, you might be able to make out the title of the game.

Like WellFilter, PatternFilter is nothing more than a proof of concept. The patterns that it can handle are limited to the lower half of the playfield due to its tendency to reach game over before finishing them. Nonetheless, it is an interesting idea worthy of further investigation.

Gamepad Version

The Lua script and the Java program ignore gravity; for them, the drop speed is irrelevant because, depending on the configuration, it either teleports pieces directly into lock or it carries them there along any pathway and rate that it desires. In a sense, they are only imitating Tetris rather than playing it. However, the source zip includes an alternate Lua script that plays entirely by generating gamepad button signals, allowing the game to govern the piece movements, gravity and all.

Introducing gravity greatly increases the search space, forcing the AI to take into account the subtle rules used for manipulating pieces. The details of these rules were discussed in prior sections and they can only be fully appreciated by directly studying the code, but here are the highlights:

To accommodate those rules, historical information needs to be incorporated into the search states. It requires fields that express the number of frames that each button has been held and the number of frames since the last automatic drop. Every unique set of values—including the x-coordinate, the y-coordinate and the rotation of the Tetrimino—characterizes a separate and distinct state. Unfortunately, the number of possibilities is so vast that it is impractical to fully search that space. Instead, the gamepad version of the AI only explores a subset of it.

{ x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor }

Rather than relying on the auto-shift, the AI presses and releases a shift button on alternate frames. Consequentially, it only needs to keep track of whether the button is pressed or not, as opposed to how long it has been held. Since there is no auto-rotate, the same idea applies to the A and B buttons. As such, the Left, Right, A and B fields can be interpreted as enums containing one of these values:

{ RELEASED, PRESSED }

On the other hand, to soft drop, the Down button must be initially held for 3 frames, necessitating 4 states:

{ RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES }

Down incrementally advances from RELEASED to PRESSED_FOR_3_FRAMES, at which point a soft drop occurs. From there, it can be RELEASED or it can return to PRESSED_FOR_2_FRAMES, providing a soft drop every other frame after the initial delay. It is prohibiting from being RELEASED from PRESSED_FOR_1_FRAME or PRESSED_FOR_2_FRAMES.

In actuality, integer constants are used in the Lua code, but the concept is the same.

Like visited and predecessor, fallTimer is an assigned value that is acquired when a child state is enqueued; its fallTimer will be one greater than its parent’s value. A state that contains a fallTimer equal to the drop speed implies that an automatic drop occurs within that frame and the successors of that state will have a fallTimer of 0.

Each Searcher pre-allocates an 8-dimensional array containing all possible states (20 rows × 10 columns × 4 rotations × 2 Lefts × 2 Rights × 4 Downs × 2 As × 2 Bs) and the BFS acts analogously to the method presented for the 3-dimensional array. The pseudocode below details how successors are derived from dequeued states.

Slide = (Left == PRESSED) or (Right == PRESSED)
Rotate = (A == PRESSED) or (B == PRESSED)

if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then  

  if Down == RELEASED then
    nextDown = PRESSED_FOR_1_FRAME
  else
    nextDown = PRESSED_FOR_2_FRAMES
  end

  addChild(Down = nextDown)

  if not Rotate then
    addChild(A = PRESSED, Down = nextDown)
    addChild(B = PRESSED, Down = nextDown)
  end

  if Slide then

    addChild()

    if not Rotate then
      addChild(A = PRESSED)
      addChild(B = PRESSED)
    end

  else

    addChild(Left = PRESSED)
    addChild(Right = PRESSED)

    if not Rotate then

      addChild(Left = PRESSED, A = PRESSED)
      addChild(Left = PRESSED, B = PRESSED)
      addChild(Right = PRESSED, A = PRESSED)
      addChild(Right = PRESSED, B = PRESSED)
      
    end

  end

else

  if Down == PRESSED_FOR_1_FRAME then
    nextDown = PRESSED_FOR_2_FRAMES
  else
    nextDown = PRESSED_FOR_3_FRAMES
  end

  addChild(Down = nextDown)

  if not Rotate then
    addChild(A = PRESSED, Down = nextDown)
    addChild(B = PRESSED, Down = nextDown)
  end  

end

As illustrated by the pseudocode that follows, the addChild function takes into account the order of events that occur within each frame (i.e. shift, rotate and drop).

nextFallTimer = fallTimer + 1

if Left == PRESSED and testPosition(x - 1, y, rotation) then
  x = x - 1
elseif Right == PRESSED and testPosition(x + 1, y, rotation) then
  x = x + 1 
end

if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then
  rotation = nextClockwiseRotation
elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then
  rotation = nextCounterclockwiseRotation    
end

if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then
  if testPosition(x, y + 1, rotation) then
    y = y + 1
    nextFallTimer = 0
  else
    lockTetrimino()
    return
  end
end       

childState = states[y][x][rotation][Left][Right][Down][A][B]
if not childState.visited then
  childState.visited = mark
  childState.predecessor = state  
  childState.fallTimer = nextFallTimer  
  queue.enqueue(childState)
end

As in the prior version, AI.search returns a chain of State objects. But, in this case, each State contains the set of buttons to press within each frame. The x, y and rotation fields are not used for manipulating the pieces, but they can be used to verify that the pieces moved as expected.

Although the search space was greatly reduced by imposing the constraints that are describe above, it still takes 1–3 seconds to complete the search. If you run it, you’ll experience a pause every time a Tetrimino is spawned. Also, the movements appear very unnatural; it tends to rotate the piece a moment before lock. Nonetheless, it plays almost as well as the version that ignored gravity, even at the highest speed.

To try it, launch lua/NintendoTetrisAIGamepadVersion.lua located in the source zip.

A simpler method to incorporate gravity is to restrict piece movement to a rotation followed by a shift followed by a drop to the bottom. The idea is that by eliminating slides and spins, the rate at which pieces move vertically will have little effect on the AI; all it needs to do is to get a piece into the correct column and orientation and gravity will do the rest. Another advantage of this technique is that the search space is very small, enabling it to play in real-time without computation delays. However, the downside is that without slides and spins, it plays significantly worse. Nevertheless, a Tetris AI that cannot play in real-time is less than useful.

30000–49999	50000–69999	70000–99999
100000–119999	120000+

$00	$02	$07	$08	$0A	$0B	$0E	$12
0	2	0	1	3	4	0	4
1	3	1	2	4	5	1	5
2	4	2	3	5	6	2	6
3	5	3	4	6	0	3	0
4	6	4	5	0	1	4	1
5	0	5	6	1	2	5	2
6	1	6	0	2	3	6	3
7	2	0	1	3	4	0	4

00	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15
1	16	17	18	19	20	21	22	23	24	25	26	27	28	29	00	0A
2	14	1E	28	32	3C	46	50	5A	64	6E	78	82	8C	96	A0	AA
3	B4	BE	C6	20	E6	20	06	21	26	21	46	21	66	21	86	21
4	A6	21	C6	21	E6	21	06	22	26	22	46	22	66	22	86	22
5	A6	22	C6	22	E6	22	06	23	26	23	85	A8	29	F0	4A	4A
6	4A	4A	8D	07	20	A5	A8	29	0F	8D	07	20	60	A6	49	E0
7	15	10	53	BD	D6	96	A8	8A	0A	AA	E8	BD	EA	96	8D	06
8	20	CA	A5	BE	C9	01	F0	1E	A5	B9	C9	05	F0	0C	BD	EA
9	96	38	E9	02	8D	06	20	4C	67	97	BD	EA	96	18	69	0C
A	8D	06	20	4C	67	97	BD	EA	96	18	69	06	8D	06	20	A2
B	0A	B1	B8	8D	07	20	C8	CA	D0	F7	E6	49	A5	49	C9	14
C	30	04	A9	20	85	49	60	A5	B1	29	03	D0	78	A9	00	85
D	AA	A6	AA	B5	4A	F0	5C	0A	A8	B9	EA	96	85	A8	A5	BE
E	C9	01	D0	0A	A5	A8	18	69	06	85	A8	4C	BD	97	A5	B9
F	C9	04	D0	0A	A5	A8	38	E9	02	85	A8	4C	BD	97	A5	A8

Starting Level	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Expected Lines	10	20	30	40	50	60	70	80	90	100	110	120	130	140	150	160	170	180	190	200
Actual Lines	10	20	30	40	50	60	70	80	90	100	100	100	100	100	100	100	110	120	130	140

$00	$02	$07	$08	$0A	$0B	$0E	$12
0	2	0	1	3	4	0	4
1	3	1	2	4	5	1	5
2	4	2	3	5	6	2	6
3	5	3	4	6	0	3	0
4	6	4	5	0	1	4	1
5	0	5	6	1	2	5	2
6	1	6	0	2	3	6	3
7	2	0	1	3	4	0	4

00	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15
1	16	17	18	19	20	21	22	23	24	25	26	27	28	29	00	0A
2	14	1E	28	32	3C	46	50	5A	64	6E	78	82	8C	96	A0	AA
3	B4	BE	C6	20	E6	20	06	21	26	21	46	21	66	21	86	21
4	A6	21	C6	21	E6	21	06	22	26	22	46	22	66	22	86	22
5	A6	22	C6	22	E6	22	06	23	26	23	85	A8	29	F0	4A	4A
6	4A	4A	8D	07	20	A5	A8	29	0F	8D	07	20	60	A6	49	E0
7	15	10	53	BD	D6	96	A8	8A	0A	AA	E8	BD	EA	96	8D	06
8	20	CA	A5	BE	C9	01	F0	1E	A5	B9	C9	05	F0	0C	BD	EA
9	96	38	E9	02	8D	06	20	4C	67	97	BD	EA	96	18	69	0C
A	8D	06	20	4C	67	97	BD	EA	96	18	69	06	8D	06	20	A2
B	0A	B1	B8	8D	07	20	C8	CA	D0	F7	E6	49	A5	49	C9	14
C	30	04	A9	20	85	49	60	A5	B1	29	03	D0	78	A9	00	85
D	AA	A6	AA	B5	4A	F0	5C	0A	A8	B9	EA	96	85	A8	A5	BE
E	C9	01	D0	0A	A5	A8	18	69	06	85	A8	4C	BD	97	A5	B9
F	C9	04	D0	0A	A5	A8	38	E9	02	85	A8	4C	BD	97	A5	A8

$00	$02	$07	$08	$0A	$0B	$0E	$12
0	2	0	1	3	4	0	4
1	3	1	2	4	5	1	5
2	4	2	3	5	6	2	6
3	5	3	4	6	0	3	0
4	6	4	5	0	1	4	1
5	0	5	6	1	2	5	2
6	1	6	0	2	3	6	3
7	2	0	1	3	4	0	4

00	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15
1	16	17	18	19	20	21	22	23	24	25	26	27	28	29	00	0A
2	14	1E	28	32	3C	46	50	5A	64	6E	78	82	8C	96	A0	AA
3	B4	BE	C6	20	E6	20	06	21	26	21	46	21	66	21	86	21
4	A6	21	C6	21	E6	21	06	22	26	22	46	22	66	22	86	22
5	A6	22	C6	22	E6	22	06	23	26	23	85	A8	29	F0	4A	4A
6	4A	4A	8D	07	20	A5	A8	29	0F	8D	07	20	60	A6	49	E0
7	15	10	53	BD	D6	96	A8	8A	0A	AA	E8	BD	EA	96	8D	06
8	20	CA	A5	BE	C9	01	F0	1E	A5	B9	C9	05	F0	0C	BD	EA
9	96	38	E9	02	8D	06	20	4C	67	97	BD	EA	96	18	69	0C
A	8D	06	20	4C	67	97	BD	EA	96	18	69	06	8D	06	20	A2
B	0A	B1	B8	8D	07	20	C8	CA	D0	F7	E6	49	A5	49	C9	14
C	30	04	A9	20	85	49	60	A5	B1	29	03	D0	78	A9	00	85
D	AA	A6	AA	B5	4A	F0	5C	0A	A8	B9	EA	96	85	A8	A5	BE
E	C9	01	D0	0A	A5	A8	18	69	06	85	A8	4C	BD	97	A5	B9
F	C9	04	D0	0A	A5	A8	38	E9	02	85	A8	4C	BD	97	A5	A8