Хабрахабр

[Перевод] История алгоритмов рандомизации «Тетриса»

image
В 1985 году Алексей Пажитнов и Вадим Герасимов выпустили в свет Tetris. Эта увлекательная и вызывающая сильное привыкание игра требовала от игроков соединять фигуры, появлявшиеся в случайном порядке. С того времени было выпущено более 150 лицензионных версий «Тетриса». Отличаясь игровыми режимами, правилами и реализацией, все они игрались слегка (или очень) по-разному. Рандомизатор «Тетриса» — это функция, возвращающая случайно выбранную фигуру. На протяжении многих лет правила выбора фигур эволюционировали, оказывая влияние на геймплей и саму случайность. Некоторые из этих алгоритмов были подвергнуты реверс-инжинирингу и задокументированы. Я составил список рандомизаторов, которые считаю важными, и покажу в статье, как с годами менялось внутреннее устройство «Тетриса».

Tetris (прибл. 1985 год)

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

Мы увидим, как дизайнеры разных версий «Тетриса» пытались слегка сгладить эту проблему. При использовании рандомизатора без смещения возникают ситуации, в которых игрок получает последовательность из одной фигуры (называемую «потопом», flood) или последовательность, в которой отсутствует определённая фигура (называемую «засухой», drought).

Однако в реальной игре такого не случается, потому что в компьютерах нет генераторов истинных случайных чисел. Хотя рандомизатор без смещения создаёт для игроков самую большую сложность головоломок, он нестабилен и может привести к непобедимой последовательности (PDF). Генераторы псевдослучайных чисел (ГПСЧ) пытаються имитировать истинную случайность, но не имеют свойств, способных сгенерировать подряд 70 тысяч фигур Z.

Истинная псевдослучайность

function* random()
}

Сложность головоломки: 4/5

Предотвращение потопов: 0/5

Предотвращение засух: 0/5

Tetris, Nintendo (1989 год)

Четыре года спустя была выпущена ставшая необычно популярной версия «Тетриса» для NES.

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

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

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

То есть в каком-то смысле это шаг назад по сравнению с традиционным Tetris для NES. Из-за отсутствия у «мешков» истории на их стыках могут возникать потопы длительностью 2 фигуры и «змейки» из 4 фигур (, и т.п.).

Легко понять, в какой части «мешка» вы находитесь, и когда может прийти нужная вам фигура. Фигуры выпадают из 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 сильно продвинула вперёд идею генерации случайности. Это уникальная система, не встречавшаяся ни в одной другой версии.

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

Пул из 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; }
}

Выводы

Сложно подвести какой-то определённый итог. Рандомизатор TGM3 кажется более предсказуемым и менее сложным для игрока. Неуклюжий 7-bag ощущается неестественным, но позволяет создавать множество стабильно жизнеспособных стратегий строительства. Недружелюбный рандомайзер, как, например в Tetris для NES, может испортить вам игру, или, что вероятнее, настроение играть.

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

Показать больше

Похожие публикации

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

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

Кнопка «Наверх»