Cet article est une synthèse de plusieurs conférences, de la documentation C++ et de mon expérience sur la génération de nombre aléatoire en C++.

Mon besoin

Je suis le développeur de Rolisteam. Un logiciel pour faire du jeu de rôle en ligne. Il intègre une solution badass (oui, je m’envoie des fleurs) de lancer de dés. J’ai passé beaucoup de temps entre juillet 2014 et février 2015 pour produire un langage de script interprété de lancement de commandes de dés. Vous pouvez y jeter un œil sur ce lien: DiceParser. Bref, j’ai crée tout un système pour lancer les dés et faire des opérations sur les résultats: tri, relance, filtre, explosion, arithmétique, gestion des priorités mathématiques et il est même capable de générer l’arbre d’exécution avec dot.

L’aléatoire

Pour la partie aléatoire dans tout le système, j’ai réutilisé le code historique de rolistik (l’ancêtre de rolisteam).
Certains utilisateurs sont venus me voir pour me demander de vérifier le système d’aléatoire car ils avaient fait des tests et avez déterminé que Rolisteam favorisait les résultats haut; ou bas selon les personnes.
J’avais droit à un tableau de statistique réalisé sur quelques dizaines de lancer de dés.
Argument qu’il est facile de détruire avec une étude statistique plus riche en lancer. DiceParser fonctionne en ligne de commande, donc très facile à «scripter». Bref, des gens avaient des doutes sans réelle preuve.
Du coup, je me suis un peu renseigné s’il n’y avait pas des méthodes plus «C++» avec le C++11, C++14 et/ou C++17.

L’existant

Quand il s’agit de générer des nombres aléatoires, la première implémentation qu’on apprend est souvent celle ci :

[pastacode lang=”cpp” manual=”int%20resultat%20%3D%20std::rand()%25MAX%2Bdebut%3B” message=”usage classique de rand();” highlight=”” provider=”manual”/]

Je pense que tous les étudiants ont implémenté cette méthode, dans leurs premières années d’études.  Elle est facile à comprendre. Elle est disponible dans beaucoup de langages. Elle vient du C. Elle met en avant le modulo, ce qui lui donne peut-être une valeur pédagogique. Elle suffit dans de très nombreux cas.

Nous allons voir un peu ce qui cloche avec cette méthode.

Les défauts

1/ Pauvre entropie
Déjà, rand() ou std::rand() sont définis dans le “man” comme une solution pauvre pour obtenir de l’aléatoire. Il est précisé que les vieilles implémentations de rand() ou les implémentations sur d’autres systèmes fournissent un aléatoire pauvre sur les bits de poids faibles. Cela explique peut-être pourquoi certains utilisateurs sous Windows se plaignent.
Donc l’entropie de rand n’est pas bonne. Il existe une autre méthode: random() qui fonctionne normalement mieux, avec un période beaucoup plus grande.

2/ Erreur de répartition
Ces deux méthodes génèrent un nombre entre 0 et RAND_MAX. Maintenant, nous souhaitons obtenir des résultats sur un dés à 100 faces. (C’est un format de dés courant en Jeux de rôle).
Imaginons que RAND_MAX vaut 32767.

Si je découpe la valeur maximum en tranche de 100 cela donne ceci:

[0 : 99] => 100 valeurs
[100 : 199] => 100 valeurs
[200 : 299] => 100 valeurs
:
:
[32700 : 32767 ] => 67 valeurs.

Nous avons 327 tranches complètes et une dernière de 67.  L’usage du modulo vient faire la correspondance entre la valeur tirée dans l’espace de valeurs désirées. Cela favorise les résultats entre 0 et 67. Il y a une chance supplémentaire de tomber en dessous de 67. La différence est probablement négligeables mais tout de même, cela me pose problème d’avoir cela dans mon logiciel.

3/ Problème de portabilité

La valeur RAND_MAX vaut au minimum 32767 dans la norme. Elle diffèrent en fonction des implémentations, nous avons vu également que la portabilité de la méthode rand() n’est pas garantie.
Cette somme de problèmes vient conforter les utilisateurs de Rolisteam dans leur idée de problème relatif au système de dés. Deux problèmes de portabilité se cumulent.

Le constat de ces erreurs m’a poussé à chercher une solution moderne pour générer ces nombres.

Dans les API C++ est arrivé un nouveau “module” avec le C++11. Il s’agit de random.

#include <random>

Ce module présente toute une série de classes pour générer des nombres aléatoires et les répartir.
Il propose un nombre intéressant d’algorithmes ou de moteurs différents pour la génération. Je ne suis pas un expert en génération pseudo-aléatoire de nombre. Du coup, le nom des algorithmes ne me parle pas.
Cependant, il semble que deux éléments sortent du lot: le std::random_device et le std::mt19937.

Le std::random_device

Il est défini dans la documentation comme: Un générateur de nombre aléatoire non déterministe. En gros, cela signifie qu’on ne peut pas prévoir son comportement.
D’habitude, vous initialisez votre méthode aléatoire par un seed. Il peut être intéressant pour des tests automatiques ou une résolution de bug de pouvoir rejouer une séquence entière de nombre aléatoire.
Pour atteindre cet objectif, il suffit de mettre la même seed. Donc vous avez là une méthode de nombre aléatoire qui est déterministe. random_device n’a pas de seed. Il n’a pas besoin d’être initialiser. Il est donc impossible de lui faire “jouer” deux fois la même chose. Dans mon cas, cela me satisfait complètement.

C’est facile à mettre en place:

[pastacode lang=”cpp” manual=”std%3A%3Arandom_device%20rd%3B%0Astd%3A%3Auniform_int_distribution%3Cint%3E%20dist(1%2C%2010)%3B%0Aint%20randomNumber%20%3D%20dist(rd)%3B%0Astd%3A%3Acout%20%3C%3C%20%20randomNumber%20%3C%3C%20std%3A%3Aendl%3B” message=”” highlight=”” provider=”manual”/]

On génère une nombre et on le distribue entre 1 et 10. Cela suffit. Il y a rien besoin de plus. C’est propre, élégant etc.
J’ai implémenté cette méthode dans rolisteam 1.8, malgré les avertissements qu’on trouve à droit à gauche. Cela donne de bons résultats sous Linux. J’ai fait une version pour Windows et là, c’est le drame.
L’entropie du module sous windows est de zéro. Cela signifie qu’il renvoie toujours le même résultat. Bref, les dés étaient toujours de la même valeur.
La solution du random_device ne marche pas. Elle n’est pas portable.

Le std::mt19937

Il reste donc la méthode du std::mt19937. Elle fait toujours partie de l’API de <random>. Voici l’implémentation finale dans rolisteam.

[pastacode lang=”cpp” manual=”%2F%2F%20dans%20le%20constructeur%20de%20ma%20classe%20d%C3%A9%0Aauto%20seed%20%3D%20std%3A%3Achrono%3A%3Ahigh_resolution_clock%3A%3Anow().time_since_epoch().count()%3B%0Am_rng%20%3D%20std%3A%3Amt19937(quintptr(this)%2Bseed)%3B%0A%0A%2F%2Fdans%20la%20fonction%20lancer%20(roll())%0Astd%3A%3Auniform_int_distribution%3Cqint64%3E%20dist(m_base%2Cm_faces)%3B%0Aqint64%20value%20%3D%20dist(m_rng)%3B” message=”L’implementation dans rolisteam.” highlight=”” provider=”manual”/]

On peut voir qu’elle est plus proche de l’ancienne méthode car Il est nécessaire de l’initialiser avec un seed. Pour cela, il est également possible d’utiliser une API C++11: <chrono>.

[pastacode lang=”cpp” manual=”%20%23include%20%3Cchrono%3E%0A%E2%80%A6%0Aauto%20seed%20%3D%20std%3A%3Achrono%3A%3Ahigh_resolution_clock%3A%3Anow().time_since_epoch().count()%3B%0Am_rng%20%3D%20std%3A%3Amt19937(quintptr(this)%2Bseed)%3B” message=”Politique Agricole Commune” highlight=”” provider=”manual”/]

 

Autres méthodes:

Il existe d’autres moyens de tirer des nombres aléatoires en C++. Il existe des tonnes de bibliothèques C++ pour faire cela. Si j’en avais une seule à vous conseiller, je parlerais de PCG (www.pcg-random.org). Elle est écrite par Melissa O’Neill. Cheinan Marks fait l’éloge de cette bibliothèque et du site qui l’accompagne.

Il y a de nombreux articles sur le sujet. Personnellement, je n’ai pas intégré PCG dans rolisteam, tout simplement parce que chaque bibliothèques externes est un calvaire à gérer dans le processus d’installation pour une application multi-plateforme.

Conclusion:

J’espère avoir fait le tour des nouvelles API pour la génération aléatoire de nombres entiers en C++. Il est important de garder à l’esprit que l’API <random> fournit bien sur bien plus de chose que ce que j’ai montré. Je n’ai pas fait d’étude statistique pour démontrer que c’est mieux maintenant. Dans tous les cas, j’ai implémenté le device_random dans mon lecteur audio maison, et je découvre plein de nouvelle musique de ma collection.

Les sources:

CppCon 2016: Cheinan Marks “I Just Wanted a Random Integer!”:
https://www.youtube.com/watch?v=4_QO1nm7uJs
Stephan T. Lavavej – rand() Considered Harmful:
https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful