Équilibrer un arbre technologique de 4X avec un algorithme génétique

Dans l’article précédent, nous avons construit un moteur générique sans jamais le confronter à un vrai problème. Le voici devant son premier. Et plutôt que de lui demander comment bien jouer, nous allons lui faire concevoir le jeu.

Tout joueur de 4X¹ connaît l’arbre technologique : des bâtiments et des recherches reliés par des dépendances, chacun débloquant les suivants. Côté joueur, on le parcourt. Mais côté game designer, il faut le régler : à quel niveau de bâtiment débloquer telle recherche ? Combien doit coûter chaque palier ? C’est un travail d’équilibrage² interminable, fait à la main, par essais et erreurs.

Le problème : régler l’arbre, pas le parcourir

La structure de l’arbre est une décision de conception. Notre arbre offre deux objectifs de fin de phase que le joueur poursuit en parallèle : la Recherche avancée, au bout d’une branche scientifique (Laboratoire), et la Flotte de guerre, au bout d’une branche militaire (Mine de cristal puis Chantier spatial). Les deux sont alimentés par la même Centrale d’énergie, qui produit l’énergie du labo comme celle du chantier en plus de toute l’économie. Cette topologie est donnée.

graph LR
    M[Mine de métal] --> E[Centrale d'énergie]
    K[Mine de cristal] --> E
    E --> L[Laboratoire]
    L --> R[Recherche avancée]
    E --> S[Chantier spatial]
    K --> S
    S --> F[Flotte de guerre]

    E -. "énergie ≥ ?" .-> R
    L -. "labo ≥ ?" .-> R
    E -. "énergie ≥ ?" .-> F
    K -. "cristal ≥ ?" .-> F
    S -. "chantier ≥ ?" .-> F

    style M fill:transparent
    style K fill:transparent
    style E fill:transparent
    style L fill:transparent
    style R fill:transparent
    style S fill:transparent
    style F fill:transparent

Ce que l’on ignore, ce sont les bons nombres : à quels niveaux débloquer chaque objectif, et combien doit coûter chaque palier. Et c’est plus subtil qu’une simple durée. Si une branche est trop bon marché, elle devient un raccourci que tout le monde prend en premier, gratuitement : le choix de jouer scientifique ou militaire ne veut plus rien dire. Si l’autre est hors de prix, elle devient une corvée que personne ne touche. Un bon arbre veut l’inverse : que foncer sur un objectif le donne tôt, mais se paie par un retard sur l’autre, et qu’aucun style de jeu ne soit globalement supérieur. Personne ne peut vérifier de tête cet équilibre pour chaque jeu de réglages ; l’espace est bien trop vaste pour être exploré à la main.

Ce que le concepteur fixe, ce qu’il cherche

Distinguons clairement les deux mondes :

• Fixé par le concepteur : la structure du graphe (les dépendances) et le rythme voulu pour chaque style de joueur, c’est-à-dire le moment où il devrait atteindre chaque objectif.
• Cherché par le moteur : les seuils de déblocage des deux objectifs, et les coûts de chaque bâtiment.

Modéliser l’arbre et ses réglages

Une technologie connaît son nom et ses prérequis. Cette partie ne bouge pas : c’est la topologie.

// Tech décrit un nœud de l'arbre. Sa structure est FIXE : ce sont des
// décisions de conception, pas des paramètres à régler.
type Tech struct {
    Name      string
    Requires  []int   // indices des prérequis dans l'arbre
    BuildRate float64 // vitesse de construction propre au nœud
}

Tout ce que le moteur a le droit de toucher est rassemblé dans un second type, séparé : les réglages.

// Tuning regroupe les nombres que le moteur ajuste. C'est notre génome.
type Tuning struct {
    // seuils des deux objectifs
    ReqEnergieR, ReqLabo                  int // pour la Recherche avancée
    ReqEnergieF, ReqCristalF, ReqChantier int // pour la Flotte de guerre

    BaseCost []float64 // coût du premier niveau de chaque bâtiment
    Growth   []float64 // facteur de croissance géométrique du coût
}

Le coût d’un bâtiment croît géométriquement³ avec son niveau : chaque palier coûte Growth fois le précédent.

Le coût n’est pourtant pas le seul temps que paie le joueur. Comme dans un 4X tel que Stellaris⁴, monter un niveau prend aussi un temps de construction, et tous les nœuds ne se valent pas : un laboratoire est long à ériger, une mine bien plus rapide. Ce rythme propre à chaque nœud, le BuildRate, est une donnée de conception : il vit dans Tech, au côté de la topologie, et le moteur n’y touche pas. C’est là toute la séparation : la nature de l’arbre est gravée dans Tech, ses sensations de jeu vivent dans Tuning.

Le génome : les réglages de l’arbre

Notre génome est donc Tuning, un struct complet, et non plus une simple liste comme dans les exemples précédents. Le moteur s’en moque éperdument.

// Le génome n'a aucune contrainte de forme : G = Tuning.
best := genetic.New(genetic.Config[Tuning]{ /* ... */ }).Run(ctx)

C’est la promesse de l’article précédent qui se vérifie : G est un paramètre de type, le moteur ne suppose rien sur sa structure. Un struct de réglages est un génome aussi valable qu’une chaîne de caractères ou une route.

L’intention : équilibrer les chemins, pas les aplatir

Reste à dire au moteur ce que « bien réglé » veut dire. La tentation serait de viser une durée unique : « que tout le monde ait tout débloqué en une heure ». Mais ce serait une erreur de game design. Si tous les chemins mènent au même résultat au même moment, pourquoi choisir ? Un arbre vivant veut des choix qui se ressentent.

L’intention juste est donc plus fine. On confronte l’arbre à trois styles de joueur aux priorités opposées :

• Le chercheur fonce sur la branche scientifique (énergie, labo) et garde la flotte pour la fin.
• L’amiral fonce sur la branche militaire (cristal, chantier) et garde la recherche pour la fin.
• L’équilibré progresse sur les deux fronts à la fois.

Et le concepteur exprime, pour chacun, quand il devrait atteindre ses objectifs :

• un spécialiste obtient son objectif tôt, disons vers 45 min, et au même moment que l’autre spécialiste obtient le sien : aucune des deux branches n’est un raccourci, aucun style n’est globalement meilleur ;
• ce choix se paie : son objectif négligé tombe nettement plus tard, vers 80 min ;
• l’équilibré, lui, obtient les deux à un rythme moyen, vers une heure.

Mesurer un arbre : simuler le temps de jeu

Comment savoir si un jeu de réglages tient ce calendrier ? On ne le calcule pas, on le joue. Comme dans tout 4X, les ressources s’accumulent dans le temps à un rythme de production. Atteindre un niveau coûte alors du temps deux fois : il faut d’abord en réunir le prix, puis attendre sa construction, qui occupe le chantier le temps dicté par le BuildRate du nœud. La simulation rend donc, pour une stratégie, la minute où chaque objectif se débloque.

Concrètement, une partie tient en une boucle. Chaque minute, un chantier en cours peut s’achever, on encaisse la production, puis, si le chantier est libre, la stratégie choisit le prochain bâtiment et le lance. On note au passage la minute où chaque objectif tombe, et on rend la main quand les deux sont acquis.

// simulate joue une partie avec une stratégie et renvoie la minute où chaque
// objectif se débloque. Un seul chantier tourne à la fois : le temps mis sur
// une branche n'est pas mis sur l'autre.
func simulate(t Tuning, choose Strategy) (recherche, flotte int) {
    var g game // niveaux, ressources, et chantier en cours
    recherche, flotte = -1, -1
    for minute := 0; ; minute++ {
        if g.building >= 0 && minute >= g.doneAt { // un chantier s'achève
            g.level[g.building]++
            g.building = -1
        }
        if recherche < 0 && unlockedRecherche(g, t) {
            recherche = minute
        }
        if flotte < 0 && unlockedFlotte(g, t) {
            flotte = minute
        }
        if recherche >= 0 && flotte >= 0 { // les deux objectifs sont acquis
            return
        }
        g.res += income(g)                 // la production de la minute
        if g.building < 0 {                // le chantier est libre
            b := choose(g, t)              // le bâtiment que vise la stratégie
            if cost := nextLevelCost(t, b, g); g.res >= cost {
                g.res -= cost              // on paie et on lance la construction
                g.building = b
                g.doneAt = minute + buildMinutes(t, b, g)
            }
        }
    }
}

C’est ici que naît le compromis. Comme un seul chantier tourne à la fois, chaque minute passée à monter le laboratoire est une minute volée au chantier spatial. Foncer sur la recherche la donne tôt, mais repousse d’autant la flotte, qu’il faudra bâtir ensuite en partant de zéro. S’y ajoute le couplage de l’économie : une mine ne produit que ce que la centrale lui permet d’exploiter, si bien que sur-investir d’un côté ne rapporte rien sans l’énergie en face.

Une stratégie, dès lors, n’est qu’une fonction qui désigne le prochain bâtiment à monter, func(game, Tuning) int. Le chercheur renvoie d’abord les nœuds de la branche scientifique, l’amiral ceux de la branche militaire, l’équilibré le prérequis encore manquant le moins cher, toutes branches confondues. Trois fonctions, trois façons de parcourir le même arbre.

Reste à confronter l’arbre à toutes. Chaque style porte le calendrier que le concepteur veut pour lui ; evaluate rejoue sa partie et mesure l’écart à ce calendrier.

// Chaque style vise un calendrier : son objectif favori tôt, l'autre tard.
func evaluate(t Tuning) float64 {
    var dist float64
    for _, s := range strategies {
        rech, flotte := simulate(t, s.play)
        dist += ecart(rech, s.cibleRecherche) // recherche à l'heure voulue ?
        dist += ecart(flotte, s.cibleFlotte)  // et la flotte ?
    }
    return 1 / (1 + dist) // maximale quand chaque style tient son calendrier
}

// ecart : erreur RELATIVE au carré. Rater une cible de 45 min de quelques
// minutes pèse plus lourd que rater une cible de 80 min d'autant.
func ecart(atteint int, cible float64) float64 {
    e := (float64(atteint) - cible) / cible
    return e * e
}

La fitness ne récompense donc ni un style ni un autre, mais un arbre où chaque choix est viable et se paie : foncer sur un objectif s’achète par le retard sur l’autre, et aucune branche n’est un raccourci gratuit.

Brancher le problème sur le moteur

Comme toujours, il suffit de remplir la Config et de lancer le moteur.

cfg := genetic.Config[Tuning]{
    NewRandom: randomTuning,   // des seuils et coûts au hasard, dans leurs bornes
    Fitness:   evaluate,       // simule chaque style, mesure l'écart à son calendrier
    Crossover: crossTuning,    // mélange les réglages de deux parents
    Mutate:    mutateTuning,   // perturbe quelques seuils ou coûts

    PopulationSize: 200,
    MutationRate:   0.2,
    MaxGen:         500,
}

best := genetic.New(cfg).Run(ctx)

Croisement et mutation des réglages

Les deux opérateurs travaillent désormais sur des nombres. Le croisement mélange les réglages gène par gène : chaque seuil, chaque coût de l’enfant est hérité de l’un ou l’autre parent.

// crossTuning compose l'enfant en piochant chaque réglage chez un parent.
func crossTuning(a, b Tuning) Tuning {
    child := a
    if rng.Float64() < 0.5 {
        child.ReqLabo = b.ReqLabo
    }
    // idem pour les autres seuils, puis BaseCost et Growth bâtiment par bâtiment
    return child
}

La mutation déplace légèrement une valeur dans ses bornes : un seuil monte d’un cran, un coût gagne ou perd quelques pour cent. C’est elle qui permet d’explorer finement le voisinage d’un bon équilibrage.

// mutateTuning ajuste un réglage au hasard, sans sortir des bornes.
func mutateTuning(t Tuning) Tuning {
    t.ReqChantier = clamp(t.ReqChantier+pick(-1, +1), 1, maxLevel)
    return t
}

Un arbre où chaque choix se paie

Il ne reste qu’à lancer le moteur. Pour mesurer ce qu’il apporte, regardons d’abord l’arbre avant réglage, avec des seuils posés au jugé. Le résultat est cassé : la flotte se débloque en 13 minutes quelle que soit la façon de jouer, tandis que la recherche réclame plus de deux heures de labeur. La branche militaire est un raccourci gratuit que tout le monde rafle d’entrée, la branche scientifique une corvée que l’on subit. Choisir un style ne change rien : l’arbre ne propose pas de vrai choix.

Après réglage, l’arbre raconte enfin quelque chose. Chaque spécialiste obtient son objectif favori autour de 46 minutes, exactement au même moment que l’autre spécialiste obtient le sien : aucune branche n’est plus rapide que l’autre. Et ce coup d’éclat se paie : son objectif négligé ne tombe que vers 75 minutes. L’équilibré, lui, décroche les deux autour d’une heure, sans jamais briller ni traîner.

Le graphe montre le compromis ; le livrable concret, lui, ce sont les réglages. Voici l’arbre rempli des seuils que le moteur a trouvés.

graph LR
    M[Mine de métal] --> E[Centrale d'énergie]
    K[Mine de cristal] --> E
    E --> L[Laboratoire]
    L --> R[Recherche avancée]
    E --> S[Chantier spatial]
    K --> S
    S --> F[Flotte de guerre]

    E -. "énergie ≥ 10" .-> R
    L -. "labo ≥ 3" .-> R
    E -. "énergie ≥ 2" .-> F
    K -. "cristal ≥ 4" .-> F
    S -. "chantier ≥ 5" .-> F

    style M fill:transparent
    style K fill:transparent
    style E fill:transparent
    style L fill:transparent
    style R fill:transparent
    style S fill:transparent
    style F fill:transparent

Le détail est révélateur : pour caler la recherche, le moteur s’appuie surtout sur l’énergie, qu’il exige à un niveau élevé (≥ 10) tout en la rendant bon marché, si bien que ce sont les dix paliers à construire, plus que leur prix, qui occupent le joueur. La flotte, elle, se gagne sur le cristal et le chantier, énergie à peine effleurée. Aucun de ces réglages n’est intuitif pris isolément, mais ensemble ils font tomber les deux objectifs spécialisés à la même minute, et rendent les deux chemins également désirables.

Conclusion

Pour son premier problème concret, le moteur n’a pas eu à jouer : il a aidé à concevoir le jeu. La recette est pourtant celle de l’article précédent : un génome, quatre fonctions, et une fitness qui sait reconnaître une bonne réponse. Ici le génome décrit un réglage, et la fitness mesure non pas une performance mais une fidélité à une intention de design.

Le moteur s’est ainsi transformé en assistant d’équilibrage : on lui décrit le compromis voulu entre les chemins, il fait émerger l’arbre qui le rend vrai. Le moteur trouve les nombres ; il ne dit pas si le jeu est amusant. Cela, aucun algorithme ne le mesure : le ressenti reste un jugement de concepteur, et le moteur ne fait que lui épargner le tâtonnement chiffré. C’est un usage souvent négligé des algorithmes génétiques, et pourtant l’un des plus utiles en production de jeu.

Jusqu’ici, nous avons toujours travaillé sur une structure donnée. Dans le prochain article, nous franchirons une dernière marche : au lieu de régler un contenu existant, nous demanderons au moteur d’en générer un de toutes pièces.