🎨 👨🏽 🥥 L'histoire des algorithmes de randomisation Tetris 😛 🍞 🧜

En 1985, Alexey Pajitnov et Vadim Gerasimov ont sorti Tetris. Ce jeu fascinant et très addictif obligeait les joueurs à connecter des pièces apparaissant au hasard . Depuis lors, plus de 150 versions sous licence de Tetris ont été publiées. Différents dans les modes de jeu, les règles et l'implémentation, ils ont tous joué légèrement (ou très) différemment. Le randomiseur Tetris est une fonction qui renvoie une forme sélectionnée au hasard. Au fil des ans, les règles de choix des formes ont évolué, influençant le gameplay et l'aléatoire lui-même. Certains de ces algorithmes ont été rétroconçus et documentés. J'ai compilé une liste de randomiseurs que je considère importants, et je montrerai dans l'article comment la structure interne de Tetris a changé au fil des ans.

Tetris (vers 1985)

La première et originale version de Tetris avait un randomiseur sans biais. Rien n'a influencé le choix de la figure suivante, elle a simplement été choisie et montrée au joueur.

Lors de l'utilisation d'un randomiseur sans déplacement, des situations surviennent dans lesquelles le joueur reçoit une séquence d'une figure (appelée «inondation», inondation) ou une séquence dans laquelle il n'y a pas de figure certaine (appelée «sécheresse», sécheresse). Nous verrons comment les concepteurs de différentes versions de Tetris ont tenté de résoudre légèrement ce problème.

Bien qu'un randomiseur sans biais crée la plus grande complexité du puzzle pour les joueurs, il est instable et peut conduire à une séquence invincible (PDF) . Cependant, cela ne se produit pas dans un vrai jeu, car les ordinateurs n'ont pas de véritables générateurs de nombres aléatoires. Les générateurs de nombres pseudo-aléatoires (PRNG) tentent de simuler le vrai hasard, mais n'ont pas les propriétés qui peuvent générer consécutivement 70 000 chiffres Z.

Véritable pseudo-aléatoire

function* random() { const pieces = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; while (true) { yield pieces[Math.floor(Math.random() * pieces.length)]; } }

Difficulté du puzzle: 4/5

Prévention des inondations: 0/5

Prévention de la sécheresse: 0/5

Tetris , Nintendo (1989)

Quatre ans plus tard, la version inhabituellement populaire de Tetris pour NES est sortie .

Pour réduire le nombre d'inondations (répétitions) des figures, une vérification de l'historique a été ajoutée au randomiseur. Cette simple vérification a fait ce qui suit:

choisissez une figure
vérifié si le chiffre correspond au précédent,
si c'est le cas, l'algorithme a sélectionné une nouvelle forme, mais une seule fois,
et quel que soit le résultat, le chiffre a été remis au joueur.

Bien que la probabilité d'obtenir une pièce d'affilée diminuait, rien n'empêchait le jeu d'émettre deux pièces en alternance. De plus, dans cette version, la sécheresse de plus de 30 chiffres était une situation fréquente. Une sécheresse pourrait survenir pour tout type de tétramino, mais la figure I est importante pour marquer dans ce jeu, et sa grande sécheresse pourrait affecter de manière significative le score final.

Mémoriser une histoire 1 figure en profondeur et avec 1 lancer

 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; } }

Difficulté du puzzle: 5/5

Prévention des inondations: 2/5

Prévention de la sécheresse: 0/5

Tetris: le grand maître (1998)

Bien que Tetris pour NES ait amélioré l'algorithme par rapport à la randomisation sans biais, les sécheresses y étaient encore fréquentes. Tetris: Le Grand Master ( TGM ) a essentiellement utilisé le même système, mais avec une histoire plus longue et plus de lancers.

En raison de l'augmentation de ces valeurs, non seulement le nombre d'inondations a diminué, mais la situation des sécheresses s'est également améliorée. Quatre figures ont été conservées dans l'histoire, ce qui signifie que la probabilité d'obtenir une figure qui n'existait pas depuis longtemps a augmenté. Malgré cela, le jeu manquait toujours d'une règle stricte pour éviter les sécheresses et elles se sont toujours produites, bien que beaucoup moins fréquemment que dans Tetris pour NES .

Mémoriser une histoire avec 4 pièces et 4 lancers

 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; } }

Difficulté du puzzle: 4/5

Prévention des inondations: 4/5

Prévention de la sécheresse: 2/5

Tetris Worlds et autres (2001)

Tetris Worlds a présenté les masses au générateur aléatoire. Il est maintenant le randomiseur officiel, dans la plupart des versions officielles du jeu après Tetris Worlds, et à ce jour, il est utilisé.

Les randomiseurs basés sur l'histoire ont aidé à se débarrasser des inondations (ou du moins à les minimiser), mais n'ont pas mis fin à la sécheresse. Sous certaines conditions, il était toujours possible d'obtenir une séquence mortelle de chiffres.

Le générateur aléatoire (Random Generator) résout ces problèmes grâce à l'utilisation d'un nouveau système de "sacs" (sacs). Dans ce système, la liste des figures est placée dans un «sac», après quoi les figures en sont extraites au hasard les unes après les autres jusqu'à ce que le «sac» soit vide. Lorsqu'il est vide, les morceaux y retournent et le processus se répète. Le générateur aléatoire a un «sac» de taille 7 (7 sacs), c'est-à-dire un «sac» rempli de chacun des 7 tétraminos. D'autres types de «sacs» sont possibles, par exemple un sac de 14, dans lequel deux morceaux de chaque type de tétramino sont placés.

En raison du manque d'historique des «sacs», des inondations de 2 chiffres et des «serpents» de 4 chiffres peuvent se produire à leurs jonctions (

etc.). C'est, en un sens, un pas en arrière par rapport au Tetris traditionnel pour NES .

Les pièces sortent du sac 7 de manière stable, ce qui le rend plus prévisible. Il est facile de comprendre dans quelle partie du «sac» vous vous trouvez et quand le chiffre dont vous avez besoin peut venir. En raison de la prévisibilité de ce générateur de hasard, le jeu peut en fait être joué sans fin . En général, c'est un système très stupide, et on ne sait pas comment il est généralement devenu un randomiseur officiel.

7 sacs

 function* randomGenerator() { let bag = []; while (true) { if (bag.length === 0) { bag = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']; bag = shuffle(bag); } yield bag.pop(); } }

Difficulté du puzzle: 3/5

Prévention des inondations: 3/5

Prévention de la sécheresse: 4/5

Tetris: The Grand Master 3 - Terror-Instinct (2005)

TGM3 a considérablement avancé l'idée de générer de l'aléatoire. Il s'agit d'un système unique que l'on ne trouve dans aucune autre version.

Au lieu d'un sac ou d'une histoire, le TGM3 utilise un ensemble de formes. Initialement, il comporte 5 chiffres de chaque type, soit un total de 35 chiffres. Lorsqu'une figurine est tirée, elle n'est pas retirée du bassin, mais est remplacée par la figurine ayant la sécheresse la plus importante (celle qui n'a pas été retirée depuis longtemps). Progressivement, la piscine est de plus en plus remplie de ce chiffre jusqu'à ce qu'elle soit finalement retirée. Cela résout les problèmes des systèmes de «sac», ainsi que des systèmes avec une histoire; elle tire le meilleur parti des deux types de randomisation.

Pool de 35 figurines avec 6 lancers

 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; } }

Difficulté du puzzle: 4/5

Prévention des inondations: 4/5

Prévention de la sécheresse: 4/5

Conclusions

Il est difficile de tirer un résultat définitif. Le randomiseur TGM3 semble plus prévisible et moins complexe pour le joueur. Le 7-bag maladroit ne semble pas naturel, mais vous permet de créer de nombreuses stratégies de construction stables et viables. Un randomiseur inamical, comme dans Tetris pour NES, peut ruiner votre jeu ou, plus probablement, votre humeur à jouer.

Pouvons-nous améliorer ces systèmes en les faisant paraître plus aléatoires et en imposant de sévères restrictions aux sécheresses et aux inondations? Ou ces restrictions sévères rendent-elles le jeu plus prévisible?

L'histoire des algorithmes de randomisation Tetris