IA-t-il un wargamer dans mon PC ? Le cas d’HistWar

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 ?

IA, Intelligence Artificielle, tout est dit. Un programme qui essaye de simuler les fonctions intellectuelles d’un humain :

• soit par reproduction de comportements appris face à une situation connue (doctrine),
• soit par recherche de nouvelles solutions face à une problématique complexe.

L’IA d’HistWar reproduit ces deux modes. Il faut de fait parler de trois IA indépendantes, échangeant des messages.

• L’IA régimentaire (IA-R) prend en charge la “survie” des unités tout en essayant d’exécuter au mieux les ordres reçus. Dans ce cadre, l’IA applique scrupuleusement les ordres tant que cela est possible. A cette fin, elle utilise la doctrine qui est définie par le joueur a priori. On peut parler de script : à l’occurrence de tel événement, réaliser telle action.
• L’IA de Corps (IA-C) organise le groupe à réception d’un ordre de l’autorité à moins que le corps même se mette en ordre défensif à la détection d’une menace. L’autorité est soit le joueur soit l’IA Grande Tactique décrite dans le paragraphe suivant. A l’inverse de l’IA régimentaire, sa priorité est l’exécution de l’ordre indépendamment des pertes. Elle fonctionne avec des règles (pour illustrer, placement de cavalerie sur les flancs si possible) et des procédures de recherches de solution optimale. Par exemple lors d’un ordre de défense à établir sur une ligne, l’IA, utilisant un algorithme génétique, recherche un placement idéal en utilisant au mieux les différents éléments géographiques (constructions, zones arborées,…).
• L’IA Grande Tactique (IA-GT), activée seulement en mode Solo, assure le commandement de l’armée opposée au joueur. Cette IA n’utilise quasiment aucune règle. Sa première tache est de comprendre la géométrie du champ de bataille et de trouver où peuvent être appliqués les efforts. Elle élabore ensuite un plan de bataille en utilisant une technique proche de celle utilisée dans l’algorithmie génétique puis affecte les effectifs en fonction des missions attribuées à chaque corps. L’élaboration du plan est faite en mode « brouillard de guerre » complet avant que le joueur ne place ses troupes. Ainsi, il peut apparaître que le placement est incongru et ne s’oppose pas forcément aux troupes adverses. Toutefois, suivant le principe clausewitzien, chaque protagoniste va tenter d’imposer sa volonté matérialisée par le plan de bataille. Cette IA est actuellement peu réactive et ne modifie pas le plan tactique initial ; cette faiblesse évidente sera corrigée dans HistWar II.

Pour conclure, le nouvelle version d’HistWar va s’enrichir avec deux nouvelles IA en charge respectivement des Divisions et des Brigades. Elles s’appuieront sur un système de doctrines complété par un algorithme de recherche de solutions optimales.

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

Des théoriciens des jeux ont décrit les éléments d’une typologie afin d’en faciliter le classement ; ils caractérisent les jeux par quelques attributs :

• Symétrie ou asymétrie : un jeu d’échec est strictement symétrique, ce qui n’est pas généralement le cas d’un wargame… quoique théoriquement rien n’empêche de forcer une symétrie dans le cadre d’exercice non historique.
• Synchrone ou asynchrone : à l’inverse des jeux de plateau, les jeux informatiques sont synchrone et les deux protagonistes jouant en même temps.
• Jeu à somme nulle : ce qui n’est pas le cas d’un wargame.
• Jeu à information complète (parfaite ou imparfaite) ou incomplète : de par ses options, HistWar permet de définir cet attribut suivant les 3 valeurs.

• Jeu déterministe ou non : HistWar est un jeu déterministe, à quelques exceptions près tel que la perte d’un chef de corps ou l’interception de messages. Toutefois, le nombre de paramètres est suffisamment élevé pour que le joueur ne puisse prédire à coup sûr le résultat d’un engagement. En conséquence, la probabilité qu’une unité d’élite au moral élevé dans une armée organisée soit mise en déroute par de la  milice est nulle… ce qui pourrait advenir par l’utilisation d’un tirage aléatoire usant une table comme l’on en trouve généralement dans les jeux de plateau.

Et alors ? Et bien il s’avère que pour un wargame, la théorie des jeux démontrent qu’il n’existe pas de modèle permettant de trouver à coup sûr une solution gagnante. Ceci dit, des méthodes telles que l’algorithmique génétique offre un moyen efficace et rapide de recherche d’une solution qui, sans toujours être optimale, propose une réponse satisfaisante. La logique floue est une technique permettant de décrire de manière lâche un problème. Elle est la base de la procédure de quantification du moral des unités dans HistWar.
Pour conclure cette question, l’un des problèmes majeurs dans l’utilisation de ces techniques est la définition de la fonction d’évaluation qui sert à élaborer la solution la meilleure.

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 ?

Dans le cadre d’HistWar, jeu en temps réel avec une compression temporelle variant entre 1 et 10 (de 1 mn par minute historique à 6 secondes par minute), la charge de l’IA est d’environ 250 ms pour une bataille avec environ 200 unités et 300 canons. Le doublement de puissance des processeurs permettrait théoriquement de traiter 700 entités pour un temps d’exécution similaire correspondant à un engagement majeur.
En conséquence, on peut penser que la puissance de calcul profite surtout au rendu graphique. Par exemple, HistWar est en train d’évoluer vers une échelle 1/1 pour les figurines, permettant de gérer environ 300 000 figurines dans une bataille comme celle de Wagram.

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 ?

Histwar étant essentiellement un jeu tactique, je n’ai pas assez de recul pour parler d’autres échelles de jeu. La passage aux échelles opérationnelles et stratégiques nécessitent d’autres techniques.

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 ?

Le développement d’une procédure efficace de recherche de trajectoires est un problème académique. Dès lors que la concentration des troupes est importante, que les unités ont des contraintes opérationnelles (rayon de giration, groupement aux formes complexes, présence de géométrie invariante ou encore de zone théoriquement inaccessible, …), que s’ajoute la nécessité de fournir un résultat sûr sans prendre beaucoup de ressources processeurs, le problème posé devient assurément complexe.
Actuellement, la partie élaboration des trajectoires représente environ 18% du code complet de l’IA. Il est fortement probable que cette partie soit doublée par un nouveau moteur physique issu de l’Open Source. Il est tout aussi probable que ce moteur nécessite plus de puissance de calcul aussi les deux moteurs seront présents et sélectionnés manuellement ou automatiquement en fonction de la charge.

De manière générale, la problématique d’un jeu tel HistWar qui prend en charge une grande quantité d’entités (régiments, canons) dans un environnement complexe est liée à la mise en place d’un code efficace et optimisé. L’algorithme doit aussi être pensé avec un objectif d’efficience, pouvant éventuellement nuire un peu à l’organisation du programme.

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) ?

Dès l’origine, HistWar s’est vu doté de 3 IA indépendantes. L’IA de Corps est au service du joueur et de l’IA Grande Tactique en mode solo. Dans cette perspective, il n’existe pas de difficulté supplémentaire. Toutefois, il est probable que le joueur sera moins tolérant aux réponses inadéquates si son IA de Corps semble le trahir.

Par ailleurs, il est possible que l’IA adverse aurait été plus efficace si elle avait été conçue comme un bloc unique, sans distinguer les 3 niveaux ; cette asymétrie des IA aurait toutefois entrainée une dissymétrie comportementale nuisible à l’équilibre du jeu.

Pour conclure, HistWar II va intégrer un mode collaboratif IA vs IA où le joueur prendra le contrôle d’un Corps. Il recevra des ordres de l’IA et aura à gérer ses régiments.

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

Probablement que les joueurs sont aussi meilleurs en défense. Attaquer nécessite de prendre l’initiative et d’affirmer sa volonté d’aller vers l’adversaire. Défendre est plus facile, surtout si les forces en présence sont similaires. Jomini et Clausewitz ont chacun affirmé ce principe.

Comme cela a déjà été mentionné, l’IA-GT d’HistWar n’est pas très réactive. Une fois le plan de bataille définie, elle va simplement s’appliquer à le mener à son terme quelque soit la réaction adverse.

HistWar II va évoluer suivant deux axes :

• une IA-GT fortement réactive avec une capacité à faire évoluer son plan de bataille en tenant compte du déploiement des forces de l’adversaire. Elle pourra aussi s’adapter efficacement aux joueurs dont la stratégie est d’attendre en posture défensive.
• Une nouvelle évaluation du résultat final tenant compte des initiatives développées par les joueurs. Une tactique résolument défensive sera pénalisée.

8/ Dans quelle mesure la perception qu’a 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 ?

Les mécanismes développés dans HistWar conjuguent Historicité et Ludicité, le second terme ne présentant aucune antinomie avec le premier tout en étant privilégié.
Ce préambule décliné, un jeu doit satisfaire les demandes du joueur : l’IA doit être un adversaire efficace présentant une résistance réelle sans toutefois tricher. Les variations doivent être nombreuses afin que chaque nouvel engagement apporte son lot de surprises, de découvertes.

Toutefois, si l’IA joue un rôle important, le jeu doit être avant tout beau et servi par une interface agréable accompagné par un fond sonore immersif. Un wargame est un tout et doit privilégier tout ces aspects, sans oublier l’historicité.

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) ?

Je ne peux répondre de manière générique mais encore parler d’HistWar.
La sortie d’HistWar II n’est pas encore annoncée que l’évolution vers HistWar III est déjà dans les têtes. Elle aura pour objectif de proposer une IA-GT de qualité avec des capacités d’apprentissage continues. La réflexion n’est pas formellement engagée mais on peut penser à un modèle d’apprentissage par renforcement s’appuyant sur un processus de décision markovien. Ce procédé aux contours encore incertains pourrait facilement s’intégrer puisque le jeu possède un mode de fonctionnement IA vs IA. Une fois la technique maitrisée, il serait possible d’enrichir continument le modèle en utilisant le résultat des rencontres des joueurs eux mêmes. A suivre donc, après HistWar II…

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 ?

Quelques chiffres…
Nombre de coups possibles au jeu d’échec : 10 puissance ¹²⁸
Nombre de coups possibles au jeu de Go: 10 puissance ⁶⁰⁰
Nombre d’atomes dans l’Univers : 10 puissance ⁶⁰

On peut penser qu’a minima, un wargame se situe dans la catégorie du jeu de Go. Évaluer ne serait ce qu’une partie des solutions envisageables (algorithme A*) parait hors de portée pour les milliards d’années à venir. Mais est ce important ? Faire une IA seulement au niveau d’un bon joueur de wargame paraît envisageable tenant compte des processeurs disponibles actuellement et des méthodes d’analyse dont beaucoup ne sortent pas encore du monde académique, non par manque d’intérêt mais simplement parce que le développement des IA n’est pas un objectif majeur de la plupart des sociétés de développement, les producteurs et éditeurs de jeux ayant surtout le regard fixé sur la qualité du rendu.
Je crois que des techniques mélangeant algorithme génétique, logique floue et Multi-agents sont à cet instant largement suffisant pour produire une simulation ludique où le joueur sort satisfait.

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

Bien sûr qu’il faut limiter la capacité de l’IA afin que le joueur l’emporte… mais à chaque victoire, réactualiser les paramètres de l’IA pour que le joueur élève sans cesse son niveau. Je vais y penser ;-)

Tous nos remerciement à Jean-Michel Mathé pour avoir pris le temps de répondre à nos questions.

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

AI,  Artificial Intelligence, all is said. That is a program that tries to simulate the intellectual functions of a human being.

• either by reproduction of the behaviours learned while facing a well known situation (doctrine),
• or by research of new solutions that are necessary to face a complex problem.

The Histwar AI reproduces these two modes. In fact,  we need to speak of three independent AI that exchange messages.

• The regimental AI (AI-R ) is in charge of the “survival” of the units but tries to do its best to execute the given orders . In this frame,  the AI scrupulously applies the orders as long as it is possible. For that, it uses an “a priori” doctrine defined by the player. We can call it a script: in case of such an event, perform  such an action.
• The corps AI (AI-C) manages the group when it receives an order from the authority except if the corps decides to organise itself in a defensive order after a threat detection. The authority is either the player or the “Grand Tactical” described in the next paragraph. Unlike the regimentary AI, its priority is the execution of the given order regardless from human losses. It functions with rules (to illustrate :  positioning of the cavalry on the flank if possible) and with search procedures to find an optimum solution. For example, when receiving a defensive order on a  line , the AI, by using a genetic algorithm,  searches for  an ideal placement by making the best possible use of all geographical elements (buildings, woodlands, …)
• The Grand Tactical AI ( AI-GT), only activated  in solo mode, provides the command of the army opposed to the player. This AI almost uses no rule. Its first goal is to understand the  geometry of the battlefield and to find where the efforts can be applied. Then, it elaborates a battle plan by using a technique very close to the one used in the genetic algorithmic. After that, it allocates strengths according to the missions attributed to each corp. The elaboration of the plan is made in complete « war fog » mode before the player places his troops. So, it can appear that the placement is improper and therefore does not necessarily face the opposite troops. However, according to the clausewitzien principle, each protagonist will  try to impose his will by the mean of the battle plan. For the moment, this AI  is not very reactive and does not modify the initial tactical plan ; this obvious weakness will be corrected in HistWar II.

To conclude, the new version of HistWar will be enhanced with two new AI respectively in charge of Divisions and Brigades. These AI will lean on a system of doctrines completed by an algorithm of search to find optimal solutions.

2/ For a PC wargame, what are the differents AI models ? And the differents software tools for developers ?

Game theoreticians have described the elements of a typology to facilitate games classification : they characterise the games with these few attributes:

• Symmetry or asymmetry: Chess, for example, is a strictly symmetric game. Generally it is not the case for a wargame …. It is although interesting to note that nothing prevents, in theory,  from forcing a symmetry within the framework of a non historic exercise.
• Synchronous or asynchronous: unlike board games, computing games are synchronous and both protagonists play at the same time.
• Zero-sum game: it is not the case of a wargame.
• Game with full information (precice  or not) or incomplete: with its options, HistWar allows to define this attribute with these 3 values.
• Determinist game or not : HistWar is a determinist game including a few exceptions such as the loss of a commanding corp officer or the interception of messages. However, the number of parameters is high enough so that the player can never be sure of a commitment result. Therefore, the probability that a unit of elite, with a strong fighting spirit in a well organised army, could be put to flight by militia is zero-probability …This could happen in most board games with a random sampling using a table.

Well and then ? In fact,  it turns out that for a wargame, the theory of games demonstrates that there is no model allowing to find a winning solution with certainty. Having said that, methods such as genetic algorithmic offers an effective and fast means of search to find a solution which, without being always optimal, proposes a satisfactory answer. The fuzzy logic is a technique that allows to describe a problem in a blur way . This is the basis of the quantification procedure used to get Histwar units morale.
To conclude, one of the major problems in the use of these techniques,  is the definition of the fitting function that leads to elaborate the best solution.

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 are there ?

Within the framework of HistWar, which is a  real time game with a temporal compression varying between 1 and 10 (from 1mn per historic minute to 6 seconds per minute), the load of the AI is about 250 ms for a battle with approximately 200 units and 300 cannons). Doubling the power of processors would in theory allow to handle 700 entities with a similar time of execution corresponding to a major commitment.
Therefore, we can think that the computing power mainly improves the graphics rendering. For example, HistWar is evolving towards a scale 1/1 for figurines, that allows to manage approximately 300 000 figurines in a battle such as Wagram.

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

Histwar being essentially a tactical game , I can’t stand back enough to speak about other game scales. The move to operational and strategic scales require other techniques.

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

The development of an effective procedure to search for trajectories is an academic problem. When the concentration of the troops is important, and when the units have operational constraints (radius of gyration, grouping in complex forms, presence of invariant geometry or theoretically inaccessible zone) and that it is necessary to supply a safe result without taking too much processors resources, the problem becomes undoubtedly complex.

For the moment,  the elaboration of trajectories represents approximately 18 % of the complete code of the AI. It is highly probable that this part could be doubled with a new Open Source physical engine.  It is highly probable as well that this engine would require more computing power, so both engines will be present and will be selected manually or automatically according to the load.

In a general way, the problem of a game such as HistWar which uses of a big quantity of entities (regiments, cannons) in a complex environment is bound to the implementation of an effective and optimised code. The algorithm must also be thought with an objective of efficiency which could possibly slightly damage the organisation of the program.

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) ?

From the start, HistWar works with 3 independent AI. The corps AI serves the player but also the Great Tactical AI in solo mode. In this perspective, there is no additional difficulty. However, it is likely that the player will be less tolerant to inadequate replies if his corps AI seems to betray him.

Besides, it is possible that the opposite AI would have been more effective if it had been designed as a unique block, without distinguishing the 3 levels; this asymmetry of the AI would have however possibly led to a behavioural asymmetry potentially harmful to the balance of the game.

To conclude, HistWar II is going to integrate a collaborative mode AI vs AI where the player will take the control of a corp. It will receive orders from the AI and will have to lead its regiments.

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

Probably that the players are also better in defence. To attack requires to take the initiative and to assert its will to go towards the opponent. To defend is easier, especially if the strengths in presence are similar. Jomini and Clausewitz each asserted this principle.
Like it has already been mentioned, the AI-GT of HistWar is not very reactive. Once the battle plan is defined it simply leads to apply it whatever the opposite reaction is.

HistWar II is going to evolve in two ways :

• A strongly reactive AI-GT with a capacity to improve its plan of battle by taking into account the opponent deployment of strengths . It can also adapt itself effectively to the players whose strategy is to wait in a defensive posture.
• A new fftting of the final result taking into account initiatives developed by the players. A determinedly defensive tactic will be penalised.

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 ?

Mechanisms developed in HistWar conjugate historicity and playfulness, this second term does not present any contradiction with the first but is privileged.

This introduction done, a game has to satisfy the requests of the player: the AI has to be an effective opponent presenting a real resistance without cheating however. The variations must be numerous so that every new battle brings its bunch of surprises and discoveries.
However, when the AI plays an important role, the game must above all be beautiful and be served by a pleasant interface accompanied by an immersive background sound. A wargame is a whole and has to privilege all the aspects without forgetting the historicity.

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

I cannot answer in a generic way but only speak about HistWar. The release of HistWar II is not announced yet that the evolution towards HistWar III is already in heads. It will have for objective to propose an AI-GT of quality with continuous capacities of learning. The reflection is not formally undertook but we can think of a learning model by strengthening. It will lean on a markovien process of decision. The outlines of this process is still uncertain but it could easily be integrated as the game owns a “AI vs AI” mode . Once the technique is under control, it will be possible to continuously enrich the model by using the meetings results of the players themselves. To follow, … after HistWar II…

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 millions move / sec.), in 1996-97 Deep Blue has finally beaten the world chess champion Gary Kasparov. In theory, well programmed, a computer do 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 ?

Some figures…
Number of possible strokes for chess : 10ˆ128
Number of possible state strokes for the game of Go : 10ˆ600
Number of atoms in the Universe: 10^60

We think that,  at a minimal level, a Wargame is situated in the category of the Go game. To estimate what would be, at least, a part of the possible solutions (algorithm A *) seems to be impossible for the billions of coming years. But is this important? To make an AI, only at the level of a good Wargame player, seems to be possible by taking into account the current available processors and by picking in the available methods of analysis even if many of them still don’t go out of the academic world. It is not due to the lack of interest but, in fact,  the development of the AI is not a major objective for most of the development companies as the producers and games editors mainly focus their efforts on the graphic quality rendering.

I believe that mixing techniques melting genetic algorithm, fuzzy logic and multi-agents are nowadays quite  enough to produce a playful enjoyable simulation for the player.

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 ?

Of course it is necessary to limit the capacity of the AI so that the player wins but after each victory it would be nice to update the AI parameters so that the player improves his level. I am going to think of it ;-)

Our thanks to Jean-Michel Mathé for taking the time to answer and translate this interview.