URL: https://linuxfr.org/forums/programmation-python/posts/ia-pacman
Title: IA pacman
Authors: denrou
Date: 2016年01月18日T11:31:44+01:00
License: CC By-SA
Tags: 
Score: 3
Bonjour à tous,
Relativement nouveau dans le domaine de la programmation, je m’entraîne sur différents sites. L'un d'entre eux propose des problèmes sous forme de jeux et je bloque un peu sur un en particulier. Si je poste ici c'est parce que :
1. j’apprécie cette communauté et je sais que des gens compétents viennent régulièrement ici
2. le but du problème en question est caché : on connaît les variables en input et on doit donner en output une lettre (A, B, C, D ou E). À la fin du programme, on obtient un score qui est plus ou moins élevé. La première partie du problème consiste donc à découvrir le fonctionnement de ce jeu. C’est pourquoi je ne veux pas poster un message sur leur forum afin de ne pas trop en dévoiler.
# Le jeu
Voici à quoi ressemble l’algorithme au départ avant de commencer le jeu :
```python3
import sys
import math
# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.
first_init_input = int(input())
second_init_input = int(input())
third_init_input = int(input())
# game loop
while True:
 first_input = input()
 second_input = input()
 third_input = input()
 fourth_input = input()
 for i in range(third_init_input):
 fifth_input, sixth_input = [int(j) for j in input().split()]
 # Write an action using print
 # To debug: print("Debug messages...", file=sys.stderr)
 print("A, B, C, D or E")
```
En affichant les différentes variables, on trouve assez rapidement leur signification et le but du jeu.
Le jeu est donc un jeu de plateau en tour par tour qui simule le jeu [Pac-Man](https://fr.wikipedia.org/wiki/Pac-Man).
- Les variables d’initialisations `first_init_input` et `second_init_input` déterminent à la taille du plateau et `third_init_input` nous donne le nombre de joueurs sur le plateau (nombres de fantômes + 1, Pac-Man).
- À chaque tour la position des joueurs est donnée par les variables `fifth_input` et `sixth_input`
- les autres variables (`first... fourth_input`) contiennent un caractère (`#` ou `_`). Ils déterminent l'environnement de Pac-Man : 4 variables pour les 4 directions dans lequel il peut aller. `#` correspond à un mur (impossible d'aller dans cette direction) et `_` à un chemin libre.
Par conséquent, la lettre donnée que l'on doit afficher donne la direction de Pac-Man pour le tour suivant. Le jeu s’arrête lorsqu'un fantôme et Pac-Man se trouve sur la même case. Plus Pac-Man explore la carte, plus notre score sera élevé.
# Un algorithme relativement simple
Pour découvrir le jeu et voir ce qu'on peut faire, j'ai implémenté un algorithme dans lequel Pac-Man explore la carte sans jamais se soucier des fantômes et sans revenir en arrière. Et pour visualiser ce qu'il se passe, j'ai créé une classe.
```python3
import sys
import math
from string import ascii_uppercase
class Graph:
 '''
 At the beginning, all nodes are supposed to be connected
 '''
 def __init__(self, width, height):
 self.width = width
 self.height = height
 self.node = {}
 for y in range(self.height):
 for x in range(self.width):
 if x> 0:
 self.addEdge(self.getNode(x, y), self.getNode(x - 1, y))
 if x < self.width - 1: self.addEdge(self.getNode(x, y), self.getNode(x + 1, y)) if y> 0:
 self.addEdge(self.getNode(x, y), self.getNode(x, y - 1))
 if y < self.height - 1:
 self.addEdge(self.getNode(x, y), self.getNode(x, y + 1))
 def getNode(self, x, y):
 return str(y * self.width + x)
 def addNode(self, i):
 if self.node.get(i) == None:
 self.node[i] = {'name': '?', 'neighbours': [], 'type': 'unknown'}
 def addEdge(self, i, j):
 self.addNode(i)
 if not j in self.node[i]:
 self.node[i]['neighbours'].append(j)
 def removeEdge(self, i, j):
 self.node[i]['neighbours'].remove(j)
 self.node[j]['neighbours'].remove(i)
 def updateNode(self, entity = None):
 i = self.getNode(entity.getPos()['x'], entity.getPos()['y'])
 if 0 <= int(i) <= self.width * self.height:
 self.node[i]['name'] = str(entity.getName())
 self.node[i]['type'] = str(entity.getType())
 def constructWall(self, i):
 self.node[i]['type'] = 'wall'
 self.node[i]['name'] = '{:^3}'.format('#')
 for n in self.node[i]['neighbours']:
 self.removeEdge(n, i)
 def manhatanDistance(self, pacman, ghosts):
 x1 = pacman.getPos()['x']
 y1 = pacman.getPos()['y']
 distance = {}
 direction = []
 for g in ghosts:
 x2 = g.getPos()['x']
 y2 = g.getPos()['y']
 distance[g.getName()] = abs(x1 - x2) + abs(y1 - y2)
 return distance
 def __str__(self):
 s = ""
 for y in range(self.height):
 for x in range(self.width):
 s = s + '{:^3}'.format(self.node[self.getNode(x, y)]['name'])
 if x < self.width - 1:
 s += str(' ')
 if y < self.height - 1:
 s += str('\n')
 return str(s)
class Ghost:
 def __init__(self, name, x = -1, y = -1):
 self.pos = {"x": x, "y": y}
 self.name = name
 self.type = 'ghost'
 def setPos(self, x, y):
 self.pos['x'] = x
 self.pos['y'] = y
 def getPos(self):
 return self.pos
 def getName(self):
 return self.name
 def getType(self):
 return self.type
class Pacman:
 def __init__(self, x = -1, y = -1):
 self.pos = {"x": x, "y": y}
 self.name = 0
 self.type = 'pacman'
 def setPos(self, x, y):
 self.pos['x'] = x
 self.pos['y'] = y
 self.name += 1
 def getPos(self):
 return self.pos
 def getName(self):
 return self.name
 def getType(self):
 return self.type
height = int(input())
width = int(input())
maze = Graph(width, height)
players = int(input())
ghosts = [Ghost(name) for name in ascii_uppercase[:(players - 1)]]
pacman = Pacman()
turn = 0
go = 'right'
# game loop
while True:
 down = input() == '_'
 right = input() == '_'
 up = input() == '_'
 left = input() == '_'
 for i in range(players):
 x, y = [int(j) for j in input().split()]
 if i < players - 1:
 ghosts[i].setPos(x, y)
 maze.updateNode(ghosts[i])
 else:
 pacman.setPos(x, y)
 maze.updateNode(pacman)
 if not down:
 maze.constructWall(maze.getNode(x, y - 1))
 if not up:
 maze.constructWall(maze.getNode(x, y + 1))
 if not left:
 maze.constructWall(maze.getNode(x - 1, y))
 if not right:
 maze.constructWall(maze.getNode(x + 1, y))
 # Just don't go back where you were
 if (go == 'right') & (not right):
 go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "left")][0]
 if (go == 'left') & (not left):
 go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "right")][0]
 if (go == 'down') & (not down):
 go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "up")][0]
 if (go == 'up') & (not up):
 go = [dir for dir in ["right", "left", "up", "down"] if eval(dir) & (dir != "down")][0]
 dir = {"right":"A", "left":"E", "up":"D", "down":"C"}
 print(dir[go])
 # If I'm close to lose the game, print the maze
 if min(maze.manhatanDistance(pacman, ghosts).values()) <= 2:
 print(maze, file=sys.stderr)
 turn += 1
```
Le résultat juste avant de perdre ressemble à ça :
```
 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
 ? B B B B B B B B B B B B ? ? ? ? ? ? ? ? A A A A A A ? 
 ? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ? 
 ? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ? 
 ? B ? ? ? ? B ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? ? ? A ? 
 ? B ? ? ? ? B B B B B B B ? ? ? ? ? A A A A A A A A A ? 
 ? B ? ? ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? A ? ? ? ? ? ? 
 ? B ? ? ? ? ? ? ? B ? ? ? ? ? ? ? ? A ? ? A ? ? ? ? ? ? 
 ? B B B B B B ? ? B B B B ? ? A A A A ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? ? B ? ? ? ? ? B ? ? A ? ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? ? B ? ? ? ? ? B ? ? A ? ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? ? B ? ? ? ? ? B B A A ? ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? ? B ? ? ? ? ? ? ? A ? ? ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? ? B ? ? ? ? A A A A B B ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? # 65 # ? ? ? ? ? ? ? ? ? ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? # 64 # ? ? ? C C C ? ? D ? ? ? ? A ? ? ? ? ? ? 
 ? ? ? ? ? # 63 # ? ? ? ? ? C ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? # 62 # ? ? ? ? ? C C C C C C ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? # 61 # ? ? ? ? ? ? ? ? ? ? C ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? # 60 # ? ? ? ? ? ? ? ? ? ? C ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? ? 59 ? ? ? ? ? ? ? ? ? ? ? C C C C ? ? C C C ? 
 ? ? ? ? ? # 58 # ? ? ? ? ? ? ? ? ? ? ? ? ? C ? ? ? ? C ? 
 ? ? ? ? ? # 57 # ? ? ? ? ? # # ? # # # # # C ? ? ? ? C ? 
 ? ? ? ? ? # 56 ? ? ? ? ? ? 1 2 3 4 5 6 7 8 C # ? C C C ? 
 ? ? ? ? ? # 55 # ? ? ? ? ? # # # # # ? # # C # ? C ? ? ? 
 ? # # ? # # 54 # ? ? ? ? ? ? ? ? ? ? ? ? # C # # C # # ? 
 # 48 49 50 51 52 53 # ? ? ? ? ? ? ? ? ? ? ? ? # C C C C 16 17 # 
 # 47 # # # # # ? ? ? ? ? ? ? ? ? ? ? ? ? ? # # # # # 18 # 
 # 46 # # # # # # # # # # ? # # ? # # # # # # # # # # 19 # 
 # 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 # 
 ? # # # # # # # # # # # # # # # # # # # # # # # # # # ? 
 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 
 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
```
# Améliorations
Voilà, maintenant j'aimerais aller un plus loin et développer un algorithme qui permettrait d'optimiser le parcours du labyrinthe pour le découvrir le plus possible.
La classe que j'ai implémenté me permet d'ajouter facilement des fonctions de recherche de chemin le plus court (BFS par exemple) entre les fantômes et Pac-Man, mais ce n'est pas ce qu'on veut ici.
Une idée que j'ai eu a été d'établir un score correspondant à la distance séparant un fantôme de Pac-Man dans une direction donnée. La direction à prendre étant celle dont le score est le plus haut. Mais après avoir implémenté cette fonction, Pac-Man s'est mis à tourner en rond sans explorer le labyrinthe.
Avez-vous des idées pour explorer le labyrinthe sans se faire attraper ? Une recherche d'IA et pacman sur un moteur de recherche ne renvoie des informations que sur l'IA des fantômes et souvent en connaissant le labyrinthe (dans ce cas une recherche de chemin le plus court marche bien).
Je reste également ouvert à toutes les critiques que vous pourriez avoir sur mon code, je ne demande qu'à progresser.
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://linuxfr.org/forums/programmation-python/posts/ia-pacman.md">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://linuxfr.org/forums/programmation-python/posts/ia-pacman.md" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>