[Перевод] Как я научил ИИ играть в Tetris для NES. Часть 1: анализ кода игры24.08.2018 12:36

В этой статье я исследую обманчиво простые механики Nintendo Tetris, а во второй части расскажу, как создал ИИ, эксплуатирующий эти механики.

Попробуйте сами

О проекте

Для тех, кому не хватает упорства, терпения и времени, необходимых для освоения Nintendo Tetris, я создал ИИ, способный играть самостоятельно. Вы наконец-то сможете добраться до уровня 30 и даже дальше. Вы увидите, как получить максимальное количество очков и понаблюдаете за бесконечным изменением счётчиков рядов, уровней и статистики. Узнаете, какие цвета появляются на уровнях, выше которых не мог забраться человек. Посмотрите, насколько далеко можно зайти.

Требования

Для запуска ИИ вам понадобится универсальный эмулятор NES/Famicom FCEUX. Искусственный интеллект был разработан для FCEUX 2.2.2, самой новой версии эмулятора на время написания статьи.

Также вам понадобится ROM-файл Nintendo Tetris (версия для США). Попробуйте поискать его в Google.

Скачивание

Распакуйте lua/NintendoTetrisAI.lua из этого zip-файла с исходниками.

Запуск

Запустите FCEUX. В меню выберите File | Open ROM… В диалоговом окне Open File выберите ROM-файл Nintendo Tetris и нажмите Open. Запустится игра.

В меню выберите File | Lua | New Lua Script Window… В окне the Lua Script введите путь к NintendoTetrisAI.lua или нажмите кнопку Browse, чтобы найти его. После этого нажмите Run.

Скрипт на Lua перенаправит вас на первый экран меню. Оставьте тип игры A-Type, а музыку можете выбирать любую. На медленных компьютерах музыка может играть очень дёргано, тогда стоит её отключить. Нажмите на Start (Enter), чтобы перейти к следующему экрану меню. Во втором меню можно с помощью клавиш со стрелками изменить начальный уровень. Нажмите на Start, чтобы начать игру. И здесь управление перехватит ИИ.

Если после выбора уровня на втором экране меню зажать кнопку геймпада A (изменить раскладку клавиатуры можно в меню Config | Input…) и нажать Start, то начальный уровень будет на 10 больше выбранного значения. Максимальный начальный уровень — девятнадцатый.

Конфигурация

Чтобы игра шла быстрее, откройте скрипт Lua в текстовом редакторе. В начале файла найдите следующую строку.

PLAY_FAST = false

Замените false на true, как показано ниже.

PLAY_FAST = true

Сохраните файл. Затем нажмите кнопку Restart в окне Lua Script.

Механики Nintendo Tetris

Описание тетримино

Каждой фигуре тетримино соответствует однобуквенное название, напоминающее её форму.

Дизайнеры Nintendo Tetris произвольным образом задали показанный выше порядок тетримино. Фигуры показаны в той ориентации, в которой они появляются на экране, а схема создаёт почти симметричную картинку (возможно, поэтому выбран такой порядок). Индекс последовательности даёт каждому тетримино уникальный числовой ID. Идентификаторы последовательности и типа важны на уровне программирования; кроме того, они проявляют себя в порядке фигур, отображаемом в поле статистики (см. ниже).

19 ориентаций используемых в Nintendo Tetris тетримино закодированы в таблице, расположенной по адресу $8A9C памяти консоли NES. Каждая фигура представлена как последовательность из 12 байтов, которые можно разбить на тройки (Y, tile, X), описывающие каждый квадрат в фигуре. Указанные выше hex-значения координат выше $7F обозначают отрицательные целые числа ($FF= −1, а $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

Внизу таблицы есть одна неиспользованная запись, потенциально дающая возможность добавления ещё одной ориентации. Однако в различных частях кода $13 обозначает, что идентификатору ориентации активного тетримино не присвоено значение.

Для простоты чтения ниже представлены координаты квадратов в десятичном виде.

-- { { 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)

Все ориентации помещаются в матрицу 5×5.

На показанном выше рисунке белый квадрат означает центр матрицы, опорную точку для поворота фигуры.

Ниже графически представлена таблица ориентаций.

Идентификатор ориентации (индекс таблицы) показан в шестнадцатеричном виде в правом верхнем углу каждой матрицы. А придуманная для этого проекта мнемоника показана в левом верхнем углу. u, r, d, l, h и v — это сокращения от «up, right, down, left, horizontal и vertical». Например, проще обозначать ориентацию Jd, а не $07.

Матрицы, содержащие ориентации фигур при создании, отмечены белой рамкой.

Тетримино I, S и Z можно было дать 4 отдельных ориентации, но создатели Nintendo Tetris решили ограничиться двумя. Кроме того, Zv и Sv не являются идеальными зеркальными отражениями друг друга. Обе созданы поворотом против часовой стрелки, что приводит к дисбалансу.

В таблице ориентаций также присутствуют значения тайлов для каждого квадрата в каждой ориентированной фигуре. Однако при внимательном исследовании становится понятно, что значения для одного типа тетримино всегда одинаковы.

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

Значения тайлов являются индексами таблицы (псевдоцветного) паттерна, показанной ниже.

Тайлы $7B, $7C и $7D расположены прямо под «ATIS» из слова «STATISTICS». Это три типа квадратов, из которых создаются тетримино.

Для любопытных скажу, что страусы и пингвины используются в концовках режима B-Type. Эта тема подробно рассмотрена в разделе «Концовки».

Ниже показан результат модификации ROM после замены $7B на $29. Сердце — это тайл под символом P в таблице паттерна для всех ориентаций T.

Тайлы-сердца остаются на игровом поле даже после того, как модифицированные T блокируются на месте. Как сказано ниже в разделе «Создание тетримино», это означает, что игровое поле хранит настоящие значения индексов тайлов сыгранных тетримино.

Программисты игры обеспечили возможность использования для каждой фигуры 4 отдельных тайлов, а не только один неизменный тип квадратов. Это полезная фишка, которую можно использовать для модификации внешнего вида игры. В таблице паттерна очень много пустого места для новых тайлов, способных придать каждому тетримино уникальный внешний вид.

Координатами квадратов очень легко манипулировать. Например, ниже показана модифицированная версия первых четырёх троек в таблице ориентаций.

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

В результате получается разделённое тетримино.

При перемещении разделённого тетримино его квадраты не могут выходить за границы игрового поля и не могут проходить через ранее заблокированные на месте фигуры. Кроме того, игра запрещает поворот в этой ориентации, если он приведёт к попаданию квадрата за границы игрового поля или к тому, что квадрат наложится на уже лежащий квадрат.

Разделённое тетримино блокируется на месте, когда находится опора для любого из его квадратов. Если фигура блокируется, то висящие в воздухе квадраты продолжают висеть.

Игра обращается с разделёнными тетримино как с любой нормальной фигурой. Это даёт нам понять, что нет дополнительной таблицы, хранящей метаданные фигур. Например, могла бы существовать таблица, хранящая размеры ограничивающего прямоугольника каждой ориентации для проверки коллизий с периметром игрового поля. Но такая таблица не используется. Вместо этого игра просто выполняет проверки всех четырёх квадратов прямо перед манипуляциями с фигурой.

Кроме того, координаты квадратов могут быть любыми значениями; они не ограничены интервалом [−2, 2]. Разумеется, сильно превышающие этот интервал значения дадут нам неприменимые фигуры, которые не поместятся на игровом поле. Что более важно, как сказано в разделе «Состояния игры и режимы рендеринга», когда фигура блокируется на месте, механизм очистки заполненных линий сканирует только смещения рядов от −2 до 1 от центрального квадрата фигуры; квадрат с координатой y за пределами этого интервала окажется нераспознанным.

Вращение тетримино

В графической иллюстрации таблицы ориентаций вращение заключается в переходе от матрицы к одной из матриц слева или справа с переносом ряда при необходимости. Эта концепция закодирована в таблице по адресу $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

Чтобы было понятнее, каждый столбец из этой таблицы мы переместим в строку показанной ниже таблицы.

	Tu	Tr	Td	Tl	Jl	Ju	Jr	Jd	Zh	Zv	O	Sh	Sv	Lr	Ld	Ll	Lu	Iv	Ih
Против часовой стрелки	Tl	Tu	Tr	Td	Jd	Jl	Ju	Jr	Zv	Zh	O	Sv	Sh	Lu	Lr	Ld	Ll	Ih	Iv
По часовой стрелке	Tr	Td	Tl	Tu	Ju	Jr	Jd	Jl	Zv	Zh	O	Sv	Sh	Ld	Ll	Lu	Lr	Ih	Iv

Мнемоники в заголовках вверху можно интерпретировать как индекс последовательности или ключ для распределения. Например, поворот против часовой стрелки Tu даёт нам Tl, а поворот по часовой стрелке Tu даёт Tr.

Таблица поворотов кодирует соединённые в цепочку последовательности ID ориентаций; следовательно, мы можем модифицировать записи таким образом, чтобы поворот преобразовывал один тип тетримино в другой. Эту технику потенциально можно использовать для извлечения пользы из неиспользованной строки в таблице ориентаций.

Перед таблицей поворотов расположен код для доступа к ней.

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;

Для поворота против часовой стрелки индекс таблицы поворотов вычитается удвоением ID ориентации. Прибавлением к нему 1 мы получаем индекс поворота по часовой стрелке.

Координаты x, y и ID ориентации текущего тетримино хранятся соответственно по адресам $0040, $0041 и $0042.

Код использует временную переменную для резервного копирования ID ориентации. Позже, после изменения ориентации, код проверяет, что все четыре квадрата находятся в границах игрового поля и ни один из них не накладывается на уже лежащие квадраты (код проверки находится по адресу $948B, под показанным выше фрагментом кода). Если новая ориентация неверна, то восстанавливается исходная, не позволяя игроку повернуть фигуру.

Считая с крестовиной, у контроллера NES восемь кнопок, состояние которых представлено битом адреса $00B6.

7	6	5	4	3	2	1	0
A	B	Select	Start	Вверх	Вниз	Влево	Вправо

Например, в $00B6 будет содержаться значение $81 пока игрок удерживает A и «Влево».

С другой стороны, $00B5 сообщает о том, когда были нажаты кнопки; биты $00B5 истинны только в течение одной итерации игрового цикла (1 отрендеренного кадра). Код использует $00B5, чтобы реагировать на нажатия A и B. Каждую из них нужно отпустить, прежде чем использовать снова.

$00B5 и $00B6 являются зеркалами $00F5 и $00F6. Код в последующих разделах использует эти адреса взаимозаменяемо.

Создание тетримино

Игровое поле Nintendo Tetris состоит из матрицы с 22 строками и 10 столбцами так, что верхние две строки скрыты от игрока.

Как показано в представленном ниже коде, при создании фигуры тетримино она всегда располагается в координатах (5, 0) игрового поля.

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

Ниже показана наложенная на эту точку матрица размером 5×5.

Ни у одной из матриц создания нет квадратов над исходной точкой. То есть при создании тетримино все четыре его квадрата сразу становятся видны игроку. Однако если игрок быстро повернёт фигуру, прежде чем она успеет опуститься, то часть фигуры будет временно скрыта в первых двух строках игрового поля.

Обычно мы считаем, что игра завершается, когда куча достигнет вершины. Но на самом деле это не совсем так. Игра заканчивается, когда больше нет возможности создать следующую фигуру. То есть перед появлением фигуры должны быть свободны все четыре ячейки игрового поля, соответствующие позициям квадратам создаваемого тетримино. Фигура может оказаться заблокированной на месте таким образом, что часть её квадратов окажется в отрицательно пронумерованных строках, и игра при этом не закончится; однако в Nintendo Tetris отрицательные строки — это абстракция, относящаяся только к активному тетримино. После того, как фигура блокируется (становится лежащей), на поле записываются только квадраты в строках от нуля и больше. Концептуально получается, что отрицательно пронумерованные строки автоматически очищаются после блокировки. Но в реальности игра просто не хранит эти данные, отсекая верхние части фигур.

Видимая область игрового поля 20×10 хранится по адресу $0400 в построчном порядке, каждый байт содержит значение фонового тайла. Пустые клетки обозначаются тайлом $EF, сплошным чёрным квадратом.

При создании фигуры используются три таблицы поиска. При наличии произвольного ID ориентации таблица по адресу $9956 даёт нам ID ориентации при создании соответствующего типа тетримино.

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

Например, все ориентации J привязываются к Jd.

Таблица по адресу $993B содержит тип тетримино для заданного ID ориентации.

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

Третью таблицу поиска мы рассмотрим в следующем разделе.

Выбор тетримино

В Nintendo Tetris в качестве псевдослучайного генератора чисел (PRNG) используется 16-битный регистр сдвига с линейной обратной связью (linear feedback shift register, LFSR) в конфигурации Фибоначчи. 16-битное значение хранится как big-endian по адресам $0017–$0018. В качестве Seed используется произвольное число $8988.

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

Каждое последующее псевдослучайное число генерируется следующим образом: значение воспринимается как 17-битное число, а наиболее значимый бит получается выполнением XOR для битов 1 и 9. Затем значение сдвигается вправо, отбрасывая наименее значимый бит.

Этот процесс происходит по адресу $AB47.

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

Интересно, что параметры показанной выше подпрограммы можно задать так, чтобы вызывающая функция могла указать ширину регистра сдвига и адрес, по которому его можно найти в памяти. Однако те же параметры используются повсюду, поэтому можно предположить, что разработчики где-то позаимствовали этот код.

Для тех, кто хочет ещё больше видоизменить алгоритм, я написал его на Java.

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);
}

Этот PRNG непрерывно и детерминированно генерирует 32 767 уникальных значений, начиная каждый цикл с исходного seed. Это на единицу меньше половины возможных чисел, которые могут поместиться в регистр, и любое значение в этом множестве можно использовать в качестве seed. Многие из значений за пределами множества создают цепочку, которая со временем приведёт к числу из множества. Однако некоторые начальные числа в результате приводят к бесконечной последовательности нулей.

Чтобы приблизительно оценить производительность этого PRNG, я сгенерировал графическое представление создаваемых им значений, основанное на предложении с RANDOM.ORG.

При создании изображения PRNG использовался как генератор псевдослучайных чисел, а не 16-битных целых чисел. Каждый пиксель раскрашен на основании значения бита 0. Изображение имеет размер 128×256, то есть покрывает всю последовательность.

Если не считать едва заметные полосы по верхней и левой сторонам, она выглядит случайной. Не проявляется никаких очевидных паттернов.

После запуска PRNG постоянно перемешивает регистр, срабатывая не реже, чем раз в кадр. Это не происходит не только на экране заставки и экранах меню, но и при падении тетримино между операциями создания фигур. То есть от количества кадров, уходящих у игрока на размещение фигуры, зависит появляющаяся следом фигура. По сути, игра полагается на случайность действий взаимодействующего с ней человека.

Во время создания фигуры выполняется код по адресу $9907, выбирающий тип новой фигуры.

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;

По адресу $001A хранит счётчик количества фигур, созданных с включения питания. Инкремент счётчика выполняется первой строкой подпрограммы, и поскольку это однобайтный счётчик, через каждые 256 фигур он снова возвращается к нулю. Поскольку между играми счётчик не сбрасывается, история предыдущих игр влияет на процесс выбора фигуры. Это ещё один способ, которым игра использует игрока в качестве источника случайности.

Подпрограмма преобразует самый значимый байт псевдослучайного числа ($0017) в тип тетримино и использует его как индекс таблицы, расположенной по адресу $994E для преобразования типа в ID ориентации создания фигуры.

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

На первом этапе преобразования к верхнему байту прибавляется счётчик созданных фигур. Затем применяется маска для сохранения только нижних 3 битов. Если результат не равен 7, то это правильный тип тетримино, и если он не такой же, как предыдущая выбранная фигура, то число используется в качестве индекса в таблице создания фигур. В противном случае генерируется следующее псевдослучайное число и применяется маска для получения нижних 3 битов верхнего байта, а затем прибавляется предыдущий ID ориентации создания фигуры. Наконец, выполняется операция по модулю для получения правильного типа тетримино, который используется как индекс в таблице создания фигур.

Поскольку процессор не поддерживает деление с остатком, этот оператор эмулируется многократным вычитанием 7, пока результат не станет меньше 7. Деление с остатком применяется к сумме верхнего байта с наложенной маской и к предыдущей ID ориентации создания фигуры. Максимальное значение этой суммы равно 25. То есть для уменьшения её до остатка 4 потребуется всего 3 итерации.

В начале каждой игры ID ориентации создания фигуры ($0019) инициализируется со значением Tu ($00). Это значение потенциально может быть использовано по адресу $9928 во время первого создания фигуры.

При использовании в сумме предыдущего ID ориентации создания фигуры, а не предыдущего типа тетримино добавляет искажение, потому что значения ID ориентации распределены не равномерно. Это показано в таблице:

$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

В каждой ячейке содержится тип тетримино, вычисленный прибавлением ID ориентации создаваемой фигуры (столбца) к 3-битному значению (строке), а затем применением к сумме остатка от деления на 7. В каждой строке содержатся дубликаты, потому что $07 and $0E равномерно делятся на 7, а $0B и $12 имеют общий остаток. Строки 0 и 7 одинаковы, потому что они находятся на расстоянии 7.

Существует 56 возможных входных комбинаций, и если получающиеся типы тетримино распределены равномерно, то можно ожидать, что в показанной выше таблице каждый тип должен появиться ровно 8 раз. Но как показано ниже, это не так.

Тип	Частота
T	9
J	8
Z	8
O	8
S	9
L	7
I	7

T и S появляются чаще, а L и I — реже. Но код с перекосом, использующий ID ориентации, не выполняется при каждом вызове подпрограммы.

Предположим, что PRNG действительно создаёт последовательность равномерно распределённых статистические независимых значений. На самом деле это справедливое допущение, учитывая то, как игра пытается получить правильную случайность из действий игрока. Прибавление количества созданных фигур по адресу $990C не повлияет на распределение, потому что между вызовами количество увеличивается равномерно. Применение битовой маски по адресу $990E аналогично применению деления на 8 с остатком, которое тоже не влияет на распределение. Следовательно, проверка по адресу $9910 переходит к invalidIndex в 1/8 всех случаев. А вероятность попадания при проверке по адресу $9918, где сравнивается новая выбранная фигура с предыдущей фигурой, равна 7/8, при вероятности совпадения в 1/7. Это значит, что существует дополнительная вероятность 7/8 × 1/7 = 1/8 оказаться в invalidIndex. В целом существует вероятность 25% использования кода с перекосом и вероятность 75% использования кода, выбирающего тетримино равномерно.

В наборе из 224 созданных тетримино математическое ожидание равно 32 экземплярам для каждого типа. Но на самом деле код создаёт следующее распределение:

Тип	Частота
T	33
J	32
Z	32
O	32
S	33
L	31
I	31

То есть очистив 90 строк и достигнув уровня 9, игрок получит на одну лишнюю T и S и на одну меньше L и I, чем это ожидается статистически.

Тетримино выбираются со следующими вероятностями:

Тип	Вероятность
T	14.73%
J	14.29%
Z	14.29%
O	14.29%
S	14.73%
L	13.84%
I	13.84%

Похоже, в утверждении о том, что «длинная палка» I никогда не появляется, когда она нужна, есть часть правды (по крайней мере, для Nintendo Tetris).

Сдвиг тетримино

Nintendo Tetris используется отложенный автоматический сдвиг (Delayed Auto Shift, DAS). Нажатие на «Влево» или «Вправо» мгновенно перемещает тетримино на одну ячейку по горизонтали. В то время как удерживание одной из этих кнопок направлений заставляет игру автоматически сдвигать фигуру через каждые 6 кадров с изначальной задержкой в 16 кадров.

Такой вид горизонтального движения управляется кодом по адресу $89AE.

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;

Как и в коде вращения, здесь используется временная переменная для резервного копирования координаты x на случай, если новая позиция окажется неправильной.

Заметьте, что проверка мешает сдвигать фигуру, пока игрок нажимает «Вниз».

Бросание тетримино

Скорость автоматического спуска тетримино — это функция от номера уровня. Скорости кодируются как количество отрендеренных кадров на спуск в таблице, расположенной по адресу $898E. Так как NES работает с частотой 60,0988 кадров/с, можно вычислить период между спусками и скорость.

Уровень	Кадров на спуск	Период (с/спуск)	Скорость (ячеек/с)
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

В таблице всего 30 записей. После уровня 29 значение кадров на спуск всегда равно 1.

Целое число кадров на спуск — это не особо детализированный способ описания скорости. Как показано на графике ниже, скорость растёт с каждым уровнем экспоненциально. На самом деле уровень 29 в два раза быстрее, чем уровень 28.

При 1 кадре/спуск у игрока есть не больше ⅓ секунды на расположение фигуры, прежде чем она начнёт двигаться. На этой скорости спуска DAS не позволяет фигуре достигнуть краёв игрового поля до блокирования на месте, что означает для большинства людей быстрый конец игры. Однако некоторым игрокам, в частности Тору Акерлунду, удалось победить DAS быстрой вибрацией кнопок крестовины (D-pad). В показанном выше коде сдвига видно, что пока кнопка горизонтального направления отпускается через кадр, возможно сдвигать тетримино на уровнях 29 и выше с половинной частотой. Это теоретический максимум, но любая вибрация большого пальца выше 3,75 нажатий/с может победить исходную задержку в 16 кадров.

Если автоматический и управляемый игроком спуск (нажатием «Вниз») совпадают и происходят в одном кадре, эффект не складывается. Любой или оба из этих событий заставляют фигуру опуститься вниз в этом кадре ровно на одну ячейку.

Контролирующая спуск логика находится по адресу $8914.

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;

Таблица кадров на спуск находится под меткой lookupDropSpeed. Как сказано выше, на уровне 29 и выше скорость постоянно равна 1 спуску/кадр.

fallTimer (адрес $0045) запускает спуск, когда достигает dropSpeed ($00AF). Инкремент fallTimer выполняется по адресу $8892 за пределами этого фрагмента кода. При автоматическом или управляемом спуске он сбрасывается на 0.

Переменная autorepeatY ($004E) инициализируется со значением $0A (по адресу $8739), которое интерпретируется как −96. Условие в самом начале вызывает начальную задержку. Самое первое тетримино остаётся подверженной в воздухе в точке создания, пока autorepeatY не увеличится до 0, что занимает 1,6 секунды. Однако при нажатии «Вниз» в этой фазе autorepeatY мгновенно присваивается 0. Интересно, что можно сдвигать и вращать фигуру в этой фазе начальной задержки, не отменяя её.

Инкремент autorepeatY выполняется при 

© Habrahabr.ru