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

Le premier article de cette série a présenté l'exemple d'un jeu nommé SuperTank. Le deuxième s'est occupé des concepts de base dans la modélisation des décisions et a montré un exemple simple utilisant le solveur d'Excel.

Maintenant, il est temps d'appliquer ces techniques dans le cas de SuperTank et de prouver qu'elles donnent une solution rapide et simple pour SuperTank. Un petit rappel : ce jeu propose de conduire un tank personnalisable, un SuperTank, similaire à celui montré ci-après.

Chaque tank peut avoir autant d'armes que le joueur le désire, à condition de les choisir parmi les cinq types présentés dans ce tableau.

Un tank peut porter cinquante tonnes d'armes, le joueur dispose de cent crédits à dépenser. Le tank ne possède que trois « emplacements critiques », utilisés par des armes comme les mégaroquettes ou les ultralasers.

La feuille de calcul pour cet exemple est disponible.

L'objectif est de choisir les armes qui maximisent les dommages causés par le tank, tout en restant dans les limites de cinquante tonnes, cent crédits et trois emplacements critiques. Par hypothèse, ce tableau encapsule tout ce qu'il faut savoir : les facteurs comme la portée des armes, le temps de réarmement et la précision n'ont aucune importance ou sont déjà inclus dans les dommages causés par chaque arme.

Pour optimiser cette situation, il faut d'abord entrer les données ci-dessus dans une feuille de calcul. Ensuite, juste comme ci-dessous, une deuxième table contiendra cinq cellules de « quantité » qui indiqueront le nombre d'armes de chaque type.

Pour le moment, ces cellules contiendront une valeur unitaire, juste afin de tester que le reste de la feuille de calcul fonctionne correctement, mais il s'agit bien des cellules de décision : le solveur d'Excel cherchera les meilleures valeurs. Ce fait est indiqué par leur couleur, selon les conventions expliquées dans le deuxième article. À la droite des cellules de quantité, d'autres cellules calculeront le produit entre les décisions et les dommages, les poids, les coûts et les nombres de slots critiques utilisés. Ainsi, chaque ligne de cette table indique les dommages, les coûts, les poids et les slots utilisés pour les armes de chaque catégorie.

Finalement, une nouvelle section déterminera la somme des quantités, des poids, des coûts et des emplacements critiques de la table ci-dessus et les comparera aux valeurs maximales admissibles de l'énoncé du problème.

Selon les conventions précédemment expliquées, les cellules bleues au-dessus sont les critères déterminés de l'énoncé du problème. Les cellules en gris sont des calculs représentant les totaux de la table des quantités. Finalement, la cellule orange représente le dommage total du tank.

Avant de continuer et de résoudre ce problème, il est intéressant de prendre un peu de temps pour rendre la feuille de calcul plus facile à utiliser : Excel autorise le renommage des cellules. Ces sept cellules importantes peuvent donc avoir des noms plus explicites. Ce n'est pas strictement nécessaire, mais, sur le long terme, ce genre d'améliorations tend à rendre la feuille de calcul bien plus lisible, avec des noms comme « MaxCriticalSlot » plutôt que « $F$21 ». À cette fin, il suffit de sélectionner une cellule et de changer le nom dans la case en haut de la feuille de calcul, juste à gauche de la barre de formule.

La dernière étape est de laisser le solveur d'Excel trouver la solution. Il est accessible dans l'onglet « Données » : la case « Analyse » devrait présenter un bouton « Solveur ». S'il n'est pas visible, il faut l'activer. Dans le bouton Office, les options d'Excel proposent une catégorie « Compléments » : dans la zone « Gérer », sélectionner « Compléments Excel », s'assurer que la case « Complément Solveur » est bien cochée.

Dans les paramètres, la « Cellule cible » sera la cellule orange, l'objectif qui devra être maximisé. Sous « Cellules variables », il faut sélectionner les cellules de décision, en jaune, dans la colonne « Quantité » du deuxième tableau. En dessous, quelques contraintes seront nécessaires.

• Les cellules de décision devraient avoir une valeur entre zéro et un maximum raisonnable (par exemple, cinquante, même si ce nombre est une limite largement supérieure aux besoins). Il est aussi essentiel d'ajouter une contrainte d'intégrité sur chaque cellule de décision. Il n'est pas possible d'avoir une quantité fractionnaire de n'importe quelle arme : puisque le solveur considère chaque variable comme réelle sauf contre-ordre, il essayera sans l'ombre d'un doute ces valeurs fractionnaires à moins de le lui interdire.
• Les totaux de coûts, de poids et d'emplacements critiques doivent également être inférieurs ou égaux aux maxima présentés dans l'énoncé du problème. Dans la capture d'écran de la boîte de dialogue, ces contraintes sont très lisibles, grâce aux noms donnés à ces cellules.

Il est maintenant temps d'appuyer sur le bouton « Résoudre » et, après une petite attente, le solveur aura rempli les quantités pour leur valeur optimale :

• cinq mitrailleuses ;
• trois roquettes ;
• deux mégaroquettes ;
• un laser ;
• un ultralaser.

Cette combinaison donne un dommage total de quatre-vingt-trois et utilise exactement toutes les ressources disponibles (cinquante tonnes, cent crédits, trois emplacements critiques). Cette solution optimale ne change pas avec le temps laissé au solveur : même en remettant les valeurs précédentes et en optimisant à nouveau ou en changeant le nombre aléatoire utilisé dans les options, les valeurs obtenues ne changent pas. Il n'est pas absolument sûr qu'il s'agisse de la solution optimale, mais le solveur utilisé semble incapable de l'améliorer après plusieurs passes : il s'agit probablement du vrai optimum et non d'un maximum local.

Problème résolu !

Ce qui est intéressant à propos de cette solution, ce n'est pas seulement que le problème a été résolu bien plus rapidement qu'à la main : il est facile de changer les calculs pour tester les armes les plus utiles avec différentes options. Il est donc relativement facile de voir et de mesurer les effets de divers changements pour chacun de ces paramètres : si le concepteur souhaite ajouter un autre modèle de tank (plus léger, plus lourd, avec un autre nombre d'emplacements critiques, etc.), il peut le faire très facilement.

Toujours en modifiant ces paramètres, le concepteur peut « sentir » l'utilité relative de chaque type d'arme. Il peut aussi rapidement identifier les armes trop utiles ou pas assez, celles qui n'ont pas un prix approprié pour leur poids ou les dommages infligés, etc.

À nouveau, ce genre d'outils est prévu pour explorer l'espace de conception bien plus rapidement qu'à la main : pour toute décision incrémentale sur la conception, qu'elle change les paramètres des armes ou du tank, qu'elle ajoute de nouvelles armes ou modèles de tank, qu'elle ajoute de nouveaux paramètres (comme une limite sur la taille), ces outils esquissent rapidement les ramifications potentielles d'un tel changement.

Plus explicitement, en changeant le coût maximal à nonante-neuf unités (au lieu de cent), la nouvelle solution donnée par le solveur donne une charge fortement différente :

• aucune mitrailleuse ;
• deux roquettes ;
• trois mégaroquettes ;
• trois lasers ;
• aucun ultralaser.

Cette charge infligera des dommages très légèrement inférieurs (quatre-vingt-deux au lieu de quatre-vingt-trois), mais aura une constitution très différente.

Pour un coût maximal à cent un ou cent deux, la configuration sera très semblable au premier cas, avec des dommages qui restent à quatre-vingt-trois unités : les résultats peuvent varier, car il existe plusieurs charges optimales dans ces cas. Par contre, pour un budget de cent trois unités, la configuration change à nouveau radicalement :

• une mitrailleuse ;
• quatre roquettes ;
• deux mégaroquettes ;
• aucun laser ;
• un ultralaser.

Les dommages infligés seront de quatre-vingt-quatre. Ce cas est intéressant, puisque la charge est très différente des autres cas.

Le résultat est surprenant : le choix optimal d'armes dépend fortement des paramètres du tank et peut changer du tout au tout avec une très légère variation. Cette observation donne d'autres informations utiles : tous les types d'armes sont utiles au moins dans deux des trois configurations, les roquettes et mégaroquettes sortant clairement du lot. Cela semble indiquer que les cinq armes sont bien équilibrées, dans le sens qu'elles sont toutes utiles, par rapport aux autres, tout en restant uniques.

Cette sorte de modélisation et d'optimisation donne un excellent moyen de traverser rapidement le voisinage de solutions. Pour certains types de problèmes, cette recherche donne une bonne visibilité sur les stratégies de jeu dominantes et des failles qui seraient difficiles ou impossibles à trouver par d'autres méthodes.

Les deux exemples précédents (le niveau de taxes et le tank) pourraient indiquer qu'il n'est possible d'appliquer ces techniques qu'aux cas présentant des chiffres. Rien ne pourrait être plus faux ! Comme l'exemple suivant le prouvera, de nombreux cas peuvent bénéficier de l'optimisation d'éléments de conception qui n'apparaissent pas comme des nombres à l'utilisateur… ou n'impliquent pas de nombre du tout !

De même, le lecteur pourrait conclure que la modélisation des décisions ne s'applique qu'aux décisions que les joueurs prennent dans un jeu. Cette affirmation est incorrecte : dans certains cas, il est aussi possible de modéliser et d'optimiser les décisions en tant que concepteur.

Mise en situation : vous travaillez sur un jeu de rôle massivement multijoueur dans un environnement spatial, le concepteur en chef vient vous trouver l'air inquiet, voire préoccupé. « Nous sommes en train de repenser le secteur Oméga », vous dit-il, « mais il nous pose problème : nous avons prévu de placer des téléporteurs dans cette zone, sauf que nous ne pouvons nous mettre d'accord sur leur emplacement.

— Combien de téléporteurs ?

— Rien n'est encore décidé : probablement trois, mais ça pourrait être deux ou quatre. Nous ne savons pas encore. »

Il tend alors une carte qui ressemble à celle-ci.

« Qu'est-ce ?

— C'est une carte du secteur Oméga. Au moins, les systèmes solaires que le joueur peut visiter dans ce quadrant. Nous aimerions que tu détermines les cases qui devraient contenir des téléporteurs.

— OK, quelles sont les règles pour leur placement ? Peut-on avoir un téléporteur dans le même quadrant qu'un système solaire ?

— Nous aimerions minimiser la distance entre tout système solaire et le téléporteur le plus proche. Oui, tu peux les mettre dans le même quadrant qu'un système solaire : il s'agit juste de petits téléporteurs, ils peuvent se mettre n'importe où. N'oublie pas, nous n'avons pas encore décidé du nombre, regarde ce qu'il se passe pour deux, trois ou quatre téléporteurs. »

Comment formuleriez-vous ce problème, le résoudriez-vous ?

Pour commencer, il est intéressant de définir les cellules de décision. Les quatre téléporteurs seront nommés « A », « B », « C » et « D ». Chacun n'est rien de plus qu'un jeu de coordonnées (x, y) sur la carte du secteur ci-dessus. Il faudra également un moyen de définir le nombre de téléporteurs actifs, ce qui fait une cellule de plus, de telle sorte que le téléporteur D ne sera utilisé que pour quatre téléporteurs, le C uniquement pour trois ou plus.

En dessous, une table donnera la distance de chaque système solaire au plus proche téléporteur.

Les coordonnées de chaque système solaire de la carte sont présentes à gauche en bleu. Chaque système est représenté par une ligne, simplement reprise de la carte précédente.

À la droite de ces informations est présente la distance à chacun des quatre téléporteurs, en appliquant simplement le théorème de Pythagore :

=SQRT(($B14-Ax)^2+($C14-Ay)^2)

(Ne vous inquiétez pas : les expressions mathématiques du reste de cette série ne seront pas plus compliquées que cela !)

Les coordonnées de chaque système solaire sont données dans les colonnes en bleu, celles de chaque téléporteur (qui correspondent aux cellules « Ax » et « Ay », dans le cas du téléporteur A, dans la formule ci-dessus) des cellules de décision en jaune.

Finalement, le minimum de ces valeurs est sélectionné dans la dernière colonne, en utilisant la fonction MIN(). Cette colonne est finalement sommée en bas : cette somme est la cellule d'objectif.

Dans la capture d'écran précédente, toutes les cellules de distance au téléporteur D ont la valeur nonante-neuf. La raison se cache derrière la cellule du nombre de téléporteurs au début de la feuille de calculs, utilisée pour faire varier le nombre de téléporteurs considérés. Si seuls deux téléporteurs sont autorisés, la valeur nonante-neuf sera utilisée pour les téléporteurs C et D. Ce mécanisme s'assure que chaque système solaire ignore tout téléporteur superflu lors du calcul de la distance au téléporteur le plus proche dans le cas de deux ou trois téléporteurs.

La dernière étape est de lancer le solveur, comme précédemment.

La cellule d'objectif est la somme en bas de la colonne des distances au téléporteur le plus proche. Contrairement aux autres exemples, il s'agit de minimiser la distance minimale de tous les systèmes solaires aux téléporteurs, non de la maximiser.

En dessous, les cellules de décisions correspondent aux huit cellules jaunes pour les coordonnées des quatre téléporteurs. Dans la zone réservée aux contraintes, les conditions imposent que les coordonnées soient des valeurs entières comprises entre zéro et douze. L'utilisation de ces contraintes d'intégrité est simplement due au fait que la solution doit préciser une cellule dans laquelle le téléporteur doit être, mais ces contraintes pourraient être retirées pour un emplacement dont les coordonnées sont des nombres réels.

En définissant le nombre de téléporteurs à deux, trois ou quatre et en lançant le solveur chaque fois, les résultats obtenus sont les suivants.

Ces informations peuvent être remontées au concepteur en chef pour montrer les emplacements optimaux en fonction du nombre de téléporteurs (deux, trois ou quatre). Voici ces emplacements sur une quatre, montrés en vert, pour deux, trois et quatre téléporteurs, respectivement.

La feuille de calcul afférente est disponible.

« OK, c'est très bien », répond votre chef, son visage dépeignant une certaine anxiété. « Hum… En fait, j'ai oublié de te dire que certaines de ces étoiles sont habitées par des ninjas de l'espace. Nous aimerions que les systèmes avec ces ninjas soient éloignés des téléporteurs, pour éviter que le joueur se sente trop menacé.

— Oh. Ça ne fait que saboter mon travail.

— Ouais. Aussi, certains systèmes ont deux colonies au lieu d'une, il est donc deux fois plus important pour les téléporteurs d'être proches des téléporteurs. Ou deux fois plus important d'en être éloignés si le système contient deux colonies de ninjas. Voici ce à quoi ressemble la carte, maintenant. »

« Chaque nombre négatif est une colonie de ninjas. Le système avec le chiffre 2 possède deux colonies humaines, celui avec -2 a deux colonies de ninjas. Où mettre les téléporteurs dans ce cas ?

— Dis-moi que tu as au moins décidé s'il va y avoir deux, trois ou quatre téléporteurs, maintenant.

— Je crains que tu n'aies pas encore de telle chance. »

Pour résoudre ce nouveau problème, une solution élégante est d'ajouter une nouvelle colonne à la table pour représenter les pondérations de la carte, les « multiplicateurs ». Cette valeur sera alors multipliée par la distance au téléporteur le plus proche.

Par cette modification, cependant, cette altération change la signification des valeurs obtenues : il ne s'agit plus vraiment d'une distance, puisque, dans le cas de systèmes infestés de ninjas, il s'agit de son opposé. Il est plutôt question d'un « score » généralisé.

De cette manière, le score est maintenant une valeur agrégée : en le minimisant, le solveur s'assurera d'être aussi près que possible des systèmes colonisés et aussi loin des systèmes ninjas.

Les résultats obtenus sont les suivants.

Les emplacements des téléporteurs sont radicalement différents du cas plus simple, avant l'introduction des ninjas.

La feuille de calculs pour cette version améliorée du téléporteur est disponible au téléchargement.

Le modèle de décision a donné une solution très rapide à ce problème non trivial et a pu très vite s'adapter à d'autres besoins.

Ce problème est une instance particulière de la classe des « problèmes de placement d'installations », très étudiés dans le domaine de la gestion opérationnelle. Cette classe a aussi un potentiel d'application important dans la conception de jeux et de niveaux, tout en étant très facilement implémentable dans Excel.

L'article suivant appliquera la modélisation et l'optimisation des décisions à un problème ardu d'équilibrage de jeu pour de multiples classes de personnages dans un système de combat entre joueurs (PvP) pour un jeu de rôle simplifié.

L'auteur souhaiterait remercier Robert Zubek et Jurie Horneman pour leurs retours sur cet article. Le professeur Christopher Thomas Ryan, Assistant Professor of Operations Management à la University of Chicago Booth School of Business, a également participé à la révision de ce texte.

Cet article est une traduction autorisée de Decision Modeling and Optimization in Game Design, Part 3: Allocation and Facility Location Problems, écrit par Paul Tozour. Le traducteur souhaiterait remercier Alexandre Laurent et Wachter pour leur relecture.