IA-t-il un wargamer dans mon PC ? Le cas de Crusader Kings II

Henrik Fåhraeus a rejoint Paradox en 2001 où il a fait ses premières armes sur les scripts de Europa Universalis II. Il est désormais un chef de projet et game designer accompli à qui l’on doit la seconde version de Crusader Kings. Un jeu qui mélange donc subtilement gestion, diplomatie et conquêtes militaires, dans le cadre peu fréquent sur PC du Moyen-âge. En outre, une fois n’est pas coutume, le jeu propose au joueur non pas d’incarner une nation mais une famille, qui devra prospérer et intriguer au fil des siècles afin d’asseoir son pouvoir.
Depuis sa sortie en février 2012 Crusader Kings 2 a bénéficié d’un important suivi et de nombreux add-ons et DLC, contribuant à étoffer son contenu, tant au niveau des graphismes ou de la bande-son, qu’en ce qui concerne les fonctionnalités. Henrik Fåhraeus nous livre ici sa vision du cas de l’intelligence artificielle dans les jeux de stratégie.

1/ Pour vous, qu’est-ce réellement qu’une IA dans un wargame ? Une suite de scripts et d’algorithmes, bien sur, mais encore ?

Des algorithmes, des scripts mais aussi une bonne dose de chance ! Il ne faut absolument pas négliger l’importance que joue l’aléatoire. Introduit aux bons endroits, en bonne quantité, il permet de donner à l’humain l’impression qu’il affronte une “intelligence”.

2/ Pour un wargame PC, quels sont différents modèles d’IA ? Et les différents outils logiciels pour les développeurs ?

Les titres issus du Paradox Development Studio utilisent une programmation basée sur des modèles reposant sur une structure d’agents intelligents hiérarchisée spécialement adaptée aux jeux de stratégie en temps réel. Il existe d’autres modèles mais je pense que la plupart des jeux de ce genre emploient des systèmes similaires. Dans nos jeux chaque joueur informatique s’appuie sur une IA principale subdivisée en éléments secondaires, capables de prendre en charge les composants primordiaux du jeu (commerce, armées, flottes, bâtiments, etc.). Elles sont par ailleurs capables d’activer ou désactiver d’autres IA chargées de taches plus spécifiques, comme le transport de troupes vers une province, le blocus de ports, etc. En parallèle nous avons une IA stratégique à même d’analyser les situations idoines courantes, comme celles souhaitées à plus long terme ; c’est un aspect que j’avais originellement programmé pour In Nomine, une extension de Europa Universalis III. Autrement nous n’utilisons aucun outil externe pour développer nos IA.

3/ Que permet sommes toutes pour les développeurs la puissance de calcul d’un PC moderne, récent (+/- 2 ans), et de bonne qualité ? 3D mise à part, quelles autres contraintes techniques y a-t-il ?

Nous utilisons évidemment une puissance de calcul bien supérieure dévolue aux algorithmes comparé à ce dont nous disposions il y a onze ans quand je suis arrivé chez Paradox.  Hearts of Iron III nécessite beaucoup plus de puissance, notamment pour le calcul des déplacements (path finding), que ce que demandait  Hearts of Iron, et de loin. Cependant, déjà à cette époque, les possibilités des ordinateurs imposaient des limites, ce qui est toujours d’actualité. Par exemple, je pourrais probablement améliorer considérablement l’IA tactique dans nos jeux en allouant davantage de ressources au calculs de déplacements (au détriment d’autre chose – NDLR). Quoi qu’il en soit, la majorité des faiblesses relatives à l’IA n’a rien à voir avec les contraintes liées au processeur mais est simplement due à la complexité importante que représente le codage de cette même IA (comment évaluer la priorité de différentes situations et envisager leur évolution à long terme ?).

4/ Certains types de wargames, donc de conflits historiques, ou d’échelles de jeu, sont-ils plus appropriés aux IA (actuelles) ? Si oui, lesquels ?

Je dirais que le contexte du jeu ou son aspect historique ne sont pas significatif dans ce cas mais que l’important réside dans la manière dont vous déterminez le niveau d’abstraction, ainsi que dans la modélisation des règles. Cependant il est vrai que les jeux couvrant un conflit particulier posent d’autres problèmes. Pour Hearts of Iron, par exemple, nous voulions que l’IA adopte un comportement historiquement convainquant, ce qui impliquait d’éviter qu’elle ne s’écarte trop de règles strictes que nous avions fixées. Voilà bien l’un des problèmes du recul inhérent que nous avons sur une situation avec les jeux d’histoire.

5/ Selon votre expérience dans le développement de jeux, quel(s) défi(s) technique(s) avez-vous rencontré ? Lesquels avez-vous pu surmonter ? Lesquels sont-ils encore une barrière ?

Concernant la programmation d’IA il me semble que les problèmes principaux récurrents ont trait à l’allocation des ressources limitées (par exemple : comment vais-je utiliser mon argent ?) ; le calcul des déplacements (gros impact CPU) ; l’aspect action / réaction (quand dois-je prendre l’initiative et quelle importance accorder à l’attitude des autres joueurs ?) ; l’indécision (jauger les actions sur la base de valeurs repères), ainsi que la planification à long terme. Parmi tout cela je dirais que les parties actions / réaction et planification sur le long terme représentent les défis majeurs à relever.

6/ Une IA alliée du joueur (pour un jeu incluant des alliances et de nombreuses factions) est-elle plus simple ou plus compliquée à réaliser qu’une unique IA ennemie du joueur (pour un jeu où il n’y a principalement qu’un seul adversaire) ?

Bien qu’il s’agisse d’un aspect que nous avons souvent tendance à négliger, je pense qu’il est plus simple de créer une IA alliée « suffisamment évoluée ». Malgré tout je pense que les joueurs humains conservent un avantage immense sur l’IA, aussi complexe soit-elle dans les titres que nous créons ; normalement ils n’éprouvent pas la nécessité de se faire aider par des IA alliées (même si je considère que la possibilité de désigner des objectifs et gérer des fronts secondaires via l’IA dans Hearts of Iron III représente une exception intéressante). Une IA adverse requiert beaucoup plus de travail car elle doit au final proposer un réel défi pour le joueur.

7/ Dans les jeux de stratégie et les wargames les IA sont très souvent meilleures en défense qu’en attaque, pourquoi ?

Je ne suis pas sur d’être d’accord avec cela ; je pense que cela dépends surtout de la spécificité des jeux. Dans les nôtres la profondeur stratégique offre un avantage énorme que l’IA peut probablement exploiter à son profit. Il est notamment possible de laisser filer quelques provinces dans la phase initiale du conflit et voir ainsi les armées ennemies s’affaiblir, suite aux effets de l’attrition. Un bon exemple concerne Victoria II ; y tenter de s’approprier des provinces aux dépends de la Russie, en tant que nation secondaire voisine, est un but presque désespéré. En revanche, vous pourrez détruire ses armées lorsqu’elles vous attaquerons. Si l’IA est meilleure en attaque cela signifie généralement que vous êtes désespérément en sous effectifs par rapport à l’adversaire ou bien que vous avez été pris au dépourvu, après avoir négligé la défense de certains points clefs.

8/ Dans quelle mesure la perception qu’à le joueur de l’IA compte-t-elle ? Une IA d’un jeu peut-elle se contenter d’être moins bonne stratégiquement (qu’un adversaire humain), tant qu’elle est crédible ludiquement, dans ses actions ? Et donc au final, pour un jeu, offre un résultat amusant, donc satisfaisant ?

Je dirais que c’est une part très importante. Une IA dans un jeu doit juste être adaptée ; cela signifie que, de temps à autre, les joueurs veulent pouvoir perdre une partie. Toutefois il désirent aussi rencontrer une opposition suffisante,  leur donnant l’impression d’avoir obtenu une victoire gratifiante. Cette position est pour nous du pain béni dans la mesure où, en l’état actuel des choses, une IA d’un niveau équivalent à celui d’un bon joueur humain représente encore un souhait pour l’avenir, plutôt qu’une réalité.

9/ Niveau wargames, à quelles évolutions peut-on s’attendre pour les IA dans un avenir relativement proche ? Une idée probablement folle, si cela était possible techniquement, un wargame ayant son IA en partie dans le futur (et un peu hypothétique) « cloud » pourrait-il bénéficier d’un avantage (ex : puissance de calculs, comparaison des coups joués dans d’autres parties) ?

Tout l’engouement et la publicité autour des algorithmes bayésiens (d’apprentissage ou “probabilistes”), les réseaux neuronaux, appliqués à la programmation d’IA s’est lentement éteint ces dernières années. De telles évolutions ne semblent simplement pas réalistes dans un futur proche. En revanche on peut raisonnablement envisager d’utiliser davantage la puissance des processeurs pour améliorer et multiplier l’emploi des calculs de déplacements, une chose qui nous pose régulièrement problème.

10/ Le jeu d’échec offre un plateau de 64 cases et 32 pièces. Donc une base bien moins importante qu’un bon wargame, et encore moins que certains « monster wargames ».
Avec 256 processeurs en parallèle (soit 200 millions de coups / sec.), en 1996-97 Deep Blue a fini par battre le champion du monde d’échec Gary Kasparov. En théorie, bien programmée, la machine ne fait pas d’erreur. Mais même avec un super-ordinateur, malgré tout il lui manque presque toujours la vision stratégique, la vue d’ensemble ? Si l’on augmente la taille du « plateau de jeu », pour une simulation vidéoludique tout n’est-il que puissance de calculs ?

La puissance de calcul permet de résoudre des problèmes de calcul mathématique, un aspect autour duquel il demeure aisé de réduire une partie d’échecs. Par ailleurs, et c’est un point crucial, les échecs ne comportent aucun élément de chance (le facteur aléatoire – NDLR). Certains aspects des wargames les plus évolués pourraient véritablement tirer profit d’un surplus de puissance de calcul (path finding ; optimisation des files d’attente de construction ; équilibrage des budgets, etc.) mais ainsi que vous le disiez, ce ne serait pas envisageable pour l’aspect planification ou vision stratégique. En supposant que ce serait le cas, un jeu comme Europa Universalis, avec une IA au comportement logique, ne serait guère efficient ; il serait alors beaucoup trop prévisible.

11/ Question subsidiaire : si dans un wargame une IA pouvait battre à coup sur un joueur aguerri, quel que soit le théâtre d’opérations simulé, un bon jeu doit-il limiter l’IA pour nécessairement laisser gagner le joueur ?

Oui, bien entendu :) . Il n’y aurait aucun intérêt à jouer sans aucune possibilité de victoire. Il est essentiel de pouvoir ajuster le niveau de difficulté, ainsi que vous pouvez le faire dans une partie d’échecs sur ordinateur.

Tous nos remerciements à Henrik Fåhraeus et Paradox Interactive pour avoir accepté de répondre à nos questions. Traduction réalisée par David B. (Gloo).

Pour plus d’informations sur Crusader Kings II, voyez le site www.crusaderkings.com mais aussi notre notre test, ainsi que ceux de l’extension Sword of Islam et de l’extension Legacy of Rome. Nous reparlerons prochainement du nouvel add-on The Republic.

Paradox Development Studio Interview regarding AI. Answered by Henrik Fåhraeus, project lead and senior AI programmer at Paradox Development Studio.

1/ For you, what’s really an AI in an historical wargame. Several scripts and algorythms, of course, but anything more ?

Algorithms, scripts, and a healthy dose of chance! Really, the random element should not be underestimated. Applied in the right amount and at the right places, it can fool human players into believing they are watching « intelligence ».

2/ For a PC wargame, what are the different AI models? Are there different software tools for developers ?

Well, all our games from Paradox Development Studio use a hierarchical Intelligent Agent model, which is very suitable for real time strategy games. There are other models, but I believe most strategy games use similar systems. In our games, each computer player has a top level IA with a number of subservient IAs that handle the major areas of the game (trading, armies, navies, buildings, etc.) These in turn can start or stop other IAs with more specific tasks (transport troops to a province, blockade ports, etc.) On the side, there is a Strategic AI that analyzes the current strategic situation as well as the desired future situation (long term goals), something I originally wrote for the In Nomine expansion to Europa Universalis III. We do not use any third party tools for AI development.

3/ What is possible with the computing power of a modern PC (more or less 2 years old) of good quality? 3D asides, what other technical constraints is there?

We certainly can get away with more CPU intensive algorithms than we could when I started at Paradox eleven years ago. Hearts of Iron III uses a lot more juice for path finding and other algorithms than HoI by far. But even these days, computing power does set boundaries that we keep running into. For example, I could probably dramatically improve the military AI in our games with more generous use of path finding. However, most weak spots in the AI have nothing to do with CPU constraints, but are simply down to the sheer complexity of writing a good AI (how to prioritize in different situations, and working toward proper long term goals).

4/ Are some kind of war-games, so of historical conflicts, or scales of games, more appropriate for (current) AI? If so, which one?

I would say that the historical setting or context is not so relevant, but rather how you choose your abstractions and design the rule set. However, games that cover a specific conflict are problematic in other ways. In Hearts of Iron, for example, you want the AI to behave as it did historically; you cannot allow too much deviation, so you must provide stricter rules for the AI. This is another aspect of the « hindsight » issue that exists in all historical games.

5/ From your experience in game design, what technical challenges have you meet ? Which one did you overcome? Which one are still a barrier?

Regarding the AI, I’ve found that the main recurring problems are limited resource allocation (e.g. what do I use my money for?), path finding (CPU intensive), action vs. reaction (when do I take the initiative and how much should I care about what other players are doing?), indecisiveness (going back and forth over some threshold value), and long term planning. Of these, I would say that action vs. reaction and long term planning remain the most serious barriers.

6/ Is an AI allied with the player (for a game including alliances and several factions) more simple or more complicated to build than a unique AI enemy of the player (for a game where there’s mainly one adversary)?

It is simpler to make an allied AI « good enough », although it’s an area we often tend to neglect. After all, human players still have a huge intelligence advantage over any AI in games as complex as the ones we make – they normally don’t need help from allied AI players that much (though the ability to set goals for allies in Hearts of Iron III is an interesting exception). A hostile AI is much more demanding since it is supposed to put up a real fight.

7/ In strategy games and wargames AIs are often better in attack than in defense, why?

I am not sure I agree with that; I think it depends a lot on the specific game. In our games, strategic depth provides an enormous advantage that the AI could potentially exploit more. You can afford to lose a few provinces in the initial phase of a war only to see the enemy armies die of attrition, etc. A good example would be in Victoria II; trying to take provinces off Russia as a neighboring middling country is almost hopeless, but you can kill off their armies when they attack you. If the AI is better on the attack, it usually means you’re either hopelessly outnumbered or have neglected to defend some key positions properly and were taken by surprise.

8/ To what extent the perception of the AI from the player has to be taken into account? Can an AI in a game just be less good strategically (than a human adversary), as long as it offers a good gameplay with its actions? And so at the end, for a game, offers an entertaining result, thus something satisfying?

I would say to a very great extent. A game AI only ever has to be good enough, meaning that every once in a while, players want to lose. Mostly, however, they just want sufficient opposition so they can feel good about winning. This is really a saving grace, because with the complexity in our games, an AI on the level of a human player is still far in the future.

9/ For war-games, what development can we expect for AI in a relatively near future ? A crazy idea probably, if that was possible technically, could a war-game having part of its AI in the future (and rather hypothetical) « cloud » gain an advantage (ex: computing power, comparing moves in same other games)?

All the hype about learning algorithms and neural networks in game AI has quietly petered down a lot in recent years. It is simply not realistic in the near future. However, more computing power could for example be used for better and more frequent path finding, which is something we often come up against.

10/ A chess game has a board with 64 squares and 32 pieces. So a base less important than a good wargame, and far much less than some « monster wargames ». With 256 processors in parallel (allowing 200 million move / sec.), in 1996-97 Deep Blue has finally beaten the world chess champion Gary Kasparov.
In theory, well programmed, a computer does not make mistakes. But even with a super-computer, the machine still lacks a strategical vision, a global view ? If we increase the size of the « board game », for a wargaming simulation is it just a question of computing power ?

Computing power helps for solving mathematical problems, and the rules of Chess are easy to reduce to mathematics. Also – and this is crucial – in Chess there is no element of chance. Some areas of more complex wargames would really benefit from more computing power (path finding, optimizing build queues, balancing the budget), but as you say, long term planning and strategic vision are not. Even if you could somehow do it, in a game like Europa Universalis an AI which always behaved logically would not be very strong – it would be far too predictable.

11/ Tiebreaker question: If in a wargame an AI could beat certainly an experienced wargamer, whatever the simulated theatre of operations, to be a good game does it have to limit the AI to necessarily let the player win ?

Yes of course :) There would be no point playing if you could never win. You would have to be able to adjust the AI strength like you do with the AI in computer Chess games.

Our thanks to Henrik Fåhraeus and Paradox Interactive for taking the time to answer these questions.