Ce mémoire présente une comparaison de deux algorithmes de reconnaissance de plan, soit YAPPR (Yet Another Probabilistic Plan Recognizer) et PR-Plan (Plan Recognizer as Planning). Afin de comparer les algorithmes, nous avons voulu utiliser un domaine plus complexe et réaliste que ceux utilisés jusqu’à présent. Pour ce faire, nous avons établi un protocole de comparaison en utilisant le concept d’observation in situ. Nous avons utilisé le jeu de stratégie en temps réel StarCraft comme environnement de simulation. Puis, nous avons créé un agent jouant à StarCraft qui utilise la reconnaissance de plan comme élément central pour le système de prise de décision. Pour valider que notre principe d’observation in situ fonctionne, nous avons créé des agents témoins et exécuté de nombreuses simulations.

La capacité à reconnaître les intentions d’un agent est un élément important de l’analyse de la situation. Connaître ces intentions est souvent un facteur clé de la prise de décision dans plusieurs domaines tels que la robotique, les jeux vidéo, la sécurité informatique et l’analyse du renseignement. Une des approches algorithmiques souvent utilisées pour reconnaître les intentions d’un agent suppose une connaissance préalable de tous les plans exécutables par l’agent observé. À partir de ces plans et des données d’observation, on peut alors prédire les comportements et les intentions de l’agent observé simplement en générant les modèles d’exécution de plans cohérents avec les données d’observation. Ces modèles d’exécution constituent en quelque sorte les hypothèses sur le plan et le but poursuivi par l’agent observé. Ainsi, la probabilité que l’agent observé poursuive un but particulier est établie comme étant la proportion des modèles cohérents avec ce but. Cette approche existe depuis une dizaine d’années et fait partie des approches les plus étudiées en ce moment. Cependant, elle comporte des lacunes fondamentales, notamment une explosion combinatoire de la taille de l’espace d’hypothèses. Ce mémoire de maîtrise propose un algorithme permettant d’aborder ce dernier problème en contrôlant l’exploration de l’espace d’hypothèse. Avec ce nouvel algorithme, on peut approximer la probabilité du but, de sorte que la précision de l’approximation s’améliore graduellement avec le temps de calcul. Cette approche a été publiée dans l’une des deux plus prestigieuses conférences scientifiques sur l’intelligence artificielle : International Joint Conference on Artificial Intelligence (IJCAI), en 2013.

Ce mémoire propose une approche pour la reconnaissance de plan qui a été conçue pour les environnements avec des adversaires, c'est-à-dire des agents qui veulent empêcher que leurs plans soient reconnus. Bien qu'il existe d'autres algorithmes de reconnaissance de plan dans la littérature, peu sont adaptés pour de tels environnements. L'algorithme que nous avons conçu et implémenté (PROBE, Provocation for the Recognition of Opponent BEhaviours ) est aussi capable de choisir comment provoquer l'adversaire, en espérant que la réaction de ce dernier à la provocation permette de donner des indices quant à sa véritable intention. De plus, PROBE utilise des machines à états finis comme représentation des plans, un formalisme différent de celui utilisé par les autres approches et qui est selon nous mieux adapté pour nos domaines d'intérêt. Les résultats obtenus suite à différentes expérimentations indiquent que notre algorithme réussit généralement à obtenir une bonne estimation des intentions de l'adversaire dès le départ et que cette estimation s'améliore lorsque de nouvelles actions sont observées. Une comparaison avec un autre algorithme de reconnaissance de plan démontre aussi que PROBE est plus efficace en temps de calcul et en utilisation de la mémoire, sans pourtant sacrifier la qualité de la reconnaissance. Enfin, les résultats montrent que notre algorithme de provocation permet de réduire l'ambiguïté sur les intentions de l'adversaire et ainsi améliorer la justesse du processus de reconnaissance de plan en sélectionnant une provocation qui force l'adversaire, d'une certaine façon, à révéler son intention.

Les jeux vidéo font aujourd'hui partie de la culture de nombreux étudiants au même titre que la télévision, les films ou les livres. Or depuis quelques années, les étudiants se détournent des sciences. La recherche dans le domaine de l'enseignement de l'informatique aborde les problèmes du recrutement et du maintien des étudiants dans les formations informatiques. Une approche prometteuse consiste à utiliser la culture vidéoludique des étudiants pour les motiver à investir du temps dans la pratique de la programmation. Dans ce cadre, les travaux présentés portent sur la conception, la réalisation et l'évaluation d'un jeu sérieux pour l'apprentissage des fondamentaux de la programmation. Ce jeu est basé sur un jeu de stratégie temps réel où la programmation est un moyen d'interaction. Grâce au système Prog&Play, le jeu sérieux a pu être déployé et évalué dans différents contextes d'enseignements.

L’intelligence artificielle est un domaine de l’informatique étudiant la conception d’agents intelligents. Un agent est une entité acquérant de l’information sur son environnement par ses capteurs et agissant sur son environnement à travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vidéo, alors que d’autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vidéo et de la robotique partagent certaines caractéristiques, dont la nécessité de prendre des décisions en temps réel dans un environnement dynamique ainsi qu’une vue incomplète sur cet environnement. Ce mémoire est divisé en deux chapitres. Le premier chapitre traite d’une approche de planification de trajectoires exploitant la géométrie d’une classe particulière de robots omnidirectionnels non-holonomes afin de calculer des chemins adéquats leur permettant d’atteindre une destination désirée. Les résultats obtenus avec cette approche tendent à démontrer qu’elle est plus efficace que les algorithmes traditionnels de planification de trajectoires grâce à l’information additionnelle prise en compte lors du calcul. Le second chapitre décrit l’architecture décisionnelle de l’agent intelligent SPAR qui est en mesure de jouer de façon autonome des parties de StarCraft : Brood War, un jeu de stratégie en temps réel. L’architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires à ceux du premier chapitre. Elle permet de faire face plus facilement et de façon plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficultés propres à ce type de jeu. Ces difficultés incluent un degré élevé de concurrence dans les actions et une multitude d’unités à contrôler dans un contexte temps réel. L’agent SPAR a participé aux volets 2011 et 2012 de la compétition AIIDE de StarCraft et à l’édition 2012 de la compétition SSCAI où il a obtenu à chaque fois des résultats honorables.

Doctorat en sciences psychologiques / info:eu-repo/semantics/nonPublished

Cette thèse aborde la problématique de la création d’intelligences artificielles (IA) contrôlant la prise de décision haut-niveau dans les jeux de stratégie. Ce type de jeux propose des environnements complexes nécessitant de manipuler de nombreuses ressources en faisant des choix d’actions dépendant d’objectifs à long terme. La conception de ces IA n’est pas simple car il s’agit de fournir une expérience pour le joueur qui soit divertissante et intéressante à jouer. Ainsi, le but n’est pas d’obtenir des comportements d’IA imbattables, mais plutôt de refléter différents traits de personnalités permettant au joueur d’être confronté à des adversaires diversifiés. Leur conception fait intervenir des game designers qui vont définir les différentes stratégies en fonction de l’expérience qu’ils souhaitent créer pour le joueur, et des développeurs qui programment et intègrent ces stratégies au jeu. La collaboration entre eux nécessite de nombreux échanges et itérations de développement pour obtenir un résultat qui correspond aux attentes des designers. L’objectif de cette thèse est de proposer une solution de modélisation de stratégies accessible aux game designers en vue d’améliorer et de simplifier la création de comportements stratégiques. Notre proposition prend la forme d’un moteur stratégique choisissant des objectifs à long terme et vient se placer au dessus d’un module tactique qui gère l’application concrète de ces objectifs. La solution proposée n’impose pas de méthode pour résoudre ces objectifs et laisse libre le fonctionnement du module tactique. Le moteur est couplé à un modèle de stratégie permettant à l’utilisateur d’exprimer des règles permettant au moteur de choisir les objectifs et de leur allouer des ressources. Ces règles permettent d’exprimer le choix d’objectifs en fonction du contexte, mais également d’en choisir plusieurs en parallèle et de leur donner des importances relatives afin d’influencer la répartition des ressources. Pour améliorer l’intelligibilité nous utilisons un modèle graphique inspiré des machines à états finis et des behavior trees. Les stratégies créées à l’aide de notre modèle sont ensuite exécutées par le moteur de stratégie pour produire des directives qui sont données au module tactique. Ces directives se présentent sous la forme d’objectifs stratégiques et de ressources qui leur sont allouées en fonction de leurs besoins et de l’importance relative qui leur a été donnée. Le module stratégique permet donc de rendre accessible la conception du niveau stratégique d’une IA contrôlant un adversaire dans un jeu de stratégie. / This PhD thesis addresses the topic of creating artificial intelligence (AI) to control high-level decision-making in strategy games. This kind of game offers complex environments that require the manipulation of a large number of resources by choosing actions depending on long-term goals. This AI design is not simple because it is about providing to the player a playful and interesting experience. Hence, the aim is not to create unbeatable behaviors, but rather to display several personality traits allowing the player to face diverse opponents. Its creation involves game designers who are responsible of defining several strategies according to the experience they want to provide to the player, and game developers who implement those strategies to put them into the game. The collaboration between them requires many exchanges and development iterations to obtain a result corresponding to game designers’ expectations. The objective of this PhD thesis is to improve and simplify the creation of strategical behaviors by proposing a strategy model intelligible to game designers and that can be interfaced easily with developers’ work. For game designers, a strategy model has been created to allow them to express rules guiding the choice of goals and their allocated resources. These rules make it possible for game designers to express which goal to choose according to the context but also to choose several of them and give them relative importance in order to influence the resource distribution. To improve intelligibility we use a graphical model inspired from finite state machines and behavior trees. Our proposition also includes a strategy engine which executes the strategies created with the model. This execution produces directives that are represented by a list of selected strategical goals and the resources that have been allocated according to the importance and needs of each goal. These directives are intended for a tactical module in charge of their application. The developers are then responsible for the implementation of this tactical module. Our solution enables game designers to directly design the strategical level of an AI and therefore facilitates their cooperation with game developers and simplifies the entire creation process of the AI.

L'objectif de notre travail est de déterminer des algorithmes qui facilitent la résolution de jeux combinatoires par des calculs informatiques. En premier lieu, nous expliquons comment l'implémentation du nimber permet d'accélérer le calcul de jeux impartiaux en version normale. Puis, nous proposons des raffinements ou des généralisations d'algorithmes de parcours des arbres de jeu, en particulier le PN-search, tout en discutant de l'intérêt de l'intervention humaine lors de l'exécution de ces algorithmes. Enfin, nous présentons des algorithmes de vérification, dont le but initial était de s'assurer de la validité de nos calculs, mais qui permettent également d'obtenir des arbres solutions de taille réduite. Ces techniques sont appliquées à l'étude de deux jeux : le Sprouts, où les joueurs relient des points par des lignes, et le Dots-and-boxes, dont le but est de compléter le maximum de boîtes en plaçant des arêtes. Le Sprouts est un jeu combinatoire impartial, dont la nature topologique rend difficile la représentation informatique. Nous explicitons une telle représentation, avant d'étudier une généralisation où le jeu se déroule sur des surfaces compactes. Le Dots-and-boxes est un jeu partisan, et nous détaillons diverses simplifications théoriques qui nous ont permis d'obtenir informatiquement des résultats nouveaux sur ce jeu.

Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.

Pour respecter les droits d’auteur, la version électronique de ce mémoire a été dépouillée de ses documents visuels et audio‐visuels. La version intégrale du mémoire a été déposée au Service de la gestion des documents et des archives de l'Université de Montréal. / Cette recherche propose une analyse du jeu de stratégie en temps réel StarCraft (Blizzard Entertainment, 1998). Il s’agit de questionner le concept de stratégie dans le jeu sans s’en tenir à ce qu’on peut voir et entendre. Ce mémoire débute sur une description du jeu en détails afin de faire ressortir comment la stratégie joue un rôle dans l’ensemble des compétences qui y sont mobilisées. Ensuite, le cercle heuristique du processus stratégique offre une modélisation du fonctionnement de la stratégie en tant que processus cognitif, basé sur les états du jeu inférés chez le joueur et sur ses plans stratégiques. Ce modèle et les concepts qui en découlent sont consolidés par des analyses de parties spécifiques de StarCraft. / This thesis offers an analysis of the Real-Time Strategy game StarCraft (Blizzard Entertainment, 1998). Its goal is to explore beyond the visible and audible part of the game to elucidate the concept of strategy into play. Following a description of the game and its constraints, it demonstrates how strategy plays a major role within the skills needed to play. Then, our “heuristic circle of the strategic process” describes how strategy works as a cognitive process, and how it interacts with both the game states inferred by the player and his or her strategic plans. Finally, this model and its underlying concepts are supported by close analyses of StarCraft game sequences.