Les Générateurs de Nombres Aléatoires
Les Générateurs de Nombres Aléatoires
Sommaire
1. Introduction
2. Génération Pseudo-aléatoire
3. Générateur congruentiel linéaire (LCG)
4. Xorshift
5. Mersenne Twister
6. Utilisation de la graine
7. Distribution normale
8. Conclusion
1. Introduction
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 bug 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 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 le 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 le TypeScript qui est un sur-ensemble du 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.
2. Génération Pseudo-aléatoire
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 aléatoires à l'aide d'un ordinateur à cause de son mode de fonctionnement purement déterministe (à condition de faire abstraction des bugs 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'apparentent 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 divers 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.
3. Générateur Congruentiel Linéaire (LCG)
3.1. Théorie
Un Générateur Congruentiel Linéaire ou LCG pour son acronyme en anglais, est essentiellement une suite mathématique relativement simple, définie de la manière suivante :
Xn+1 = (a * Xn + c) mod m
où mod désigne l'opérateur modulo, le reste de la division entière.
Le premier élément de la suite, X0 est souvent nommé seed dans le jargon informatique. C'est la graine qui engendrera tous les autres nombres pseudo-aléatoires.
Les coefficients <a, c, m> (resp. multiplicateur, incrément, modulo) définissent complètement un LCG et doivent obéir à certaines contraintes pour que le LCG produise des nombres aléatoires de qualité satisfaisante, ce qui n'est pas toujours le cas comme nous le verrons un peu plus bas.
C'est sur la base de ce modèle simple voire simpliste qu'encore aujourd'hui une majorité de nombres aléatoires sont produits sur nos ordinateurs. Cette famille de générateurs de nombres aléatoires a des défauts que nous allons voir, mais a trois principales qualités :
- Les LCG sont très simples à implémenter.
- Les LCG s'appuient sur un processus reproductible via la graine.
- Les LCG sont rapides par rapport à d'autres générateurs de nombres aléatoires.
Ces trois qualités suffisent à expliquer la présence encore très importante des LCG dans les implémentations de langages.
Passons donc en revue les différents LCG.
3.2. 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 :
Xn+1 = (a * Xn) 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 X0 qui doit être impaire, et idéalement un nombre premier.
L'algorithme RANDU est défini par le couple <65539, 231> soit la formule de récurrence :
Xn+1 = (65539 * Xn) mod 231
On constate que le modulo n'est pas un nombre premier, même s'il n'est pas loin de 231-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 :
Code:
1
2
3
4
5
6
| 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. Il est une pratique courante d'initialiser la graine avec l'heure courante même si en toute rigueur il faudrait l'initialiser avec une valeur plus chaotique (ayant plus d'entropie) comme par exemple 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é 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és par RANDU comporte des régularités flagrantes ce qui explique pourquoi cet algorithme soit 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...
3.3. 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 fourni 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 :
Xn+1 = (214013 * Xn + 2531011) mod 216
En TypeScript l'implémentation pourrait être celle-ci :
Code:
1
2
3
4
5
6
7
| 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.
3.4. Central Randomizer de Hoole
A une époque maintenant reculée, où il fallait se connecter à Internet via un modem bruyant et que le HTML n'était 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 Houle 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 :
Xn+1 = (9301 * Xn + 49297) mod 233280
Implémentation en TypeScript :
Code:
1
2
3
4
5
6
| 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 et 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 et permet dans l'absolu une meilleure rapidité bien que cela était 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.
3.5. 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, 216> et par la suite :
Xn+1 = (1103515245 * Xn + 12345) mod 216
En TypeScript voici ce que cela pourrait donner :
Code:
1
2
3
4
5
6
7
8
| var randomSeed = Date.now();
function randCLib(): number {
randomSeed = randomSeed * 1103515245 + 12345;
randomSeed = (randomSeed / 65536) % 32768; // extract bits 30..16
return randomSeed / 32767.0;
} // randCLib |
A 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.
3.6. Bilan
Le LCG du langage C est-il donc la solution à notre besoin ? Disons que cela dépend. Si on fait abstraction de la cryptographie qui nécessite des générateurs autrement plus complexes, la simulation numérique et à fortiori les jeux vidéo, notamment ceux utilisant intensivement la génération procédurale et les processus stochastiques (eg. phénomènes physiques, IA), la quantité requise de nombres aléatoires fait que fatalement ce LCG, comme n'importe quel autre biaisera d'une façon ou d'une autres les nombres aléatoires générés, et ceci en vertu d'un théorème affirmant de façon schématique que les nombres générés par les LCG n'occupent pas tout l'espace des possibles mais uniquement une fraction. Le LCG de Windows en est un exemple flagrant mais le LCG de la bibliothèque C comporte également ce défaut, même si c'est dans une bien moindre mesure.
Par conséquent, pour avoir des nombres aléatoires occupant de façon homogène l'ensemble des possibles il faudra faire appel à d'autres générateurs un peu plus élaborés que les LCG.
4. Xorshift
Ce générateur aléatoire mis au point en 2003 par George Marsaglia, 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 :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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é.
5. Mersenne Twister
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 :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| 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.
6. Utilisation de la graine
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'envie une même séquence.
Si on s'appuie sur l'exemple de générateur d'univers aléatoire 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.
7. Distribution normale
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 :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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 est appelée 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 :
8. Conclusion
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. Il convient tout d'abord de garder à l'esprit que tous les générateurs présentés dans cet article ne sont pas exploitable 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.
Nous avons vu que les LCG sont une bonne première approche, à condition de bien choisir ses coefficients, mais qu'ils avaient des limitations intrinsèques que seules d'autres approches pouvaient surmonter. Au final, 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.
Le code source des différents algorithmes présentés est disponible sur mon compte Github.
