Eléments de correction du concours de chasse au Wumpus
Posted: 09 Nov 2013, 16:55Voici aujourd'hui quelques éléments de corrections de notre concours de chasse au Wumpus dans le contexte de graphes et d'IA (Intelligence Artificielle), qui pourront apparemment vous être fort utiles si vous décidez de participer au concours Prologin 2014.
Vous pourrez télécharger ci-dessous ma propre participation test (hors concours bien évidemment) que j'ai développée en une journée. Elle ne reprend pas l'ensemble des possibilités énoncées ci-après, mais est représentative de ce que l'on pouvait faire sans trop se casser la tête à un niveau lycée.
Le travail de recherche consistait dans un premier temps à observer le comportement de l'IA aléatoire et à supprimer les comportements stupides:
L'IA a donc besoin d'une mémoire dans laquelle elle va construire au fur et à mesure sa représentation du labygraphe. Représenter un graphe peut se faire à l'aide d'un tableau à deux dimensions (matrice) ou encore d'une liste de listes. Dans les deux cas, il s'agit de connaître pour chaque salle, la liste des salles voisines. J'ai choisi pour mon IA une représentation sous forme de matrice.
L'IA doit également réfléchir. Elle doit également pouvoir stocker des informations sur chaque salle afin de faire des déductions:
Si la première question n'appelle qu'à une réponse binaire (oui ou non), il fallait bien comprendre que les trois dernières attendaient une réponse moins catégorique: oui, non ou peut-être.
En effet, au départ on ne sait rien: les Wumpus, piège(s) et trésor peuvent se situer dans toutes les salles. C'est au fur et à mesure de notre exploration que l'on peut faire des déductions positives et négatives.
Plusieurs possibilités d'implémentation d'un tel raisonnement existaient:
Notre IA suit successivement deux phases:
Pour le première phase, je vous propose les priorités suivantes à chaque déplacement:
Comme vous le voyez, quand il n'y a plus de salle sûre à explorer et que l'on n'a pas suffisamment d'informations pour déduire ce qui nous intéresse, l'IA en appelle à la chance. Et c'est là qu'il est utile d'avoir stocké de vraies probabilités.
Enfin, à chaque déplacement on choisit donc une salle cible qui n'est pas forcément voisine de notre position. Il convient pour optimiser les déplacements d'avoir un algorithme construisant le plus court chemin vers cette salle.
Un tel algorithme recherchant le plus court chemin entre deux sommets d'un graphe est celui de Dijkstra, vu en Terminale ES spécialité mathématiques. On peut alors même améliorer les priorités b), c) et d) où l'on doit choisir parmi plusieurs salles, en ciblant la salle la plus proche.
J'ai implémenté cet algorithme.
Au final grâce à ce dernier point, parmi toutes les IA fournies par les candidats la mienne est celle qui réussit à ressortir munie du trésor avec le minimum de coups moyens.
Par contre, ce n'est pas la meilleure en terme de pourcentage de parties gagnées, puisque l'on peut faire bien mieux en déduction en optant pour les méthodes c) et d) ci-dessus.
Téléchargement : archives_voir.php?id=22671
Vous pourrez télécharger ci-dessous ma propre participation test (hors concours bien évidemment) que j'ai développée en une journée. Elle ne reprend pas l'ensemble des possibilités énoncées ci-après, mais est représentative de ce que l'on pouvait faire sans trop se casser la tête à un niveau lycée.
- retourner inutilement dans la salle d'où l'on vient
- retourner inutilement dans une salle déjà visitée
- ne pas trouver la sortie après avoir ramassé le trésor
L'IA a donc besoin d'une mémoire dans laquelle elle va construire au fur et à mesure sa représentation du labygraphe. Représenter un graphe peut se faire à l'aide d'un tableau à deux dimensions (matrice) ou encore d'une liste de listes. Dans les deux cas, il s'agit de connaître pour chaque salle, la liste des salles voisines. J'ai choisi pour mon IA une représentation sous forme de matrice.
L'IA doit également réfléchir. Elle doit également pouvoir stocker des informations sur chaque salle afin de faire des déductions:
- est-ce une salle explorée?
- y a-t-il un piège dedans?
- y a-t-il le Wumpus dedans?
- y a-t-il le trésor dedans?
Si la première question n'appelle qu'à une réponse binaire (oui ou non), il fallait bien comprendre que les trois dernières attendaient une réponse moins catégorique: oui, non ou peut-être.
En effet, au départ on ne sait rien: les Wumpus, piège(s) et trésor peuvent se situer dans toutes les salles. C'est au fur et à mesure de notre exploration que l'on peut faire des déductions positives et négatives.
Plusieurs possibilités d'implémentation d'un tel raisonnement existaient:
- Une première possibilité quand notre IA visite une salle, est de faire des déductions logiques sur les salles voisines en fonction des perceptions.
- Si l'on réfléchit davantage, on se rend compte que comme il n'y a qu'un seul Wumpus et qu'un seul trésor, on peut également faire des déductions sur les salles voisines des salles voisines. C'est cette option que j'ai choisie.
- Si l'on pousse plus loin, une information obtenue dans une salle du labygraphe peut permettre une déduction dans une autre salle éloignée. Reproduire un tel raisonnement peut se faire en implémentant un gestionnaire de propositions logiques et la "méthode de résolution logique" qui va recouper ces propositions avec les informations données et faire le maximum de déductions. Je n'ai pas retenu cette option, trouvant qu'il était difficile d'exécuter une telle méthode en un temps raisonnable sur TI-Nspire, l'espace de travail étant exponentiel: chaque salle, puis les voisines de chaque salle, puis les voisines des voisines de chaque salle et etc...
- Une amélioration des déductions découlant de la méthode précédente est de ne plus stocker des oui/non/peut-être, mais directement des probabilités totales. Leur calcul qui doit se faire par rapport à l'ensemble du graphe est assez gourmand. Je n'ai pas implémenté ce choix ici.
Notre IA suit successivement deux phases:
- 1) trouver le trésor
- 2) sortir du labygraphe
Pour le première phase, je vous propose les priorités suivantes à chaque déplacement:
- a) aller dans la salle du trésor (si l'on a déduit où il est)
- b) aller dans une salle sûre non explorée, ou dans la salle du Wumpus (si on a déduit où il était et si on a toujours la flèche pour le tuer)
- c) pas le choix, on en appelle à la chance: aller dans une salle où il y a peut-être un piège ou un Wumpus (en espérant qu'au final il n'y soit pas)
- d) on est désespéré: aller dans une salle piégée ou avec le Wumpus (suicide)
Comme vous le voyez, quand il n'y a plus de salle sûre à explorer et que l'on n'a pas suffisamment d'informations pour déduire ce qui nous intéresse, l'IA en appelle à la chance. Et c'est là qu'il est utile d'avoir stocké de vraies probabilités.
Enfin, à chaque déplacement on choisit donc une salle cible qui n'est pas forcément voisine de notre position. Il convient pour optimiser les déplacements d'avoir un algorithme construisant le plus court chemin vers cette salle.
Un tel algorithme recherchant le plus court chemin entre deux sommets d'un graphe est celui de Dijkstra, vu en Terminale ES spécialité mathématiques. On peut alors même améliorer les priorités b), c) et d) où l'on doit choisir parmi plusieurs salles, en ciblant la salle la plus proche.
J'ai implémenté cet algorithme.
Au final grâce à ce dernier point, parmi toutes les IA fournies par les candidats la mienne est celle qui réussit à ressortir munie du trésor avec le minimum de coups moyens.
Par contre, ce n'est pas la meilleure en terme de pourcentage de parties gagnées, puisque l'on peut faire bien mieux en déduction en optant pour les méthodes c) et d) ci-dessus.
Téléchargement : archives_voir.php?id=22671
