Calcul d'indices de non-linéarité de livres-jeux

[Alendir]

Pour les contacts, il me semble que Maddog avait rédigé une thèse sur les livres-jeux mais il ne m'a pas répondu.

Merci pour vos conseils (H.D.V tu as fait prépa aussi??)

[H.d.V]

Yep, je suis passé par le rouleau compresseur de la prépa (en PC).

[Jehan]

J’ai un peu de retard sur le sujet, n’ayant pas eu beaucoup de temps pour y réfléchir jusque là, mais j’y vais quand même de ma contribution.

Si je devais définir la linéarité, je me baserais sur les variables suivantes :

— Nombre de paragraphes ;
— Nombre de chemins possibles (cp) ;
— Nombre de chemins victorieux (cv).

Le ratio cv / cp donne une idée de l’aspect one-true-path du bouquin. Ça peut être intéressant car la définition de « linéarité » ne me paraît pas si claire que ça. Est ce qu’un livre jeu est non-linéaire s’il possède beaucoup de chemins ou s’il possède beaucoup de chemins victorieux ? Comme le faisait remarquer Caïthness, les OTP ne se classent pas dans le même groupe selon la définition que l’on choisit.

Ensuite, pour définir la linéarité en tant que telle, je me baserais sur le nombre moyen de chemins sur lesquels se trouve un paragraphe. C’est à dire que pour chaque paragraphe, je calcule le nombre de chemins qui passent par lui et je fais ensuite une moyenne. Exemple avec le graphe suivant :


    1
   / \
  2   3
 / \ / \
4   5   6
 \ / \ /
  7   8
   \ /
    9


Six chemins possibles : [1, 2, 4, 7, 9] ; [1, 2, 5, 7, 9] ; [1, 2, 5, 8, 9] ; [1, 3, 5, 7, 9] ; [1, 3, 5, 8, 9] ; [1, 3, 6, 8, 9]. Les paragraphes 1 et 9 se retrouvent sur les six, les paragraphes 2, 3, 7 et 8 se retrouvent sur trois chemins, les 4 et 6 sur un seul et le 5 sur quatre. En moyenne, un paragraphe se retrouve sur : (6 × 2 + 3 × 4 + 1 × 2 + 4 × 1) / 9 = 37 % des chemins. Plus ce chiffre est haut, plus l’aventure est linéaire.

Évidemment, sur un graphe aussi petit que celui de l’exemple, ce pourcentage n’a pas une grande signification. Mais sur un livre-jeu, je pense qu’il s’agit d’une mesure intéressante. Bien sûr, il faut un programme pour faire ce calcul sur un graphe aussi grand que celui d’une AVH.

Une moyenne n’étant rien sans son écart-type, il faudrait associer les deux. L’écart-type permettrait de distinguer les aventures à fort maillage, où les différents chemins sont très entrecroisés, de celles qui possèdent un certain nombre de chemins assez indépendants les uns des autres.

Enfin, il y a sûrement d’autres indices intéressants à mesurer, comme la longueur (en nombre de paragraphes) moyenne d’un chemin, et peut-être essayer de jouer sur la distinction entre chemins et chemins victorieux. Je sens confusément qu’il y a un truc à creuser dans cette direction, sans trop parvenir à deviner quoi.

Voilà, j’espère que ça te donnera quelques idées.

PS : Je me suis bien sûr basé sur le cas le plus simple d’un graphe sans boucle et n’ai pas tenu compte des aspects non structurels d’un livre-jeu, comme les mots de passe, les objets, les combats, etc.

[Alendir]

Ce que tu proposes est très pertinent Jehan, notamment pour le deuxième indice, même si tes calculs sont faux et incomplets à la fois, désolé (enfin je crois, j'ai l'esprit un peu embrumé et en prépa on ne sait plus calculer mais quand même), par contre l'idée de base est excellente, tu as trouvé mon indice préféré. En théorie je t'aurais pas fait la remarque parce que c'est certainement un erreur d'étourderie comme notre prof de math en fait souvent et qu'on corrige automatiquement mais vu que je pète pas la forme c'est peut-être moi qui me trompe donc je préfère vérifier...

Bon déjà
(6 × 2 + 3 × 4 + 1 × 2 + 4 × 1) / 9 est différent de 37 ou de 0,37, ça vaut 3,33... ça correspond bien sûr au nombre de chemins moyen auquel chaque paragraphe fait partie.
là je me dit que tu as dû oublié de diviser par le nombre de chemins possibles (qui permet d'obtenir le pourcentage) donc 3,33/6=0,55...
Bon après on multiplie par 100 pour avoir un beau pourcentage et on obtient qu'un paragraphe se trouve en moyenne sur 55,55% des chemins.


Pour résumer ton idée:

Indice définissant la variété de lecture d'un livre-jeu: on cherche à déterminer dans quel pourcentage de chemins se trouve en moyenne chaque paragraphe:

Méthode:

-on affecte à chaque paragraphe la valeur correspondant au nombre de chemin différents auxquels ils font partie
-on somme ces coefficients et on les divise par le nombre total de paragraphe pour obtenir le nombre moyen de chemins sur lesquels se trouve un paragraphe
-on divise le tout par le nombre de chemins possibles

soit:
(somme du nombre de chemins différents auxquels font partie chaque paragraphe) / (nombre de chemins possibles*nombre de paragraphes)

Plus ce nombre est bas, plus les relectures sont variées, donc il y aura non-linéarité.


Et ton idée sur l'écart-type est bien pensée aussi.


Voilà bon j'ai à peine eu le temps de me relire j'espère que ce n'est pas moi qui me suis trompé ^^

[Jehan]

Non, non, c’est bien moi qui me suis trompé. : ) J’ai commencé par griffonner tous ces calculs sur plusieurs feuilles et je me suis probablement emmêlé les pinceaux en les recopiant dans mon message (surtout pour l’oubli de la division par le nombre de chemins possibles !). Enfin bon, au moins j’ai réussi à faire passer mon idée, même si c’était un peu confus. ^^; Content qu’elle te plaise.

[Alendir]

Disons que comme indice de linéarité général c'est le must je pense, et en plus c'est réalisable assez facilement algorithmiquement, on peut adapter facilement l'algorithme qui compte le nombre de chemins possibles pour savoir aussi combien des chemins passent par un paragraphe (il suffit d'enregistrer chaque chemin et de tester chaque paragraphe pour voir s'il le contient).
Sinon je pense aussi diviser la définition de linéarité en plusieurs sous-définitions pour créer des indices spécifiques à chaque côté, chaque signification de la linéarité. Par exemple, un indice qui testerait la diversité du livre, le fait de ne pas repasser souvent aux mêmes endroits que ceux de la première lecture, et un qui testerai la liberté octroyée au joueur (par exemple dans quelle mesure il peut s'éloigner d'un noeud principal), mais ces deux sous-définitions sont quand mêmes un peu liées et je ne sais pas si on peut créer des indices séparés. Enfin celui que tu proposes mesure bien la diversité, voire la liberté avec la mesure de l'écart-type, et ce sous un seul indice, donc ma théorie ne marche peut-être pas, et de toutes façons je ne vois pas comment définir mathématiquement ces deux indices qui devraient être vraiment indépendants pour être calculés séparément (ou pas en fait, ça doit être possible quand même).
Donc je vais continuer de bosser sur la définition de linéarité et si je n'arrive pas à la diviser, et bien j'aurai quand même un certain nombre d'indices à utiliser.

Bon j'ai rédigé 8 pages sur le sujet, je vous enverrai le tout quand j'en aurai l'occasion.
J'ai quand même un peu peur que ça passe moyen le jour du concours. Mon prof est ok mais c'est un fan de JDR donc pas super objectif... enfin bon c'est original et il y a quand même pas mal de math (théorie des graphes, même si je l'utilise pas beaucoup en fait, algorithmes...) et puis ça a un côté recherche qui peut plaire. En plus, ça peut avoir un côté pratique: si on découvre au final que non-linéarité rime (en partie bien sûr) avec succès des livres-jeux (en regardant les indices des oeuvres du yaztromo), ce qui est loin d'être exclu puisque les lecteurs aiment la non-linéarité et que les auteurs chevronnés arrivent mieux à écrire de manière non-linéaire que les autres, ça pourra servir aux éditeurs pour sélectionner les livres-jeux à publier sans même avoir à les lire :p
Bon je pars dans un délire et puis de toutes façons, les livres-jeux ça les intéresse plus, les gueux !

[Alendir]

Bon l'intro est marrante mais je la changerai pour le concours ^^

[Alendir]

Bon, il me reste 2-3 bugs à régler, mais grosso modo, mon algorithme en PHP fonctionne: si on lui envoie un livre-jeu (via un formulaire, et on peut même laisser l'introduction), il vous sort les liaisons de chaque paragraphes sous forme de listes mapple (vu que c'est ce logiciel que je vais utiliser pour calculer les indices, il faut que je récupère des données compatibles et directement exploitables), et en prime il permet aussi de tracer le graphe du livre-jeu (avec un copier-coller vers graphviz, quand même).
Donc je suis assez fier de moi, c'est cet algorithme qui me faisait le plus peur (difficultés techniques, notamment pour que l'ordinateur sache reconnaître les paragraphes). Je pense que l'autre ne posera pas trop de problèmes.
Donc pendant les vacances, je pense que vous aurez les résultats de mes calculs (et tous les graphes que vous voulez, avec même les PFA couleur rouge sang ).

[Alendir]

Mis à part un microscopique détail, l'algorithme fonctionne à merveille, je l'ai vérifié avec le graphe de mon AVH (que j'avais déjà tracé en entrant les données à la main), c'est exactement le même (mis à part les couleurs là les PFA -de victoire ou de défaite- sont tous en rouges donc indifférenciés).
La taille de l'AVH n'est pas un problème; mon PC sature au bout de 300§ mais je peux le faire bout par bout et au final reconstituer le code du graphe (enfin il me semble).
Le problème viendra de Graphviz qui ne gère pas les AVH de plus de 400 ou 500§ je crois. J'ai espoir que pour le calcul d'indice de linéarité, je n'aurai pas de telle limite de puissance.
Bon la suite d'ici quelques semaines.

[Segna]

La cité des pièges est passée sans pb sous graphviz, mais pas la couronne des rois.
A mon avis, c'est plus un problème de limite de récursivité qu'autre chose.
Même si, il est vrai, tu as intérêt à lui mettre de la RAM, sinon, Graphviz plantera avant. Sinon, très bonne idée, les PFA en rouge .

[Alendir]

Quelques graphes (de livres-jeux traduits) :    
   

http://www.heberger-image.fr/images/10483_Glace.jpeg.html
   

(Ceci dit une erreur a toujours pu se produire, donc si la présence d'un PFA vous paraît bizarre ou quoi que ce soit, prévenez-moi... après tout je n'ai vérifié que sur L'Or Venu de l'Est -qui fait tout de même 170).



Par ailleurs, j'aimerai que ceux qui ont lu les AVH de cette année (pour le Yaz ou même les traductions) m'envoient par MP un petit classement en fonction de leur linéarité. Par exemple, si vous trouvez que X est plus linéaire que Y, mettez:
X>Y

Vous n'êtes aucunement obligés de classer toutes les AVH, si vous avez des doutes, ne les mettez pas. ça me permettra ensuite de voir si mes indices de linéarité sont pertinents... Il faut simplement classer au moins deux AVH. Merci

---

Notez que c'est certainement le mode neato (deuxième graphe) qui donne la meilleure idée de la linéarité puisqu'il fixe la longueur des flèches; les amas peuvent certes signifier un noeud, mais surtout ils signifient que beaucoup de paragraphes sont reliés entre eux !

[Alendir]

Pour y voir plus clair dans le mode neato, le premier paragraphe est mis en jaune (oui ça le rend pas non plus très clair...) :
   

[Alendir]

ça n'a rien à voir, mais je ne pense pas qu'il soit non plus nécessaire de créer un nouveau topic pour ça... Depuis quelques mois, il y a eu une révolution dans le monde des fractales. Un pianiste anglais passionné d'informatique et de math a réussi à créer des fractales en 3D (habituellement elles le sont en 2D). Joli.

http://www.skytopia.com/project/fractal/mandelbulb.html

[VIK]

Beau et interessant. Tout pareillement, je ne vais pas ouvrir un topic juste pour un post. Voici un copier coller de mon post sur gamebook, qui pourrait intéresser certains amateurs de statistiques:

Je regarde l'intérieur de mon exemplaire d'occasion du Sorcier en VO : "the Warlock of Firetop Mountain" que j'ai reçu d'un lot il y a plusieurs mois et j'y découvre quelque chose d'assez original.

LE STAKHANOVISTE DE LA KABBALE :

Il se trouve qu'à côté du numéro du § 1, il y a marqué un petit 1 au crayon à papier .
Dans ce §, on a le choix entre 71 et le 278, respectivement marqués 2 et 3.

Au § 2 (marqué 4 au crayon), on a le choix entre le 16 et le 269, respectivement marqués 5 et 6.

Le § 3 est marqué 7, etc ...

Je tourne les pages avec fébrilité, et ça continue ! Il y a quelqu'un qui a compté et totalisé tous les § et tous les renvois de § du livre !

Et ça continue jusqu'au dernier §, le fameux 400.
Devinez combien de numéros au total ont été inscrits par ce Stakhanoviste ?

=> le § 400 est affublé d'un 9999 au crayon à papier !!!

Je ne sais pas ce qu'a voulu démontrer notre stakhanoviste amateur de la kabbale, mais il s'est donné tant de mal à inscrire 9999 fois un n° que je me refuse à les effacer. C'est un collector !

Une version informatisée du livre devrait pouvoir calculer ça en 2 temps 3 mouvements.
Je me demande le but de tout ceci...

[Alendir]

Supposons qu'il y a quatre renvois par paragraphes en moyenne : cela fait 400*4. En comptant en plus les numéros de paragraphes, cela fait 400 de plus. Je vois mal comment il arrive à 9999 au lieu d'environ 2000... La kabbale vaincue par les maths...