Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Présentation projet Prolog Pacman

No description
by

Timothée Muller

on 5 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript 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 transcript