Хабрахабр

[Перевод] Как я научил ИИ играть в Tetris для NES. Часть 2: ИИ

image

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

Алгоритм

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Параметр

Вес

Общее количество очищенных рядов

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 на самом деле вредит способности справляться с равномерно распределёнными случайными фигурами.

Игровое поле представляет собой схему из 10 строк случайных мусорных блоков, и при каждой очистке строки снизу появляется новая строка мусора, восстанавливая высоту кучи. В альтернативном методе, на который меня вдохновила игра B-Type, управляющей PSO метрикой является частота очистки рядов. А чтобы избавляться от мусора, он должен делать это ещё быстрее. Так как игровое поле имеет ширину 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 — результат влияния стенок; только 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 ограничивают вазаимодействия в вершине кучи при её плотной упаковке.

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

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

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

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

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

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

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

Однако константы, полученные при долгих партиях, можно использовать для оптимизации функции аппроксимации, создающей возможные значения констант при коротких партиях. В противоположность тому, что предпололожил Фэй, константы в линейном и экспоненциальном приближениях требуют очень большого размера выборки, чтобы R2 приблизилось к 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 означает неназначенное значение. Оно используется для пустых ячеек игрового поля.

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

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

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

Поворот тетримино (второй индекс в обеих таблицах ориентаций) используется в объектах 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;
}

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

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

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

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

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

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

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

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

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

Для удаления строки код пользуется тем фактом, что в Java двухмерные массивы по сути являются массивами массивов; он просто сдвигает вниз ссылки на строки. Когда слушатель получает изменённое игровое поле, он вызывает PlayfieldUtil.clearRows для удаления заполненных рядов; метод распознаёт их, сверяясь со значением в дополнительном элементе массива. Перед выполнением сдвига индекс очищаемой строки сохраняется в дополнительный элемент строки. 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 в цепочке.

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

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

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.

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

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). Когда вся строка за исключением столбца-колодца полностью заполнена, ИИ переходит следующей строке. Поскольку она работает построчно, то отклоняет дочерние состояния, которые добавляют квадрат в самый правый столбец. Кроме того, отслеживается высота кучи; если она становится слишком большой, то WellFilter перестаёт влиять на ИИ. Когда готово 4 или больше таких строк, он позволяет «палке» упасть в колодец и получить Tetris.

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

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

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

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

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

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

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 используется целочисленная константа, но принцип тот же.

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

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

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

Дополнение

TETRIS

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

  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 кадр на спуск.

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

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

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

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

Мягкий спуск

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

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

Алгоритм ИИ

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

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

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

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

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

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

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

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

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

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

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

Если они одолевали плато 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.

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

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

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

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

probability density

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

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

histogram

Если игнорировать колебания, то примерно до 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
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть