La rubrique de Yoann : L’algorithme à la rescousse de l’équilibrage
Les algorithmes et l'équilibrage.
- Le cas Carnimal, anecdote avec Ludo et l'équilibrage du premier joueur.
- Donald Knuth, “The Computer as Master Mind” https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf La référence historique du genre : A la fin des années 1970, Donald Knuth, immense figure de l’algorithmique, s’intéresse à Mastermind, un jeu de déduction où un joueur cache une combinaison secrète et l’autre essaie de la retrouver grâce à des retours partiels. Dans son article The Computer as Master Mind, il montre qu’un programme peut résoudre le Mastermind classique en cinq coups maximum.
- L'entropie
L’idée générale, c’est que l’entropie mesure l’incertitude.
Plus simplement :
quand tu ne sais presque rien, l’entropie est élevée quand tu as beaucoup réduit les possibilités, l’entropie est faible quand tu connais la réponse, l’entropie tombe à zéro
Dans un jeu de déduction, au début, tu as souvent énormément de combinaisons possibles. Donc beaucoup d’incertitude. Le rôle d’un bon coup, ce n’est pas juste d’être “fort”, c’est de faire baisser cette incertitude le plus possible.
C’est là qu’intervient l’idée d’un coup à forte entropie, ou plus précisément d’un coup qui apporte un fort gain d’information.
Le principe est le suivant : pour chaque action possible, tu regardes les différentes réponses que cette action pourrait provoquer, puis tu regardes à quel point chacune de ces réponses réduirait l’ensemble des possibilités restantes.
- Exemple du Wordle Beaucoup d’articles expliquent qu’un bon algorithme ne cherche pas juste “la bonne réponse”, mais choisit un mot qui réduit au maximum l’ensemble des réponses encore possibles grâce à l’entropie.
- Explication de l'algorithme de Got Five! On programme plusieurs robots qui peuvent jouer les uns contre les autres. Pour vulgariser comment fonctionne l'un de ses robots : Quand on initialise le robot, on lui donne juste le nombre de combinaisons possible. On commence par lui donner toutes les combinaisons qui existe dans le jeu. Puis il compare chacune d'elle avec ce qu'il voit. Si un des numéros est chez un autre joueur, il élimine la combinaison. Si l'ordre des couleurs n'est pas la même que l'ordre des couleurs de ses jetons, il élimine la combinaison.
- BGA l'enemi juré des game designers
Malheureusement il n’est pas toujours possible de faire des algorithme pour équilibrer des jeux. Ce genre d’histoire existe déjà dans le jeu de société moderne. Dans Tapestry, par exemple, les ajustements ont été si nombreux qu’un pack officiel entier de civilisations rééquilibrées a fini par voir le jour. Et dans Scythe, certaines combinaisons ont même été officiellement bannies. Ce qui montre bien qu’équilibrer un jeu, surtout asymétrique, n’est pas une sensation vague : c’est parfois un vrai problème de design qu’on doit mesurer, corriger, et assumer.
- L'équilibre et la sensation d'équilibre Soren Johnson dit quelque chose de très exploitable : il explique que “plus le hasard intervient tôt, meilleure est la perception d’équilibre”. L’idée est forte, parce qu’elle montre bien que le problème n’est pas seulement la justice mathématique, mais la manière dont elle est vécue. Un coup du sort en début de partie paraît plus acceptable qu’un coup du sort final, même si statistiquement c’est la même chose.