В 1985 году Алексей Пажитнов и Вадим Герасимов выпустили в свет Tetris. Эта увлекательная и вызывающая сильное привыкание игра требовала от игроков соединять фигуры, появлявшиеся в случайном порядке. С того времени было выпущено более 150 лицензионных версий «Тетриса». Отличаясь игровыми режимами, правилами и реализацией, все они игрались слегка (или очень) по-разному. Рандомизатор «Тетриса» — это функция, возвращающая случайно выбранную фигуру. На протяжении многих лет правила выбора фигур эволюционировали, оказывая влияние на геймплей и саму случайность. Некоторые из этих алгоритмов были подвергнуты реверс-инжинирингу и задокументированы. Я составил список рандомизаторов, которые считаю важными, и покажу в статье, как с годами менялось внутреннее устройство «Тетриса».
Tetris (прибл. 1985 год)
Первая и оригинальная версия «Тетриса» имела рандомизатор без смещения. На выбор следующей фигуры ничто не влияло, она просто выбиралась и показывалась игроку.
При использовании рандомизатора без смещения возникают ситуации, в которых игрок получает последовательность из одной фигуры (называемую «потопом», flood) или последовательность, в которой отсутствует определённая фигура (называемую «засухой», drought). Мы увидим, как дизайнеры разных версий «Тетриса» пытались слегка сгладить эту проблему.
Хотя рандомизатор без смещения создаёт для игроков самую большую сложность головоломок, он нестабилен и может привести к непобедимой последовательности (PDF). Однако в реальной игре такого не случается, потому что в компьютерах нет генераторов истинных случайных чисел. Генераторы псевдослучайных чисел (ГПСЧ) пытаются имитировать истинную случайность, но не имеют свойств, способных сгенерировать подряд 70 тысяч фигур Z.
Истинная псевдослучайность
function* random() {
const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z'];
while (true) {
yield pieces[Math.floor(Math.random() * pieces.length)];
}
}Сложность головоломки: 4/5
Предотвращение потопов: 0/5
Предотвращение засух: 0/5
Tetris, Nintendo (1989 год)
Четыре года спустя была выпущена ставшая необычно популярной версия «Тетриса» для NES.
Чтобы снизить количество потопов (повторения) фигур, в рандомизатор была добавлена проверка истории. Эта простая проверка делала следующее:
- выбирала фигуру,
- проверяла, совпадает ли фигура с предыдущей,
- если да, то алгоритм выбирал новую фигуру, но только один раз,
- и каким бы ни был результат, фигура отдавалась игроку.
Хотя вероятность получения одной фигуры подряд снижалась, ничто не мешало игре выдавать две попеременно меняющиеся фигуры. Кроме того, в этой версии частой ситуацией была засуха на протяжении более чем 30 фигур. Засуха могла возникать для любого типа тетрамино, но для набора очков в этой игре важна фигура I, и её большая засуха могла существенно повлиять на окончательный счёт.
Запоминание истории на 1 фигуру вглубь и с 1 броском
function* historyRandomizer() {
const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z'];
let history;
while (true) {
// First "roll"
piece = pieces[Math.floor(Math.random() * pieces.length)];
// Roll is checked against the history
if (piece === history) {
piece = pieces[Math.floor(Math.random() * pieces.length)];
}
history = piece;
yield piece;
}
}Сложность головоломки: 5/5
Предотвращение потопов: 2/5
Предотвращение засух: 0/5
Tetris: The Grand Master (1998 год)
Хоть Tetris для NES и улучшил алгоритм по сравнению с рандомизацией без смещения, засухи в нём по-прежнему были часты. В Tetris: The Grand Master (TGM) по сути использовалась та же система, но с более долгой историей и бОльшим количеством бросков.
Благодаря увеличению этих значений не только снизилось количество потопов, но улучшилась ситуация с засухами. В истории сохранялись четыре фигуры, а это значило, что повышалась вероятность получить фигуру, которой уже давно не было. Несмотря на это, в игре по-прежнему отсутствовало строгое правило для предотвращения засух и они всё равно возникали, хоть и намного реже, чем в Tetris для NES.
Запоминание истории на 4 фигуры и с 4 бросками
function* historyRandomizer() {
const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z'];
// First piece special conditions
let piece = ['I', 'J', 'L', 'T'][Math.floor(Math.random() * 4)];
yield piece;
let history = ['S', 'Z', 'S', piece];
while (true) {
for (let roll = 0; roll < 4; ++roll) {
piece = pieces[Math.floor(Math.random() * 7)];
if (history.includes(piece) === false) break;
}
history.shift();
history.push(piece);
yield piece;
}
}Сложность головоломки: 4/5
Предотвращение потопов: 4/5
Предотвращение засух: 2/5
Tetris Worlds и далее (2001 год)
Tetris Worlds познакомил широкие массы с генератором случайности. Сейчас он является официальным рандомайзером, в большинстве официальных версий игры после Tetris Worlds и по сей день используется он.
Рандомизаторы на основе истории помогали избавиться от потопов (или, по крайней мере, минимизировать их), но не останавливали засухи. В определённых условиях по-прежнему существовала вероятность получения смертоносной последовательности фигур.
Генератор случайности (Random Generator) решает эти проблемы благодаря использованию новой системы «мешков» (bags). В этой системе список фигур помещается в «мешок», после чего фигуры одна за другой случайным образом извлекаются из него, пока «мешок» не опустеет. Когда он опустеет, фигуры возвращаются в него и процесс повторяется. Random Generator имеет «мешок» размером 7 (7-bag), то есть «мешок» заполненный каждой из 7 тетрамино. Возможны и другие типы «мешков», например 14-bag, в который кладутся по две фигуры каждого типа тетрамино.
Из-за отсутствия у «мешков» истории на их стыках могут возникать потопы длительностью 2 фигуры и «змейки» из 4 фигур (
, 
и т.п.). То есть в каком-то смысле это шаг назад по сравнению с традиционным Tetris для NES.Фигуры выпадают из 7-bag стабильно, из-за чего он более предсказуем. Легко понять, в какой части «мешка» вы находитесь, и когда может прийти нужная вам фигура. Из-за предсказуемости этого генератора случайности в игру на самом деле можно играть бесконечно. В целом это очень глупая система, и непонятно, как она вообще стала официальным рандомизатором.
7-bag
function* randomGenerator() {
let bag = [];
while (true) {
if (bag.length === 0) {
bag = ['I', 'J', 'L', 'O', 'S', 'T', 'Z'];
bag = shuffle(bag);
}
yield bag.pop();
}
}Сложность головоломки: 3/5
Предотвращение потопов: 3/5
Предотвращение засух: 4/5
Tetris: The Grand Master 3 — Terror-Instinct (2005 год)
TGM3 сильно продвинула вперёд идею генерации случайности. Это уникальная система, не встречавшаяся ни в одной другой версии.
Вместо «мешка» или истории в TGM3 используется пул фигур. Изначально в нём по 5 фигур каждого типа, то есть всего 35 фигур. При вытягивании фигуры она не удаляется из пула, а заменяется фигурой с самой большой засухой (той, которую давно не вынимали). Постепенно пул всё больше заполняется этой фигурой, пока она наконец не будет вытащена. Это решает проблемы систем «мешков», а также систем с историей; она берёт лучшее от обоих типов рандомизации.
Пул из 35 фигур с 6 бросками
function* tgm3Randomizer() {
let pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z'];
let order = [];
// Create 35 pool.
let pool = pieces.concat(pieces, pieces, pieces, pieces);
// First piece special conditions
const firstPiece = ['I', 'J', 'L', 'T'][Math.floor(Math.random() * 4)];
yield firstPiece;
let history = ['S', 'Z', 'S', firstPiece];
while (true) {
let roll;
let i;
let piece;
// Roll For piece
for (roll = 0; roll < 6; ++roll) {
i = Math.floor(Math.random() * 35);
piece = pool[i];
if (history.includes(piece) === false || roll === 5) {
break;
}
if (order.length) pool[i] = order[0];
}
// Update piece order
if (order.includes(piece)) {
order.splice(order.indexOf(piece), 1);
}
order.push(piece);
pool[i] = order[0];
// Update history
history.shift();
history[3] = piece;
yield piece;
}
}Сложность головоломки: 4/5
Предотвращение потопов: 4/5
Предотвращение засух: 4/5
Выводы
Сложно подвести какой-то определённый итог. Рандомизатор TGM3 кажется более предсказуемым и менее сложным для игрока. Неуклюжий 7-bag ощущается неестественным, но позволяет создавать множество стабильно жизнеспособных стратегий строительства. Недружелюбный рандомайзер, как, например в Tetris для NES, может испортить вам игру, или, что вероятнее, настроение играть.
Можем ли мы улучшить эти системы, делая их кажущимися более случайными, и накладывая жёсткие ограничения на засухи и потопы? Или такие жёсткие ограничения просто делают игру более предсказуемой?
usdglander
Refridgerator
В своей реализации тетриса я просто увеличил вероятность «палки» — по ощущениям, её всегда было недостаточно — в отличие от всех остальных фигур, про которые алгоритм рандомизации «забывал».
michael_vostrikov
Тоже так делал, ставил в 2 раза больше, чем у остальных фигур. У палки еще плюс, что ими можно убрать любые пустоты, если фигуры до этого были неподходящие.
algotrader2013
Интересно, есть ли в +- популярных реализациях алгоритмы, которые учитывают состояние поля, оценивают шансы игрока, и специально усложняют/упрощают игру, чтобы склонить к донату, или удержать в игре? Или даже сформировать ощущение «почти выиграл» (примерно, как в видео из первого комментария)?
alexxisr
Я играл в вариант, который подбирает самую ненужную фигуру. Не помню название -ставился в стандартном наборе какого-то дистрибутива линукса. Что-то типа «самый сложный тетрис», на инглише естественно.
Xitsa
По описанию похоже на Bastet.
Pythonpy
В candy crush алгоритм разрабатывался 7 лет чтобы максимально долго удерживать игрока
Nick0las
Более 20 лет назад я писал тетрис под DOS, еще на Паскале. Там были усложнения: Не давать палок если они нужны и подкидывать квадрат если его некуда поставить. Может еще какие-то были, не помню уже. На мой взгляд с усолжнениями интересней.
AEP
А про bastet (тетрис, который специально заваливает игрока, предлагая каждый раз худшую фигуру) ничего не сказали.
shikhov
Можно просто одни зигзаги давать, попробуй собери линию.
kudryavy
Да легко! Особенно если зигзаги одного типа. Сложнее, если разного, но тоже не смертельно
Yuuri
Смертельно, если они, например, регулярно чередуются, а стакан стандартный шириной 10.
kudryavy
Насчет не смертельно это я погорячился, конечно.
Но в контексте 'собери линию' сложностей быть не должно.
Nikoobraz
А есть алгоритмы с переменными вероятностями? Например изначально шанс для всех фигур равен, но после выбора одной из фигур, вероятность ее выпадения понижается в вдвое\втрое\вчетверо, а остальных, соответственно растет. Такой алгоритм разумеется еще оставляет вероятность потопов\засух, но:
а) она контролируема, т.к. может настраиваться коэффициент изменения вероятности
б) вероятность длинных периодов потопа\засухи все же примерно сопоставима с вероятнью резиста от иммалейт импрувед.
в) полное исключение или чрезмерное гашение таких последовательностей все же заметно убавляет азарта.
DrMefistO
Не указана сложность для TGM3 — это и в оригинале так?
PatientZero Автор
Нет, это я пропустил. Уже исправил, спасибо. Про ошибки лучше сообщать в личку.
VladimirKochetkov
shiru8bit
На NES три разных Тетриса, и каноничным теперь стал самый худший из них, от BPS, которая позже преобразовалась в The Tetris Company, и теперь владеет эксклюзивными правами и теперь ведёт очень агрессивную политику, выпихивая отовсюду нелицензионные версии и строго указывая всем лицензиатам, каким должен быть Тетрис.
У TTC есть секретный 100-страничный гайдлайн с паком материалов на почти четыре гигабайта, где подробно расписаны все игровые механики, включая рандомайзер (7-bag из статьи), и это всё обязательно к исполнению, иначе игра не пройдёт ревью. Ревью, судя по всему, проводится по чек-листу, и отвечающие за это люди не очень-то далеко ушли от ботов Play Market'а. Это к вопросу в конце статьи, как можно было бы улучшить рандомайзер — теоретически много как, но практически никак.
lobzanoff
Все эти модифицированные рандомайзеры — не тру. С ними тетрис — не тот, что был изначально придуман и во что мы играли еще на терминалах СМ. Никаких поблажек игроку быть не должно, иначе это — профанация :)
cxell
Воистину, тетрис, где ненужная закорюка выпадает стопиццот раз подряд и никаких поблажек — суть Тетрис, а остальное — HERECY!11
AranelOfDoriath
Интересно, какой рандомизатор использовался в карманных 999in1?
DrGluck07
Корейский рандом?
Maximuzz
после прочтения статьи захотелось сыграть в тетрис, рука потянулась к смартфону, но сразу вспомнилась реклама и баннеры в бесплатных приложениях, и тут я вспомнил, что у меня есть волшебная коробка с хламом, где лежат как раз парочка таких 999 в 1, как раз без рекламы и донатов, хоть обыграйся))
red_andr
Сейчас то есть, к примеру RdRand. Что мешает его использовать? И да, я сторонник подхода, что не надо модифицировать генератор, чтобы помогать игроку. Всё должно быть как в жизни, по взрослому и без поблажек. Ну выпало несколько зигзагов подряд, значит так надо, ну не повезло. А то так дойдут до того, что АИ будет анализировать ситуацию и специально выкидывать фигурки, чтобы продлить игру.
Barbaresk
Такая фигня уже есть во многих гонках против ПК ( Соперники-боты подстраиваются под твою скорость и едут медленнее, если ты тупишь, или быстрее, если ты едешь нормально.
MacIn
Отслеживать количество выпадений всех фигур за последние шагов 20-30 и подтягивать вероятность выпадения тех, которые редки. Чтобы выпадение любой фигуры было равновероятным. Скажем, за последние 30 шагов реже всего выпадали квадрат и планка — кидаем ГСПЧ между этими двумя вариантами, а не всеми.
shiru8bit
Текущий стандарт 7-bag и делает равновероятное выпадение. При нём не может выпадать реже квадрат и планка в пределах 30 шагов, за это время они выпадут не менее 4 раз каждая. Максимальные расстояния между повторами получаются до 12 фигур, т.е. может выпасть квадрат, 12 других фигур, и потом квадрат (в первом блоке квадрат оказался в начале, в следующем в конце блока), максимальный повтор две одинаковые фигуры подряд (одна в конце блока, вторая в начале следующего), вероятность таких повторов относительно низкая.
MacIn
Мне кажется, предложенный алгоритм проще, пусть он и не гарантирует равной вероятности на коротком промежутке.
ichsu
А у меня в тетрисах могут быть фигуры из любого количества кубиков (разные тетрисы, алгоритм — один). Вместо какой-то рандомизации, я просто выращиваю из центральной точки фигуры во все стороны до нужного количества квадратов. То есть фигуры могут появляться в и в совершенно разной ориентации. Посмотреть можно — keda.su.