Как сделать тетрис на java

Тетрис на JavaScript

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

В чём идея

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

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

Если вдруг не зна­е­те, как это рабо­та­ет, вот фраг­мент с чем­пи­о­на­та мира по тетрису:

Код не мой

Код, кото­рый мы раз­би­ра­ем в этом про­ек­те, напи­сал аме­ри­кан­ский раз­ра­бот­чик Сти­вен Ламберт:

В этой ста­тье мы объ­яс­ним, как этот код работает.

Неожиданная сложность

Самое глав­ное при про­грам­ми­ро­ва­нии такой игры — это как-то хра­нить содер­жи­мое игро­во­го экра­на и учи­ты­вать дви­же­ние фигур.

Если бы мы писа­ли эту игру на Unreal Engine или Unity, пер­вым инту­и­тив­ным реше­ни­ем было бы сде­лать для бло­ков какую-то сущ­ность типа объ­ек­та. У него были бы свой­ства — напри­мер, кон­фи­гу­ра­ция. Может быть, мы бы захо­те­ли потом сде­лать взры­ва­ю­щи­е­ся объ­ек­ты или объ­ек­ты с замо­роз­кой, объ­ек­ты с повы­шен­ной ско­ро­стью, отрав­лен­ные объ­ек­ты или что-то ещё в таком духе.

Но есть нюанс: смысл объ­ек­та в том, что он неде­ли­мый. А в «Тет­ри­се» все объ­ек­ты запро­сто делят­ся, когда мы «закры­ва­ем линию». У какой-нибудь Т-образной фигу­ры может запро­сто про­пасть хво­стик, а у Z-образной фигу­ры — ниж­няя перекладина.

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

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

Сами фигу­ры тоже пред­ста­вим в виде дву­мер­но­го мас­си­ва из нолей и еди­ниц, но осо­бым обра­зом — в виде квад­ра­та, где еди­ни­цы отве­ча­ют за части фигу­ры, а ноли — за пустое место:

Если вме­сто квад­ра­та про­сто взять фак­ти­че­ские раз­ме­ры фигу­ры и загнать их в мас­сив, то при вра­ще­нии они не вле­зут в исход­ный мас­сив. А внут­ри квад­ра­та их мож­но вра­щать как угод­но — раз­мер мас­си­ва от это­го не изменится:

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

Подготовка страницы

Игра будет рабо­тать на HTML-странице с помо­щью эле­мен­та Canvas — это холст, на кото­ром мы можем рисо­вать про­из­воль­ные фигу­ры через JavaScript.

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

Всё осталь­ное сде­ла­ем скрип­том. Доба­вим тэг сра­зу после того, как нари­со­ва­ли холст, и нач­нём писать содер­жи­мое скрипта.

Заводим переменные и константы

Пока что всё просто:

Генерируем выпадающие фигуры

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

Теперь мы можем создать после­до­ва­тель­ность из выпа­да­ю­щих фигур. Логи­ка будет такая:

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

Движение, вращение и установка фигуры на место

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

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

Если про­вер­ка не про­шла, то мы не дела­ем послед­нее дви­же­ние, и фигу­ра про­сто про­дол­жа­ет падать вниз. Если ей неку­да падать и она упёр­лась в дру­гие, то нам нуж­но зафик­си­ро­вать это в игро­вом поле. Это зна­чит, что мы запи­сы­ва­ем в мас­сив, кото­рый отве­ча­ет за поле, нашу мат­ри­цу фигу­ры, про­пус­кая ноли и запи­сы­вая толь­ко единицы.

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

Что будет, когда мы проиграем

Когда фигу­ра при окон­ча­тель­ной уста­нов­ке выле­за­ет за гра­ни­цы игро­во­го поля, это зна­чит, что мы про­иг­ра­ли. За это у нас отве­ча­ет флаг gameOver, и его зада­ча — оста­но­вить ани­ма­цию игры.

Что­бы было понят­но, что игра закон­че­на, выве­дем над­пись GAME OVER! пря­мо поверх игро­во­го поля:

Обрабатываем нажатия на клавиши

Всё как в обыч­ном тет­ри­се: стрел­ки вле­во и впра­во дви­га­ют фигу­ру, стрел­ка вверх пово­ра­чи­ва­ет её на 90 гра­ду­сов, а стрел­ка вниз уско­ря­ет падение.

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

Запускаем движения и анимацию

Смысл глав­но­го цик­ла игры такой:

Так как кад­ры меня­ют­ся быст­ро, мы не заме­тим посто­ян­но­го очи­ще­ния и отри­сов­ки. Нам будет казать­ся, что фигу­ра про­сто дви­жет­ся вниз и реа­ги­ру­ет на наши действия.

Послед­нее, что нам оста­лось сде­лать, — запу­стить игру:

// старт игры rAF = requestAnimationFrame(loop);

Гото­вый резуль­тат мож­но посмот­реть на стра­ни­це с игрой.

Источник

Как написать свой Тетрис на Java за полчаса

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

Нам, как обычно, понадобятся:

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

С чего начать?

Получение данных от пользователя

Код, честно говоря, достаточно капитанский:

Интерфейсы для клавиатурного и графического модулей

Так как многим не нравится, что я пишу эти модули на LWJGL, я решил в статье уделить время только интерфейсам этих классов. Каждый может написать их с помощью той GUI-библиотеки, которая ему нравится (или вообще сделать консольный вариант). Я же по старинке реализовал их на LWJGL, код можно посмотреть здесь в папках graphics/lwjglmodule и keyboard/lwjglmodule.

Интерфейсы же, после добавления в них всех упомянутых выше методов, будут выглядеть следующим образом:

Отлично, мы получили от пользователя данные. Что дальше?

А дальше мы должны эти данные обработать и что-то сделать с игровым полем. Если пользователь сказал сдвинуть фигуру куда-то, то передаём полю, что нужно сдвинуть фигуру в таком-то направлении. Если пользователь сказал, что нужно фигуру повернуть, поворачиваем, и так далее. Кроме этого нельзя забывать, что 1 раз в FRAMES_PER_MOVE (вы же открывали файл с константами?) итераций нам необходимо сдвигать падающую фигурку вниз.

Сюда же добавим проверку на переполнение поля (в Тетрисе игра завершается, когда фигурам некуда падать):

Так, а теперь мы напишем класс для того магического gameField, в который мы всё это передаём, да?

А инициализировать мы их будем так:

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

Класс GameField

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

Хранить информацию о поле…

…и о падающей фигуре

TpReadableColor — простой enum, содержащий элементы с говорящими названиями (RED, ORANGE и т.п.) и метод, позволяющий получить случайным образом один из этих элементов. Ничего особенного в нём нет, код можно посмотреть тут.

Это все поля, которые нам понадобятся. Как известно, поля любят быть инициализированными.
Сделать это следует в конструкторе.

Конструктор и инициализация полей

А что это там за spawnNewFigure()? Почему инициализация фигуры вынесена в отдельный метод?

На этом с хранением данных мы закончили. Переходим к методам, которые отдают информацию о поле другим классам.

Методы, передающие информацию об игровом поле

Таких метода всего два. Первый возвращает цвет ячейки (для графического модуля):

А второй сообщает, переполнено ли поле (как это происходит, мы разобрали выше):

Методы, обновляющие фигуру и игровое поле

Сдвиг фигуры

Что мы сделали в этом методе? Мы запросили у фигуры ячейки, которые бы она заняла в случае сдвига. А затем для каждой из этих ячеек мы проверяем, не выходит ли она за пределы поля, и не находится ли по её координатам в сетке статичный блок. Если хоть одна ячейка фигуры выходит за пределы или пытается встать на место блока – сдвига не происходит. Coord здесь – класс-оболочка с двумя публичными числовыми полями (x и y координаты).

Поворот фигуры

Логика аналогична сдвигу:

Падение фигуры

Сначала код в точности повторяет предыдущие два метода:

Так как в результате переноса ячеек какая-то линия может заполниться полностью, после каждого добавления ячейки мы проверяем линию, в которую мы её добавили, на полноту:

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

Теперь GameField реализован почти полностью — за исключением геттера для фигуры. Её ведь графическому модулю тоже придётся отрисовывать:

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

Класс фигуры

Реализовать это всё я предлагаю следующим образом – хранить для фигуры (1) «мнимую» координату, такую, что все реальные блоки находятся ниже и правее неё, (2) состояние поворота (их всего 4, после 4-х поворотов фигура всегда возвращается в начальное положение) и (3) маску, которая по первым двум параметрам будет определять положение реальных блоков:

Rotation мод здесь будет выглядеть таким образом:

Соответственно, от самого класса Figure нам нужен только конструктор, инициализирующий поля:

И методы, которыми мы пользовались в GameField следующего вида:

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

Форма фигуры и маски координат

Чтобы не занимать лишнее место, здесь я приведу реализацию только для двух форм: I-образной и J-образной. Код для остальных фигур принципиально не отличается и выложен на GitHub.

Храним для каждой фигуры маску координат (которая определяет, насколько каждый реальный блок должен отстоять от «мнимой» координаты фигуры) и цвет:

Реализуем методы, которые использовали выше:

Ну а сами маски координат я предлагаю просто захардкодить следующим образом:

Т.е. для каждого объекта enum‘а мы передаём с помощью импровизированных (других в Java нет) делегатов метод, в котором в зависимости от переданного состояния поворота возвращаем разные реальные координаты блоков. В общем-то, можно обойтись и без делегатов, если хранить в каждом элементе отсупы для каждого из режимов поворота.

Источник

Свой тетрис на JavaScript: прокачиваем проект

Как-то раз мы писа­ли соб­ствен­ный тет­рис на JavaScript. Мы закон­чи­ли на том, что у нас есть про­стое игро­вое поле, фигу­ры и базо­вая логи­ка игры. Ещё игра уме­ет оста­нав­ли­вать­ся, когда для фигур боль­ше нет места. Но это­го недо­ста­точ­но, что­бы счи­тать­ся пол­но­цен­ной игрой.

Что­бы это испра­вить, вот что мы доба­вим сего­дня в игру:

Всё это неслож­но, но тре­бу­ет вни­ма­ния. Что­бы дора­бо­тать игру, будем исполь­зо­вать код из пер­вой части проекта:

Отображаем текущий уровень и набранные очки

Если мы сде­ла­ем вывод инфор­ма­ции об уров­нях и ста­ти­сти­ке внут­ри игро­во­го ста­ка­на, это будет неудоб­но: текст будет напол­зать на фигу­ры и мешать игре. Зна­чит, нам нуж­но доба­вить отдель­ный блок, где мы будем писать все игро­вые дан­ные. Сде­ла­ем его сра­зу после объ­яв­ле­ния поля для игры и даём бло­ку имя score:

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

Заметь­те: теперь у нас на стра­ни­це есть два объ­ек­та типа canvas — то есть два хол­ста. В одном рису­ет­ся игра, в дру­гом выво­дят­ся очки. Теперь мы смо­жем обра­щать­ся к этим хол­стам отдель­но и рисо­вать в каж­дом то, что нам нуж­но, неза­ви­си­мо друг от друга.

Вот как полу­чить доступ к ново­му холсту:

// получаем доступ к холсту с игровой статистикой

const canvasScore = document.getElementById(‘score’);

const contextScore = canvasScore.getContext(‘2d’);

Доба­вим в скрипт новые пере­мен­ные — они нам сра­зу при­го­дят­ся на сле­ду­ю­щем этапе:

Теперь выве­дем на экран всю игро­вую ста­ти­сти­ку. Для это­го перед глав­ным цик­лом игры сде­ла­ем новую функ­цию showScore():

Циф­ры вро­де 15, 20, 50, 160 — это коор­ди­на­ты по вер­ти­ка­ли и гори­зон­та­ли, где долж­ны нахо­дить­ся наши тек­сто­вые бло­ки. Без этих коор­ди­нат они все нале­зут друг на друга.

Послед­нее, что нам оста­лось сде­лать — вызвать эту функ­цию внут­ри основ­ной функ­ции loop() коман­дой showScore().

Спрашиваем имя игрока

Что­бы знать, кому при­над­ле­жит рекорд игры, будем спра­ши­вать имя при каж­дом запус­ке игры:

name = prompt(«Ваше имя», «»);

Этот код мы напи­шем сра­зу после объ­яв­ле­ния всех пере­мен­ных, что­бы он выпол­нил­ся на стар­те один раз. Сме­нить имя в про­цес­се игры будет нель­зя, но это и не нужно.

Считаем очки

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

Для под­счё­та очков нахо­дим в функ­ции placeTetromino() про­вер­ку, запол­нен ли ряд цели­ком, и сра­зу пер­вым дей­стви­ем в этой про­вер­ке пишем:

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

Теперь доба­вим про­вер­ку рекор­да — поби­ли мы его уже или нет. Для это­го будем посто­ян­но срав­ни­вать теку­щие очки с рекор­дом, и если теку­щие боль­ше — уста­но­вим новый рекорд и запи­шем имя победителя:

Запоминаем рекорды

Сей­час у игры есть суще­ствен­ный недо­ста­ток — если открыть стра­ни­цу зано­во в том же бра­у­зе­ре, она не вспом­нит имя чем­пи­о­на. Когда мы дела­ли свой туду-лист на JavaScript, то исполь­зо­ва­ли для это­го локаль­ное хра­ни­ли­ще бра­у­зе­ра — localstorage. При новом откры­тии стра­ни­цы мож­но будет взять дан­ные о рекор­де оттуда.

Возь­мём из той ста­тьи наш код для локаль­но­го хра­ни­ли­ща и попра­вим его под нынеш­нюю зада­чу — хра­нить имя игро­ка и его рекорд. Поста­вим этот код сра­зу после того, как спро­сим имя игро­ка на старте:

Но в хра­ни­ли­ще ниче­го не появит­ся авто­ма­ти­че­ски — мы сами долж­ны поло­жить туда зна­че­ние рекор­да и имя чем­пи­о­на. Сде­ла­ем это в том же раз­де­ле, где мы начис­ля­ем очки за линии. Попра­вим немно­го, что­бы код выгля­дел так:

Теперь при каж­дом обнов­ле­нии рекор­да в хра­ни­ли­ще сра­зу будет запи­сы­вать­ся акту­аль­ная инфор­ма­ция. Даже если мы обно­вим стра­ни­цу, запи­си останутся:

Добавляем сложность и уровни

Что­бы играть было инте­рес­нее, сде­ла­ем так: с каж­дым новым уров­нем фигу­ры будут падать всё быст­рее. Для это­го нахо­дим в коде строч­ку, кото­рая отве­ча­ет за ско­рость дви­же­ния фигур вниз и пра­вим её сле­ду­ю­щим образом:

// фигура сдвигается вниз каждые 36 кадров минус значение текущего уровня. Чем больше уровень, тем быстрее падает.

Логи­ка тут такая: чем выше уро­вень, тем мень­ше интер­вал обнов­ле­ния меж­ду сдви­га­ми, что даёт нам ощу­ще­ние повы­шен­ной ско­ро­сти. Хотя на самом деле фигу­ры не пада­ют быст­рее, про­сто они мень­ше тупят.

Напри­мер, на пер­вом уровне фигу­ра сдви­га­ет­ся на одну клет­ку вниз каж­дые 35 кад­ров, а на 10 уровне — каж­дые 25 кад­ров, на треть быстрее.

Сами уров­ни будем счи­тать там же, где и очки. Что­бы перей­ти на новый уро­вень, нуж­но набрать 100 очков. Зная это, лег­ко полу­чить зна­че­ние уров­ня — доста­точ­но раз­де­лить наце­ло коли­че­ство очков на 100 и при­ба­вить 1. Такой под­ход и даст нам нуж­ный уровень.

Запи­шем это там же, где и идёт под­счёт очков:

level = Math.floor(score/100) + 1;

Теперь всё в поряд­ке. Може­те ско­пи­ро­вать код себе или поиг­рать на стра­ни­це про­ек­та.

Источник

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

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

Алгоритм

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вес, назначенный общему количеству ячеек-колодцев, кажется немного удивительным, потому что опытные игроки обычно намеренно строят глубокие колодцы, чтобы набрать несколько 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 (см. «гамма-коррекция»).

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

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

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

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

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

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

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

В строках 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).

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

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

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

Версия на Java

О программе

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

Пакеты

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

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

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

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

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

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

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

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

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

Вызов ИИ

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

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

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

Всё вместе это выглядит следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дополнение

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

Видео

Понаблюдайте за тем, как бот набирает максимальное количество очков Nintendo Tetris, начиная с уровня 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.

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

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

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

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

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

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

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

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

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

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

Сила ИИ

Для оценки силы ИИ было собрано примерно 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.

Источник