Développement de l'IA en utilisant l'exemple du jeu Dicey Dungeons

Pendant environ un mois, je résolvais l'un des problèmes techniques les plus difficiles de mon nouveau jeu, Dicey Dungeons - une IA améliorée pour la version finale du jeu. C'était un travail assez intéressant, et une grande partie était nouveau pour moi, alors j'ai décidé d'écrire un peu à ce sujet.

Pour commencer, je vais vous expliquer: je ne suis pas un expert en théorie des ordinateurs, mais juste un de ceux qui ont suffisamment étudié la programmation pour créer des jeux vidéo, après quoi j'ai terminé mes études en ne saisissant que ce dont j'avais besoin. Habituellement, je peux résoudre mes problèmes par moi-même, mais un vrai programmeur n'approuverait probablement pas mes décisions.

J'ai essayé d'écrire un article à un niveau d'abstraction suffisamment élevé pour que les idées de base soient claires même pour les non-programmeurs. Mais je ne suis pas un expert dans de telles choses, donc mes explications de la théorie peuvent être erronées. Écrivez-moi à ce sujet dans les commentaires de l'original, je serai heureux de faire des changements!

Eh bien, commençons par expliquer la tâche!

Défi

Si vous n'avez pas joué à Dicey Dungeons, je vais vous parler brièvement du jeu: il s'agit d'un RPG avec construction de deck, dans lequel chaque ennemi dispose d'un ensemble de cartes d'armes qui effectuent différentes actions. De plus, ils lancent des dés! Ensuite, ils mettent ces dés en armement pour infliger des dégâts, ou créer divers effets de statut, ou guérir, ou se défendre contre les dommages, etc. Voici un exemple simple de la façon dont une petite grenouille utilise une grosse épée et un petit bouclier:


Un exemple plus compliqué: ce Jack de tous les métiers a une clé, ce qui vous permet de mettre deux dés ensemble (c'est-à-dire que 3 + 2 donneront 5 et 4 + 5 donneront 6 et 3). Il a également un marteau (Hammer), qui impose un effet de «choc» au joueur, si vous lui en appliquez six, et un tireur de pois (Pea Shooter), qui fait peu de dégâts, mais il a un «compte à rebours», puis là, il est valable pour plusieurs mouvements.


Autre complication importante: le jeu a des effets de statut qui modifient les capacités des adversaires. Le plus important d'entre eux est Shock, qui désactive aléatoirement les armes; le choc peut être supprimé en utilisant un cube supplémentaire dessus, et "Burn", qui met le feu aux cubes. Pendant que les cubes brûlent, ils peuvent être utilisés, mais chaque utilisation coûtera 2 points de vie. C'est ce qu'un bricoleur intelligent fait quand je mets le choc et la brûlure sur toutes ses armes et cubes:


Bien sûr, il y a beaucoup plus dans le jeu, mais pour avoir une idée générale, cela suffit.

Alors, notre tâche: comment amener l'IA à choisir la meilleure action pour son mouvement? Comment peut-il savoir lequel des cubes brûlants éteindre, quel cube utiliser pour soulager les chocs et lequel conserver pour les armes importantes?

Comme avant

Pendant longtemps, l'IA dans Dicey Dungeons n'avait qu'une seule règle: il a regardé toutes les armes de gauche à droite, a déterminé le meilleur cube qui pouvait être utilisé sur lui, puis l'a utilisé. Cela a très bien fonctionné, mais il y avait des exceptions. J'ai donc ajouté de nouvelles règles.

Par exemple, j'ai surmonté le choc en examinant toutes les armes qui n'étaient pas soumises au choc, et en choisissant le cube que j'utiliserais dessus lorsque le choc a été retiré, puis j'ai marqué ce cube comme «réservé» pour l'avenir. J'ai travaillé avec des cubes en train de brûler comme ceci: j'ai vérifié si j'avais assez de santé pour les éteindre, et j'ai choisi aléatoirement de le faire.

J'ai ajouté règle par règle pour tout ce que je pouvais imaginer, et en conséquence j'ai eu une IA qui semblait fonctionner! En fait, il est étonnant de constater à quel point cette imbrication de différentes règles s'est révélée - l'IA dans Dicey Dungeons peut ne pas toujours prendre la bonne décision, mais elle a toujours été au moins acceptable. Du moins pour un jeu encore en développement.

Mais au fil du temps, le système consistant à ajouter constamment de nouvelles règles a commencé à se fissurer. Les gens ont découvert des exploits qui ont fait que l'IA se comporte bêtement. Par exemple, avec la bonne approche, vous pourriez déjouer l'un des boss afin qu'il n'attaque jamais le joueur. Plus j'ai ajouté de règles pour corriger la situation, plus des choses étranges ont commencé à se produire - certaines règles sont entrées en conflit avec d'autres, des cas limites ont commencé à apparaître.

Bien sûr, l'une des solutions consistait à ajouter de nouvelles règles, à considérer chaque tâche une par une et à créer de nouvelles constructions if pour les traiter. Mais je pense que de cette manière, j'ai simplement écarté la vraie solution au problème. La limitation du système était qu'il n'inquiétait qu'une seule question: "Quel sera mon prochain déménagement?" Elle n'a jamais regardé vers l'avenir et n'a pas essayé de suggérer ce qui pourrait venir d'une combinaison intelligente particulière.

J'ai donc décidé de recommencer.

Solution classique

Essayez de rechercher des informations sur l'IA pour les jeux, et probablement la première chose que vous rencontrerez une solution classique - la création d'un algorithme minimax . Voici une vidéo sur son utilisation dans le développement de l'IA pour les échecs:


L'implémentation de minimax est la suivante:

Tout d'abord, nous créons la version la plus simple et abstraite de notre jeu, dans laquelle il y a toutes les informations nécessaires pour un moment précis du jeu. Nous l'appellerons un tableau . Dans le cas des échecs, ce sont les positions actuelles de toutes les pièces. Dans le cas de Dicey Dungeons, il s'agit d'une liste de dés, d'armes et d'effets de statut.

Ensuite, nous créons une fonction de valeur qui mesure la qualité du jeu pour une configuration de jeu spécifique, c'est-à-dire pour un plateau particulier. Par exemple, aux échecs, une planche sur laquelle les pièces sont situées dans leur position d'origine est évaluée à 0 point. Le plateau sur lequel vous avez mangé le pion de votre adversaire a une valeur de 1 points, et le plateau sur lequel vous avez perdu votre propre pion a une valeur de -1 points. Et le plateau sur lequel nous avons maté l'adversaire sera évalué à un nombre infini de points, ou quelque chose comme ça!

Ensuite, à partir de ce tableau abstrait, nous simulons tous les mouvements possibles que nous pouvons faire, ce qui nous donne de nouveaux tableaux abstraits. Ensuite, nous simulons l'achèvement de tous les mouvements possibles sur ces tableaux, et ainsi de suite, autant d'étapes que vous le souhaitez. Voici une excellente illustration d'une solution similaire de freecodecamp.org :


Nous créons un graphique de tous les mouvements possibles que les deux joueurs peuvent effectuer et nous leur appliquons une fonction de valeur pour évaluer le déroulement du jeu.


Et en cela, Dicey Dungeons diffère de minimax: minimax est issu de la théorie mathématique des jeux, il est conçu pour trouver la meilleure série de coups au monde où l'adversaire cherche à maximiser son score. L'algorithme est appelé ainsi car il minimise les pertes du joueur lorsque l'adversaire joue afin de maximiser ses gains.

Mais que se passe-t-il dans les donjons Dicey? En fait, je me fiche de ce que fait mon adversaire. Pour que le jeu soit passionnant, il suffit que l'intelligence artificielle fasse des mouvements logiques - pour déterminer la meilleure façon d'appliquer les dés aux armes, afin que la bataille soit juste. En d'autres termes, seul "max" est important pour moi, sans "mini".

Autrement dit, pour que les donjons AI Dicey fassent un bon mouvement, il me suffit de créer ce graphique des mouvements possibles et de trouver le tableau qui a le score le plus élevé, puis d'effectuer les mouvements menant à ce point.

Le mouvement facile de l'ennemi

Eh bien, passons aux exemples! Regardons à nouveau la grenouille. Comment peut-elle décider quoi faire ensuite? Comment sait-elle que l'action choisie est la meilleure?


En fait, elle n'a que deux options. Placez 1 sur l'épée large et 3 sur le bouclier, ou faites le contraire. Elle décide évidemment qu'il vaut mieux mettre 3 au lieu de 1. Mais pourquoi? Parce qu'elle a étudié tous les résultats possibles:


Si vous mettez 1 sur l'épée, nous obtiendrons 438 points. Si vous en mettez 3, nous obtenons 558 points. Super! Donc, j'obtiens plus de points en plaçant sur l'épée 3, le problème est résolu.

D'où viennent ces lunettes? Le système d'évaluation de Dicey Dungeons prend actuellement en compte les aspects suivants:

• Dégâts: Le facteur le plus important est de 100 points pour chaque point de dégâts infligés.
• Poison: un effet de statut important que l'IA considère presque aussi important que les dégâts - 90 pour chaque poison.
• Création d'autres effets d'état: par exemple, choc, brûlure, affaiblissement, etc. Chacun d'eux coûte 50 points.
• Effets de statut bonus: ajouter au joueur lui-même des effets de statut positifs, tels que la défense et autres, coûte 40 points chacun.
• Utilisation d'armes: l' utilisation de tout type d'arme coûte 10 points, car si rien d'autre ne réussit, l'IA doit simplement essayer de tout utiliser.
• Réduction du compte à rebours: pour activer certains types d'armes (par exemple, pour Pea Shooter), le montant total sur les dés est juste suffisant. Par conséquent, l'IA reçoit 10 points pour chaque point de compte à rebours qu'elle réduit.
• Points sur les dés: l' IA obtient 5 points pour chaque point inutilisé sur les dés, soit 1 coûte 5 points et 6 coûte 30 points. Ceci est fait pour que l'IA préfère ne pas utiliser de cubes que vous n'avez pas besoin d'utiliser, de sorte que ses mouvements deviennent très similaires aux humains.
• Durée: l' IA perd 1 point par tour, donc les mouvements longs ont légèrement moins de valeur que les mouvements courts. Ceci est fait de sorte qu'en présence de deux mouvements qui sont par ailleurs de valeur égale, l'IA choisit le plus court.
• Traitement: il ne coûte qu'un point pour un point de santé restauré, car même si je veux que l'IA considère cela comme important, je n'ai pas vraiment surveillé ma santé. Il y a toujours des choses à faire et surtout!
• Points bonus: ils peuvent être ajoutés à n'importe quel mouvement pour forcer l'IA à faire quelque chose qu'il n'aurait jamais fait autrement. Utilisé très modérément.

Et enfin, il y a deux cas particuliers - si la cible attaquée manque de santé, cela coûte un million de points. Si la santé se termine avec l'IA, cela coûte moins un million de points. Cela signifie que l'IA ne se tuera jamais accidentellement (par exemple, en payant le dé avec une santé très faible), ou qu'elle ne manquera jamais un mouvement dans lequel elle peut tuer le joueur.

Ces chiffres ne sont pas idéaux - prenez, par exemple, les problèmes ouverts actuels: 640 , 642 , 649 , mais ce n'est pas très important. Même des chiffres approximativement précis suffisent pour stimuler l'IA à faire plus ou moins correctement.

Mouvements plus difficiles de l'ennemi

Le cas de la grenouille est si simple que même mon terrible code peut comprendre toutes les options en seulement 0,017 seconde. Mais alors la situation devient plus compliquée. Regardons à nouveau l'exemple de Jack of all trades.


Son arbre de décision est «un peu» plus délicat:


Malheureusement, même dans des cas relativement simples, une explosion de complexité se produit assez rapidement. Dans ce cas, dans notre graphique, nous obtenons 2 670 nœuds qui doivent être examinés, et cela prend beaucoup plus de temps que dans le cas d'une grenouille - peut-être une ou deux secondes.

Cela est largement dû à la complexité combinatoire - par exemple, peu importe laquelle des deux nous utilisons pour soulager le choc initialement, l'algorithme considère cela comme deux solutions distinctes et crée un arbre complet de solutions de branchement pour chacune. En conséquence, nous obtenons une branche dont la duplication est complètement inutile. Il existe également des problèmes de combinaison similaires lors du choix des blocs à échanger, pour éliminer les chocs des armes et la procédure pour leur utilisation.

Mais même si nous trouvons et optimisons de telles branches inutiles (ce que je fais dans une certaine mesure), il y aura toujours un point où la complexité de toutes les permutations possibles de solutions conduira à des arbres de décision énormes et lents, dont l'évaluation prendra un temps infini. C'est donc le premier problème sérieux de cette approche. En voici un autre:


Clé principale. Divise le cube en deux.

Ce type important d'armes (et similaires) provoque des problèmes d'IA car le résultat de son utilisation est incertain . Si j'en mets six, je peux en obtenir cinq et un, ou quatre et deux, ou peut-être deux triplets. Je ne le saurai pas avant de le faire, il est donc très difficile de créer un plan qui en tiendra compte.

Heureusement, Dicey Dungeons a une excellente solution à ces deux problèmes!

Solution moderne

La méthode Monte Carlo Tree Search (MCTS) est un algorithme probabiliste de prise de décision. Ci-dessous, une vidéo un peu étrange, qui explique néanmoins très bien le principe de la prise de décision basée sur la méthode de Monte Carlo:


En fait, au lieu d'ajouter tous les mouvements possibles au graphique, les SCTM vérifient les séquences de mouvements aléatoires, puis suivent ceux qui se sont avérés meilleurs. Grâce à une formule appelée Upper Confidence Bound, il peut par magie déterminer quelles branches de l'arbre de décision sont les «plus prometteuses»:


Au fait, j'ai pris cette formule d'un article très utile sur la recherche d'arbres en utilisant la méthode Monte Carlo . Ne me demandez pas comment ça marche!

Ce qui est étonnant avec les SCTM, c'est que pour trouver la meilleure solution, nous n'avons généralement pas besoin de faire une recherche stupide de tout, et nous pouvons utiliser le même système de simulation de plateau / déplacement abstrait que dans minimax. Autrement dit, nous utilisons en quelque sorte les deux algorithmes. C'est exactement le schéma que j'ai utilisé dans Dicey Dungeons. Tout d'abord, elle essaie de terminer un déploiement complet de l'arbre de décision, ce qui ne prend généralement pas beaucoup de temps et conduit au meilleur résultat. Mais si l'arbre semble trop grand, nous recommençons à utiliser les SCTM.

MCTS a deux fonctionnalités très intéressantes qui sont parfaites pour Dicey Dungeons:

Premièrement, la méthode fonctionne idéalement avec incertitude. Puisqu'elle est effectuée encore et encore, en collectant des données de chaque exécution, je la laisse simplement simuler des mouvements non définis, par exemple, en utilisant une clé principale, de manière naturelle, et après de nombreuses exécutions, la méthode crée une plage de points assez correcte obtenue à la suite de ce mouvement.

Deuxièmement, il peut me donner une solution partielle. En fait, lorsque vous travaillez avec les SCTM, vous pouvez effectuer autant de simulations que vous le souhaitez. Théoriquement, si elle est effectuée à l'infini, elle convergera exactement vers les mêmes résultats que minimax. Cependant, ce qui est plus important pour moi, c'est que je peux utiliser les SCTM pour obtenir une bonne solution en un temps de réflexion limité. Plus nous effectuons de recherches, meilleure sera la «solution», mais dans le cas de Dicey Dungeons, souvent quelques centaines de recherches suffisent, ce qui prend une petite fraction de seconde.

Sujets connexes intéressants

C'est ainsi que les ennemis de Dicey Dungeons décident comment vous tuer! Je veux ajouter ce système à la prochaine version du jeu v0.15!

D'où viennent les graphiques que j'ai montrés, y compris sur Twitter:


Je les ai créés en écrivant un exportateur pour GraphML , un format de fichier graphique open source qui peut être lu par de nombreux outils différents. (J'ai utilisé l'excellent YEd , que je recommande fortement.)

Une partie de la solution à ce problème était de permettre à l'IA de simuler des mouvements, ce qui en soi est un puzzle intéressant. En conséquence, j'ai implémenté un système de script d'action. Maintenant que les adversaires utilisent différents types d'armes. ils exécutent ces petits scripts:


Ces petits scripts sont exécutés par l'analyseur hscript et l'interpréteur d'expression basé sur haxe. Cette partie était difficile à mettre en œuvre, mais l'effort a porté ses fruits: cela rendait le jeu super pratique pour créer des mods. J'espère qu'après la sortie du jeu, les gens pourront utiliser ce système pour développer leurs propres armes, c'est-à-dire qu'ils pourront ajouter au jeu presque tout ce qu'ils peuvent imaginer. De plus, comme l'IA est suffisamment intelligente pour évaluer toute action qui lui est transférée, les ennemis seront en mesure de comprendre comment utiliser les armes modifiées que les joueurs créeront!