Les générateurs de nombres aléatoires

Comme dans toute activité de développement logiciel, le développement des jeux vidéo nécessite des tests et des corrections (et même beaucoup) ce qui implique souvent la nécessité de pouvoir reproduire un certain état du jeu. En cas de bogue dans un système de combat par exemple, on peut avoir besoin de reproduire à volonté et à l'identique un certain comportement des adversaires du joueur pour localiser le problème et ensuite le corriger.

La spécificité des jeux vidéo par rapport à d'autres applications, dans le domaine de la gestion par exemple, est que ce sont des applications qui font très souvent appel, et parfois très massivement, à la génération de nombres aléatoires. Mais ce caractère intrinsèquement aléatoire de bon nombre de jeux entre souvent en conflit avec les besoins de reproductibilité.

Dans la plupart des langages, il existe une fonction ou méthode permettant de générer des nombres aléatoires à partir de ce qui est communément appelé graine ou seed en anglais, et qui permet de reproduire à l'identique une séquence de nombres aléatoires.

Mais ce n'est pas le cas de tous les langages. Par exemple, en JavaScript, la fonction de base, Math.random(), ne donne aucun moyen au développeur de définir une graine et n'a donc aucun moyen de reproduire une séquence aléatoire générée plus tôt. C'est un peu comme au cinéma où le spectateur n'a aucune possibilité de pause ou de retour arrière. Même si cela fait partie de l'expérience du cinéma, dans le domaine du développement c'est autrement plus gênant.

Le but de cet article sera de présenter différents générateurs de nombres aléatoires (ou RNG pour Random Number Generator en anglais) se basant sur une graine pour générer une séquence de nombres aléatoires.

Cet article peut s'adresser aux développeurs utilisant d'autres langages que JavaScript. Soit parce que leur langage ne fournit pas non plus un générateur de séries aléatoires reproductibles, soit parce que la qualité du générateur par défaut n'est pas suffisante pour les besoins.

Le langage utilisé pour illustrer les algorithmes sera TypeScript qui est un sur-ensemble de JavaScript avec typage et héritage. Une présentation de ce langage est disponible ici.

Aussi, une démonstration en ligne de cet article est disponible ici.

Bien que le hasard soit pratiquement omniprésent dans la vie de tous les jours, si on admet que les lois de la physique quantique sont vraies, il est loin d'être trivial, encore à l'heure actuelle de produire des nombres véritablement aléatoires à l'aide d'un ordinateur à cause de son mode de fonctionnement purement déterministe (à condition de faire abstraction des bogues et des plantages). Sauf à le relier à un processus physique comme la désintégration d'un élément radioactif ou un bruit de fond, les ordinateurs actuels doivent recourir à des algorithmes déterministes pour simuler le hasard, ce qui est quelque part paradoxal.

Mais de l'ordre peut naître le chaos. Un exemple basique est de considérer le cas du nombre PI qui est un nombre parfaitement déterministe, mais dont le développement décimal est dans une certaine mesure imprévisible, en tout cas revêt beaucoup des caractéristiques du hasard. (cf. Preuss)

Dans le domaine qui nous intéresse, les jeux vidéo, qui s'apparente pour beaucoup à celui de la simulation numérique, il faut être capable de produire beaucoup de nombres aléatoires, et rapidement, sans avoir nécessairement la chance de jouer sur un supercalculateur. Pour cela, les mathématiciens ont trouvé au fil du temps diverses méthodes pour produire des nombres qui ont les apparences du hasard, même s'il faut toujours garder à l'esprit que ce n'est qu'une illusion.

Parmi les générateurs de nombres aléatoires, celui qui s'est imposé avec l'avènement des ordinateurs est le générateur congruentiel linéaire, et il est encore présent dans d'innombrables applications encore aujourd'hui.

À noter qu'en toute rigueur, les nombres générés par une procédure algorithmique déterministe comme ce sera le cas dans ce document sont appelés des nombres pseudoaléatoires. Cependant pour simplifier le propos, ils seront simplement appelés nombres aléatoires tout comme nous appellerons générateurs aléatoires, des procédures stricto sensu pseudoaléatoires.

III-A. Théorie▲

III-B. RANDU▲

C'est le nom d'un algorithme mis au point chez IBM dans les années 1960. L'algorithme RANDU fait partie d'une classe particulière de LCG nommée Park-Miller d'où dérive un autre générateur bien connu, le MINSTD. Les LCG de la classe Park-Miller ont la particularité d'avoir un incrément c qui vaut zéro. Les générateurs de ce type sont donc définis par seulement deux nombres <a, m> au lieu de trois avec la formule suivante :

• X_n+1 = (a * X_n) mod m

Les contraintes sont plus fortes que dans le cas général des LCG, avec par exemple le modulo m qui doit être un nombre premier et aussi une contrainte sur la graine initiale X₀ qui doit être impaire, et idéalement un nombre premier.

L'algorithme RANDU est défini par le couple <65539, 2³¹> soit la formule de récurrence :

• X_n+1 = (65539 * X_n) mod 2³¹

On constate que le modulo n'est pas un nombre impair et encore moins un nombre premier, même s'il n'est pas loin de 2³¹-1, ce qui posera problème si on analyse un minimum la séquence des nombres aléatoires générés par un tel algorithme.

Son implémentation en TypeScript pourrait être la suivante :

 

Sélectionnez

var randomSeed = Date.now();
 
function randU(): number {
  randomSeed = (randomSeed * 65539) % 2147483648;
  return randomSeed / 2147483648.0;
} // randU

où randomSeed est une variable globale initialisée au préalable d'un appel à la fonction. Même s'il est une pratique courante d'initialiser la graine avec l'heure courante, en toute rigueur il faudrait l'initialiser avec une valeur plus chaotique (ayant plus d'entropie) comme le mouvement de la souris.

Il existe tout un tas de tests pour s'assurer de la qualité des générateurs de nombres aléatoires. Nous nous limiterons dans cet article à une simple analyse visuelle. Une série de nombres aléatoires binaires peut être représentée sous la forme d'une suite linéaire de pixels noirs ou blancs avec retour à la ligne. C'est ce qu'on pourrait appeler la représentation pile ou face. Un générateur aléatoire de qualité doit donner une image sans motif particulier. Un bon brouillard uniforme.

Une autre façon simple de représenter une série de nombres aléatoires est une représentation dans un plan où deux nombres aléatoires consécutifs fournissent l'abscisse et l'ordonnée d'un point. Cela donne un nuage de points qui permet de voir certaines régularités. Évidemment, un générateur parfaitement aléatoire doit engendrer un nuage de points sans motif particulier et bien dispersé.

Dans le cas de RANDU, voici ce que nous obtenons :

On peut constater que pour certaines valeurs de graines, la série de nombres engendrée par RANDU comporte des régularités flagrantes ce qui explique pourquoi cet algorithme est aujourd'hui tombé en désuétude.

L'algorithme RANDU est en fait célèbre, non pas pour son efficacité, très médiocre, voire mauvaise comme on peut le constater, mais justement pour être un bon exemple de ce que ne doit pas être un LCG.

Depuis heureusement, on a fait mieux, quoique…

III-C. Windows▲

Après IBM, on va s'attaquer à un autre mastodonte de l'informatique : Microsoft. Car pour ceux qui ont utilisé les API C/C++ de Windows, il existe une fonction rand() par défaut, fournie dans les API du célèbre système d'exploitation.

Il se trouve que le générateur aléatoire par défaut de Windows est aussi un LCG, du moins jusqu'à la version XP.

Ses paramètres sont <214013, 2531011, 216> ce qui donne la suite :

• X_n+1 = (214013 * X_n + 2531011) mod 2¹⁶

En TypeScript l'implémentation pourrait être celle-ci :

 

Sélectionnez

var randomSeed = Date.now();
 
function randMSWin(): number {
  randomSeed = randomSeed * 214013 + 2531011;
  randomSeed = (randomSeed / 65536) % 32768; // extract bits 30..16
  return randomSeed / 32767.0;
} // randMSWin

On remarque une petite variante qui consiste à n'extraire qu'une partie du résultat. En effet, il a été démontré que dans le cas des LCG, les bits de poids faibles avaient tendance à ne pas être très aléatoires, ce qui explique pourquoi dans beaucoup d'implémentations informatiques de LCG, une opération d'extraction des bits de poids forts est réalisée.

Si maintenant on visualise ce que nous donne ce générateur, on obtient ceci :

Si on ne considère que la représentation pile ou face, le générateur de Windows semble tout à fait valable dans la mesure où il est impossible de distinguer des régularités à l'œil nu.

Cependant, si on considère la représentation en nuage de points, c'est une autre affaire. On constate que la plupart des points sont alignés le long de quelques droites et ce de façon systématique. Donc même si c'est moins pathologique que pour RANDU, le générateur aléatoire de Windows est à éviter dans la mesure du possible.

En remarque, quand on voit ce que des firmes telles qu'IBM et Microsoft avec les moyens qui vont avec, aient pu produire des générateurs d'aussi piètre qualité, cela devrait rassurer les modestes développeurs que nous sommes.

III-D. Central Randomizer de Hoole▲

À une époque maintenant reculée, où il fallait se connecter à Internet via un modem bruyant et que le HTML n'était que vaguement implémenté dans les quelques navigateurs de l'époque, il n'existait pas de fonction native en JavaScript pour générer un nombre aléatoire. C'est à cette époque qu'un jeune homme, Paul Hoole de son état, a mis au point un petit LCG capable de combler cette lacune.

Ce qui a fini par s'appeler le Central Randomizer de Hoole est un LCG définit par le triplet <9301, 49297, 233280> et dont la suite caractéristique est :

• X_n+1 = (9301 * X_n + 49297) mod 233280

 

Sélectionnez

var randomSeed = Date.now();
 
function randCentral(): number {
  randomSeed = (randomSeed * 9301 + 49297) % 233280;
  return randomSeed / 233280.0;
} //randCentral

La principale différence par rapport à ses prédécesseurs est que le multiplicateur utilisé est petit par rapport à ceux utilisés plus haut. Cela tend à limiter les débordements de calcul lors de la multiplication avec la graine qui est souvent un grand nombre et permet dans l'absolu une meilleure rapidité bien que cela fût surtout important à l'époque des premiers navigateurs.

Une rapide analyse visuelle nous montre que les nombres aléatoires générés par ce générateur ne sont pas mauvais, même s'il est possible de relever de légères régularités.

Dans un environnement optimal, on préférera toujours un autre générateur que celui-ci. Cependant, dans le cas d'une application JavaScript nécessitant un générateur de nombres aléatoires devant utiliser des graines, excluant donc la fonction Math.random(), et dans un environnement contraint comme pour les mobiles (même si les progrès dans ce domaine sont impressionnants), le Central Randomizer de Hoole peut être un compromis intéressant et facile à mettre en œuvre.

III-E. La bibliothèque C standard▲

On en arrive enfin à un LCG valable, celui décrit par Kernighan et Ritchie dans l'ouvrage de référence sur le C (1978), et qui continue à être présent dans plusieurs implémentations des compilateurs C/C++.

Ce LCG est caractérisé par le triplet <1103515245, 12345, 2¹⁶> et par la suite :

• X_n+1 = (1103515245 * X_n + 12345) mod 2¹⁶

 

Sélectionnez

var randomSeed = Date.now();
 
function randCLib(): number {
  randomSeed = randomSeed * 1103515245 + 12345;
  randomSeed = (randomSeed / 65536) % 32768; // extract bits 30..16 
 
  return randomSeed / 32767.0;
} // randCLib

À noter qu'à l'heure actuelle, des variantes plus sophistiquées de cet algorithme sont implémentées dans les compilateurs C/C++.

On notera que pour la grande majorité des graines, les résultats visuels sont satisfaisants.

III-F. Bilan des LCG▲

Le Xorshift est un générateur aléatoire mis au point en 2003 par George Marsaglia, qui utilise l'opérateur ou exclusif (xor) et le décalage de bits (shift). Comme les LCG, il a l'avantage d'être simple et rapide, mais n'a pas tous les défauts d'un LCG, même s'il n'est pas parfait.

L'implémentation de cet algorithme pourrait donner ceci en TypeScript :

var randomSeed = Date.now();
 
// Xorshift initialization
var x = 123456789;
var y = 362436069;
var z = 521288629;
 
function randXorshift(): number {
  var t = (x ^ (x << 11)) & 0x7fffffff;
  x = y;
  y = z;
  z = randomSeed;
  randomSeed = (randomSeed ^ (randomSeed >> 19) ^ (t ^ (t >> 8)));
  return randomSeed / 2147483648.0;
} // randXorshift

En termes de résultats visuels, rien ne permet de distinguer une série générée par Xorshift de celle générée par le véritable hasard.

Des études scientifiques ont démontré que cet algorithme est supérieur aux LCG. Il représente donc un meilleur choix en cas d'utilisation intensive. Je soupçonne d'ailleurs Firefox d'avoir implémenté le Xorshift pour la fonction JavaScript standard Math.random(). Néanmoins, la version de base du Xorshift présentée ici comporte quelques défauts qu'il serait hors de propos d'aborder ici. Retenons juste que pour pallier ces défauts, il existe une variante du Xorshift, nommée Xorshift*, qui est considérée par les spécialistes comme l'un des plus rapides générateurs de nombres aléatoires de haute qualité.

Venons-en à l'un des plus populaires générateurs de haute qualité, le Mersenne Twister, mis au point en 1997 par Makoto Matsumoto et Takuji Nishimura. Il doit son nom au fait que cet algorithme se base sur les propriétés des nombres premiers de Mersenne. Pour ce qui est d'une explication de l'algorithme, cela dépasse les compétences de votre humble serviteur, mais il faut savoir que ce générateur est celui utilisé par défaut dans de nombreux langages comme Python, Ruby ou PHP.

Voici une implémentation possible de cet algorithme en TypeScript :

var randomSeed = Date.now();
 
var N = 624;
var M = 397;
var MATRIX_A = 0x9908b0df; /* constant vector a */
var UPPER_MASK = 0x80000000; /* most significant w-r bits */
var LOWER_MASK = 0x7fffffff; /* least significant r bits */
var mt = new Array(N); /* the array for the state vector */
var mti = N + 1; /* mti==N+1 means mt[N] is not initialized */
 
/* initializes mt[N] with a seed */
mt[0] = randomSeed >>> 0;
for (mti = 1; mti < N; mti++) {
  var s = mt[mti - 1] ^ (mt[mti - 1] >>> 30);
  mt[mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
  + mti;
  /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
  /* In the previous versions, MSBs of the seed affect */
  /* only MSBs of the array mt[]. */
  /* 2002/01/09 modified by Makoto Matsumoto */
  mt[mti] >>>= 0;
  /* for >32 bit machines */
} // for mti
 
function randMersenne(): number {
  var y;
  var mag01 = new Array(0x0, MATRIX_A);
  /* mag01[x] = x * MATRIX_A for x=0,1 */
 
  if (mti >= N) { /* generate N words at one time */
    var kk;
 
    for (kk = 0; kk < N - M; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
      mt[kk] = mt[kk + M] ^ (y >>> 1) ^ mag01[y & 0x1];
    }
    for (; kk < N - 1; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
      mt[kk] = mt[kk + (M - N)] ^ (y >>> 1) ^ mag01[y & 0x1];
    }
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
    mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];
 
    mti = 0;
  }
 
  y = mt[mti++];
 
  /* Tempering */
  y ^= (y >>> 11);
  y ^= (y << 7) & 0x9d2c5680;
  y ^= (y << 15) & 0xefc60000;
  y ^= (y >>> 18);
 
  return (y >>> 0) * (1.0 / 4294967295.0);
} // randMersenne

Comme on s'en doutait, il n'est pas possible de distinguer visuellement une série générée par le Mersenne Twister d'une série réellement aléatoire :

Malgré la haute qualité des nombres aléatoires générés, le Mersenne Twister a un défaut non négligeable qui est une relative lenteur. Pour cette raison, il n'est pas forcément pertinent d'utiliser aveuglément cet algorithme dans des situations où les performances sont cruciales. Dans une telle situation, on lui préférera par exemple le Xorshift ou ses variantes.

Maintenant que nous avons un premier panorama de différents générateurs, on peut s'atteler à leur utilisation dans une application, en se donnant la possibilité de paramétrer la graine si besoin est. Ceci afin de répondre à l'exigence de reproductibilité que nous nous étions fixés en introduction.

En effet, à partir d'une même valeur de graine, la séquence du générateur sera toujours identique dans le cadre des algorithmes présentés qui sont tous déterministes. Il suffit donc de mémoriser la graine pour reproduire à l'envi une même séquence.

Si on s'appuie sur l'exemple de générateur aléatoire d'univers présenté dans un autre sujet, une même graine peut donc reproduire un même univers. D'une certaine façon, cela peut être considéré comme une forme de compression.

Une démonstration en ligne du générateur d'univers est disponible ici.

Dans certaines circonstances, la graine peut donc être mise à profit dans des jeux pour économiser de l'espace mémoire. Il est évidemment moins coûteux de stocker un seul nombre, plutôt que des milliers, voire des millions dans le cas des mondes ouverts.

Les générateurs présentés ici produisent des nombres aléatoires qui suivent la distribution uniforme. C'est-à-dire qu'en théorie, chaque valeur possible a la même probabilité d'apparition. Or, il est assez fréquent qu'on ait besoin d'une autre distribution, par exemple lorsqu'il s'agit de modéliser des phénomènes naturels ou s'en approchant.

La distribution normale aussi appelée distribution de Gauss est la plus utilisée, pour la simple raison que c'est en quelque sorte «  la distribution des distributions  » en vertu du Théorème de la Limite Centrale sur lequel le lecteur est invité à se documenter par lui-même.

Pour produire des nombres aléatoires suivant la distribution normale, il existe tout un tas de méthodes algorithmiques dont la plus répandue est celle s'appuyant sur la méthode de Box-Muller en coordonnées cartésiennes dont voici une implémentation en TypeScript :

function randNorm() {
  var y1, y2, rad;
 
  do {
    y1 = 2 * rand() - 1;
    y2 = 2 * rand() - 1;
    rad = y1 * y1 + y2 * y2;
  } while (rad >= 1 || rad == 0);
 
  var c = Math.sqrt(-2 * Math.log(rad) / rad);
 
  return y1 * c;
} // randNorm

La fonction rand() qui apparaît deux fois doit être une fonction renvoyant un nombre aléatoire flottant compris entre 0 et 1.

Si on applique une distribution normale à notre d'univers de graine 1411743524410, cela donne ceci :

De par l'importance des nombres aléatoires dans le domaine de la simulation numérique et des jeux vidéo, il n'est pas inutile de s'intéresser un minimum aux générateurs de nombres aléatoires.

Nous avons vu différents types de générateurs de nombres aléatoires. Mais il en existe bien d'autres.

Les LCG sont une bonne première approche, à condition de bien choisir ses coefficients, mais ils ont des limitations intrinsèques que seules d'autres approches peuvent surmonter comme l'algorithme du Xorshift ou le Mersenne Twister. Finalement, le choix d'un générateur est principalement un compromis entre la qualité des nombres aléatoires produits et la rapidité d'exécution de l'algorithme.

Il convient de garder à l'esprit que tous les générateurs présentés dans cet article ne sont pas exploitables dans le domaine de la cryptographie. Il faut pour cela utiliser des routines véritablement spécialisées et validées par des spécialistes. Pour un complément sur le sujet, on peut se référer utilement à cette Introduction à la cryptographie.

Enfin, si l'exigence de reproductibilité des nombres aléatoires n'est pas requise, il est possible d'obtenir des nombres réellement aléatoires, issus de processus physiques, via des dispositifs matériels comme des puces, des cartes ou des clés USB, ou encore via divers services Web comme le QRNG Service de l'Université Humbolt de Berlin, ou celui de la société random.org.

Le code source des différents algorithmes présentés est disponible sur mon compte Github.

VIII-A. Remerciements▲