Первая часть (анализ кода) находится здесь: https://habr.com/post/420725/.

Алгоритм

Описание

Алгоритм непрерывно выполняет следующие шаги:

1. Ждёт, пока не создастся новое тетримино.
2. Проверяет тип нового созданного тетримино, тип следующего тетримино (фигура в поле предпросмотра) и содержимое игрового поля.
3. Исследует все возможные способы добавления двух тетримино на игровое поле и оценивает каждую вероятность.
4. Перемещает новое созданное тетримино, чтобы оно совпадало с местом наилучшенней обнаруженной вероятности.

Каждый из этих этапов подробно описан ниже.

Поиск блокировки

Рассмотрим упрощённую версию Tetris, в которой фигуры не падают автоматически. Единственный способ спустить фигуру вниз — это мягкий спуск. Убрав из игры тайминги, мы можем полностью описать состояние активного тетримино его позицией и ориентацией. Фигура имеет известное место изначального создания, а для преобразования из одного состояния в другое используются следующие операции:

• Перемещение на один шаг вниз
• Перемещение на один шаг влево
• Перемещение на один шаг вправо
• Поворот на один шаг против часовой стрелки
• Поворот на один шаг по часовой стрелке

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

Множество заблокированных состояний с минимальной последовательностью создающих их операций можно найти с помощью поиска в ширину (breadth-first search, BFS). Как сказано ниже, для хранения промежуточных результатов он использует очередь.

1. Заносим в очередь состояние при создании.
2. Выводим из очереди состояние.
3. Получаем последующие состояния, применяя операции преобразования.
4. Если среди них нет перемещения вниз, то выведенное из очереди состояние является заблокированным.
5. Заносим в очередь последующие состояния, которые мы ещё не посетили.
6. Если очередь не пуста, повторяем с шага 2.

Программа представляет каждое состояние в виде объекта со следующими полями:

{ x, y, rotation, visited, predecessor }

В процессе подготовки программа создаёт трёхмерный массив объектов состояний (20 строк ? 10 столбцов ? 4 поворотов), инициализируя соответствующим образом x, y и rotation.

Поле visited помечается, когда состояние занесено в очередь. В BFS это допустимо, потому что каждое последующее состояние увеличивает общую длину пути на 1. То есть увеличением длины пути невозможно создать последующее состояние, которое нужно вставить куда-то, кроме конца очереди для сохранения порядка.

Поле predecessor указывает на объект состояния, из которого происходит текущее состояние. Оно задано, когда состояние занесено в очередь. Состояние создания не имеет предшествующих состояний.

Множество блокированных состояний, обнаруженное во время поиска, определяется типом тетримино и заполненными блоками на игровом поле. Последовательность сгенерировавших их ходов можно выяснить (в обратном порядке), переходя по ссылкам predecessor к состоянию создания. Когда константе PLAY_FAST в начале программы присваивается значение true, она полностью пропускает предшествующие состояния, напрямую кладя тетримино на поле и блокируя его.

Трёхмерный массив объектов состояний, очередь и BFS упакованы в класс. У него есть метод поиска, получающий игровое поле (двухмерный массив), тип тетримино и слушателя. Каждый раз, когда обнаруживается блокированное состояние, игровое поле обновляется, добавляя тетримино в соответствующее место. Затем изменённое игровое поле вместе с информацией об изменениях передаётся слушателю для обработки. После того, как слушатель выполнит возврат, игровое поле восстанавливается.

Слушатель используется для объединения нескольких операций поиска в цепочку, что даёт возможность нахождения всех возможных способов добавления двух (или более) тетримино на игровое поле. Первый поисковик в цепочке выполняет BFS только один раз. Однако второй поисковик выполняет BFS каждый раз, когда первый поиск обнаруживает заблокированное состояние. И так далее, если в цепочке присутствуют и другие поисковики.

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

Оценочная функция

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

• Общее количество очищенных рядов: это общее количество рядов, которые будут очищены вследствие добавления двух тетримино.
• Общая высота блокировки: высота блокировки — это высота над полом игрового поля, на которой блокируется фигура. Это вертикальное расстояние, на которое бы упала заблокированная фигура, если убрать все остальные занятые квадраты игрового поля и сохранить ориентацию фигуры. Общая высота блокировки — это сумма высот блокировки двух тетримино.
• Общее количество ячеек-«колодцев»: ячейка-колодец — это пустая ячейка, расположенная над всеми занятыми ячейками в столбце так, что её левый и правый сосед являются занятыми ячейками; при определении колодцев стенки игрового поля считаются занятыми ячейками. Идея заключается в том, что колодец — это структура, открытая сверху, закрытая снизу и окружённая стенами с обеих сторон. Вероятность прерывающихся пробелов в стенках колодца означает, что ячейки-колодцы не обязательно возникают в непрерывной куче в пределах столбца.
• Общее количество отверстий в столбцах: отверстие в столбце — это пустая ячейка, расположенная непосредственно под занятой ячейкой. Пол игрового поля не сравнивается с ячейкой над ним. В пустых столбцах отверстий нет.
• Общее количество переходов в столбцах: переход в столбцах — это пустая ячейка, соседствующая с занятой ячейкой (или наоборот) в пределах одного столбца. Сочетание самого верхнего занятого блока столбца с пустым пространством над ним не считается переходом. Аналогичным образом, пол игрового поля тоже не сравнивается с ячейкой над ним. Следовательно, в совершенно пустом столбце нет переходов.
• Общее количество переходов в строках: переход в строках — это пустая ячейка, соседствующая с занятой ячейкой (или наоборот) в пределах одного ряда. Пустые ячейки рядом со стенками игрового поля считаются переходами. Общее количество высчитывается для всех строк игрового поля. Однако совершенно пустые строки не учитываются в общем количестве переходов.

Эль-Аши предположил, что полезные веса можно найти с помощью алгоритма «метод роя частиц» (particle swarm optimization, PSO), который итеративно усовершенствует совокупность вариантов решений имитацией наблюдаемого в природе поведения роя. В нашем случае каждый вариант решения является вектором весов, а приспособленность варианта определяется игрой в Tetris; это общее количество тетримино, на протяжении которых он выживал до конца игры.

Эти идеи применены в описанной ниже версии на Java; она выполняется за пределами FCEUX и её можно настроить для неграфической, расположенной в памяти игры, работающей с гораздо более высокой скоростью. После подготовки PSO я удивился, увидев, что алгоритм не движется дальше после начальной итерации. После этой итерации несколько случайно сгенерированных вариантов решения уже играли достаточно хорошо. В течение нескольких дней размер этого множества снижался, пока не остался только один вариант. Вот значения для этого решения:

Параметр	Вес
Общее количество очищенных рядов	1.000000000000000
Общая высота блокировки	12.885008263218383
Общее количество ячеек-колодцев	15.842707182438396
Общее количество отверстий в столбцах	26.894496507795950
Общее количество переходов в столбцах	27.616914062397015
Общее количество переходов в строках	30.185110719279040

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

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

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

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

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

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

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

Другие параметры

Вот список ещё нескольких параметров, с которыми я экспериментировал в процессе разработки ИИ:

• Высота кучи: занятые блоки могут нависать над пустыми ячейками, создавая выступы и отверстия; однако зафиксировать занятые блоки над совершенно пустыми строками невозможно. Следовательно, высота кучи — это количество строк, в которых содержится хотя бы один занятый блок.
• Общее количество занятых столбцов: это количество столбцов, в которых содержится хотя бы одна занятая ячейка.
• Общее количество занятых ячеек: количество занятых ячеек на игровом поле.
• Общее количество соединённых областей: здесь применяется алгоритм заливки для подсчёта количества непрерывно связанных областей. Кроме нахождения занятых «островов», он обнаруживает отверстия, растянувшиеся по обеим осям.
• Дисперсия высоты столбцов: это статистическая мера величины разброса высот столбцов. Является показателем неровности поверхности.
• Общая величина адаптации: вычисление величины адаптации кучи под следующую неизвестную фигуру. Она подсчитывает общее количество способов, которыми 7 типов фигур можно добавить на игровое поле без появления новых отверстий. Для точного подсчёта потребуется многократное применение BFS. Но для приближенного подсчёта дерево поиска можно сильно усечь.
• Средняя оценка следующей фигуры: этот параметр углубляет поиск благодаря анализу всех возможностей для следующей неизвестной фигуры. Он использует другие парамтеры для отдельного расположения каждого типа фигур, а затем возвращает среднее для 7 оценок. Для каждого размещения фигуры требуется выполнение BFS.
• Усреднённая симулируемая игра: параметр симулирует серию партий в Tetris, подбирая фигуры с помощью собственного генератора псевдослучайных чисел и применяя для работы с ними ИИ. В конце каждой партии игровое поле оценивается с помощью других параметров. Возвращается усреднённое значение для всех партий.

Все параметры можно настраивать, если добавить настраиваемые факторы. Например, вместо простого подсчёта очищенных рядов можно назначить собственные веса для Single, Double, Triple и Tetris, сымитировав систему очков. Если одновременная очистка нескольких рядов вредит долговременной цели выживания, то одиночным рядам можно назначить отрицательный вес, а другие могут получить положительные.

Ещё одним полезным фактором является значение смещения. Например, совершенно плоская поверхность кучи имеет дисперсию высот столбцов 0. Но идеально плоская поверхность не адаптируется под S и Z, а также другие сочетания фигур. Следовательно, с помощью вычитания константы дисперсию необходимо центрировать около оптимальной неровности.

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

Многие из параметров дают понимание того, насколько хорошо куча сможет управляться с дополнительными фигурами, например, те, которые имеют дело с неровностью поверхности, но «Общая величина адаптации», «Средняя оценка следующей фигуры» и «Усреднённая симулируемая игра» оценивают изменённое игровое поле вставкой фигур, не входящих в две известные. При исследовании последующих фигур из-за быстрого устранения рядов количество полученного дополнительного знания уменьшается с глубиной. Это значит, что давно прошедшее течение партии не так важно, и течение партии в далёком будущем тоже не очень важно. На самом деле, если короткая последовательность фигур случайным образом поставлена неправильно, то ИИ быстро восстанавливает ход игры, используя несколько следующих фигур для очистки затронутых рядов. Определение оптимальной величины анализа последующих фигур требует дальнейших исследований.

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

Обучение ИИ

Существуют патологические последовательности, которые способны привести к Game Over вне зависимости от стратегии. Простейший пример — это бесконечная последовательность тетримино S и Z, которая, как показано в анимации, быстро приводит ИИ к проигрышу.


Поскольку для прогона варианта ИИ до завершения нескольких партий и вычисления среднего нужны дни, совершенно непрактично использовать как метрику управления PSO среднюю длительность партии. Вместо этого можно с контролируемой скоростью увеличивать сложность игры, повышая частоту S и Z, что со временем приведёт к попеременному созданию только этой пары фигур.

Я попробовал использовать этот метод обучения, но обнаружил, что обучение ИИ работе с частыми S и Z на самом деле вредит способности справляться с равномерно распределёнными случайными фигурами.

В альтернативном методе, на который меня вдохновила игра B-Type, управляющей PSO метрикой является частота очистки рядов. Игровое поле представляет собой схему из 10 строк случайных мусорных блоков, и при каждой очистке строки снизу появляется новая строка мусора, восстанавливая высоту кучи. Так как игровое поле имеет ширину 10 столбцов, а каждое тетримино состоит из 4 квадратов, то в среднем AI должен очищать ряд через каждые 2,5 тетримино. А чтобы избавляться от мусора, он должен делать это ещё быстрее.

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

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

Ниже показана тепловая карта множества пробных партий, в сумме содержащих 2 039 900 000 тетримино. Каждая ячейка раскрашена на основании процента заблокированных в ней фигур. Для усиления визуального контраста выбрана нелинейная палитра. Карта была создана нормализацией значений ячеек с помощью деления на максимальный процент ячеек, а затем возвещением в степень 0,19 (см. «гамма-коррекция»).

Цвет Процент ¦ 0.00000000 ¦ 0.00000315 ¦ 0.00024227 ¦ 0.00307038 ¦ 0.01860818 ¦ 0.07527774 ¦ 0.23582574 ¦ 0.61928352 ¦ 1.42923040 ¦ 2.98867416 ¦ 5.78182519

Тёмно-оранжевая и красная полоса в строках 17 и 18 означает, что подавляющее большинство фигур в результате оказываются там. Бледно-зелёный оттенок снизу — следствие геометрии фигур: только 4 из 7 типов тетримино могут оказаться в нижней строке. Нижние углы чёрные, потому что там невозможно оказаться.

Цвет вдоль каждой строки практически однороден, и это позволяет предположить, что горизонтально фигуры распределяются равномерно. Незначительные разрывы можно объяснить, посмотрев на гистограммы отдельных типов фигур:

T

J

Z

O

S

L

I

T оказывается наиболее универсальным типом: его гистограмма более равномерна, чем у всех остальных. Аномалии в гистограмме J — результат влияния стенок; только Jr и Jl могут находиться в боковых столбцах, что заставляет ИИ для компенсации чаще использовать столбцы 1 и 9. То же самое относится и к L. Гистограммы Z и S выглядят примерно одинаковыми, что подчёркивает дисбаланс из-за того, что Zv и Sv не являются идеальными зеркальными отражениями друг друга. Тип O ограничен игровым полем 19?9, и похоже, что ИИ склонен чаще использовать O по бокам, чем в центре. Тетримино I сдвинуто вправо, потому что там расположена его исходная точка; поэтому блокировка в столбце 1 случается редко.

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

Строка	Процент
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

Вот график значений:


Если не учитывать строку 19, то график демонстрирует экспоненциальный рост.

Ниже показан список соотношений количества заблокированых фигур в соседних строках.

СтрокаA/Строка B	Соотношение (%)
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

В строках 16–19 учитываются фигуры, взаимодействующие с полом игрового поля, поэтому их можно отбросить. В строках 0–5 слишком выборка слишком мала, чтобы быть значимой. Оставшиеся соотношения, пары 6/7–14/15, почти идентичны; их среднее значение равно 29.24%. Это значит, что вероятность того, что куча вырастет на одну строку примерно одинакова вне зависимости от высоты кучи. Это вполне логично, потому что правила Tetris ограничивают вазаимодействия в вершине кучи при её плотной упаковке.

Ниже показан график log₁₀ процентов фигур в строках 6–15.


Он близок к идеально прямой линии с близким к 1 коэффициентом детерминации. Формула, выведенная из показанной выше линейной регрессии, даёт нам пересечение с осью Y, предполагающее, что процент фигур в строке 0 приблизительно равен 10^?7.459%. Величина, обратная этому значению, даёт нам статистическое ожидание в 2 877 688 349 тетримино или 1 151 075 340 рядов до конца игры.

Это даёт нам понять, что log₁₀ процента фигур в каждой строке остаётся линейным вплоть до строки 0. Однако когда куча почти достигает потолка игрового поля, свобода перемещения ограничивается до такой степени, что это свойство нарушается. Кроме того, блокировка фигуры в строке 0 не обязательно означает game over; ещё можно спастись, если есть место для создания новых фигур.

Ещё один способ оценки силы ИИ заключается в измерении среднего количества созданных фигур между полными очистками игрового поля. Полную очистку можно получить всего с 5 тетримино. Например, среди прочих возможностей, этого можно добиться выложенными на полу игрового поля пятью фигурами O. В общем случае, поскольку каждое тетримино состоит из 4 квадратов, а ширина игрового поля — 10 квадратов, то количество созданных фигур между полной очисткой должно быть кратным 5 (так как 4?5n = 2?10n).

У моего ИИ среднее количество созданных фигур между полными очистками поля равно 1181 — довольно небольшое число. Поскольку полная очистка аналогична перезапуску игры, полную партию можно рассматривать как чрезвычайно долгую серию перезапусков игры, за которым следует быстрое продвижение к game over. Как и описанная выше последовательность попеременных S-Z, приводящие к завершению игры патологические последовательности обычно очень коротки.

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


Порядок степени в показанной выше формуле определяет скорость убывания и, предположительно, силу ИИ. Согласно этой формуле, примерно 0,4% или около 1 из 253 партий, начинающихся с пустого игрового поля, завершаются полной очисткой через всего 5 тетримино.

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

Версия на Java

О программе

Для разработчиков, незнакомых с Lua, я добавил в zip-файл с исходниками порт ИИ на Java. Классы являются почти построчной трансляцией объектов Lua на основе замыканий.

Пакеты

Код разделён на два пакета:

• tetris.ai содержит классы и интерфейсы ИИ.
• tetris.gui создаёт графическую модель игрового поля.

Классы и интерфейсы ИИ

Класс с соответствующим названием Tetriminos описывает тетримино. Он используется подобное enum и содержит константы для всех типов тетримино:

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;

NONE означает неназначенное значение. Оно используется для пустых ячеек игрового поля.

Также в Tetriminos содержатся две модели таблицы ориентаций. PATTERNS — это 4-мерный массив integer (тип ? поворот ? квадрат ? координаты), содержащий относительные координаты квадратов; строки упорядочены так, что в каждом типе ориентация создания фигуры является первой. ORIENTATIONS — это другая модель, 2-двухмерный массив (тип ? поворот) объектов Orientation. Каждый Orientation содержит координаты квадрата как массив объектов Point. Также в нём есть поля, описывающие интервал разрешённых позиций для соответствующей ориентации.

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

Поворот тетримино (второй индекс в обеих таблицах ориентаций) используется в объектах State, которыми манипулирует BFS.

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

x, y и rotation совместно описывают позицию и ориентацию фигуры. Так как тип тетримино остаётся постоянным с момента создания до блокировки, поле для него необязательно.

Класс Searcher, в котором содержится алгоритм BFS, создаёт при полный набор всех возможных объектов State при создании:

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

Хотя в Java есть богатый Collections API, Searcher содержит собственную реализацию очереди. Класс Queue использует State.next для соединения объектов State в связанный список. Поскольку все объекты State определены предварительно, а каждый State может быть внесёт в очередь не больше одного раза, то очередь может работать на месте, что позволяет отказаться от излишних временных объектов-контейнеров, используемых в общих реализациях очереди.

«Сердцем» BFS является показанный ниже метод search.

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

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

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

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

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

State.visited можно было реализовать как boolean; однако при этом перед поиском потребовалось бы перебирать все объекты State для сброса visited на false. Вместо этого я сделал visited значением int, сравниваемым со счётчиком, увеличивающимся при каждом вызове.

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

Метод search использует возвращаемое addChild значение для определения того, можно ли создать фигуру. Если фигуру создать нельзя, то куча достигла вершины и поиск больше выполнять нельзя; поэтому он возвращает false.

Возвращаемое addChild значение также изучается на предмет возможности спуститься ещё на один шаг. Если этого сделать нельзя, то текущее состояние является позицией блокировки и запускается вызов lockTetrimino. Метод lockTetrimino изменяет игровое поле, вызывает слушателя, а затем восстанавливает игровое поле.

Каждая строка массива playfield содержит 1 дополнительный элемент, в котором хранится количество занятых ячеек в строке. Инкремент элемента выполняется методом lockTetrimino, поскольку он помечает ячейки как занятые.

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

Потом слушатель вызывает PlayfieldUtil.restoreRows для отмены изменений, внесённых в игровое поле. Шаги отменяются в обратном порядке. Сначала получается свободная строка из вершины. Затем из стека извлекается заполненная строка и восстанавливается индекс из дополнительного элемента. Он используется для сдвига ссылок строк и для возврата на место удалённой строки. Наконец, восстанавливается дополнительный элемент, ему присваивается значение ширины игрового поля — количества занятых ячеек в заполненном ряду.

В PlayfieldUtil также имеется метод evaluatePlayfield, который вычисляет и записывает 4 параметра оценки в показанный ниже класс-контейнер.

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

Управляет всем этим класс AI. Он содержит два объекта Searcher, соединённых вместе показанным ниже слушателем.

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

Класс AI может обрабатывать любое количество объектов Searcher, но Nintendo Tetris заранее показывает только одну фигуру. Объекты Searcher хранятся в массиве, а показанный выше код служит в качестве их общего слушателя. Произвольный идентификатор, передаваемый в метод Searcher.search, на самом деле является индексом массива, который также является глубиной поиска. При вызове слушателя идентификатор направляет вызов к следующем Searcher в цепочке. Если он достиг конца массива, то оценивает игровое поле. А когда он находит игровое поле с более высокой оценкой приспособленности, то записывает заблокированное State из первого Searcher в цепочке.

AI содержит метод search, получающий игровое поле и массив, содержащий типы создаваемого и следующего тетримино. Он возвращает State, содержащий позицию и поворот, в которых должно блокироваться первое тетримино. Он никак не ориентируется на второе тетримино; при последующем вызове он заново выполняет вычисление оценки. Если куча слишком высока и цепочке Searcher не удаётся разместить оба тетримино, то AI.search вернёт 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;
}

Вызов ИИ

Поскольку версия на Java не привязана к FCEUX, потенциально её можно использовать для других проектов. Для тех, кому интересно интегрировать ИИ куда-нибудь ещё, в этом разделе описывается всё необходимое.

Во-первых, создадим экземпляр AI, экземпляр PlayfieldUtil и массив для хранения всех известных типов тетримино. Кроме того, создадим вызовом PlayfieldUtil.createPlayfield экземпляр игрового поля; он возвращает двухмерный массив с дополнительным столбцом, который мы рассмотрели выше. Вероятно, вам также понадобится генератор случайных чисел.

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

Изначально игровое поле пусто, а все ячейки имеют значение Tetriminos.NONE. Если вы заполняете ячейки программно, то не забывайте записывать в playfield[rowIndex][AI.PLAYFIELD_WIDTH] количество занятых ячеек в каждой строке.

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

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

Затем передадим игровое поле и массив типов в метод AI.search. Он вернёт State, в котором нужно заблокировать первое тетримино. Если он возвращает null, то неизбежен game over.

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

Если вам нужен путь от создания фигуры до блокировки, то передавайте State методу AI.buildStateList.

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

Для обновления игрового поля передадим его PlayfieldUtil.lockTetrimino вместе с его типом и объектом State. Этот метод автоматически очищает заполненные ряды.

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

Перед повторным вызовом AI.search необходимо случайным образом выбрать следующее тетримино.

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

Вместо вывода игрового поля в текстовом виде можно использовать более интересный способ отображения происходящего…

Отображение игрового поля

Класс TetrisFrame имитирует графику Nintendo Tetris, в том числе особенности поведения, описанные в предыдущей части статьи.


Чтобы увидеть его в действии, запустите tetris.gui.Main. Как и в случае с версией на Lua, мы можем настраивать скорость игры изменением значения константы в начале файла.

public static final boolean PLAY_FAST = true;

TetrisFrame имеет 4 метода для манипулирования экраном. Метод displayTetrimino рендерит активное тетримино в указанных координатах. Он получает параметр задержки, заставляющий метод ждать перед возвратом указанное количество кадров анимации.

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

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

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

updateStatisticsAndNext выполняет инкремент счётчика статистики для нового созданного тетримино и обновляет отображение следующей фигуры.

public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino)

Метод dropTetrimino создаёт фигуру и позволяет ей спускаться под воздействием «гравитации», не предпринимая попыток повернуть или переместить её. Main использует его для двух последних фигур, когда AI.search возвращает null. Если параметр animate имеет значение true, то при невозможности создать фигуру опустится занавес конца игры. Как и в случае со всеми другими методами, этот метод блокируется до завершения анимации. Он возвращает true только тогда, когда может создать фигуру на занятом игровом поле.

public boolean dropTetrimino(int type, boolean animate)

Эти 4 метода должны вызываться рабочим потоком, но сам TetrisFrame должен создаваться в Event Dispatch Thread. Чтобы увидеть, как это делается, см. класс Main.

Ради интереса Main использует класс Randomizer, симулирующий смещённый генератор псевдослучайных чисел из Nintendo Tetris.

Пакет tetris.gui.images содержит связанные с отображением файлы. tiles.png — это таблица паттерна, содержащая всю тайловую графику. background.dat хранит идентификаторы тайлов, из которых состоит фон; данные извлечены из $BF3F. А colors.dat содержит байты, генерирующие необычные цвета квадратов, появляющиеся с уровня 138.

ImageLoader содержит таблицу палитр NES, а в ImagePane хранится полный набор отображаемых значений уровней.

Другие проекты

Потенциально код можно использовать вместо записи для режима демо. На самом деле такое демо можно рендерить вечно, пользуясь тем, насколько быстро способен ИИ очищать всё игровое поле. Чтобы достичь этого, в генераторе псевдослучайных чисел нужно использовать в качестве seed некую произвольную константу, что даст нам детерминированную последовательность тетримино. Будут записаны первые два тетримино последовательности. Когда ИИ достигнет полной очистки поля, следующие два тетримино будут сравниваться с первыми двумя из последовательности. Если они совпадают (это событие ожидается через каждые 49 полных очисток поля), то генератору псевдослучайных чисел можно передать в качестве seed ту же константу, что создаст бесконечный цикл демо. Длительность цикла может быть очень большой, чтобы скрыть сам факт того, что это цикл. Кроме того, демо может начинаться со случайной точки цикла, создавая каждый раз новое демо.

Ещё одна возможность использования ИИ заключается в создании режима «игрок против компьютера». В многопользовательском «Тетрисе» при одновременной очистке нескольких строк в нижней части поля противника появляются мусорные строки, поднимающие игровое поле. ИИ должен быть способен защищаться от мусора по той же причине, по которой он может играть в игры режима B-Type. Однако, как сказано раньше, ИИ играет консервативно, обычно стремясь очищать за раз по одной строке. То есть он сможет защищаться от нападений, но не способен атаковать. Чтобы иметь возможность изменения его поведения, я создал интерфейс под названием IChildFilter.

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

AI имеет альтетнативный конструктор, получающий реализацию IChildFilter. При наличии IChildFilter.validate он служит в качестве дополнительной проверки разрешённости дочернего состояния; если он возвращает false, то дочернее состояние не заносится в очередь.

WellFilter — это реализация IChildFilter, нацеленная на собирание четырёх рядов (Tetris). Подобно живым игрокам, она постепенно строит колодец в самом правом столбце игрового поля, построчно поднимаясь снизу вверх. Поскольку она работает построчно, то отклоняет дочерние состояния, которые добавляют квадрат в самый правый столбец. Когда вся строка за исключением столбца-колодца полностью заполнена, ИИ переходит следующей строке. Когда готово 4 или больше таких строк, он позволяет «палке» упасть в колодец и получить Tetris. Кроме того, отслеживается высота кучи; если она становится слишком большой, то WellFilter перестаёт влиять на ИИ.


Чтобы проверить его в работе, внесите в Main следующие изменения:

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

WellFilter работает, но не особо эффективно. Он содержит простую эвристику, предназначенную для демонстрации концепции. Чтобы получать Tetris чаще, нужно использовать более изощрённую стратегию, возможно такую, которую можно оптимизировать с помощью PSO.

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


PatternFilter строит изображения построчно снизу вверх, аналогично тому, как работает WellFilter; однако вместо оберегания самого правого столбца PatternFilter одобряет только дочерние состояния, соответствующие определённому паттерну.

Конструктор PatternFilter получает имя одного из изображений в пакете tetris.gui.patterns, которое использует в качестве шаблона. В каждом изображении размером 20?10 содержатся чёрные и белые пиксели, соответствующие ячейкам игрового поля.

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

Показанная выше строка кода создаёт силуэты семи типов тетримино.


Ещё один пример с большим тетримино T, повёрнутым под углом.


Ещё один пример. Если приглядеться, то вы увидите название игры.


Как и WellFilter, PatternFilter является ничем иным, как proof of concept. Обрабатываемые им паттерны ограничены нижней частью игрового поля из-за того, что попытки их получения обычно заканчиваются game over. Тем не менее, это интересная идея, стоящая дальнейшего изучения.

Версия с геймпадом

Скрипт на Lua и программа на Java игнорируют гравитацию; для них скорость спуска не важна, потому что в зависимости от конфигурации они или телепортируют фигуры сразу на нужное место, или перетаскивают вдоль любого выбранного пути. В каком-то смысле они просто имитируют Tetris, а не играют в него. Однако в zip-файле с исходниками есть другой скрипт на Lua, который играет с помощью генерации сигналов кнопок геймпада, что позволяет игре управлять перемещением фигур, гравитацией и всем остальным.

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

• Фигуры обновляются на уровнях в следующем порядке: сдвиг, поворот и спуск.
• При зажатии «Вниз» сдвиг выполнять нельзя.
• При зажатии «Влево» или «Вправо» невозможно выполнить мягкий спуск.
• Можно выполнить сдвиг и поворот в пределах одного кадра.
• Можно выполнить поворот и мягкий спуск в пределах одного кадра.
• Можно выполнить сдвиг и автоматический спуск в пределах одного кадра.
• Можно выполнить поворот и автоматический сдвиг в пределах одного кадра.
• Можно выполнить сдвиг, поворот и автоматический спуск в пределах одного кадра.
• При нажатии A или B перед следующим нажатием их необходимо отпустить хотя бы на один кадр.
• Нажатие «Влево» или «Вправо» заставляет игру автоматически выполнять сдвиг каждые 6 кадров после начальной задержки в 16 кадров. Можно нажимать и отпускать «Влево» или «Вправо» в каждом кадре, чтобы заставить фигуры двигаться быстрее.
• Удерживание «Вниз» запускает мягкий спуск в каждом втором кадре с первоначальной задержкой в 3 кадра.
• Первая создаваемая фигура имеет задержку в 96 кадров. Мягкий спуск отменяет её, сдвиг и повороты — нет.

Чтобы приспособить все эти правила, в состояния поиска необходимо встроить историческую информацию. Им необходимы поля, в которых будет храниться количество кадров удерживания каждой кнопки и количество кадров после последнего автоматического спуска. Каждое уникальное множество значений, в том числе координаты x, y и поворот тетримино характеризуют отдельное и уникальное состояние. К сожалению, количество возможностей столь обширно, что полный поиск по этому пространству непрактичен. Версия ИИ для геймпада исследует только его подмножество.

ИИ использует объект State со следующими полями:

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

Вместо использования автоматического сдвига ИИ в попеременных кадрах нажимает и отпускает кнопку сдвига. Следовательно, ему нужно следить только затем, нажата ли кнопка, а не как долго она нажимается. Поскольку автоматического поворота нет, та же идея относится и к кнопкам A и B. Следовательно поля Left, Right, A и B можно интерпретировать как перечисления, содержащие одно из следующих значений:

{ RELEASED, PRESSED }

С другой стороны, для мягкого спуска нужно первоначально зажать на три кадра кнопку «Вниз», что требует существования 4 состояний:

{ RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Down инкрементно увеличивается со значения RELEASED до PRESSED_FOR_3_FRAMES, при котором происходит мягкий спуск. После этого он может получать значение RELEASED или возвращаться к PRESSED_FOR_2_FRAMES, вызывая мягкий спуск каждом втором кадре после первоначальной задержки. Он не может быть RELEASED из PRESSED_FOR_1_FRAME или из PRESSED_FOR_2_FRAMES.

На самом деле в коде на Lua используется целочисленная константа, но принцип тот же.

Аналогично visited и predecessor, fallTimer является назначенным значением, получаемым при занесении в очередь дочернего состояния; его fallTimer будет на единицу больше значения родительского состояния. Состояние, содержащее fallTimer, равное скорости спуска, подразумевает, что в этом кадре происходит автоматический спуск, а у последующих состояний этого состояния значение fallTimer будет равно 0.

Каждый Searcher предварительно определяет 8-мерный массив, содержащий все возможные состояния (20 строк ? 10 столбцов ? 4 поворотов ? 2 Влево ? 2 Вправо ? 4 Вниз ? 2 A ? 2 B), а BFS выполняется аналогично методу, показанному для трёхмерного массива. В показанном ниже псевдокоде описано, как из выведенных из очереди состояний получаются последующие состояния.

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

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

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

Как и в предыдущей версии, AI.search возвращает цепочку объектов State. Но в этом случае каждый State содержит множество кнопок, которые нужно нажать в каждом кадре. Поля x, y и rotation не используются для манипулирования фигурами, но их можно использовать для проверки правильности перемещения фигур.

Хотя пространство поиска значительно уменьшено благодаря описанным выше ограничениям, для выполнения поиска всё равно требуется 1–3 секунды. Если запустить его, то вы заметите паузу после создания каждого тетримино. Кроме того, движения выглядят очень неестественно; обычно поворот выполняется за мгновение до блокировки. Тем не менее, этот ИИ играет почти так же, как игнорировавшая гравитацию версия, даже на максимальной скорости.

Чтобы проверить его, запустите lua/NintendoTetrisAIGamepadVersion.lua, находящийся в zip-файле с исходниками.

Более простой способ учёта гравитации заключается в ограничении движения фигур только поворотом, за которым следует сдвиг, а затем спуск до самого дна. Идея заключается в том, что если избавиться от скольжения и прокручивания, то вертикальная скорость движения фигур будет мало влиять на ИИ; всё, что ему будет нужно — доставить фигуру в нужный столбец, а остальным займётся гравитация. Ещё одно преимущество этой техники в том, что пространство поиска очень мало, что позволяет играть в реальном времени, без задержке для вычислений. Однако недостаток такого подхода в том, что без скольжений и прокручивания ИИ играет гораздо хуже. Тем не менее, ИИ «Тетриса», неспособный играть в реальном времени, практически бесполезен.

Дополнение

Ранее я написал плагин, процедурно имитировавший игрока в «Тетрисе». Однако мой проект обладал некоторыми недостатками:

1. Бот отключал гравитацию, позволяя выполнять скольжения и прокручивания, превосходящие возможности игрока на самом минимальном уровне Nintendo Tetris. Он никогда не поднимает фигуры вниз, но единственным способом спуска фигур вниз является контролируемый мягкий спуск. То есть он играет в теоретическом, идеализированном мире. Если сказать грубее, то он жульничает.
2. Бот избегает риска. Его основная цель — долговременное выживание, а не набор максимального количества очков. Он опасается приносящих очки Double, Triple и Tetris, потому что они связаны с увеличением кучи фигур — ненужным риском, увеличивающим вероятность переполнения поля. Поэтому максимальное количество очков не набирается до уровня 90. Но в реальной игре, где существует гравитация, большинство игроков не может победить уровень 29 или выше из-за чрезвычайно высокой скорости спуска фигур.
3. Аналитические способности бота основаны на взвешенной сумме различных воздействующих факторов. Но веса были выбраны случайным образом. Он играет хорошо только по стечению обстоятельств. Это ещё одно свидетельство того, что Tetris без гравитации почти не представляет сложности.

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

---

Видео

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

---

Скачивание

TetrisAI_2018-01-28.zip

В файле .zip содержится:

• src — дерево исходного кода.
• TetrisAI.jar — скомпилированный двоичный файл.
• lgpl-2.1.txt — лицензия свободного ПО.

---

Запуск

Предварительные требования

• Nintaco — эмулятор NES / Famicom.
• Tetris (U) [!].nes — ROM-файл Nintendo Tetris.

Запуск плагина

1. Запустите Nintaco и откройте Tetris (U) [!].nes.
2. Извлеките TetrisAI.jar из скачанного .zip.
3. Откройте окно Run Program, выбрав Tools | Run Program...
4. Введите путь к файлу в поле имени JAR или перейдите к файлу с помощью кнопки Find JAR… .
5. Нажмите Load JAR, чтобы загрузить его.
6. Нажмите Run.
7. Плагин автоматически пропустит экраны юридической информации и заставки, перенеся вас непосредственно к экрану меню GAME TYPE и MUSIC TYPE. С помощью D-pad (стрелки клавиатуры в раскладке по умолчанию) выберите A-TYPE и любую музыку. Затем нажмите Start (Enter), чтобы перейти к следующему экрану меню.
8. На экране меню A-TYPE воспользуйтесь D-pad (клавишами со стрелками) и выберите LEVEL 9. Наконец, зажмите кнопку геймпада A и нажмите на Start (удерживайте клавишу клавиатуры X и нажмите Enter), чтобы начать с уровня 19, и передайте управление боту.

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

Задание скорости

Чтобы игра шла быстрее, выберите Machine | Speed | Max.

---

Подробности

Плато

Ниже уровня 10 скорость спуска на каждом уровне слегка выше, чем на предыдущем. Но на уровне 10 и выше есть несколько плато, на которых в течение нескольких уровней скорость остаётся постоянной. Это следствие способа работы механизма спуска. Скорость представлена в виде количества кадров на спуск, что является целочисленным значением. То есть для более высоких уровней остаётся не так много вариантов: 10–12, 13–15, 16–18, 19–28 и 29+ это 5, 4, 3, 2 и 1 кадр на спуск.

Бот разрабатывался с учётом только плато 19–28. В чётных кадрах он нажимает на геймпаде «Влево», «Вправо», A, B или ничего. А в нечётных кадрах он позволяет осуществлять автоматический спуск, не нажимая никаких кнопок. Похоже, что игра не воспринимает горизонтальное движение, совпадающее с поворотом; поэтому каждая кнопка нажимается независимо в чётных кадрах.

В отличие от мастеров, играющих на больших уровнях, бот не пользуется преимуществом отложенного автосдвига (Delayed Auto Shift, DAS), известного так же как «автоповтор», и связанные с ним техники. Его работа больше напоминает технику вибрирующего большого пальца Тора Акерлунда. Однако он увеличивает частоту вибрации до теоретического максимума, допускаемого игрой.

Игроков вознаграждают 40, 100, 300 и 1200 очками за Single, Double, Triple и Tetris. А значения очков умножаются на номер уровня плюс 1. Другими словами, для получения максимального счёта игрок должен стремиться к максимальному количеству Tetris, как можно дольше играя на высоких уровнях.

Уровень 19 является наибольшим, который можно выбрать в качестве начального, что позволяет боту перепрыгнуть сразу к плато 19–28. Однако из за бага в механизме подсчёта уровней, о котором я говорил в предыдущей части, игра перейдёт на уровень 20 после очистки 140 рядов, вместо ожидаемых 200. После этого игра будет менять уровни каждые 10 рядов. Однако после достижения 230 рядов бот поднимется с плато и быстро сдастся. То есть ему нужно набрать как можно больше Tetris до очистки 230 рядов.

Мягкий спуск

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

Мягкий спуск оказывает незначительное влияние на общий счёт. Тем не менее, при возможности бот завершает размещение фигуры, нажимая «Вниз» для получения этих очков. В редких случаях он может усреднять разность между очень высоким счётом и превышением максимального значения очков.

Алгоритм ИИ

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

Размещение фигуры на игровом поле имеет последствия: 4 пустые ячейки становятся занятыми, а все заполненные ряды очищаются, спуская строки вниз. Для каждого допустимого размещения текущей фигуры и связанных с ним последствий бот проверяет каждое допустимое размещение следующей фигуры, оценивая комбинацию последствий. Такая цепочка поисков представлена SearchChain.

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

Оценочная функция

Оценочная функция — это взвешенная сумма следующих параметров:

• Общее количество очищенных рядов – количество рядов, очищенных вследствие добавления обоих тетримино.
• Общая высота блокировки – сумма высот над полом игрового поля, где заблокировано тетримино. Высота блокировки отдельной фигуры — это вертикальное расстояние, на которое она может упасть при сохранении ориентации, если удалить все занятые квадраты игрового поля.
• Общее количество ячеек-колодцев – количество ячеек внутри колодцев.
• Общее количество глубоких колодцев – количество колодцев, содержащих три или более ячеек-колодцев.
• Общее количество отверстий в столбцах – количество пустых ячеек, непосредственно над которыми есть занятые ячейки. Пол игрового поля не сравнивается с ячейкой над ним. Пустые столбцы не содержат отверстий.
• Общее взвешенное количество отверстий в столбцах – сумма индексов строк отверстий в столбцах. В этом случае строки индексируются сверху вниз, начиная с 1. Идея в том, чтобы расположенным ниже в куче отверстиям давать больший штраф, потому что для заполнения верхних отверстий требуется очистить меньшее количество строк.
• Общее количество глубин отверстий в столбцах – сумма вертикальных расстояний между каждым отверстием и вершиной столбца, в котором оно находится. Вершина — это самая верхняя занятая ячейка в пределах столбца, а глубина отверстия — это разность между индексом строки отверстия и индексом строки вершины.
• Минимальная глубина отверстий в столбцах – наименьшая глубина отверстий в столбцах. Если отверстий нет, то по умолчанию параметр имеет значение высоты поля (20).
• Максимальная глубина отверстий в столбцах – наибольшая глубина отверстий в столбцах. Если отверстий нет, то значение по умолчанию равно 0.
• Общее количество переходов в столбцах – количество пустых ячеек, соседних с занятой ячейкой (или наоборот) в пределах одного столбца.
• Общее количество переходов в строках: переход в строках — это пустая ячейка, соседствующая с занятой ячейкой (или наоборот) в пределах одного ряда. Пустые ячейки рядом со стенками игрового поля считаются переходами. Общее количество высчитывается для всех строк игрового поля. Однако совершенно пустые строки не учитываются в общем количестве переходов.
• Общее количество высот столбцов – сумма вертикальных расстояний между вершиной каждого столбца и полом игрового поля. Столбец, содержащий всего 1 занятую ячейку, имеет высоту 1, а полностью пустой столбец — высоту 0.
• Высота кучи – высота наибольшего столбца.
• Разброс высот столбцов – разность высот между самым высоким и самым низким столбцами.
• Общее количество занятых ячеек – количество занятых ячеек на игровом поле.
• Общее взвешенное количество занятых ячеек – сумма высот всех занятых ячеек. Строка над полом имеет высоту.
• Дисперсия высот столбцов – сумма абсолютных разностей между высотами всех соседних столбцов.

Машинное обучение

Для нахождения весов оценочной функции использовался вариант метода роя частиц (Particle Swarm Optimization, PSO), описанный в сноске [1]. Для получения хорошего сходящегося поведения применены предложенные коэффициенты инерции и ускорения. А максимальные размеры шагов частиц определены ограничением их величин скоростей.

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

Каждый вектор позиции частицы оценивался симуляцией выполнения 100 партий на плато уровней 19–28. Полная партия подразумевает очистку 230 рядов, но многие завершались переполнением поля. Оценки партий сортировались, и оценка частиц определялась как среднее для 33 из 100 партий. Идея заключалась в выборе на основе агрессивности. Частицы в верхней трети привыкают только к желательным последовательностям фигур, что ограничивает необходимость консервативной игры. В результате они стремятся подталкивать обычную игру к грани, дожидаясь следующей «палки».

Последовательности фигур для 100 партий были сгенерированы до выполнения PSO, и одни и те же последовательности использовались снова и снова. Это было необходимо для фиксации пространства поиска, для того, чтобы варианты решения можно было сравнивать друг с другом. Последовательности создавались с помощью логики настоящего PRNG Nintendo Tetris, который предназначен для снижения шансов идущих друг за другом дубликатов. Но у PRNG тоже есть слабые места (см. раздел «Выбор тетримино» из предыдущей статьи): он не подбирает фигуры равномерно.

Первоначальные попытки давали ботов, действующих слишком агрессивно. Если они одолевали плато 19–28, то обычно добирались до максимального счёта. Но, к сожалению, они часто слишком рано приводили к переполнению поля. В ответ на это для «успокоения» ботов было сделано четыре шага:

1. Им приказали быть жадными: если текущая или следующая фигура может дать Tetris, то сделать его. До этой директивы боты использовали «палки» для дальнейшего роста идеально чистой кучи с очень глубоким колодцем. Жадное поведение потенциально может заменять долговременное выживание на кратковременные преимущества. Но ботам необязательно выживать бесконечно; им достаточно дойти до 230 рядов. Эксперименты показали, что получение при возможности комбинаций Tetris облегчает эту задачу. Однако то же самое нельзя сказать о Single, Double или Triple. Жадное стремление к ним приводило к созданию слишком консервативных ботов; они достигали конца плато со слишком низким счётом.
2. Им приказали не ставить блоки близко к потолку игрового поля. В оценочную функцию был добавлен штраф, применяемый к ячейкам, занятым в любой из верхних 7 строк. Штраф обратно пропорционален вертикальному расстоянию между блоком и потолком.
3. Ботам приказано, что когда они вынуждены ставить блок рядом с потолком поля, то нужно хотя бы делать это не в точке создания фигуры. В текущем состоянии цепочка поиска отклоняет комбинации размещения, которые могут помешать созданию любого из 7 тетримино.
4. Им было приказано при размещении подпирающего потолок блока делать так, чтобы он не разделял игровое поле, что делало бы невозможным дальнейшее развитие. Если цепочка поиска обнаруживает контакт с потолком, она выполняет заливку из точки создания фигур. И если заливка не может полностью заполнить всю строку, то цепочка поиска отклоняет комбинацию размещения.

После применения всех этих правил «успокоения» ботов, метод PSO дал следующие веса:

Параметр	Вес
Общее количество очищенных рядов	0.286127095297893900
Общая высота блокировки	1.701233676909959200
Общее количество ячеек-колодцев	0.711304230768307700
Общее количество глубоких колодцев	0.910665415998680400
Общее количество отверстий в столбцах	1.879338064244357000
Общее взвешенное количество отверстий в столбцах	2.168463848297177000
Общее количество глубин отверстий в столбцах	?0.265587111961757270
Минимальная глубина отверстий в столбцах	0.289886584949610500
Максимальная глубина отверстий в столбцах	0.362361055261181730
Общее количество переходов в столбцах	?0.028668795795469625
Общее количество переходов в строках	0.874179981113233100
Общее количество высот столбцов	?0.507409683144361900
Высота кучи	?2.148676202831281000
Разброс высот столбцов	?1.187558540281141700
Общее количество занятых ячеек	?2.645656132241128000
Общее взвешенное количество занятых ячеек	0.242043416268706620
Дисперсия высот столбцов	0.287838126164431440

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

Сила ИИ

Для оценки силы ИИ было собрано примерно 1,7 миллионов результатов (в очках) симулированных партий на плато 19–28. Оценка не отражает игру на уровне 29 или выше, и не учитывает очки, полученные от мягкого спуска. Однако в неё включены игры, преждевременно завершённые из-за переполнения поля. Для генерирования последовательностей тетримино использовалась логика PRNG Nintendo Tetris.

Среди этих результатов наибольшим счётом является 1 313 600. Минимальным — 0.

Среднее значение равно 816 379, и кажется, что это мало. Но как сказано ниже, данные искажены, поэтому лучшее представление о типичном значении даёт медианная оценка — 989 200 очков.

Как сказано выше, PSO оптимизировал веса на основании среднего значения из лучшей трети партий. В этом случае средний счёт лучшей трети равен 1 108 860. На самом деле средний счёт лучших 75% равен 1 000 000.

Бот имеет вероятность в 47% достичь предела очков до уровня 29. Он имеет вероятность в 61% получения 900 000 очков до уровня 29. На показанном ниже графике изображены вероятности набора очков до уровня 29.


Похоже, что вероятность линейно снижается примерно до 900 000 очков. Затем она переходит в перевёрнутую сигмоидную кривую.

Ниже показана сглаженная гистограмма с количеством партий для каждого из набранных величин очков. Её форма определяется производной показанного выше графика.


Если игнорировать колебания, то примерно до 900 000 она плоская, а затем переходит в нормальное распределение с центром примерно возле 1 050 000 очков. Причины колебаний непонятны. Похоже, что количество очков предпочитает прыгать с шагом, кратным 20 000 очков. Возможно, это связано с циклом построения кучи и получения Tetris.

Распределение ОЗУ и ПЗУ

Для манипуляций с памятью ЦП, передачи нажатий кнопок и получения событий рендеринга кадров плагин использует Nintaco API. Все адреса памяти обнаружены с помощью инструментов отладки Nintaco, а информация добавлена на Data Crystal ROMhacking.net wiki. В исходном коде они выглядят как константы в интерфейсе Addresses.

---

Справочные материалы

1. van den Bergh, F.; Engelbrecht, A.P. (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf