Present Remotely
Send the link below via email or IM
Present to your audience
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Présentation projet Prolog Pacman
No description
by
TweetTimothée Muller
on 5 November 2013Transcript of Présentation projet Prolog Pacman
IA Pacman
basique
Poids affecté aux éléments (boules, fantômes) sur les cases adjacentes
Poids fonction de la distance/fantômes (exp décroissante)
À défaut, revient au centre
Projet ALIA
BRODSKY Kévin – CANTENOT Thierry
CARENSAC Samuel – DUDOUIT Aurélien
MARTINET Antoine – MULLER Timothée
RAMIREZ HERNANDEZ Carlos Eduardo
4IF
Groupe 1
Novembre 2013
Projet : jeu Pacman, IA de Pacman et des fantômes
implémenter un jeu proche de Pacman
réaliser différentes IA pour contrôler Pacman et les 4 fantômes
comparer les différentes combinaisons d'IAs
évaluer l'efficacité des différentes approches à la base des IA
Objectifs
IA Pacman
IA Pacman
"fourmi"
IA Pacman
parcours de chemin
IA fantômes
distance Pacman
IA fantômes
IA fantômes
"fourmi"
IA fantômes
vision Pacman
Évaluation et comparaison des IA
Méthode d'évaluation des IA
Résultats : boules mangées (moyenne)
Conclusion
Améliorations envisageables Pacman
Démonstration
À chaque croisement, choisit le déplacement permettant de minimiser la distance avec Pacman
L'IA est paramétrable pour permettre de ne choisir le meilleur choix qu'avec une certaine probabilité
Cette IA ne peut pas faire de demi-tour
À un croisement, se dirige vers Pacman quand celui-ci est dans son champ de vision. (Pacman doit se trouver sur la même ligne/colonne sans obstacle entre ce dernier et le fantôme)
Une version "améliorée" possède un vision à travers les obstacles
Cette IA ne peut pas faire de demi-tour
IA hybride
Algorithme primaire de parcours de chemin
Algorithme secondaire de recherche
Algorithme primaire : parcours de chemin de longueur L fixe donnée
<=> Parcours d'arbre en profondeur d'abord et de profondeur limitée
Poids attribué à chaque case
Vide : 0
Boule, fantôme "peureux" : négatif
Fantôme : positif
Poids d'une case décroissant avec la profondeur de la case dans le chemin considéré
Chemins considérés : tous les chemins de longueur L partant de Pacman
Poids d'un chemin = somme des poids des cases
But : minimiser le poids du chemin
Algorithme secondaire : recherche du plus court chemin pour atteindre une boule
Recherche du plus court chemin implémentée par A*
La boule B la plus proche est choisie comme "point de mire"
Heuristique : distance (Manhattan) entre Pacman et B
À chaque tour tente de se déplacer vers l'endroit où Pacman aura tendance à se diriger (grace à une pondération suivant les éléments se trouvant sur le chemin)
Laisse une trace de son passage (s'atténuant au cours du temps) pour éviter de revenir vers les endroits déjà parcourus
Cette IA peut faire des demi-tours
Pour chaque couple d'IA, nous évaluons 100 parties.
Nous collectons :
- le taux de victoires
- le nombre de coups joués
- le nombre de boules mangées
- le nombre de fantomes dévorés
Prise en compte du temps restant d'invulnerabilité pour Pacman
Calculer à l'avance les n prochains mouvements
Prendre en compte le sens de déplacement des fantômes (la plupart ne peuvent pas faire demi-tour)
Améliorations envisageables fantômes
Avoir une IA qui communique entre les différents fantômes pour piéger Pacman
Calculer à l'avance les n prochains mouvements
Prévoir heuristiquement les déplacements de Pacman
Prendre en compte les spécificités du terrain (situations particulières)
Résultats : nombre de victoires (/100)
Résultats : nombre de coups (moyenne)
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
Résultats : score (moyenne)
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
A chaque tour tente de se déplacer dans la position la plus avantageuse (plus de boules, moins de fantômes)
Laisse une trace de son passage (s'atténuant au cours du temps) pour éviter de revenir vers les endroits déjà parcourus
Fonctionnalités essentielles implémentées
IA suffisamment variées pour pouvoir faire des comparaisons
Introduction d'aléatoire bénéfique aux IA fantômes
IA Pacman : équilibre à trouver entre prise de risque et sécurité
Full transcriptbasique
Poids affecté aux éléments (boules, fantômes) sur les cases adjacentes
Poids fonction de la distance/fantômes (exp décroissante)
À défaut, revient au centre
Projet ALIA
BRODSKY Kévin – CANTENOT Thierry
CARENSAC Samuel – DUDOUIT Aurélien
MARTINET Antoine – MULLER Timothée
RAMIREZ HERNANDEZ Carlos Eduardo
4IF
Groupe 1
Novembre 2013
Projet : jeu Pacman, IA de Pacman et des fantômes
implémenter un jeu proche de Pacman
réaliser différentes IA pour contrôler Pacman et les 4 fantômes
comparer les différentes combinaisons d'IAs
évaluer l'efficacité des différentes approches à la base des IA
Objectifs
IA Pacman
IA Pacman
"fourmi"
IA Pacman
parcours de chemin
IA fantômes
distance Pacman
IA fantômes
IA fantômes
"fourmi"
IA fantômes
vision Pacman
Évaluation et comparaison des IA
Méthode d'évaluation des IA
Résultats : boules mangées (moyenne)
Conclusion
Améliorations envisageables Pacman
Démonstration
À chaque croisement, choisit le déplacement permettant de minimiser la distance avec Pacman
L'IA est paramétrable pour permettre de ne choisir le meilleur choix qu'avec une certaine probabilité
Cette IA ne peut pas faire de demi-tour
À un croisement, se dirige vers Pacman quand celui-ci est dans son champ de vision. (Pacman doit se trouver sur la même ligne/colonne sans obstacle entre ce dernier et le fantôme)
Une version "améliorée" possède un vision à travers les obstacles
Cette IA ne peut pas faire de demi-tour
IA hybride
Algorithme primaire de parcours de chemin
Algorithme secondaire de recherche
Algorithme primaire : parcours de chemin de longueur L fixe donnée
<=> Parcours d'arbre en profondeur d'abord et de profondeur limitée
Poids attribué à chaque case
Vide : 0
Boule, fantôme "peureux" : négatif
Fantôme : positif
Poids d'une case décroissant avec la profondeur de la case dans le chemin considéré
Chemins considérés : tous les chemins de longueur L partant de Pacman
Poids d'un chemin = somme des poids des cases
But : minimiser le poids du chemin
Algorithme secondaire : recherche du plus court chemin pour atteindre une boule
Recherche du plus court chemin implémentée par A*
La boule B la plus proche est choisie comme "point de mire"
Heuristique : distance (Manhattan) entre Pacman et B
À chaque tour tente de se déplacer vers l'endroit où Pacman aura tendance à se diriger (grace à une pondération suivant les éléments se trouvant sur le chemin)
Laisse une trace de son passage (s'atténuant au cours du temps) pour éviter de revenir vers les endroits déjà parcourus
Cette IA peut faire des demi-tours
Pour chaque couple d'IA, nous évaluons 100 parties.
Nous collectons :
- le taux de victoires
- le nombre de coups joués
- le nombre de boules mangées
- le nombre de fantomes dévorés
Prise en compte du temps restant d'invulnerabilité pour Pacman
Calculer à l'avance les n prochains mouvements
Prendre en compte le sens de déplacement des fantômes (la plupart ne peuvent pas faire demi-tour)
Améliorations envisageables fantômes
Avoir une IA qui communique entre les différents fantômes pour piéger Pacman
Calculer à l'avance les n prochains mouvements
Prévoir heuristiquement les déplacements de Pacman
Prendre en compte les spécificités du terrain (situations particulières)
Résultats : nombre de victoires (/100)
Résultats : nombre de coups (moyenne)
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
Résultats : score (moyenne)
1 : pacman_ant
2 : pacman_basic
3 : pacman_treeweight(1)
4 : pacman_treeweight(5)
5 : pacman_treeweight(10)
6 : pacman_treeweight(15)
7 : pacman_treeweight(20)
IA Pacman
IA
Pacman
IA
fantômes
1 : ghost_ant
2 : ghost_visibility(0)
3 : ghost_visibility(1)
4 : ghost_dist(0)
5 : ghost_dist(1)
6 : ghost_dist(5)
7 : ghost_dist(10)
8 : ghost_dist(-1)
IA fantômes
A chaque tour tente de se déplacer dans la position la plus avantageuse (plus de boules, moins de fantômes)
Laisse une trace de son passage (s'atténuant au cours du temps) pour éviter de revenir vers les endroits déjà parcourus
Fonctionnalités essentielles implémentées
IA suffisamment variées pour pouvoir faire des comparaisons
Introduction d'aléatoire bénéfique aux IA fantômes
IA Pacman : équilibre à trouver entre prise de risque et sécurité