mpa — Calcul du nombre d’histoires dans Ma Première Aventure

La série de livres Ma Première Aventure raconte des « histoires dont tu es le tout petit héros » : à plusieurs endroits dans le livre, il faut choisir quelle page tourner en fonction de l’histoire. Il est ainsi possible de raconter différentes histoires (et d’obtenir trois fins différentes) en fonction des choix effectués.

Dans cette page, donc calculons combien d’histoires il est possible de raconter avec un seul livre, et quelle est la probabilité de victoire.

En quête du dragon (seconde édition)

Commençons avec la seconde édition de En quête du dragon.

Résultats

Voici, pour les pressé·e·s, les résultats.

  • En ne comptant qu’une fois le même chemin suivi par deux personnages différents, il y a 4783 histoires.

  • En considérant comme deux histoires différentes le même chemin suivi par deux personnages, il y a 5184 histoires. Parmi celles-ci :

    • 60 histoires mènent à la victoire (soit 1,2 % environ) ;

    • 3024 histoires mènent à la semi-victoire-semi-défaite (soit 58,3 % environ) ;

    • 2100 histoires mènent à une défaite (soit 40,5 % environ).

  • En faisant tous les choix au hasard (de façon équiprobable), on obtient les probabilités suivantes :

    • Probabilité de victoire : 1,1 % environ.

    • Probabilité de mi-victoire-mi-défaite : 56,5 % environ.

    • Probabilité de défaite : 42,4 % environ.

Nous pouvons maintenant passer aux calculs…

Description des choix

Cette page sera mieux compréhensible en ayant lu l’histoire (voire en ayant le livre sous les yeux), mais essayons quand-même.

  • Le premier choix à faire est celui du personnage : trois sont disponibles.

  • Le deuxième choix s’effectue dans le village : allons-nous visiter le moulin, la grange, ou la maison du cartographe ? Il y a derrière chacun de ces choix un nouveau choix entre deux alternatives, soit libres, soit déterminées par le personnage choisi.

  • Le choix précédent (trois possibilités, puis deux pour chacune des trois) est répété cinq nouvelles fois, avec parfois des contraintes (fonction du personnage, ou des objets récoltés plus tôt dans l’histoire).

  • À la fin, en fonction du nombre de « bobos » subis, il y a trois fins : victoire, défaite, ou entre les deux.

Nombre d’histoires

Calcul mathématique

Un premier calcul naïf donne donc comme nombre d’histoires : \(3\times (3\times2)^6\times3\) :

  • trois personnages ;

  • trois alternatives, puis deux alternatives selon le choix précédent (\(3\times2\)), le tout répété six fois (puissance 6) ;

  • trois fins possibles.

Mais ce calcul est faux, car tous les choix ne sont pas libres :

  • certains chemins sont contraints par le personnage ou l’objet ;

  • les fins sont contraintes par le nombre de « bobos ».

En ne regardant que les choix libres, le nombre de chemins possibles est donc :

  • trois personnages ;

  • trois alternatives, suivi de (globalement) quatre alternatives possibles (puisque certains choix sont contraints) (\(4\)), le tout répété trois fois (puissance 3) ;

  • trois alternatives, suivi d’un choix contraint (\(3\)), le tout répété trois fois (puissance 3) ;

  • la fin est contrainte en fonction du nombre de bobos, donc aucun choix ici.

Cela donne donc \(3\times4^3\times3^3=5184\) histoires possibles.

Mais en faisant cela, nous avons fait une interprétation particulière du problème. En effet, si un même chemin peut être emprunté par deux personnages différents, devons nous compter cela comme un seul chemin, ou deux ? Le résultat précédent (5184 histoires possibles) compte comme deux chemins le même chemin emprunté par deux personnages différents.

Combien d’histoires sont possibles en comptant une seule fois plusieurs chemins empruntés par des personnages différents ? Je ne sais pas comment le faire par le calcul. Faisons le de manière informatique.

Calcul informatique

Quelques objets ou famille de fonctions sont définies.

  • D’abord, une page est simplement une liste de choix, assortie d’une éventuelle issée (vicoire, défaite, ou entre les deux).

    class jouets.mpa.Page(choix: Iterable[Choix] = <factory>, issue: typing.Optionnal[Issue] = None)[source]

    Une page, qui contient plusieurs choix.

    choix: Iterable[Choix]

    Liste des choix possibles

    issue: Optionnal[Issue] = None

    Si None, le livre n’est pas terminé. Sinon, indique l’issue (victoire, défaite, ni l’une ni l’autre).

  • Puis un choix qui lui a davantage d’attributs:

    class jouets.mpa.Choix(code: str, cible: ~jouets.mpa.Page, condition: ~typing.Callable = <function condition_vrai>, effet: dict = <factory>)[source]

    Une alternative possible lors d’un choix

    cible: Page

    Page à laquelle on va si on fait ce choix.

    code: str

    Code qui sera utilisé pour ce choix lorsque les histoires seront affichées.

    condition()

    Condition pour pouvoir faire ce choix. Par défaut, aucune condition n’est requise.

    effet: dict

    Effet si ce choix est effectué. C’est un dictionnaire des objets à appliquer sur les roues. Par exemple, effet = {"vert": "bouclier"} signifie : « Mettre le bouclier sur la roue verte ».

  • Les issues possibles sont un simple type énuméré.

    class jouets.mpa.Issue(value, names=None, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]

    Issues possible de livre.

  • Enfin, des conditions à vérifier (« Il y a un ou deux bobos », « Tu es le personnage Lina », « Tu as les chaussons ou tu es Sachat », etc.) sont construites à partir des fonctions suivantes.

    jouets.mpa.condition_compte(valeur: str, inf: Number = -inf, sup: Number = inf)[source]

    Le nombre de roues ayant une certaine valeur est comprise dans l’intervalle.

    Par exemple, condition_compte("bobo", inf=2) signifie qu’au moins deux roues ont la valeur "bobo".

    jouets.mpa.condition_non(condition)[source]

    Vérifie que la condition n’est pas satisfaite.

    jouets.mpa.condition_ou(*conditions)[source]

    L’une des conditions données en argument est vérifiée.

    jouets.mpa.condition_roue(**kwargs)[source]

    Les roues contiennent tous les objets donnés en argument.

    Par exemple, condition_roue(jaune="chaussons", rouge="Lina") vérifie que - les chaussons sont sur la roue jaune, et - le personnage de la roue rouge est Lina.

    jouets.mpa.condition_vrai(**roues)[source]

    Cette condition est toujours vérifiée.

Voici par exemple la première page du livre. Elle contient simplement que trois choix sont possibles, sans conditions, sans effets.

pageTuVisDansUn = Page(
    choix=(
        Choix(code="H", cible=pageDemanderDeLAide),
        Choix(code="M", cible=pageFouillerLaGrangeAbandonnée),
        Choix(code="B", cible=pageVolerUneCarteChez),
    )
)

Le premier choix avec conditions est celui-ci :

pageDemanderDeLAide = Page(
    choix=(
        Choix(
            # Si la roue rouge est Sachat,
            # alors tourner une page vers la page « Alors que tu quittes… »
            code="1",
            condition=condition_roue(rouge="Sachat"),
            cible=pageAlorsQueTuQuittes,
        ),
        Choix(
            # Si la rouge rouge n'est pas Sachat,
            # alors ajoute la pierre sur la roue verte,
            # et tourne deux pages vers la page « Alors que tu quittes… »
            code="2",
            condition=condition_non(condition_roue(rouge="Sachat")),
            effet={"vert": "pierre"},
            cible=pageAlorsQueTuQuittes,
        ),
    )
)

Enfin, pour compter le nombre de chemins (dans la méthode Page.histoires()), nous allons itérer sur les choix, si la condition est remplie.

 1    def histoires(self, **roues):
 2        """Itère sur toutes les histoires possibles.
 3
 4        Pour chacun des choix, si la condition est vérifiée,
 5        on applique l'effet et itère les histoires à partir de cette cible,
 6        """
 7        if self.choix:
 8            for choix in self.choix:
 9                if choix.condition(**roues):
10                    for histoire in choix.cible.histoires(**(roues | choix.effet)):
11                        yield choix.code + histoire
12        else:
13            yield ""

Résultats

À l’aide de ce programme, nous obtenons une liste de codes, par exemple LH2B1H2B2H2B2B2 :

  • L : choisir le personnage Lina ;

  • H2 : au premier choix, tourner la page du haut, puis faire le choix qui fait tourner deux pages ;

  • B1 : au second choix, tourner la page du bas, puis faire le choix qui fait tourner une seule page ;

  • H2, B2, H2, B2 : etc.

  • B2 : à la fin, tourner la page du bas (défaite) puis faire le choix qui fait tourner deux pages.

Notre programme affiche la liste brute de tous les chemins possibles, mais avec quelques commandes shell, nous pouvons répondre à quelques questions :

  • Combien d’histoires sont possibles (sachant que le même chemin suivi par deux personnages compte comme deux histoires) ?

    $ mpa dragon histoires | wc -l
    5184
    

    Nous retrouvons le nombre calculé dans la partie précédente.

  • Combien d’histoires sont possibles (sachant que le même chemin suivi par deux personnages compte comme une seule histoire) ?

    $ mpa dragon histoires | # Génère toutes les histoires \
    > cut -c2- | # Supprime la première lettre (choix du personnage) \
    > sort -u | # Trie les histoires, et ne conserve qu'un exemplaire des histoires identiques \
    > wc -l # Compte le nombre d'histoires
    4783
    
  • En considérant le même chemin suivi par deux personnages différent comme deux histoires :

    • Combien d’histoires mènent à la victoire ?

      $ mpa dragon histoires | # Génère toutes les histoires \
      grep H$ | # Ne conserve que celles qui se terminent par "H" (ce qui correspond à une victoire) \
      wc -l # Compte le nombre d'histoires
      60
      
    • Combien d’histoires mènent à une semi-victoire semi-défaite ?

      $ mpa dragon histoires | # Génère toutes les histoires \
      grep M$ | # Ne conserve que celles qui se terminent par "M" (ce qui correspond à une semi-victoire semi-défaite) \
      wc -l # Compte le nombre d'histoires
      3024
      
    • Combien d’histoires mènent à une défaite ?

      $ mpa dragon histoires | # Génère toutes les histoires \
      grep B[12]$ | # Ne conserve que celles qui se terminent par "B" suivi de 1 ou 2 (ce qui correspond à une défaite) \
      wc -l # Compte le nombre d'histoires
      2100
      
    • Bilan : Sur 5184 histoires, il y en a donc seulement 60 qui mènent à la victoire, soit à peine 1,2 % environ.

Probabilité de victoire

Puisque 1,2 % des histoires mènent à la victoire, nous pourrions être tenté d’affirmer que la probabilité de victoire en tournant les pages au hasard est de 1,2 %. Mais nous faisons ici l’erreur de croire que toutes les histoires sont équiprobables, ce qui n’est pas le cas (certaines histoires ont plus de chance d’être racontées au hasard que d’autres).

La classe Page a une méthode Page.proba() qui permet de calculer la probabilité d’une issue donnée. C’est une fonction récursive :

  • Si l’issue de la page est connue (c’est la page qui annonce la victoire, ou la défaite, ce qui est déterminé en regardant l’attribut Page.issue), la probabilité est 0 ou 1, suivant que c’est l’issue recherchée.

  • Si l’issue n’est pas connue (l’attribut Page.issue est None), la probabilité d’obtenir l’issue cherchée est la moyenne des probabilités d’obtenir cette issue pour chacun des choix possibles de cette page.

 1    def proba(self, issue: Issue, **roues: dict):
 2        """Calcule la probabilité d'obtenir l'issue donnée en argument."""
 3        if self.issue is not None:
 4            # C'est une page finale
 5            if self.issue == issue:
 6                return 1
 7            return 0
 8        # Ce n'est pas une page finale :
 9        # Calcule la moyenne des probabilités de de victoire pour chacun des choix.
10        return statistics.mean(
11            choix.cible.proba(issue, **(roues | choix.effet))
12            for choix in self.choix
13            if choix.condition(**roues)
14        )

Nous obtenons alors les probabilités suivantes.

$ ./bin/mpa.dragon proba
Probabilité de victoire : 0.010802469135802469
Probabilité de mi-victoire mi-défaite : 0.5648148148148149
Probabilité de défaite : 0.4243827160493827

Et comme on pouvait s’en douter, la probabilité de victoire (1,08 %) n’est pas égale à la proportions d’histoires victorieuses (1,16 %).

Chemins victorieux

Enfin, une fois le livre représenté comme un graphe (dans les parties précédentes), il devient relativement aisé de représenter toutes les histoires victorieuses possibles. Le résultat est du code \(\LaTeX\) qui, une fois compilé, donne le dessin suivant (en PDF).

../_images/dragon.png

Autres livres

Il me semble que les deux livres suivants au moins (La Découverte de l’Atlantide et L’Odyssée du Phobos) sont construits avec exactement la même mécanique, donc les résultats devraient être les même. D’autres livres ont commençé à introduire des mécaniques différentes, qui nécessiteraient donc d’autres calculs, mais pour la partie informatique au moins, le fonctionnement est suffisament proche, et le code suffisament générique pour que le travail requi ne soit pas insurmontable. Des volontaires ?