Intelligence Artificielle et Total War Rome II

[yahiko]

La Recherche Arborescente Monte-Carlo dans l'IA de Campagne de TOTAL WAR: ROME II

En 2006, un algorithme appelé Recherche Arborescente Monte-Carlo (RAMC) a été découvert indépendamment par plusieurs chercheurs en intelligence artificielle. Il combine l'exhaustivité du parcours des arbres en largeur et les avantages de l'échantillonnage aléatoire en une seule technique de recherche qui est bien adaptée aux divers compromis à faire en terme de temps de calcul pour trouver des solutions optimales. Au fil des années, cet algorithme a été utilisé avec un grand succès pour divers jeux de société tels que le Go, surpassant toutes les autres approches.

Cette année, la RAMC entre enfin dans l'industrie des jeux AAA, en particulier grâce à TOTAL WAR: ROME II de Creative Assembly. A la Game/AI Conference 2014, qui a eu lieu il y a un mois à Vienne (ndt : juillet 2014), Tim Gosling et Piotr Andruszkiewicz ont expliqués plus en détail la façon dont l'algorithme a été mis en place et a été intégré dans l'IA de haut niveau de la campagne du jeu de stratégie basé sur le thème romain.

Arguments pour la mise en œuvre

Bien que l'algorithme RAMC est intéressant en soi, ce n'est pas une excuse suffisante à donner au producteur lorsque vous souhaitez l'appliquer à un jeu AAA. Pourquoi l'équipe IA de Creative Assembly a utilisé cette technique basée sur l’échantillonnage aléatoire ?

• L'Aléatoire dès la Conception - L'imprévisibilité est parfois la bienvenue dans une perspective de conception de jeux à des fins de rejouabilité. Le joueur ne veut pas toujours faire face aux mêmes compositions d'armée.
• Évitez les mauvaises décisions - La recherche stochastiques par force brute permet à l'IA d'éviter des erreurs plus efficacement dans la mesure où de nombreuses options différentes sont tentées et que les statistiques ne mentent pas. :-)
• Économie de Calculs - La RAMC est capable de bien tirer profit les calculs pour trouver un équilibre entre "explorer" de nouvelles solutions et "exploiter" au mieux les meilleures solutions connues. L'algorithme peut s'arrêter à tout moment.

Dans Total War: Rome II, la mise en œuvre de la Recherche Arborescente Monte-Carlo a été déployée progressivement, en commençant par un problème bien adapté puis élargi une fois ses preuves faites. Mais comment cela s'inscrit-il dans les grandes lignes de l'IA et du moteur du jeu ?

Architecture : Diviser pour Régner

L'IA de Campagne de Total War: Rome II est construite autour de l'observation que le jeu est insoluble si on considère toutes les interdépendances. Cela implique des centaines de régions, d'unités, des dizaines de bâtiments et la coordination de la diplomatie, des technologies, des compétences, les legs, les édits de chaque faction...

La solution est donc construite sous la forme de modules indépendants de prise de décisions qui communiquent entre eux :

1. Génération de tâches - objectifs de haut niveau, chacun avec les ressources nécessaires, sont créés comme la synthèse de plusieurs "générateurs" simples (non RAMC).
2. Allocation des ressources - attribuer des ressources (peu) à des tâches (beaucoup) en tenant compte de la diplomatie, de la stratégie et de l'allocation précédente (utilisant la RAMC).
3. Coordination des ressources - Un planificateur basé sur la RAMC détermine le meilleur ensemble d'actions compte-tenu des ressources et de leurs actions.

Pour accompagner ces modules, il existe un autre système qui fournit le contexte stratégique en interrogeant l'état du jeu et en préparant les informations pertinentes. En outre, d'autres systèmes sont conçus pour compléter la RAMC, comme un algorithme de budgétisation qui permet d'éviter les conflits.

Optimisations de la performance

Sur le plan de mise en œuvre, le code lui-même est écrit en C++. Des structures de données sont conçues avec soin pour une meilleure mise en cache (structurées en arbre), et un système d'allocation de mémoire de la pile est utilisé pour les nœuds afin de réduire les coûts d'allocation dynamique de mémoire. Ceci sont les meilleures pratiques pour la mise en œuvre de planificateurs ou de recherche de chemins, et l'utilisation de la RAMC à ces mécanismes est particulièrement impactante puisque des dizaines de milliers d'étapes de recherche peuvent être réalisées à chaque exécution (des limites strictes sont imposées sur la recherche).

Contrairement aux précédents opus de la franchise Total War, Rome II fait une plus nette distinction entre l'IA et le jeu grâce à des interfaces. Ceci permet plus facilement de préparer et de mettre en cache les données suivant les besoins. De plus, la RAMC fonctionne généralement sur un modèle simplifié du jeu plutôt que sur l'intégralité des structures de données.

La RAMC est appliquée à plusieurs endroits dans Total War: Rome II, et l'implémentation permet des réglages qui varient en fonction des données. Ceci est évidemment nécessaire pour permettre aux concepteurs d'équilibrer le jeu et de s'assurer que l'IA fonctionne encore après ! Cependant, l'IA nécessite encore des examens approfondis d'experts pour fonctionner de manière suffisamment efficace...

Connaissance du domaine

Alors que la RAMC fonctionne relativement bien (par rapport à d'autres algorithmes d'IA basés sur la recherche) sans connaissance du domaine, elle est beaucoup plus performante avec des indications supplémentaires. Total War: Rome II le fait de plusieurs façons :

• Élagage agressif - Les algorithmes de recherche peuvent être configurés pour ignorer des branches entières de l'arborescence du jeu. Dans ce cas, les règles spécifiques à l'IA de Campagne ont été codées en dur pour éviter les recherches inutiles.
• Éliminer les doublons - Le simple fait de supprimer les options similaires ou en double dans l'arbre du jeu peut constituer une forme avancée d'élagage. (Les résultats de recherches antérieures peuvent également être réutilisés).
• Restrictions partielles - Puisque la RAMC s'appuie également sur ce qu'on appelle des « politiques » pour guider son expansion dans l'arbre et pour la simulation aléatoire, elle peut également être influencée en ajustant les scores en virgule flottante - orientant ainsi la recherche dans certaines directions.

Bien sûr, toute l'architecture pour la RAMC dans Total War: Rome II est conçue avec les connaissances du domaine, de sorte que le principe du diviser pour régner est de loin le plus important pour optimiser les performances et les résultats du système.

source : aigamedev.com/open/coverage/mcts-rome-ii

Compléments :
* Arbre de Recherche : http://www.enseignement.polytechniqu...in4/node7.html
* Utilisation de la Recherche Arborescente Monte-Carlo au Hex : http://www.lamsade.dauphine.fr/~caze...rs/hex-ria.pdf

[Julius Theos]

Yahiko peut tu traduire en français s'il te plaît. Anglais un peu trop technique pour moi.

[yahiko]

Pour une seule personne, c'est un peu just. Mais bon, je vais voir ce que je peux faire.

[Julius Theos]

Peut être que d'autres sont intéressés mais trop timide pour le dire... Merci d'avance en tous cas.

[Mitri]

Intéressé par une traduction également! (s'il te plaît )

[cristofo]

Pareil !

[yahiko]

Traduction en cours messieurs

[yahiko]

Traduction faite.

[flavius1er]

Article très intéressant, merci yahiko pour la traduction

[Julius Theos]

Merci pour la traduction.