Forum Programmation.python IA pacman

Posté par  . Licence CC By‑SA.
Étiquettes : aucune
3
18
jan.
2016

Sommaire

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 :

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.

  • 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.

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.

  • # Exploration ?

    Posté par  (site web personnel) . Évalué à 2.

    Salut,

    Déjà, bravo pour le code. Si tu apprends, je ne peux que te conseiller d'essayer d'écrire ton code en TDD, et aussi de passer un coup de pylint, qui va te dire pas mal de chose sur le format de ton code (comme le manque de docstring presque partout, nom de variables, trucs inutilisés, etc.).

    Ensuit, pour la carte, c'est pas facile à lire comme ça. Tu pourrais simplement afficher des "." si le lieu est inconnu, puis tes murs et c'est tout. Tu peux afficher une deuxième carte avec le trajet de Pacman pour voir ce qu'il fait.

    De plus, tu connais la position des fantômes, et ils ne peuvent pas (?) être sur des murs. Ils te donnent donc des indications sur les emplacements possibles pour Pacman. Tu peux donc construire ta carte beaucoup plus vite (pour toi-même).

    Enfin, ton problème me rappelle comment les abeilles font pour déterminer la taille et le volume d'un lieu noir avec une quantité limitée d'info : quand tu arrives à une intersection, tu peux choisir la direction d'une manière pseudo-aléatoire.

    Tu pourrais aussi poursuivre les fantômes, minimiser le rebrousse chemin, etc.

    Bon courage !

  • # Mon implémentation

    Posté par  . Évalué à 1.

    Salut,

    Pour être également sur le jeu en question, quelques pistes que j'ai implémenté et qui m'ont mené pour l'instant à un score pas trop mal :

    • tenir compte du mouvement des fantômes pour en déduire une partie du labyrinthe

    • à chaque tour sélectionner une cible parmi les cases non encore visitées : j'ai essayé différentes tentatives avec plus ou moins de succès basées sur les distances estimées (manhattan actuellement) aux fantômes et à pacman

    • recherche de la route la plus courte et la plus sure (affectation d'un coût de mouvement supérieur si je passe proche d'un fantôme) vers la cible

    Bon courage à toi !

  • # Quel site ? et un possible optimisation

    Posté par  (site web personnel) . Évalué à 1.

    Quel est le site du jeu ?
    Une optimisation possible est d'essayer de s'éloigner du fantôme le plus proche en distance manhatan pour survivre plus longtemps

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.