Notice: Undefined property: JDocumentHTML::$base in /var/www/http/faf/libraries/joomla/document/document.php on line 677
Tu as le bonjour d'Albert

Tu as le bonjour d'Albert

Vouloir jouer contre l'ordinateur à Diplomacy est une idée ancienne et une solution pratique pour jouer quand vous manquez de joueurs disponibles. Le jeu a été porté à quelques reprises sur PC, en étant principalement une interface pour permettre à des individus de jouer à distance entre eux, mais les logiciels comportaient aussi une I.A. pour simuler les puissances et pas uniquement faire la résolution des mouvements. Je pense à la version Microprose de 1999, téléchargeable et payable en ligne pendant longtemps, et un peu plus récemment à la version Paradox Interactive de 2005.

Même en occultant la phase de négociations, où vous pouvez l'induire en erreur, l'I.A. est d'une grande faiblesse dans la gestion de ses unités. A part quelques séquences d'ouvertures préenregistrées, la suite des mouvements résiste difficilement aux coups de butoir d'un joueur humain, même débutant. Dans la version Paradox par exemple, attendez-vous à voir l'Allemagne ouvrir 90% du temps en Silésie et les unités turques se bouncer sur le sol national alors qu'il n'y a aucune force étrangère aux alentours. A se demander si l'I.A. ne suit pas un algorithme de déplacements aléatoires.

A la décharge des concepteurs des logiciels, faire une IA pour Diplomacy est loin d'être trivial, rien qu'en se limitant au mode no press. La théorie classifie les jeux suivant différents critères pour créer différentes catégories, telles que les jeux à information complète, les jeux de hasard, les jeux à somme nulle ou non nulle, les jeux séquentiels ou simultanés. En guise d'exemples, le jeu de dames est à information complète mais aussi Risk ou le Backgammon. Il y a un facteur chance dans ces derniers mais les probabilités sont stables et connues pendant le coup.

Contrairement aux autres jeux usuels, Diplomacy se joue à 7 - alors que la configuration courante est d'avoir que 2 joueurs - ce qui oblige à prendre en compte le phénomène des alliances. Le fait d'exécuter les ordres en simultané, brouillent encore les cartes et surtout les probabilités, faute d'information complète.

Même s'il y a déjà un problème d'application du modèle déterministe de base, il est difficile de s'agripper aux méthodes de calculs, utilisées par exemple aux échecs, rien qu'en considérant le nombre de coups. L'approche simple est de construire des arbres décisionnels avec tous les coups possibles et de déterminer le score de chaque scénario et de retenir le meilleur. Avec 75 régions sur le plateau et 34 unités à terme et une dizaine de mouvements potentiels pour chacune – entre les convois et les supports - nous obtenons à la louche 2 millions de milliards de combinaisons possibles à chaque tour. Si vous faites abstraction des historiques et imaginez juste toutes les photographies possibles avec 34 unités sur la carte, vous arrivez à quelques 10^27 combinaisons. 10^27 c'est environs un milliard de fois la taille de La Voie Lactée, exprimée en kilomètres.

Comme toujours, l'exploration de l'arbre peut être abrégée en interrompant le parcours d'un chemin pas prometteur mais pour une même profondeur de calcul, l'immersion est moins poussée que dans le cas du jeu d'échecs ou encore du jeu de dames. En plus, il reste à estimer le score du mouvement envisagé, ce qui peut devenir rapidement complexe : Gagner un allié vaux parfois mieux que de gratter un centre supplémentaire en se retrouvant avec l'ensemble de la table contre soi.

A la simple vision combinatoire vient se superposer une approche, d'ailleurs plus humaine, qui s'intéresse à la carte elle-même et à l'importance des différentes provinces pour les joueurs. L'I.A. assigne un score à chaque case en suivant une multitude de critères. Ceux-ci sont d'abord simples, tels que le paramètre géographique qui considère l'éloignement de la région par rapport au pays d'origine ou le fait d'être un arsenal ou pas, ou encore s'il s'agit d'une province nationale ou d'un espace neutre. D'autres critères sont plus subtils et évoluent en fonction de la situation: Highland aura un score différent suivant qu'une flotte étrangère borde la région ou pas. Un autre exemple est la Bourgogne, qui est vitale pour le français en 1901 mais sans doute moins importante plus tard, s'il a atteint Berlin.

L'exercice permet à la fois à l'I.A. de mesurer la qualité de ses combinaisons de mouvements mais aussi de se donner un ou plusieurs buts pour le coup suivant. L'algorithme de recherche consiste alors à optimiser la gestion de ses unités pour atteindre les objectifs. En termes d'implémentation, un agent de calcul peut être affecté à chaque unité et ils discutent entre eux en mode coopératif pour établir la combinaison optimale.

En pratique, le résultat est honnête en terme tactique mais manque de cohérence stratégique, même si, implicitement, des équilibres doivent apparaître. Si dans un coin du plateau, il peut être équivalent de taper sur le joueur A et sur le joueur B, il y a un certainement un critère qui permet de départager les 2 joueurs, que ce soit au niveau global ou en fonction de l'historique du jeu, pour éviter de casser une alliance fructueuse, par exemple.

Le processus de calcul est cependant itératif avec un score des régions revu pendant les simulations et une projection dans le futur pour enchaîner les coups suivants, mais nous tombons dans le même écueil de recherche via les arbres décisionnels.

A partir de là, le comportement de l'I.A. peut être adaptée. Un chercheur a conçu par exemple un bot Berserk, qui donne un score bonus aux centres adversaires et privilégie l'attaque à la défense. De même, vous avez la configuration inverse avec le bot qui blinde ses centres acquis et utilise le reliquat de mouvements pour avancer.

Au fil de mes lectures, j'ai vu principalement deux types de personnes se pencher sur la question des I.A. pour Diplomacy : Des thésards en informatique qui se sont approprié le problème en théorisant leurs modèles, et de l'autre, des joueurs de Diplomacy, qui ont découvert ce que pouvait être une I.A. en programmant laborieusement leurs bots et qui n'y connaissaient rien à la théorie des jeux. Bien entendu, la meilleure A.I. reconnue à ce jour est l'oeuvre d'un membre de la 2ème population.

Jason van Hal travaille sur son bot Albert – d'où le titre – depuis 2005. Les récentes améliorations concernent surtout la gestion du mode diplomatique, le moteur no press étant stable depuis des années. Au fil de l'eau, l'auteur a enrichi sa bibliothèque d'ouvertures et il a effectué de nombreux réglages pour corriger les comportements. Par exemple, il a fait en sorte que les armées anglaises aient plus de chance d'être convoyées que les forces autrichiennes. Le bot a aussi beaucoup évolué au niveau des mouvements tactiques, tel que les mouvements en triangle pour optimiser la distribution des flottes et des armées sur les provinces côtières.

Je trouve que l'auteur fait bien jouer les situations de guess à son bot. Ce dernier est capable de tenter un coup à gauche, puis un coup à droite si cela ne passe pas, puis il vous surprend finalement en débarquant au milieu avec une armée convoyée. Si vous commettez une erreur tactique en début de partie, la punition arrive très vite et le bot est généralement un sparring partner de niveau honorable en blitz.

Albert a aussi une vision stratégique, dans le sens où il choisit un ennemi et quelques fois des alliés. L'approche classique que j'ai pu lire dans d'autres projets est de se placer dans la pire hypothèse – et la plus simple -, à savoir que tous les autres pays sont des ennemis et qu'ils forment une alliance coordonnée. Le bot de de van Hal a une phase d'analyse visiblement plus fine des alliances, ce qui lui permet d'optimiser ses percées, en allégeant ses défenses devant un allié.

Il arrête intelligemment de taper sur ses voisins quand il voit un orge apparaître à l'autre bout de la carte et qu'il ne peut pas affronter directement. Il se met même en mode casque bleu : C'est presque touchant de voir des armées turques essayer de se frayer un chemin vers l'Allemagne en évitant soigneusement de stationner sur le peu de centres qui détiennent encore les puissances russe et autrichienne.

D'un autre côté, l'I.A. peut être expéditive en acceptant de marcher à fond à une alliance à 2, où elle est seulement à 2 ou 3 centres derrière, avant de vraiment taper sur le premier de la carte, à partir d'un seuil vers 13 centres, quand le solo se précise. Cela aboutit quelques fois à des parties incongrues. Je me souviens notamment d'une vague russo-austro-turque qui a avancé jusqu'en France, avant que les I.A. ne commencent à se stabber, la Turquie et la Russie, bille en tête. Jusqu'à là, l'Autriche avait laissé ses arsenaux nationaux vides, à portée de ses voisins, et ce ne sont pas les premiers centres qu'elle a perdus après. Un joueur humain aurait optimisé ses coups et piqué tous ces territoires bien avant, en tant que Turc ou Russe.

La combinaison d'ouvertures est aussi plus variée que pendant les parties blitz habituelles jouées dans le hobby français. Les développements au nord sont classique mais au sud, l'Autriche n'hésite pas à ouvrir sur l'Italie, avec la bénédiction Russo-turque. Dans ses notes de versions du bot, van Hal a du implémenter explicitement les cas où l'Allemagne ne bounce pas la Russie pour corriger le comportement logique, obtenu par calcul. En revanche, il a omis la Lépante terrestre et la prise de Trieste par l'Italie conduit inexorablement à un conflit avec l'Autriche au tour suivant.

Albert a un comportement prévisible en terme stratégique quand vous approchez de la fin de la partie. Même en position de faiblesse, vous pouvez passer sous ses écrans radar pour qu'il vous épargne et vous refaire une santé pendant qu'il attaque un adversaire plus gros avec ou sans vous. A force, vous savez quand il est possible de basculer l'intégralité de vos forces d'un front à l'autre sans rien risquer. C'est un peu trop facile.

Faisons maintenant concrètement un panorama des outils associés pour pouvoir installer et tester Albert.

Le bot s'inscrit dans le cadre du DAIDE (Diplomacy AI Development Environment), un environnement amorcé en 2002, qui consiste en un système client serveur, avec le serveur qui résout les coups et les clients qui sont les interfaces des joueurs. En tant qu'utilisateur, vous pouvez récupérer le client standard qui comporte une carte pour visualiser le jeu et rendre vos ordres. Il y a autant de clients que de joueurs, et pour faire rentrer un bot dans la partie, il suffit qu'il prenne un des slots joueurs.

Concrètement, si vous êtes tout seul, vous démarrez le serveur, vous lancez une partie dessus, puis vous lancez votre client graphique pour rejoindre la partie et vous exécuter aussi 6 fois le programme bot, ce qui vous fait 6 joueurs de plus en face. Le site propose une liste complète d'autres bots mais je n'en ai encore testé aucun autre à part Albert.

L'application fait old school mais elle fonctionne très bien et je m‘y suis fait très vite. Il suffit de cliquer sur la carte pour donner des ordres, que ce soit des soutiens ou des convois. Cerise sur le gâteau, vous pouvez jouer à beaucoup de variantes, du moment que les règles sont les mêmes que la carte classique. La Moderne et la Hundred sont dans la liste mais pas la Coloniale ni la vraie 1900, par exemple.

En revanche, tout est en mode solo/draw, sans date d'arrêt. Si vous optez pour le jeu avec une date limite, ce n'est pas gênant entre des humains qui peuvent convenir d'une année de fin fixe, mais l'I.A. ne règlera pas ses mouvements pour jouer le dernier tour en optimisant ses gains d'arsenaux.

Les différents sites sources ont une apparence digne des années 90 et donnent l'impression d'être abandonnés mais en fait non : Les exécutables ont été recompilés et testés sous Windows 7, bien que la documentation associée date de Mathusalem. Les pages comportent aussi les papiers écrits par différents chercheurs, avec des propos plus ou moins pertinents à propos de la modélisation des I.A. pour Diplomacy.

Les programmes sont disponibles via le site du DAIDE, qui vous conduit aussi à une mailing list sur les Diplomacy Ai, où les gardiens des clefs sont encore là en 2013 pour valider les inscriptions en moins de 24h. Si vous vous intéressez au sujet et n'êtes pas réfractaire à l'anglais, vous devriez y faire un tour.

Bibliographie

[Nested Look-Ahead Evolutionary Algorithm Based Planning for a Believable Diplomacy Bot->http://ls11-www.cs.tu-dortmund.de/_media/rudolph/planning-diplomacy-bot.pdf] Kemmerling K, Ackermann N, Preuss M, 2011

[Diplomacy - A.I.->http://www.daide.org.uk/external/ritchie200309.pdf] Ritchie, A., 2003

Ressources

http://www.daide.org.uk Le site du DAIDE avec les binaires et les kits de développement

http://groups.yahoo.com/group/dipai/ Mailing list pour discuter de Diplomacy Ai

https://sites.google.com/site/diplomacyai/ Le site sur Albert, le bot de Jason van Hal

Additional information