![[Перевод] История алгоритмов рандомизации «Тетриса»](https://habrastorage.org/getpro/habr/post_images/98b/032/444/98b032444bc6166195004d46d9b4ee2c.jpg "[Перевод] История алгоритмов рандомизации «Тетриса»")
В 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; } }Выводы
Сложно подвести какой-то определённый итог. Рандомизатор TGM3 кажется более предсказуемым и менее сложным для игрока. Неуклюжий 7-bag ощущается неестественным, но позволяет создавать множество стабильно жизнеспособных стратегий строительства. Недружелюбный рандомайзер, как, например в Tetris для NES, может испортить вам игру, или, что вероятнее, настроение играть.
Можем ли мы улучшить эти системы, делая их кажущимися более случайными, и накладывая жёсткие ограничения на засухи и потопы? Или такие жёсткие ограничения просто делают игру более предсказуемой?
Источник
