Le sous‐sol des Wumpus -Sammy Bessette, Alexandre Deschamps, Simon Langevin et Jean‐Michel Nadeau

Présentation de projet conjoint
Ift615, intelligence artificielle et Ift630, processus concurrents et parallélisme

Motivation

Après beaucoup de questionnements à propos du sujet du projet, et après un long brainstorm, l’équipe
s’est mise d’accord pour implanter un monde de Wumpus. Cependant, il ne devait pas être simpliste ni
ennuyant. Nous avons donc changé un peu la mise en situation de ce monde pour le transformer en
sous‐sol.

Mise en situation

Plusieurs personnes fêtent dans une taverne quand la bière vient à manquer. Il en reste, mais elle est cachée au sous‐sol, qui est infesté de Wumpus. Quelques braves décident d’aller en chercher.

Cependant, au bout de quelques pas, ils se frappent tous la tête et oublient tout : pourquoi ils étaient descendu, comment remonter, etc. Étant aussi devenus très paranoïaques, dès qu’ils rencontreront un de leurs confrères, ils se battront à mort avec lui.

Ils devront apprendre comment survivre et comment retrouver leur chemin, que ce soit pour trouver le baril de bière ou pour sortir du sous‐sol des Wumpus.

Idée générale
Plusieurs personnes (clients) se promènent en temps réel dans le monde des Wumpus. Lors de la mort ou de la réussite d’un des clients, son « fils » refait l’aventure avec l’expérience de son père.

Résumé sur L’IA
Chacun des clients utilisera un algorithme de type Q‐Learning pour apprendre à se déplacer
adéquatement et intelligemment dans le sous‐sol. Ses seuls moyens de reconnaissance seront les
« sens » qu’il aura, comme l’odorat et l’ouïe. Aussi, un algorithme A* adapté s’assurera que la carte,
générée aléatoirement, ait une sortie accessible et qu’aucun des joueurs ne soit pris ad vitam aeternam
dans le sous‐sol.

Résumé sur l’architecture distribuée
Chacun des clients sera un programme indépendant pouvant rouler sur une différente machine et se
connectera au serveur, qui gèrera la carte. De plus, les clients pourront communiquer directement entre
eux, dans le cas d’une bagarre. Toute la communication sera implantée par sockets.

Intelligence artificielle

Énoncé du problème
Les clients – ayant tout oublié – devront reconstruire leur mémoire à l’aide d’une association
sens/récompenses. C'est‐à‐dire que chacun des clients ne saura pas ce qu’il doit faire pour vivre et
mourir, et – au bout de plusieurs itérations – il fera une association entre ce que ses sens (est‐ce que ça
pue, est‐ce qu’il y a du vent, etc.) lui ont indiqué et la probabilité moyenne pondérée d’être récompensé
de bonheur (sortir, avoir la bière, etc.).

Le tout sera implanté à l’aide d’un algorithme de type Q‐Learning qui sera indépendant de clients en
clients. Cette indépendance aura comme résultat que chacun des clients apprendra des choses
différentes. Le client ne saura même pas ce qu’est son but, ni comment sortir du sous‐sol; il devra tout
réapprendre. Lors de la mort d’un personnage et après un court délai, un nouveau personnage (le fils de ce dernier) apparaîtra dans le sous‐sol avec la mémoire de son père, ce qui permettra une évolution plus grande.
La carte sera générée par un engin aléatoire, afin qu’aucun des clients ne puise « tricher » et se
remémorer la carte au lieu d’apprendre comment maximiser ses chances de gagner. Afin de valider que
tous les chemins sont accessibles, nous utiliseront un algorithme A* modifié qui passera en revu toute la
carte et qui s’assurera (en débouchant des murs ou en enlevant des trous, par exemple) que tous les
endroits importants (endroit d’apparition des différents clients, sortir, bière) sont accessibles.
Résultats attendus
À la fin du projet, nous souhaitons obtenir des agents qui sont capable, grâce à l’algorithme Q‐Learning,
d’apprendre à jouer à un jeu simple. Dans le cas présent, nous souhaitons les voir jouer à notre version
modifié du monde des Wumpus.

Ultimement, nous souhaiterions voir un joueur évoluer suffisamment pour qu’il puisse récupérer le baril
de bière et se rendre à la sortie.

Une autre partie du projet concerne la création de sous‐sols. Effectivement, pour que les agents ait un
défi à leurs tailles, nous voulons les faire jouer sur des cartes uniques qui seront crées et validées. Nous
voulons donc être capables de générer efficacement et rapidement un sous‐sol de dimensions variable.
Évaluation
Dans le cadre du cours IFT 615, nous croyons que notre évaluation devrait être fait selon les critères
suivant:

• Notre implémentation de Q‐Learning.
• L’efficacité de l’apprentissage.
• La création de sous‐sols.

Nous laissons de coté l’évaluation sur le coté graphique réalisé à l’aide de XNA. Nous ne croyons pas que la création d’affichage graphique soit pertinente dans le cadre du cours.

Parallélisme

Le projet se divise en deux programmes qui devront rouler ensemble et s’échanger des informations.
Les clients utiliseront les informations transmises par le serveur afin de choisir la meilleure action à
réaliser avant de l’envoyer au serveur.

Le serveur sera l’entité suprême qui contrôlera la création de la carte, l’affichage des mouvements des
joueurs et la synchronisation de tout ce beau monde.

Étant donné que les clients seront exécutés en temps réel, il faudra s’assurer qu’aucun conflit ne sera
crée par les déplacements de ces derniers. Une synchronisation spéciale devra être mise en place afin de bien gérer les situations de combat. C’est à dire qu’une connexion client‐client devras être mis en place afin qu’ils gèrent le combat entre eux et qu’ensuite le résultat soit transmis au serveur.

Les clients seront peut‐être parallélisés eux‐mêmes si le besoin s’en fait sentir.

Implémentation
 

Pour la réalisation de ce projet, notre équipe à décidé d’utiliser le C#. L’utilisation de ce langage
permettra de focaliser nos énergies dans l’implémentation de l’algorithme Q‐Learning et de faciliter la
parallélisations.

Afin de rendre le projet visuellement intéressant à présenter, nous souhaitons ajouter une interface
graphique en deux dimensions, réalisée avec XNA. Cette librairie à été privilégié face à BEEF par
exemple, car son intégration dans VisualStudio et avec C# est parfaite. De plus, certains membres de
notre équipe ont déjà travaillé avec XNA et vu le temps alloué pour la réalisation de ce projet, nous
souhaitons profiter au maximum des acquis et expertise présente dans notre équipe.