Comment un ordinateur peut-il générer du hasard ?


L'aléatoire et le pseudo-aléatoire

Qui ne s'est ou ne s'était pas posé la question ? Comment une machine pourrait-elle avoir une notion de hasard alors qu'elle n'est capable d'effectuer que des opérations logiques qui, a priori n'ont aucun lien avec le hasard.

Il faut être conscient qu'aucun algorithme ni expérience pratique ne donne un résultat parfaitement aléatoire. Ainsi il faut plutôt parler de pseudo-aléatoire pour désigner une expérience ou une fonction qui s'approche d'un aléatoire parfait.

Les générateurs congruentiels linéaires

C'est l'algorithme le plus utilisé pour générer des nombres pseudo-aléatoires. Ils ont l'avantage d'être très rapides et peuvent s'avérer être de très bonne qualité. Leur seule contrainte est qu'il faut les initialiser à partir d'un nombre appelé graine (seed en anglais). Deux graines produiront toujours la même séquence de nombres aléatoires, c'est pourquoi il faut s'assurer que la graine de départ soit différente à chaque exécution. Généralement c'est l'unité de temps qui est utilisé comme graine (temps en nanosecondes par exemple) mais on pourrait très bien additionner à cela d'autres facteurs de hasard comme les mouvements de la souris, les touches du clavier, etc.

Un générateur congruentiel linéaire n'est autre qu'une suite mathématique. Elle est définie par trois paramètres (en plus de la graine de départ qui elle est variable) :

En connaissant le terme précédent de la suite (ou le terme initial (la graine) si la suite vient d'être initialisée), le calcul du terme suivant s'effectue de la manière suivante Xn+1 = (a * Xn + c) mod m.

Si les paramètres ont été judicieusement choisis (voir choix du multiplicateur et de l'incrément), les m premiers termes apparaitront chacuns une seule et unique fois. Passé m la suite se mettra à répéter les termes dans le même ordre : c'est sa période.

Ce qui est intéressant c'est que chaque terme apparait de manière uniforme et c'est à partir de cette propriété notable qu'on va pouvoir retourner un nombre pseudo-aléatoire. On ne va pas utiliser le nombre directement, mais plutôt le tronquer pour ne conserver que les bits de poids fort car « plus » aléatoires. On répète cette opération autant de fois que nécessaire pour obtenir le nombre de bits attendus.

Imaginons maintenant que l'on souhaite retourner un nombre entier compris entre 0 et 2n. C'est très simple puisqu'il suffit de retourner le nombre représenté par n bits aléatoires.

Maintenant qu'en est-il pour un nombre entier quelconque, entre 0 et k ? On va chercher le plus petit entier n tel que 2n ≥ k, autrement dit n = ceil(log2(k)). On génère 2n bits aléatoires que l'on représente en nombre entier r. Si r < k2, on s'arrête et on retourne ce nombre modulo k. Dans le cas inverse, on n'a pas le choix : il faut recommencer l'opération jusqu'à ce que l'inégalité soit vérifiée.

Cet algorithme retourne des valeurs pseudo équiprobables ; la seule chose qui n'est pas garantie c'est le nombre de fois que l'on devra répéter l'opération si la valeur aléatoire ne vérifie pas l'inégalité. Mais c'est le prix à payer pour obtenir un nombre pseudo-aléatoire compris dans intervalle quelconque, à partir de bits pseudo-aléatoires.

Limites

Le plus gros danger sur lequel il faut être attentif est la prédiction des termes de la suite. En effet, en connaissant les paramètres utilisés par le générateur ainsi qu'un des termes de la suite il est possible de déduire tous les termes suivants (en utilisant en autres l'inversion modulaire). Aussi, si le module est trop petit les nombres qui vont en découler auront l'air « moins » aléatoires que si le module avait été plus grand.

De ce fait, il ne faut pas les utiliser en cryptographie. D'autres algorithmes plus lents mais moins biaisés et quasiment imprédictibles sont utilisés pour cela.

De la même façon, s'il s'agit d'une plateforme de jeu où le hasard prend une place importante ce n'est probablement pas une bonne idée.

Petite anecdote

Le jeu PacMan datant de 1980 utilisait déjà un générateur congruentiel linéaire pour diriger les fantômes dans le labyrinthe.

Les paramètres utilisés par le développeur Shigeo Funaki (a = 5, c = 1 et m = 8192) produisent un générateur qui a une période de "seulement" 1365 ; cela peut tout à fait s'expliquer par les contraintes de l'époque (un Z80 dans ce cas mais les contraintes sont généralisables pour tout type de matériel) :

Le code source en assembleur (commenté et formaté) qui m'a servi à illustrer cet exemple se trouve ici, en particulier la procédure qui génère des octets pseudo-aléatoires se situe au niveau de l'octet 0x2a23.


Références


© Florian Cassayre 2018
Version 11ceed0