Modélisation et optimisation des décisions dans la conception de jeux

Mise en situation : c'est votre premier jour dans une entreprise qui conçoit un jeu de rôle massivement multijoueur (MMORPG) dans un univers fantastique. Vous êtes très excité de commencer à travailler sur ce projet, en développement depuis six mois déjà.

À votre arrivée, votre nouvelle patronne vous appelle par Skype, elle qui vient de partir pour deux mois de recherche intensive à Tahiti. Elle vous explique :

« Nous avons un problème : nous venons de repenser notre conception - c'est-à-dire que nous avons tout changé. Ça ne fonctionnait pas, alors nous avons pulvérisé notre travail précédent pour tout recommencer.

— Ça a l'air bien », répondez-vous, encore naïf. « Vous m'avez prévenu, lors de notre précédent entretien, que vous aviez fait beaucoup de changements.

— Ouais, c'est ça. Donc, en fait, le résultat, c'est que nous avons un problème avec les sorts du deuxième niveau pour les classes orientées magie. J'aimerais que vous y jetiez un coup d'œil. Nous avons, en tout, cinq classes capables de jeter des sorts. Cinq sorts ne sont toujours pas assignés, cinq aptitudes pourraient bien convenir à ces classes. J'aimerais que vous déterminiez quelle classe reçoit quel sort et quelle aptitude.

— Ça a l'air facile.

— Essayez donc. Voici les classes, sorts et aptitudes :

• classes : Mage de guerre, Magicien, Mage, Runologue, Sorcier ;
• sorts : Boule de feu, Tempête de glace, Vol de sort, Écoulement de vie, Main fracassante ;
• aptitudes : Régénération de mana, Endurance, Hâte, Maîtrise du feu, Maîtrise de la glace.

— Comment voulez-vous que je les assigne ?

— J'ai eu quelques retours de la part de l'équipe.

• Évidemment, Maîtrise du feu et de la glace devraient aller avec les classes qui ont les sorts de Boule de feu et de Tempête de glace, respectivement.
• Nous aimerions que le Mage de guerre ait la Régénération de mana.
• Nous ne savons pas encore quel sort le Magicien devrait avoir, mais nous sommes sûrs que Tempête de glace ne lui conviendrait pas.
• Nous voulons que le Runologue ait Écoulement de vie.
• Hâte ne serait pas approprié pour le Mage.
• Régénération de mana n'est pas vraiment compatible avec le sort Écoulement de vie.
• Nous voulons absolument que le Mage n'ait ni Boule de feu ni Tempête de glace.

— OK, boss. J'ai tout noté.

— Honnêtement, je ne sais même pas s'il y a une manière de faire l'assignation. Ça pourrait même ne pas être possible. Sinon, il pourrait même y avoir plusieurs manières d'assigner les sorts et les aptitudes. Je n'en sais rien, en fait. Qu'en pensez-vous ? »

Pensez un instant à ce problème. Comment le résoudriez-vous ? Combien y a-t-il de solutions ? Zéro, une, plusieurs ?

En fait, c'est un problème assez difficile. Cependant, contrairement à la plupart des problèmes de cette série, il peut être résolu à la main, c'est-à-dire trouver une solution faisable (ici, il n'y en a qu'une).

Les amateurs de jeux de logique peuvent reconnaître ce type de problème. La plus grande partie est de trouver les assignations correctes pour les objets - par exemple, trouver qui, parmi N personnes, a porté tel chapeau de telle couleur à une fête donnée.

Pour résoudre ce type de problèmes, il est courant de dessiner un ensemble de tableaux NxN, un pour chaque permutation de deux catégories. Ensuite, après avoir rempli autant que possible à partir des données de l'énoncé, il suffit de les résoudre par inférence, comme un Sudoku. Une assignation correcte sera désignée par un « o », une incorrecte par un « x » ; ensuite, des règles de base en logique peuvent servir à remplir le reste de la table.

Par exemple, chaque « o » dans une partie d'un tableau permet de remplir toutes les cellules dans la même ligne et colonne avec un « x », puisqu'il n'y a qu'une assignation possible. De même, si tout ligne ou colonne d'un sous-tableau NxN est rempli de « x » sauf pour une cellule, elle doit contenir un « o », puisque, par élimination, la cellule restante doit être l'assignation valide.

(Il y a quelques bons exemples en ligne, par exemple sur Printable Puzzles ; des techniques de résolution sont données sur d'autres sites, y compris en vidéo.)

Puisque ce problème consiste à assigner N classes à N sorts et N aptitudes, où N vaut cinq, il faudra un ensemble de trois tableaux 5x5, un pour chaque assignation (Classe, Sort), (Classe, Aptitude) et (Aptitude, Sort) possible. Voici par exemple ce à quoi cela pourrait ressembler dans le cas présent : un tableau (Classe, Sort) en haut, couleur pêche ; un tableau (Classe, Sort) en bas à gauche, en bleu ; un tableau (Aptitude, Sort) en bas à droite, en vert.

Pour initier le mouvement, la table ci-dessus est déjà remplie avec les contraintes de la description du problème. Un « O » est mis dans toute cellule où l'assignation est forcée, un « X » quand elle est interdite.

Dans ce cas, l'insistance de votre patronne que les aptitudes Maîtrise du feu et de la glace s'accordent les sorts de Boule de feu et de Tempête de glace est traduite par deux « O » dans le tableau vert aptitude-sort, en bas à droite : le premier pour la corrélation entre Maîtrise du feu et Boule de feu, l'autre pour Maîtrise de la glace et Tempête de glace. Le « X » en dessous et à droite interdit tout lien entre Régénération de mana et Vol de sort, à cause de son insistance sur l'inadéquation entre l'aptitude Régénération de mana et le sort Vol de sort pour une même classe. Cette table représente parfaitement toutes les contraintes imposées.

L'étape suivante est d'effectuer autant d'inférences que possible depuis ce point. Pour toute cellule avec un « O », aucune autre cellule dans cette ligne ou colonne du sous-tableau ne peut avoir de « O » : ces cellules sont donc marquées d'un « X ».

Par exemple, le « O » dans le sous-tableau en haut à gauche (couleur pêche) indique que le Mage de guerre doit avoir l'aptitude Régénération de mana : par conséquent, aucune autre classe ne peut avoir cette aptitude, le Mage de guerre ne peut avoir aucune autre aptitude.

Après avoir rempli ces premières inférences, la table ressemble à ceci :

C'est nettement mieux ! Maintenant, on peut voir les assignations impossibles, ce qui aide à saisir les possibilités restantes. On peut aussi utiliser quelques autres règles de logique de base pour compléter ce tableau. Par exemple, s'il y a quatre « X' dans une ligne ou une colonne et que la cinquième cellule dans cette ligne ou colonne est blanche, alors, par élimination, il doit y avoir un « O ». Un peu de chance a suffi pour remplir presque complètement la ligne Tempête de glace dans le tableau bleu des assignations sort-classe, en bas à gauche. Par conséquent, seuls le Mage de guerre et le Sorcier peuvent avoir le sort Tempête de glace : dès qu'une assignation est effectuée, l'autre peut l'être également.

L'inférence logique de base peut encore aider à remplir cette table. Par exemple, le Mage de guerre a Régénération de mana et le tableau sort-aptitude en vert, en bas à droite, marque d'un « X » l'intersection entre Régénération de mana et Tempête de glace ainsi que Vol de sort. Cela signifie que, dans le tableau sort-classe en bas à gauche (en bleu), la colonne du Mage guerrier peut être remplie de « X » pour Tempête de glace et Vol de sort. Par conséquent, par l'inférence du paragraphe précédent, mène à assigner la Tempête de glace au Sorcier.

Au lieu de finir l'exercice de la sorte, cet article explore une autre voie. Les lecteurs les plus curieux pourront continuer à remplir la table à la main (ce n'est pas difficile avec toutes ces indications), mais continuer à le détailler serait une perte de temps. Après tout, cette série parle d'optimisation automatique des décisions : les ordinateurs peuvent effectuer ce lourd travail de remplissage de tableaux.

Au lieu de trouver une solution à la main, Excel peut aider, en formalisant la chose sous la forme d'un problème de décision. Même s'il s'agit évidemment d'un cas très simple, il y a des choses à apprendre.

Idéalement, on pourrait importer cette table telle quelle dans Excel et lui laisser remplir les cellules avec des « X » ou des « O ». Malheureusement, le faire dans une seule table n'est pas facile, puisque le solveur a besoin qu'on lui spécifie les cellules de décision et qu'on y ajoute des contraintes dans des sections rectangulaires, ce qui ne correspond pas vraiment à une forme avec des cellules fixées à « X » ou « O ».

Une meilleure solution est de diviser le problème en trois tables : l'une pour les contraintes imposées, une deuxième pour les cellules à optimiser, la troisième pour combiner les deux.

Tout d'abord, la « table des contraintes », montrée ci-dessous. Elle a exactement la même forme que celle utilisée pour la résolution manuelle du problème de logique, sauf que les cellules contiennent le chiffre 1 pour indiquer un « O », un 0 pour « X », -1 signifie que la cellule n'a pas de valeur imposée par la définition du problème.

Ensuite, dans une nouvelle table, les variables de décision seront optimisées par le solveur. Initialement, toutes les cellules contiennent des 0 : le solveur mettra des valeurs à 0 ou à 1.

Finalement, la troisième table combine les deux précédentes : la « table des sorties combinées ». Elle combinera les valeurs de la table des contraintes et les cellules de décision. Chaque cellule utilisera la valeur de la table des contraintes s'il s'agit d'un 0 ou d'un 1, mais de la table des valeurs de décision pour un -1 (c'est-à-dire que cette valeur n'est pas imposée par la définition du problème). Chaque cellule dans cette table combinée servira comme valeur finale.

Des cellules spéciales serviront de compteurs, autour des bords du tableau, pour déterminer le nombre de cellules dans chaque ligne ou colonne de la table qui ont la valeur 1. Dans la solution finale, chaque combinaison ne devrait être assignée qu'une fois, c'est-à-dire exactement un 1 dans chaque ligne et colonne de chaque sous-tableau. Par conséquent, ces cellules de sommation devraient avoir une valeur finale de 1.

Les cellules grises - à gauche et à droite, en bas et en haut - effectuent les sommations, elles comptent le nombre de 1 dans la ligne ou la colonne la plus proche du sous-tableau le plus proche. Elles comptent le nombre de fois qu'un élément est utilisé. Une fois qu'une assignation convenable est trouvée, toutes ces cellules grises doivent avoir la valeur 1, pour indiquer qu'il y a exactement cinq assignations (Sort, Classe), cinq (Classe, Aptitude) et cinq (Sort, Aptitude), sans conflit aucun.

Les deux cellules en mauve, en bas à gauche, calculent les sommes, des colonnes pour la cellule de gauche, de la ligne des cellules de sommation pour l'autre. Une fois les tableaux remplis, chacune de ces deux cellules devrait avoir comme valeur 10, puisque chacune des dix cellules de sommation sur les colonnes ou lignes devrait avoir une valeur unitaire.

La cellule d'objectif, en organe, ne fait qu'additionner les valeurs des deux cellules mauves. Maintenant, il est temps de lancer le solveur.

• La cellule d'objectif est maximisée. Il aurait été possible d'imposer sa valeur à 20, puisqu'elle ne peut pas excéder cette valeur, mais cette technique est moins fiable que de simplement la maximiser, puisqu'elle ne peut pas dépasser la valeur de 20.
• Les cellules à faire varier sont les variables de décision, en jaune.
• Les contraintes binaires portent sur les cellules de décision. Imposer une telle contrainte s'assure que le solveur forcera chaque cellule à prendre une valeur de 0 ou de 1.
• Toutes les autres contraintes imposent l'égalité à 1 pour les quatre catégories de cellules de sommation de la table combinée. Ainsi, il n'y aura qu'une assignation de classe pour chaque sort, de classe pour chaque aptitude, de sort pour chaque aptitude.
• Le solveur sera « Évolutionnaire », puisque les autres ne peuvent pas traiter un problème de ce type.

Après cinq à dix secondes de calcul, la table combinée devrait ressembler à ceci :

Problème résolu, non ? En fait, non, pas exactement.

Les trois tableaux ont été résolus, mais indépendamment : ils n'ont pas forcément de sens tous ensemble. Le côté gauche de la table indique que le Mage de guerre a Régénération de mana et Tempête de glace, alors que le tableau sur la droite montre que le sort Tempête de glace devrait plutôt aller avec Maîtrise de la glace. De même, le Magicien a Hâte et Main fracassante, alors que le tableau sort-aptitude sur la droite montre que Main fracassante doit être associé à Régénération de mana.

En d'autres termes, cette solution est partielle : les trois sous-tableaux (Classe, Aptitude), (Aptitude, Sort) et (Classe, Sort) ont été traités séparément, alors qu'ils doivent l'être tous ensemble.

C'est un problème majeur. Il y a probablement moyen de le corriger, mais à l'aide de formules Excel bien plus complexes pour ajouter les contraintes pour la corrélation entre les trois tableaux. Ne serait-il pas plus tentant de représenter le problème plus simplement ?

Au lieu de construire une énorme table et de l'optimiser, il est possible de la représenter de manière plus simple. Après tout, chaque classe ne peut avoir qu'un sort et qu'une aptitude, il doit donc être possible de s'en sortir avec juste une entrée « Sort » et une autre « Aptitude » pour chaque classe. Ensuite, en maintenant les classes fixées et en optimisant le sort et l'aptitude pour chaque classe, le modèle ne contient plus que dix cellules de décision, au lieu des septante-cinq précédentes.

La première étape est de créer trois tableaux, listant les classes, sorts et aptitudes :

Ces trois tableaux donnent les correspondances numériques : les chiffres de 1 à 5 seront utilisés pour représenter les cinq classes, sorts et aptitudes. Ces tableaux indiquent la signification de chaque chiffre en fonction de son contexte.

Ensuite, un « tableau d'assignation » liste un sort et une aptitude pour chaque classe, chacune représentant un chiffre entre 1 et 5 qui correspond à une entrée dans les tableaux précédents.

Ce tableau montre les assignations courantes. Chaque ligne représente une classe (fixée) ; les colonnes correspondantes « Sort » et « Aptitude » représentent les assignations de sort et d'aptitude pour chacune des classes. Une fois que les valeurs optimales pour chacune de ces dix cellules de décision sont trouvées, les cinq assignations répondront aux contraintes du problème ; les colonnes « Sort » et « Aptitude » contiendront les chiffres de 1 à 5 dans un certain ordre.

Les cellules sur la gauche (dans la colonne « Classe ») ne sont pas colorées : elles ne seront pas optimisées, l'ordre des classes restera constant ; il suffira de déterminer les valeurs relativement aux classes.

Le tableau juste à sa droite (« Tableau d'assignation nommé ») se borne à montrer les noms des classes, sorts et aptitudes du tableau de gauche. Il contient les fonctions Excel qui traduisent les nombres du tableau d'assignation en descriptions textuelles - elles utilisent à leur tour les tableaux définis au début de cette section, de telle sorte que, par exemple, la première ligne indique que le Mage de guerre reçoit Boule de feu et Maîtrise du feu dans cette première assignation.

Ce tableau fournit une encapsulation propre pour les sous-sections (Classe, Sort) et (Classe, Aptitude) pour la matrice logique utilisée précédemment (les sous-tableaux pêche et bleu, du côté gauche). Par contre, la correspondance entre sort et aptitude n'est pas renseignée (le sous-tableau vert, à droite, dans la matrice logique). C'est un problème, puisque plusieurs contraintes sont formulées comme des correspondances entre sorts et aptitudes, sans mentionner les classes. Avec ce tableau d'assignation, il n'est donc pas possible d'imposer des contraintes de cette forme sans tester chaque paire dans la liste - ce qui deviendrait vite lourd.

Une meilleure solution est de définir un nouveau tableau qui effectue la correspondance entre un sort et une aptitude à l'aide d'un nombre : les sorts correspondent aux chiffres des dizaines, les aptitudes aux unités.

De cette manière, il est facile d'imposer des contraintes qui cherchent, implicitement à travers tout le tableau, si une combinaison sort-aptitude existe ou pas.

Il faut aussi s'assurer que, lors de l'optimisation des cellules de décisions, chaque sort et chaque aptitude ne soit assignée qu'une seule fois. Cette opération serait facile si Excel disposait d'une fonction imposant que toutes les cellules d'une plage donnée aient des valeurs différentes ; malheureusement, elle n'existe pas. Le solveur dispose d'un type de contrainte « dif » qui est supposé imposer ce type d'unicité, mais ses particularités sont telles qu'il est à peu près inutile dans ce cas.

Par conséquent, pour s'assurer que toutes ces valeurs soient présentes, dans n'importe quel ordre, un nouveau tableau « Détecteur d'unicité » est créé ; chaque ligne détecte la présence d'un chiffre particulier dans les colonnes « Sort » et « Aptitude » du tableau d'assignation. Ce test est effectué par la fonction MATCH() d'Excel, entourée d'un ISNA() puisque MATCH() renvoie la valeur spéciale #N/A quand la valeur cherchée n'est pas trouvée.

Finalement, un dernier tableau contiendra les contraintes. L'approche est assez particulière : une cellule correspond à chaque contrainte, avec 1 comme valeur si la contrainte est satisfaite, 0 sinon. Chacune de ces cellules (grises, dans le tableau ci-dessous) teste une condition dans la description du problème.

Quelques remarques sur ces contraintes :

• les contraintes liées aux correspondances (Classe, Sort) et (Classe, Aptitude) sont triviales : elles utilisent simplement la fonction IF() d'Excel pour tester une condition donnée dans le tableau d'assignation (les cellules de décision) ;
• les contraintes liées aux correspondances entre sorts et aptitudes utilisent plutôt le tableau sorts-aptitudes défini plus tôt. Comme dans le compteur d'unicité, elles utilisent la fonction MATCH() pour tester la présence ou l'absence d'une combinaison donnée dans ce tableau, entourée d'un appel à ISNA() au cas où la valeur n'est pas trouvée ;
• finalement, les deux dernières cellules s'assurent que chaque aptitude et sort n'est utilisé qu'une fois. Ce test s'effectue simplement en sommant la colonne correspondante du compteur d'unicité créé plus haut. Si la colonne « Sort » du tableau d'assignation contient les chiffres de 1 à 5 dans n'importe quel ordre, alors la colonne « Sorts » du compteur d'unicité devrait avoir ses cellules toute à 1, c'est-à-dire un total de cinq (tout comme les aptitudes).

Finalement, la cellule orange d'objectif en bas additionne les contraintes satisfaites. Cet objectif est différent de ceux habituellement utilisés : au lieu de minimiser ou de maximiser une valeur, il s'agit de vérifier que toutes les contraintes sont satisfaites. Toute solution qui satisfait toutes les contraintes est « correcte », il suffit donc de compter le nombre de contraintes satisfaites et de l'utiliser comme fonction objectif.

Avec toutes ces valeurs intermédiaires définies, il est temps de lancer le solveur.

La cible est la cellule objectif, en orange, comme toujours, en tentant de maximiser sa valeur (qui ne peut jamais dépasser dix). Les cellules à changer sont celles du tableau d'assignation, les cellules de décision. Finalement, trois contraintes indiquent que les cellules du tableau d'assignation doivent être des entiers entre un et cinq compris.

Finalement, la méthode de résolution doit être « Évolutionnaire » ; enfin on peut cliquer sur Résoudre. Le processus peut prendre du temps, puisque le problème est loin d'être trivial à résoudre. Il peut prendre trente à soixante secondes pour que la cellule d'objectif prenne une valeur de dix, indiquant que toutes les dix contraintes sont satisfaites.

Voici donc la solution finale, la seule correcte :

Et voilà ! Ces tableaux montrent les valeurs numériques et textuelles de la solution finale. Vous pouvez prendre le deuxième et l'envoyer à votre patronne : votre journée est finie, vous pouvez rentrer chez vous !

Le classeur Excel est disponible. Chaque section correspond à une feuille de calcul différente.

Votre conclusion ? « Bien, c'était long, absurde. Le problème était évidemment facile, de la logique à peine déguisée. Cette situation n'arriverait jamais en pratique. Surtout avec toutes ces feuilles de calcul compliquées, pour une solution qu'on pourrait obtenir à la main en à peine dix minutes ! »

C'est vrai. Totalement vrai.

L'objectif n'est pas de déterminer l'assignation des sorts et des aptitudes à des classes, mais bien de développer un modèle de décisions qui pourrait se révéler utile dans d'autres cas. Le voyage est bien plus important que la destination - et cette forme de voyage est souvent rencontrée par les concepteurs, sous une forme ou l'autre.

L'épisode prochain plongera dans un exemple bien plus pratique et montrera comment une approche similaire a été utilisée pour concevoir les tours dans City Conquest.

L'auteur souhaiterait remercier le professeur Christopher Thomas Ryan, Assistant Professor of Operations Management à la University of Chicago Booth School of Business, pour sa participation à la révision de ce texte.

Cet article est une traduction autorisée de Decision Modeling and Optimization in Game Design, Part 5: Class Assignment Problems, écrit par Paul Tozour. Le traducteur souhaiterait remercier Alexandre Laurent pour sa relecture.