Stratégies de capture de fugitifs… ou l’application de la théorie des graphes à PacMan

Le jeu PacMan^tm est sorti en 1979 dans les salles d’arcades. Il a ensuite donné lieu à de très nombreux clones. Son principe est le suivant : le héros PacMan, personnage en forme de rond jaune doté d’une bouche, se déplace dans un labyrinthe ; son objectif est de manger toutes les PacGommes qu’il rencontre sur son chemin et surtout d’éviter les fantômes qui hantent les couloirs. Plusieurs niveaux de jeu sont définis ; ils se distinguent par le dessin du labyrinthe, ainsi que par l’existence de différents bonus que peut gagner PacMan.

Au bout d’un moment, le joueur humain, qui dirige les mouvements de PacMan, finit par perdre contre l’ordinateur. PacMan est rattrapé par un fantôme. Est-ce une fatalité ? Peut-on imaginer une stratégie gagnante pour PacMan ?

La question demande à être précisée. Dans le jeu originel, les fantômes bougent au hasard. Mais, si les fantômes étaient intelligents, pourraient-ils toujours attraper PacMan ? Ou au contraire PacMan pourrait-il leur échapper indéfiniment ?

Un modèle simplifié de PacMan^tm

Dans le jeu originel, la vitesse compte : le héros et les fantômes, se déplacent de plus en plus vite, et la vitesse relative des fantômes par rapport à PacMan est de plus en plus élevée. Dans les niveaux supérieurs, ils sont donc plus difficiles à éviter. Pour répondre à notre question sans avoir à tenir compte des vitesses, nous allons nous placer dans le cas le plus favorable pour PacMan : nous supposons qu’il se déplace beaucoup plus vite que les fantômes. C’est-à-dire que la vitesse relative de PacMan par rapport aux fantômes est aussi élevée qu’on le veut ; on peut même dire que PacMan se déplace infiniment vite. Mais attention ! Il ne peut pas pour autant passer sur un fantôme sans se faire attraper.

Qui va gagner ? Les fantômes sont plus nombreux et peuvent donc encercler PacMan, ce qui l’empêche de fuir. Par exemple, si deux fantômes se trouvent aux extrémités d’un couloir et PacMan au milieu, ils vont attraper PacMan. En revanche, PacMan a l’avantage de sa vitesse, ce qui lui permet de fuir à l’autre bout du jeu s’il le désire.

Défaite inéluctable… ou victoire assurée ?

Un labyrinthe du jeu Pacman.
Il peut être divisé en quatre zones suivant un axe Nord-Sud (ou haut-bas) et un axe Ouest-Est (ou gauche-droite). Il est possible de passer d’une zone à l’autre par un couloir. Dans chaque zone, il existe un pilier autour duquel Pacman peut tourner pour échapper à un fantôme.

Imaginons PacMan comme un jeu entre deux joueurs intelligents : l’un joue PacMan, et l’autre tous les fantômes en même temps. Les fantômes gagnent s’ils acculent PacMan et qu’ils l’attrapent. Inversement, PacMan gagne s’il réussit à échapper aux fantômes. Existe-t-il une stratégie de victoire, c’est-à-dire une stratégie qui assure Pacman d’échapper toujours aux fantômes ?

Par exemple, dans le cas d’un seul fantôme, PacMan gagne toujours. Sa stratégie de victoire consiste en effet à trouver un couloir circulaire et à tourner autour du pilier central dès que le fantôme s’approche de lui. Comme PacMan est plus rapide, le fantôme ne peut l’attraper.

Même s’il y a deux fantômes, PacMan a une stratégie de victoire. Pour le comprendre, divisons le jeu en quatre zones : Nord-Est, Nord-Ouest, Sud-Est et Sud-Ouest. PacMan est dans une de ces zones. Tant qu’il n’y a qu’un seul fantôme dans sa zone, il peut tourner autour d’un pilier pour lui échapper, comme expliqué précédemment. Et si un deuxième fantôme arrive dans la zone, PacMan peut s’échapper dans la zone opposée (Nord-Est s’il est au Sud-Ouest, etc.). Comme quatre couloirs permettent de quitter les zones et que PacMan est infiniment plus rapide, il peut toujours appliquer cette stratégie, qui peut être étendue à trois ou quatre fantômes : dès que deux fantômes sont dans une zone, PacMan s’enfuit dans une zone où il n’y en a aucun.

On remarquera donc que si PacMan est assez intelligent, il pourra éviter de se faire attraper par un, deux, trois ou quatre fantômes. Et au-delà ? On imagine facilement que s’il y a des centaines de fantômes, PacMan va perdre. Des dizaines aussi. En résumé, en dessous d’un certain nombre de fantômes, PacMan peut leur échapper indéfiniment et gagner la partie (s’il joue bien). Au-delà d’un certain nombre, les fantômes (s’ils jouent bien) peuvent coincer PacMan et remporter la partie.

Le seuil, c’est-à-dire le nombre minimal de fantômes qu’il faut pour attraper PacMan, dépend uniquement de la forme du labyrinthe. Dans le cas du labyrinthe de Pacman de la figure ci-dessus, il suffit de cinq fantômes pour attraper PacMan à coup sûr ! Pourquoi cinq ? Comme nous le verrons un peu plus loin, dans l’algorithme de capture, le nombre de fantômes nécessaire dépend de la décomposition en arbre du graphe. L’arbre obtenu est formé de différentes boîtes contenant un certain nombre de sommets, et il faut placer autant de fantômes qu’il y a de sommets dans la plus grosse boîte. Et justement, le maximum possible est cinq. Mais ce n’est pas toujours 5 ! Dans un couloir simple, un seul fantôme peut attraper PacMan. Et dans un couloir circulaire, un seul n’y arrive pas, mais deux y parviennent.

Peut-on déterminer la valeur de ce seuil de façon systématique et rigoureuse ? Oui, grâce à un théorème prouvé en 1993 par les mathématiciens P. D. Seymour et Robin Thomas. Ils ne travaillaient pas sur PacMan, mais sur le jeu des gendarmes et du voleur, dont PacMan peut être considéré comme un cas particulier, si on confère à PacMan une vitesse de déplacement aussi élevée que nécessaire.

Gendarmes et voleur

Le jeu des gendarmes et du voleur a été inventé par Torrence Douglas Parsons. Il se joue à deux, sur un graphe, c’est-à-dire un ensemble de sommets reliés par des arêtes. Un joueur joue les gendarmes et l’autre le voleur.

Chaque tour de jeu comporte trois étapes :

1. Le joueur qui joue les gendarmes choisit des nouveaux sommets pour ses pions. Il peut choisir de bouger un ou plusieurs gendarmes (même tous, s’il le veut). Il annonce son choix au deuxième joueur, qui joue donc le voleur.
2. Le voleur déplace son pion « voleur » sur le graphe en empruntant autant d’arêtes qu’il le souhaite, mais sans passer par un sommet qui contient un pion « gendarme ».
3. Enfin le gendarme déplace ses pions en les posant aux positions qu’il avait prévues et annoncées.

Au début d’une partie, les gendarmes partent tous d’un même sommet, « la maison », et le voleur d’où il veut. Les gendarmes gagnent s’ils attrapent le voleur.

Concrètement, cela signifie que le voleur s’est placé (à l’étape 2) sur une case où il a été prévu de placer un pion « gendarme », sans pouvoir s’échapper sur une case prévue sans pion « gendarme ». Donc à l’étape 3, le voleur sera attrapé, puisqu’un gendarme se trouvera sur cette case !

Le voleur gagne si les gendarmes ne réussissent pas à l’attraper. Concrètement, on peut choisir un « grand » nombre de coups (100, 10 000…) au terme desquels, si les gendarmes n’ont pas réussi à attraper le voleur, celui-ci a gagné.

Qui va gagner ? Les gendarmes sont plus nombreux et peuvent donc encercler le voleur, ce qui l’empêche de fuir. En revanche, le voleur a un avantage sur les gendarmes. Ces derniers doivent annoncer leurs déplacements à l’avance, ce qui permet ainsi au voleur de choisir un endroit « sûr » où fuir.

Des gendarmes et voleur aux fantômes et PacMan

Évidemment, l’analogie avec PacMan passe par l’identification des gendarmes aux fantômes et du voleur à PacMan. Mais ce jeu en « tour par tour », avec à chaque tour des déplacements sur des distances aussi grandes que l’on veut, diffère de PacMan, où les déplacements sont continus, c’est-à-dire que les fantômes et le PacMan « glissent » de façon simultanée sur le labyrinthe. C’est pourquoi nous avons fait précédemment l’hypothèse que PacMan pouvait se déplacer aussi rapidement que souhaité.

Et si l’on supposait que la vitesse des fantômes devenait non négligeable par rapport à celle de Pacman ? Cela leur donnerait effectivement un avantage supplémentaire, mais les conséquences de cet avantage restent encore inconnues. Il va sans dire que si les fantômes sont plus rapides que Pacman, un seul fantôme suffit à l’attraper. On peut donc imaginer des seuils tels que si la vitesse des fantômes est inférieure à c (avec c < 1) fois la vitesse de Pacman, cinq fantômes sont nécessaires. Entre c et c’, ce seraient quatre fantômes ; entre c’ et c », trois ; entre c » et c?, deux ; et enfin, au-delà de c?, un seul fantôme suffirait.

Mais à quoi correspond le graphe sur les sommets duquel se placent les pions « gendarmes » et le pion « voleur » ? C’est le graphe dont les sommets sont les carrefours du labyrinthe et les arêtes les couloirs. PacMan, ainsi que les fantômes, se déplacent sur ce graphe : ils passent de sommet en sommet (de carrefour en carrefour), en empruntant les arêtes (les couloirs) qui les relient.

Le labyrinthe précédent est représenté par un graphe. À un carrefour du labyrinthe correspond un sommet du graphe, à un couloir correspond une arête du graphe.
En bleu, on a représenté les sommets ayant 4 sommets voisins ; en vert, les sommets ayant 3 sommets voisins et en rouge, ceux ayant 2 sommets voisins.

Décomposition en arbre

Cette figure représente en haut un graphe, et en bas, la décomposition en arbre de ce graphe.

En fait, les théoriciens s’intéressent non pas à jouer une partie en particulier, mais aux conditions de victoire théoriques.

Seymour et Thomas ont montré comment le nombre minimal de gendarmes nécessaires pour attraper le voleur dépendait de la configuration du graphe du jeu. Plus précisément, ils ont prouvé que ce nombre est égal à la largeur d’arbre du graphe.

Pour comprendre ce résultat, il convient d’introduire l’opération de décomposition en arbre d’un graphe. On obtient ainsi un nouveau graphe dont chaque sommet (que nous appellerons également « boîte » quand il sera nécessaire de bien les distinguer des sommets du graphe à décomposer) rassemble un ou plusieurs sommets du graphe donné. Un même sommet du graphe peut apparaître dans plusieurs boîtes de la décomposition.

Le graphe résultant doit vérifier les propriétés suivantes :

1. Ce graphe est un arbre, c’est-à-dire qu’il n’y figure aucun cycle : si on passe d’une boîte à l’autre en suivant les arêtes sans repasser deux fois par la même boîte, on ne peut pas revenir à son point de départ.
2. Pour chaque arête du graphe, les sommets de ses deux extrémités doivent apparaître ensemble dans au moins une boîte de la décomposition (dans plus qu’une est autorisé)
3. Si un même sommet apparaît dans plusieurs boîtes de la décomposition, celles-ci sont reliées par des arêtes.

La décomposition en arbre d’un graphe donné est loin d’être unique. Par exemple, on peut mettre tous les sommets du graphe dans une seule boîte. À l’inverse, on peut chercher à obtenir une décomposition dont les boîtes rassemblent le plus petit nombre possible de sommets du graphe. On appelle ainsi largeur d’une décomposition en arbre le plus grand nombre de sommets contenus ensemble dans une boîte de l’arbre résultant.

La largeur d’arbre d’un graphe (ou largeur arborescente, treewidth en anglais) est alors la plus petite largeur qu’il est possible d’obtenir pour ce graphe. C’est un nombre entier compris entre 2 et le nombre de sommets du graphe.

Le théorème de Seymour et Thomas dit que la largeur d’arbre du graphe du jeu est exactement le nombre minimal de gendarmes nécessaires pour attraper le voleur.

Et PacMan dans tout ça ?

Voilà la décomposition en arbre du graphe de PacMan. C’est la preuve que 5 fantômes sont nécessaires pour attraper PacMan, car la plus grande boîte contient seulement cinq sommets.

Décomposition en arbre de notre graphe de jeu.
La plus grande boîte de l’arbre rassemble 5 sommets du graphe. Le théorème de Seymour et Thomas permet d’affirmer que 5 est aussi le nombre minimal de fantômes pour être certain d’attraper PacMan dans cette configuration du labyrinthe.

Déterminer la décomposition en arbre d’un graphe est malheureusement un problème dont la complexité est non-polynomiale : le temps de calcul nécessaire augmente de façon exponentielle en fonction de la taille du graphe à décomposer.

Stratégie de capture

Au-delà du résultat fourni par le théorème, il est intéressant de comprendre pourquoi et comment l’arbre de décomposition permet de déterminer des stratégies gagnantes dans le jeu des gendarmes et du voleur, et donc dans le jeu de PacMan, et fournit le nombre minimal de gendarmes qui leur assure la victoire.

L’algorithme de capture suit l’arbre de décomposition : le joueur qui joue les gendarmes doit toujours placer tous ses pions sur les sommets inclus dans une même boîte. En effet, les boîtes issues de la décomposition hiérarchique présentent la particularité d’être des séparateurs : si on retire du graphe les sommets contenus dans une boîte, le graphe se trouve coupé en plusieurs composantes sans lien de l’une à l’autre. Placer un gendarme sur chacun des sommets d’une boîte revient de fait, puisque le voleur ne peut passer par l’un de ces sommets sans se faire attraper, par retirer ces sommets du graphe. Les mouvements du voleur sont ainsi restreints à la composante dans laquelle il se trouve. Un gendarme n’a qu’à avancer vers lui… en suivant les mouvements dans l’arbre !

On passe alors d’un jeu de capture dans un graphe à un jeu de capture dans un arbre. Ainsi, un seul fantôme ne suffit plus, il en faut autant qu’il y a de sommets. À chaque étape, l’ensemble des sommets que le voleur peut atteindre se restreint, jusqu’à être réduit à rien : le voleur est capturé. On comprend également qu’il faut autant de gendarmes que de sommets dans la plus grosse boîte.

Inversement, le voleur gagne s’il y a moins de gendarmes que la taille de la plus grosse boîte. Il lui suffit de rester tout le temps sur les sommets d’une grosse boîte et les gendarmes, qui ne sont pas assez nombreux, ne peuvent l’attraper.

Exemple de la décomposition obtenue à partir du graphe modélisant notre labyrinthe.

Revenons à PacMan et regardons de plus près l’exemple de la décomposition obtenue à partir du graphe modélisant notre labyrinthe. Certaines boîtes ne sont connectées qu’à une seule autre, comme la boîte numéro 51 qui contient les sommets {14, 60, 61}. Il y a aussi des boîtes connectées à plusieurs autres, comme la boîte numéro 14 qui contient les sommets {36, 37, 39, 44}. Les sommets de ces boîtes-là possèdent donc la propriété d’être des séparateurs du graphe représentant le labyrinthe : si on met un fantôme sur chaque sommet, le labyrinthe du jeu se trouve décomposé en plusieurs zones telles que PacMan, même s’il va infiniment vite, ne peut passer d’une de ces zones à une autre sans se heurter à un fantôme, et donc être attrapé.

Ainsi, la boîte numéro 14 découpe le labyrinthe en trois zones : une toute petite zone qui contient seulement le sommet 38 ; une zone (correspondant à un petit quart Sud-Est) avec les sommets 40, 41, 42, 43 et 45, et enfin une zone rassemblant l’ensemble des autres sommets. PacMan n’a pas d’autre choix que de se trouver dans l’une de ces trois zones. S’il se trouve dans la zone du sommet 38, les fantômes l’attraperont en un seul mouvement : ceux des cases 37 et 39 se jettent sur lui. S’il se trouve dans la zone Sud-Est, là encore on imagine aisément le mouvement convergent des fantômes pour l’attraper.

Mais s’il se trouve dans la grande zone, comment placer les fantômes ? L’arbre donne la réponse. On voit que la boîte 14 est connectée à trois autres : les boîtes 15, 39 et 10. La boîte 39 correspond au placement des fantômes pour attraper PacMan s’il se trouve dans la zone du sommet 38. La boîte 15 correspond au placement des fantômes si PacMan est dans la zone Sud-Est. Enfin la boîte 10 montre comment positionner les fantômes si PacMan est dans la grande zone : il faut placer 5 fantômes, sur les sommets 14, 36, 39, 44 et 48. Cela veut dire déplacer le fantôme du sommet 37, dont on n’a plus besoin, et ajouter un cinquième fantôme.

En conclusion

Résumons-nous :

• Chaque boîte dicte un placement de fantômes.
• Les connexions d’une boîte déterminent en combien de zones ce placement des fantômes coupe le graphe du jeu. Par exemple, la boîte 14 est connectée à trois autres : elle coupe le graphe en trois zones.
• La zone où se trouve PacMan détermine une boîte, qui donne à son tour un placement des fantômes.

La stratégie de capture mise en œuvre par des fantômes correspond à un déplacement dans l’arbre. Par exemple, on place les fantômes comme dans les boîtes 14, puis 10, puis 6, puis 51. Si une boîte n’est connectée qu’à une seule autre, elle correspond à une position où PacMan est acculé : les fantômes ont gagné ! Comme les boîtes ne forment pas de cycle, les fantômes, en nombre minimal, finissent toujours par gagner. En d’autres termes, l’espace vital de PacMan est inexorablement réduit par l’avancée des fantômes, jusqu’à être réduit à néant : PacMan est capturé.

La décomposition en arbre ne sert bien sûr pas qu’à attraper PacMan, mais a de nombreuses autres applications qui dépassent le domaine du jeu. Ainsi Bruno Courcelle, un informaticien français, a montré en 1990 que si la largeur de clique d’un graphe (une variante de la largeur d’arbre, qui est un nombre inférieur) est petite, alors on sait efficacement résoudre sur ce graphe de nombreux problèmes NP-complets, particulièrement difficiles !