Challenge CodinGame – Mangez les tous !!!

Du 8 au 18 mai 2020, Ingéniance a participé au challenge d’implémentation d’IA de CodinGame. Il s’agit d’une plateforme qui met à disposition de tous et gratuitement des puzzles autour de différents aspects du codage. Cette plateforme possède son propre interpréteur et elle est disponible pour plus d’une vingtaine de langages. De plus elle fournit une représentation graphique de l’exécution du code.

Les règles du challenge

Les challenges CodinGame sont des compétitions internationales sur 10 jours. Leur particularité est que l’on fait combattre son IA (son bot) contre ceux des autres participants. Un classement est ainsi déterminé au travers de différents combats. Le classement de l’entreprise (ou de l’école) quant à lui est déterminé grâce aux points accumulés des cinq meilleurs participants.

Les autres spécificités de ces challenges sont le fait de coder dans un seul fichier, ce qui peut perturber un codeur Java au début. Mais aussi le fait que notre code doit donner une réponse dans un temps imparti, sinon la partie est perdue. Cette année ce temps était de 50 millisecondes.

Pour ce challenge, chaque joueur contrôle entre 2 et 5 pac-man devant manger plus de pastilles que l’adversaire, dans un labyrinthe généré à la volée. La partie s’arrête si l’un des participants a mangé plus de la moitié des pastilles de départ (l’adversaire ne peut donc pas rattraper son retard) ou que l’on ai atteint le 200ème tour de jeu (le joueur avec le plus de points l’emporte). A chaque tour, l’algorithme doit renvoyer une action pour chacun des pac-man (e.g. : MOVE pac_id x y | MOVE pac_id2 x2 y2). Les pac-man avanceront d’une case en prenant le plus court chemin.

Cependant, ce n’est pas si simple car nous devons tenir compte de certaines règles. Premièrement, nous ne connaissons que la position des pastilles et des ennemies visibles (on ne voit pas à travers les murs).

Ensuite, les pac-man ont un type suivant les règles d’un pierre-feuille-ciseaux classique, ce qui permet, par exemple, à un pac-man de type ROCK de manger un pac-man ennemi de type SCISSOR (si tous les pac-man d’un joueur sont morts il perd automatiquement la partie).

Ensuite, les pac-man peuvent activer une capacité à la place de bouger :

• SPEED : ce boost de vitesse permet au pac-man d’avancer de deux cases par tour pendant cinq tours.
• SWITCH : cette capacité permet de se changer dans le type spécifié.

On ne peut activer qu’une abilité à la fois et on ne peut la réactiver qu’après dix tours.

Les stratégies des participants d’Ingéniance

Parmi toutes les stratégies mises en place par les participants d’Ingéniance, j’ai décelé 2 catégories d’implémentation.

Les points communs

Le premier tour diffère des tours suivants car avant toute chose il faut récupérer le labyrinthe qui nous est donné comme une succession de lignes correspondant à la hauteur et constitué d’une chaîne de caractère avec un espace pour du sol et le symbole ‘#’ pour un mur. Le stockage de ce dernier est assez libre. En effet on peut le stocker tel quel et définir une méthode qui permet de déterminer si la case évaluée est un mur, ou la grille peut être stockée comme une matrice contenant l’état de la case (e.g. : la case correspond à un mur, la case contient une pastille ou la case est vide). Il peut aussi être utile de stocker directement les voisins de la case pour éviter de le faire plus tard.

Toujours au premier tour, on peut connaître l’état complet du labyrinthe. Nous partons du principe que sur chaque case de type « sol » il y a une pastille (ou un pac-man) donc nous avons la position de toutes les pastilles même si on ne les voit pas. De plus, la disposition des pac-man est symétrique par rapport à l’axe vertical au centre de la grille, donc en connaissant la position de ces pac-man on connaît celle des ennemis.

Au départ, il y a un nombre pair de maxi-pastilles qui valent dix points. Elles sont aussi placées de manière symétrique dans la grille et elles ont la particularité d’être visibles à travers les murs. Le plus souvent les stratégies consistent à aller récupérer ces maxi-pastilles le plus vite possible et avant l’ennemi de préférence.

Fonctionnement en objectifs

Cette stratégie repose sur le fait qu’à la fin d’un tour de jeu il faut donner une position et un objectif (existante dans le labyrinthe). Le moteur du jeu s’occupe de faire passer le pac-man par le chemin le plus court. Ensuite à chaque tour on évalue les cases accessibles autour de chaque pac. On va donc vérifier dans un premier temps où sont les autres pac-man (qu’ils soient alliés ou ennemis) et ainsi éviter que le pac soit coincé, qu’il se fasse manger ou alors d’aller manger un pac-man ennemi selon la disponibilité des habilités de chacun.

Pour déterminer le premier objectif des pac-man, chacun d’eux se voit attribuer la maxi-pastille la plus proche. Pour les autres tours on attribue la pastille visible la plus proche et sans danger (e.g. : il y a un ennemi non loin, la pastille potentielle est déjà l’objectif d’un autre pac-man …). Pour déterminer cette proximité on utilise la distance euclidienne et plus particulièrement la norme 1 (aussi appelée la distance Manhattan) qui est plus optimale car elle est suffisante dans ce cas et elle nous évite le calcul de carrés et de racines carré :

abs(pacman.x - case.x) + abs(pac.y - case.y)

Un cas à traiter est le cas de l’absence de pastilles visibles (ce qui se produit vers la fin de la partie où il ne reste que peu de pastilles). Dans ce cas, une manière de procéder est de donner comme objectif au pac-man, une pastille probablement non prise, c’est-à-dire qu’à aucun moment la case correspondante n’a été vu / prise par un pac-man. Le problème évident avec cette méthode est le risque qu’elle soit déjà prise, cependant elle permet aussi d’explorer le labyrinthe et de vérifier la présence de pastilles pendant le parcours.

Pour conclure, cette stratégie va être efficace au début de la partie mais plus la partie durera plus cela sera compliqué de trouver des pastilles, de plus le chemin parcouru pour aller à l’objectif sera le plus court mais pas forcément le plus rentable en terme de gain de points. Un autre point concerne le temps de réponse, le temps requis pour donner une action est de 1 seconde le premier tour et 50 millisecondes ensuite. D’abord, la stratégie ne tire pas partie de cette seconde au premier tour et pour les autres tours, elle ne fait presque jamais de timeout car le code exécuté n’est pas lourd. Cela rend la stratégie moins optimale.

Recherche dans un arbre

Pour cette stratégie, le but est de regarder tous les chemins possibles jusqu’à une certaine longueur et de prendre le meilleur. Pour déterminer ce meilleur chemin, on a besoin d’évaluer l’état du labyrinthe et d’y associer un score, le pac-man prendra le chemin avec le plus gros score. Pour commencer cette évaluation il suffit de réaliser la simple somme des pastilles présentes sur le chemin, en soustrayant une certaine valeur pour chaque pac-man (allié ou ennemi) présent.

En pratique, on va utiliser un algorithme récursif en faisant remonter le score total une fois la profondeur maximale atteinte, et renvoyer finalement la deuxième case du chemin (L’une des règles du jeu impose sous boost de vitesse de donner une destination qui se trouve à au moins deux cases de la position du pac-man). Les principales améliorations qui vont être apportées s’appliqueront sur la fonction d’évaluation et la fonction d’élagage.

La fonction d’élagage a pour vocation de nous éviter de parcourir certaines branches de l’arbre dont on sait déjà qu’il y a une meilleure branche. La plupart du temps on va vouloir éviter de parcourir le chemin d’où le pac-man vient (sauf dans le cas où le pac-man doit revenir en arrière quand il est dans une impasse).

Pour cette stratégie, il est inutile d’attribuer une maxi-pastille aux pac-man en début de jeu. En effet, la plupart du temps les pac-man voient assez loin pour voir le chemin avec la maxi-pastille. De la même manière, il est possible de voir assez loin pour ne jamais être coincé quand il n’y a plus de pastilles visibles (cela correspond à la tactique précédente qui consistait à aller dans une zone inexplorée, mais ici cela peut être fait automatiquement).

Pour conclure, ce type de stratégie avec une recherche d’arbre semble plus approprié pour ce type de problème grâce à l’optimisation du gain de points durant la partie. De plus, les retours des top-players sur le challenge indiquent qu’ils ont privilégié ce type de stratégie (de manière plus performante).

Résumé de mon algorithme

Ce que j’ai choisi de faire dès le départ est d’utiliser une recherche dans un arbre. Je vais détailler dans cette partie comment j’ai mis en œuvre l’algorithme.

Les structures de données utilisées

En ce qui concerne le stockage du labyrinthe j’ai utilisé un tableau Python de largeur width et de hauteur height contenant un objet de la classe Pall représentant les pastilles.

class Pall:
    def __init__(self, value, x, y):
        self.value = value
        self.x = x
        self.y = y
        self.voisins = []
        self.isLast = False
        self.objectif = []

Pour les pac-man j’ai créé une classe Pac répartie dans 2 dictionnaires python, un pour mes pac-man et un pour les pac-man ennemis, dont la clé est leurs identifiants.

class Pac:
    def __init__(self, id, x, y, type_pac, speed_left, cooldown):
        self.id = id
        self.x = x
        self.y = y
        self.type_pac = type_pac
        self.speed_left = speed_left
        self.cooldown = cooldown
        self.is_update = True
        self.chemin = [[x, y]]
        self.next = []
        self.next_move = [] # contient les coordonnées qui seront renvoyées
        self.vis_pac = [] # contient les pac qui sont visible par lui
        self.type_move = ""
        self.cannot_see = [] # répertorie les cases où il ne faut pas aller
        self.objectif = []

Le cœur de l’algorithme

La majeure partie de l’implémentation et de l’amélioration de mon IA se trouve dans deux fonctions best_move et minimax (minimax est le nom de l’algorithme dont je me suis inspiré). Le principe est que best_move, appelée pour chaque pac-man allié, va sélectionner le prochain mouvement situé sur le chemin dont le score est le plus élevé. Ce score est calculé récursivement sur les cases voisines par minimax en faisant décroître la profondeur maximale.

Pour calculer le score d’un chemin, la première manière de faire est de réaliser la somme des valeurs des pastilles présentes sur celui-ci. Par contre, il arrive régulièrement de devoir gérer le cas de scores égaux. Prenons le cas des deux meilleurs chemins ayant une seule pastille. Pour traiter ce cas, le pac-man choisit aléatoirement un des chemins sinon le pac-man se bloque car l’ordre de parcours des voisins est fixé. Le pac-man choisi donc un chemin et avance d’une ou deux cases s’il est sous boost de vitesse. Mais au tour tour suivant il est possible qu’il choisisse le chemin qu’il avait abandonné précédemment, ce qui nous fait perdre un temps précieux. Une solution moins naïve, mais qui ne semble pas non plus optimale, est de multiplier la valeur de la pastille par la distance (qui correspond à la profondeur à laquelle on se trouve). Le pac-man choisira ainsi la pastille la plus proche, et on gardera le choix aléatoire pour celles qui sont à la même distance.

Pour gérer les ennemis et les alliés, on va diminuer ou augmenter suffisamment le score pour éviter les cas de blocage avec un allié ou de défaite face à un pac-man ennemi avec un type gagnant, ou au contraire pour aller manger un pac-man ennemi avec un type perdant et dont l’habilité de SWITCH n’est pas disponible.

Ci-dessous, une version simplifiée de l’algorithme :

def minimax(lab, pac, my_pac, ennemy_pac, depth):
    x = pac.chemin[-1][0]
    y = pac.chemin[-1][1]

    if depth == 0:
        return lab[y][x].getValue(), next_next, False
        
    for other_pac in my_pac.values():
        if other_pac.id != pac.id and other_pac.x == x and other_pac.y == y:
            return -10 * depth
    
    best_score = -99
    score = 0

    for voisin in lab[y][x].voisins:   
        
        next_move = voisin
        pac.chemin.append([voisin.x, voisin.y])
        score = minimax(lab, pac, my_pac, ennemy_pac, depth-1, max_depth)
        if score > best_score:
           best_score = score
        pac.chemin.pop()    

    if pac.speed_left > 0 and depth >= max_depth - 2:
        # on regarde les pacs visibles
        for e_pac in pac.vis_pac:
            if e_pac.x == x and e_pac.y == y:
                print("ennemy detected : {}".format(e_pac), file=sys.stderr)
                win = winner_type(pac.type_pac, e_pac.type_pac)
                if win and e_pac.cooldown > 1:
                    # l'ennemie ne peut pas switch
                    return 20 * depth + best_score
                return -200            
  return lab[y][x].getValue() * depth + best_score

Les limites et les problèmes de mon algorithme

La principale limite de mon programme est que la profondeur maximale atteignable dans le temps imparti est de 8 étapes ce qui est bien en-dessous de ce qui peut être vu dans les forums (au moins une profondeur de 10 étapes, en moyenne 15, et une personne chez Ingéniance arrivait à 18). Cette limite amène aussi des cas supplémentaires à gérer. En effet, l’algorithme ne voyait pas assez loin pour toujours trouver un meilleur chemin, et les pac-man se retrouvaient bloqués au milieu de rien. J’ai dû mettre en place un système de zone exploré ou non. Un pac-man sans pastilles autour de lui doit aller vers une case d’une zone inexplorée, en attendant de trouver d’autres pastilles.

Un problème que j’ai eu concernait la gestion des impasses sous boost de vitesse. En effet un pac-man se retrouvait bloqué dans un cul-de-sac car sous boost on doit donner une position à au moins deux cases de distance pour pouvoir profiter du mouvement supplémentaire. Dans la situation suivante, si je donne une position à deux cases de distance en passant par la pastille, cette position sera celle du pac-man et donc il se bloque en essayant constamment d’aller sur sa position. Si je donne une position avec une distance plus grande, le moteur du jeu va prendre le chemin le plus court pour y aller et donc le pac-man va aller en arrière. Il faut donc sacrifier le mouvement supplémentaire et ne faire qu’un mouvement même sous boost de vitesse.

Une autre difficulté était de vérifier le choix de chemin des pac-man car le seul outil de débug à disposition est un affichage sur la sortie d’erreur. Or comme j’utilise une recherche récursive le nombre d’affichage dépasse rapidement la quantité de messages affichables. De ce fait, quand un pac-man choisissait un chemin incohérent il m’était difficile d’en définir la cause et donc d’en corriger ce comportement.

Conclusion

Ingéniance a obtenu un résultat correct compte tenu du nombre de participant au challenge, bien inférieur au nombre de participant du top 10. Pour ma part, je suis satisfait de ma performance dans l’ensemble, bien que je sois un peu frustré de mon blocage les derniers jours. Ce genre de challenge est un bon exercice pour s’entraîner à résoudre des problèmes dans un temps réduit et de manière ludique.