# IA02 - Rapport HellTaker - P22

* **Auteurs** **:** Anaël Lacour, Antoine Marquis et Pierre Tétard
* **Enseignants :** Sylvain Lagrue et Khaled Belahcène

### Introduction

L’objet de ce rapport est l’étude de la partie labyrinthe (1ère partie) du jeu HellTaker. Il s’agit d’un jeu de type Sokoban. Un personnage doit résoudre une série de labyrinthes contenant ennemis, pièges et objets à récupérer. Pour préciser l’univers de HelleTaker, le protagoniste se réveille un matin avec pour objectif de former son propre harems de démonesses. Il se rend donc en enfer pour tenter de trouver les différents éléments de son harem.

Nous nous attacherons dans un premier temps à modéliser le problème en STRIPS. Ensuite, nous tenterons d’apporter une solution à ce problème en implémentant deux méthodes de résolution, à savoir la recherche dans un espace d’états grâce à un algorithme A* (en python) et un solveur SAT.

### I. Préliminaires
A. Présentation des règles du jeu

Les règles du jeu sont relativement simples. Le but du jeu est d’atteindre la démonesse de chaque niveau et de répondre correctement à leur unique question respective.

Le joueur possède un nombre de coups imposé pour chaque niveau. Chaque labyrinthe est clos et le joueur a la possibilité de se déplacer dans les 4 directions. Voici les différents éléments que l’on peut rencontrer dans le jeu :
* deux personnages : le joueur et la démonesse qui représente la sortie.
* des blocs de pierre : ils entravent le chemin du joueur qui a la possibilité de les pousser, sauf s' il y a un mur, un autre bloc ou un ennemi derrière.
* des pièges (mobiles ou fixes) : lorsque le joueur tombe sur un piège, il perd un point de déplacement supplémentaire. Les pièges mobiles alternent entre une position “inactive” et une position “active” à chaque déplacement du joueur.
* des ennemis : si le joueur se trouve face à un ennemi et qu’il va dans la direction de cet ennemi, il le frappe et l’ennemi recule d’une case dans cette direction. Lorsque le joueur frappe un ennemi sur le mur, sur un bloc de pierre ou sur un piège actif.
* une clé et un cadenas : il ne peut y avoir qu'une seule clé par niveau et une fois récupérée elle permet de déverrouiller le cadenas.

Enfin, si le héros ne respecte pas le nombre de coups pour atteindre la sortie ou ne répond pas correctement à la question de la démonnesse, il perdra et se fera foudroyer. S'il y parvient, il passera au niveau suivant.

B. Le problème en STRIPS

HellTaker possède un grand nombre de points communs avec le jeu du Sokoban. Cependant, il est légèrement plus complexe. On trouve dans les labyrinthes du HellTaker :

* une sortie représentée par les cases entourant la démonnesse.
* des ennemis/squelettes que l’on peut détruire.
* des pièges, mobiles ou fixes, qui ajoutent une difficulté en enlevant un point d’action au joueur lorsqu’il tombe dedans.
* une clé et un cadenas pour ajouter une étape avant l’accès à la sortie.

De plus, les points d’ancrages du Sokoban disparaissent dans le HellTaker. En effet le but du jeu n’est plus de placer les blocs dans une certaine configuration mais de parvenir dans le nombre de coups imparti à atteindre la sortie. On peut noter aussi que lorsque le joueur pousse un bloc ou frappe un ennemi, il reste à la même position dans le labyrinthe, seul le bloc ou l’ennemi recule. Dans le Sokoban au contraire, le joueur pousse le bloc et avance dans le même coup.
Enfin, le HellTaker ajoute un nombre de points d’action à respecter pour chaque niveau.

La conséquence directe de ces différences avec le Sokoban est que les actions possibles du joueur à chaque tour sont multipliées. Dans HellTaker, le joueur pourra donc réaliser les actions suivantes : se déplacer vers une case libre, frapper/tuer un ennemi, pousser un bloc, prendre la clé, déverrouiller le cadenas, tomber dans un piège actif ou tomber dans un piège passif.

Voir le fichier HellTaker-STRIPS.pdf en Annexe.

### II. Recherche dans un espace d’état (python)
A. Représentation du problème

Un premier objet (“mapTaker”) contient la logique métier pour créer une map depuis le fichier texte. Dans cet objet on définit les différents objets de la map avec un intégrateur (le protagoniste, la sortie, les squelettes, les blocs de pierre et les pièges).
A partir de cette map et de ses différents attributs, on crée un objet matrice grâce à numpy (numpy.array). A chaque élément de la map on associe un numéro (1: player, 2: pièges, 3: block…, 15: block-on Trap).
Comme on se doute, il y a beaucoup de cas possibles, la bonne pratique ( avec une logique de matrice )aurait été de modéliser le contenu d’une case avec un objet ,qui est solide,ou collectable.

Par exemple, lorsque le joueur est sur un piège, il faudra associer un numéro unique à cette situation. On aura donc un numéro qui correspond à “player + piège”.
Une modélisation avec des tuples aurait simplifié la modélisation et permis d’éviter des parcours de toute la matrice . Par exemple, à chaque itération on doit parcourir tout les pièges pour changer le statut ( ce qui prend environs 50% du temps d’une simple itération )

Ensuite on a créé un objet “node”. Il contient la position actuelle du joueur, le parent - c’est-à-dire la position du joueur à t-1 -, un coût (heuristique), le nombre de mouvements et la matrice correspondant à la map. Cet objet possède des méthodes qu’il faut expliquer :
* “Create-child” (logique “doMove”) : Renvoie potentiellement 4 nœuds fils, correspondants aux quatres cases à porté du player. Renvoie une erreur si le “doMove” n’est pas possible.
* "_ _eq_ _" : Compare deux hashs entre eux.
* "update_trap" : update le status on/off de chaque piège.

Nous allons maintenant présenter les algorithmes utilisés ainsi que les différentes heuristiques.

B. Choix d’implémentation et structure des données

On utilise un algorithme A*. C’est une extension de l’algorithme de Djikstra. Dans un graphe, connaissant a priori le noeud de départ et le noeud d’arrivée, l’algorithme A* va chercher un chemin solution optimisé grâce à une heuristique reposant sur le coût associé à chaque nœud.
On peut se demander à présent comment faire pour optimiser le chemin. Dans un premier temps, on prend la map actuelle et on la compare avec les maps “historiques”, préalablement sauvegardées et on se demande si la position a déjà été observée. Pour ne pas comparer à chaque itération toute la matrice, on applique un hash grâce à numpy.array, et on va comparer les hashs des matrices.

Ensuite,pour ne pas se déplacer au hasard, on définit une heuristique. Une première heuristique consiste à prendre la distance euclidienne entre le player et la sortie. Plus on est proche, moins le chemin coûte cher. Cette heuristique est minorante

Une deuxième heuristique passe par deux étapes. On supprime tout d’abord tous les objets, sauf la sortie, la clé et le cadenas, pour trouver le plus court chemin en ignorant les difficultés ( on garde le cadenas si celui est considéré comme bloquant )

Nous avons conçu une heuristique non minorante en affectant un numéro à chaque case correspondant au nombre de coups pour y parvenir et on prend une distance euclidienne par rapport au chemin. C'est-à-dire que la case numéro 1 ( celle de départ du joueur ) est élevée ,et la dernière ( celle des Démones ) est faible.


***Figure 1** : map représentant les coûts des différentes cases (niveau 1) et le parcours optimal.*

Cette heuristique (2) ne donne pas de bon résultat, même en étant dopée à un algorithme génétique.

Optimisation du code réalisé :
- Comparaison de **Hash** : au début,on comparé les numpy arrays et on parcourait tout la matrice,ce qui était long ( gain divisé par 6 approximativement )

- Système de **break-loop** :Auparavant,on vérifié si dans toute la liste le nombre de hash d’un maze était supérieur à 0 ( donc potentiellement on pouvait en trouver 2 ) , or, dès qu’il y en a 1 similaire il faut arrêter cette boucle for très couteuse. Il est possible de retrouver des labyrinthes similaire puisque l’on hash l’état d’un labyrinthe , et non pas les informations tel que le nombre de mouvement restant

- Changer la structure, en prenant un **dictionnaire**, où la clef correspond à la position et le contenu est trié à l’intérieur ( avec le coût le plus faible et le nombre de coût restant.Ainsi,pour prendre le coût le plus faible depuis chaque position il suffit de prendre le premier élément.Étrangement, ce système de tri, et de structure plus optimisé n'accélère pas grandement le processus.

###### *Algorithme génétique*
Toujours dans le but d’optimiser la résolution du problème. Nous avons utilisé un algorithme génétique afin de minimiser le temps de recherche d’une solution. Il s’agit d’un algorithme évolutionniste qui s’inspire des dynamiques de sélection naturelles. Ici, afin de minimiser notre fonction de l'heuristique, nous avons choisi comme paramètre (gène) de l’algorithme génétique le coût.
Le problème étant qu’il faut faire apprendre sur des maps différentes,pour éviter le surapprentissage.

***Figure 2** : Courbe représentant l'évolution du fitness au court des générations.*

Ainsi,avec un exemple sur 5 générations, sur une seule map , on voit qu’au bout de seulement 2 générations (2 multiplications et 2 sélections) les meilleurs paramètres sont obtenu pour optimiser la map. Ainsi avec cette algorithme génétique on obtenait 2 secondes au départ sans paramètres, à seulement 0,15 avec les paramètres d’heuristique.

C. Expérimentation pratiques

Dans cette partie, nous allons vous présenter nos différents résultats.

| Niveau | Temps d'exécution (en secondes) |
| -------- | -------- |
| 1 | 3 |
| 2 | 0,5 |
| 3 | 4 |
| 4 | 7 |
| 5 | 10 |
| 6 | 30 |
| 7 | Aucun |
| 8 | 1 |
| 9 | Infini |

***Figure 3** : Temps d'exécution sur chacun des niveaux (sans algorithme génétique).*

Le niveau 7 ne trouve pas de solution, puisque notre heuristique nous encourage à allez vers le haut, et qu’on enregistre des solutions où le labyrinthe est dans une mauvaise configuration.

Pour finir voici les résultats obtenus avec l'algorithme génétique.

| Niveau | Temps d'exécution (en secondes) |
| -------- | -------- |
| 1 | 5 |
| 2 | 0,4 |
| 3 | 2,3 |
| 4 | 6 |
| 5 | 5 |
| 6 | 28 |
| 7 | - |
| 8 | 0,2 |
| 9 | - |

***Figure 4** : Temps d'exécution sur chacun des niveaux (avec algorithme génétique appris sur les niveaux 1 à 5, et avec un faible nombre de génération (10) et de population (6/3)).*

Pour conclure sur la parti Python,une matrice comme structure de donnés pour un tel système, n’est pas optimal, on aurait pu trouver avec un système de set(tuple) empêcher tout les cas symétriques, détecter plus facilement les collisions,gérer les cas des boxes sur des objets au sol sans des règles métiers très longue ( 500 lignes de codes de logique brute,pour la fonction do_move, c’est énorme, et ce n’est pas maintenable dans le cadre d’un projet hors étudiant ),et également faire un a_star qui calcule directement tout le chemin vers la fin.

Beaucoup de tentatives d’optimisation ont donc été réalisées, mais peu sont véritablement efficace, l’agorithme génétique peut correspondre à un brute force d’apprentissage, l’avantage c’est qu’il sera normalement capable de répondre plus facilement à des maps similaires.

L’heuristique du chemin le plus court est une bonne idée sur des labyrinthes très grands,pas sur des problèmes où il faut optimiser le placement des blocs.

### III. SATPLAN (réécriture en SAT du problème de planification)

#### A. Représentation du problème

Pour la résolution du problème, nous avons établi des variables et décrit des règles avec celles-ci. Dans cette modélisation, l'algorithmique (codée en python) sert simplement à créer le les variables ainsi que les règles. Les algorithmes ne vont en aucun cas aider à résoudre le problème.
Ce choix de méthode pour la résolution du problème est dû au contexte, étant un exercice, le but est pour nous d’apprendre à résoudre un problème complexe en SAT.
En utilisant des algorithmes pour commencer à résoudre le problème et ainsi considérablement réduire le nombre de règles mais aussi de variables, ce qui aurait pour effet principal d’accélérer le temps de résolution (de la lecture à l’affichage de la solution) mais potentiellement améliorer la lisibilité du sujet. Cette méthode hybride entre algorithmes python et résolution SAT aurait demandé un structuration général s’éloignant d’un exercice de représentation SAT, ce qui nous aurait éloigné du but de l’exercice.

#### B. Choix d’implémentation et structure des données

##### Les variables

Nous avons modélisé le problème par 2 types de variables, décrites par des tuples de taille 3 (type, temps, information) :
* Les variables “at” décrivent la position d’un objet sur la carte. L’information est un couple objet-position :
* L’objet étant un parmi ceux de la liste suivante : "player", "wall", "mob", "simple_trap", "unactive_trap", "active_trap", "key", "chest", "box"
* La position étant représentée par un couple (x, y) parmi les cases présentent sur la carte.
* Les variables “do” les actions effectuées. L’information est une action :
* L’action étant une parmi les suivantes "up", "down", "right", "left", "take dammage". Avec la dernière étant la représentation de la perte d’un coup lorsque que le joueur passe sur un piège
* Le temps correspond à chaque fois au nombre de coups effectués au préalable.

##### Les Règles

Pour simplifier la lecture, nous avons séparé les règles en plusieurs catégories. Cependant, ces catégories n’ont aucune influence sur la résolution. Même si certaines règles pourraient appartenir à plusieurs catégories, cela ne pose donc aucun problème. Par ailleurs, les règles sont ordonnées et catégorisées de la même manière dans le code.

1. Unicités et murs
* Un et uniquement un joueur par temps de jeu
* Une et uniquement une action par temps de jeu
* Sur chaque case, pour chaque temps de jeu, il ne peut y avoir au maximum qu'un seul des objets parmi la liste suivante : player, mob, key, chest, box
* Il n'y a aucun objet là où il y a des murs
* Il y a des murs là où il y a des murs à l'initiation (à tout temps) et uniquement à ces endroits
2. Clefs et coffres (dans cette logique les coffres sont détruits à la récupération de la clefs)
* Si il y en a un, c'est qu'il y en avait un au tour d'avant
* Quand un joueur est sur une clef, les clefs disparaissent
* Quand un joueur est sur une clef, les coffres disparaissent
* Si un joueur ne marche pas sur une clef, les clefs restent
* Si un joueur ne marche pas sur une clef, les coffres restent
3. Joueurs, déplacements et dégats
* Si un joueur se déplace en direction d'une case disponible, il y sera au temps suivant
* Si un joueur se déplace en direction d'une case non disponible, il sera sur la même case au temps suivant
* Si un joueur est sur une case infligeant des dégâts, il aura pour action de prendre des dégâts au même temps (temps d'action suit le temps de position)
* Si un joueur prend des dégâts, il gardera la même position au temps suivant
* Si un joueur prend des dégâts, il n'en prend pas au temps suivant
* Si un joueur n'est pas sur une case infligeant des dégâts, il ne prend pas de dégâts au même temps
4. Pièges
* Si un joueur ne prend pas de dégâts, les pièges qui s'activent changent d'états d'activation
* Si un joueur prend des dégâts, les pièges gardent le même état
* Pas plus d'un piège par case
* Pas de piège à tout temps là où il n'y a pas de piège à l'initialisation
5. Mouvements des squelettes et boîtes
* Si un joueur déplace une boite ou un squelette vers une case vide, il y aura cet objet au temps suivant
* Si un squelette ou une boîte n'est pas déplacé, elle est toujours là au temps suivant
* Si il n'y a pas de boite et que le joueur n'en déplace pas une sur la case, il n'y aura pas de boite
* Même chose pour le squelette avec la vérification dans le cas de la présence que le joueur ne le détruit pas
6. Arrivée
* La position du joueur au dernier temps doit être à un déplacement du but (dans le jeu on doit arriver à côté du personnage de fin)
7. Initialisation
* Au temps 0, les positions sont forcées tel que décrites sur la carte
* Les pièges simple sont à tout temps au même endroit qu'indiqué sur la carte

#### C. Expérimentation pratiques

Par manque de temps, la partie sur les comportements des boites et squelettes à dû être en partie retirer pour obtenir des résultats fonctionnelles. Même si la majorité des règles sont écrites, en pratique notre résolution sat résoud un labyrinthe standard.

### Annexes

- HellTaker-STRIPS.pdf