Introduction

Un graphe est un objet mathématique abstrait qui possède des sommets, et des arêtes reliant les sommets. Il permet de représenter de nombreux problèmes très concrets : un réseau de distribution d'eau avec des stations de pompage et des maisons (les sommets) et les canalisation reliant tout ça (les arêtes). On cherche alors par exemple à maximiser le flux d'eau entre les pompes et les maisons; ou encore des émetteurs de radio (les sommets) et la possibilité d'interférence entre elles (une arête relie deux émetteurs s'ils peuvent interférer), on cherche alors à affecter à chaque émetteur une fréquence différente de tous ceux auxquels il est relié, avec un minimum de fréquences. C'est le problème de coloration de graphe. Ou encore, peut-être le problème le plus classique, un graphe peut représenter un réseau routier, avec des villes (les sommets) et des routes (les arêtes). On cherche alors typiquement un chemin avec certaines propriétés (souvent le plus court) entre deux villes.

Dans cet article, on considère des variantes de ce dernier problème basées sur la même idée : trouver un chemin. Mais ici, c'est dans un labyrinthe constitué de cases. Les cases du labyrinthe sont les sommets et il y a une arête entre deux cases si on peut passer de l'une à l'autre. Par souci de simplicité, on ne montrera jamais les graphes eux-même juste les labyrinthes, la relation entre les deux étant assez naturelle.

Dans notre exemple présenté sur la figure ci-dessous, les cases sont numérotées de 0 (en haut à gauche) à 24 (en bas à droite) et notre premier objectif est de trouver un chemin de la case 0 vers la case 25. Les cases noires sont des murs infranchissables.

Dans une deuxième partie, on compliquera ce problème relativement simple pour arriver à celui qui nous intéresse vraiment : trouver son chemin en présence d'un adversaire qui possède des actions pour entraver la progression.

Savoir trouver son chemin

Regardons donc d'abord comment trouver de manière algorithmique un chemin pour que notre aventurier arrive jusqu'au diamant qu'il convoite. Il existe de nombreuses façons de faire pour ce problème très classique. Ici on va faire ce qu'on appelle un parcours en largeur et en arrière.

On va déjà définir ce qu'est une stratégie pour notre aventurier :  il s'agit de donner, pour chaque case, la case sur laquelle il faut se rendre ensuite : par exemple, en 0 je vais en 5, en 5 je vais en 6, en 6 en 7, en 7 en 12, etc. On pourrait aussi prendre en compte l'historique pour définir la stratégie : par exemple, la première fois que je passe en 14, je vais en 9, et la deuxième fois je vais en 19. On voit qu'il faut alors mémoriser ce qu'on a déjà fait : on parle de stratégie avec mémoire. Cependant, on se convainc facilement que pour le problème qui nous intéresse, à savoir atteindre une case donnée, la mémoire n'est pas nécessaire. Puisque je peux gagner en allant la deuxième fois en 19, autant le faire dès la première fois et plus besoin de mémoriser là où je suis déjà passé.

On va maintenant dire qu'une case est gagnante s'il existe depuis cette case une stratégie pour notre aventurier pour arriver jusqu'au diamant. L'objectif est donc de montrer que la case 0 est gagnante, et de trouver la stratégie qui correspond, qu'on appellera naturellement stratégie gagnante.

L'idée est la suivant : on va procéder par induction : d'abord, la case 24 qui contient le diamant est gagnante par définition car si l'aventurier l'a atteinte, il n'a plus qu'à ramasser la gemme précautionneusement. Ensuite, une case est gagnante s'il est possible depuis elle d'aller sur une case gagnante; et (le morceau de) la stratégie gagnante qui correspond est justement d'aller sur cette case. Ainsi, cela nous permet de trouver que les cases 18, 19 et 23 sont gagnantes puisque 24 est gagnante. En itérant ce raisonnement, on en déduit que puisqu'on a 18, 19 et 23 gagnantes, alors 13, 14 et 22 aussi car de chacune d'elles on peut aller sur une case gagnante. La stratégie en 13 est d'aller en 18, en 14 d'aller en 19 et en 22 d'aller en 23. À partir de là, on continue et on en déduit que 9, 12 et 21 sont gagnantes, etc. À la fin, on obtient bien que la case 0 est gagnante et on a la stratégie gagnante correspondante. Cette procédure termine quand on ne trouve plus de nouvelle case gagnante, ce qui arrivera forcément puisque le nombre de cases est fini.

Éviter les pièges

Après cette mise-en-bouche compliquons un peu le problème : supposons que notre aventurier a un adversaire qui peut manipuler des pièges représentés dans la figure ci-dessous par des flèches rouges avec un ligne horizontale, rouge également. Le fonctionnement de ces pièges est le suivant : quand l'aventurier est, par exemple, sur la case 5, il a devant lui un mur et ne peut pas aller en 10 (c'est ce que représente la ligne horizontale rouge) mais l'adversaire peut décider d'activer le piège. Le mur et le sol pivotent alors et l'aventurier se retrouve sur la case 10. À nouveau il y a un mur entre la case 5 et 10 et il ne peut donc pas revenir en arrière. Il est important de noter que l'adversaire peut activer le piège mais il n'est pas obligé de le faire. Ainsi, s'il y avait aussi un piège de la case 22 vers la case 17, notre aventurier n'aurait aucune chance d'arriver jusqu'au diamant : en effet, il est initialement obligé d'aller en 5, puis l'adversaire active le piège en 5 et l'aventurier est coincé pour toujours incapable de sortir du couloir 10-15-20-21-22 sans l'aide de l'adversaire pour le faire passer de 22 à 17.

Mais heureusement pour lui ce piège de 22 à 17 n'existe pas dans notre exemple. Voyons alors comment il peut s'en sortir.

On redéfinit le calcul par induction des cases gagnantes. La case diamant numéro 24 est toujours gagnante par définition. Mais la deuxième partie est un peu plus compliquée. Avant que nous ne donnions la solution, essayez de deviner comment définir une case gagnante à partir des autres cases gagnantes...

Ça y est ? Pour qu'une case soit  gagnante il faut au moins, comme tout à l'heure, qu'il soit possible à partir d'elle d'aller vers une autre case gagnante ce qui donnera à l'aventurier sa stratégie... mais cela ne suffit pas en général : s'il y a un piège sur sa case, l'aventurier pourrait ne pas être capable de mettre en œuvre sa stratégie pour aller vers la case gagnante. Ici on n'a pas d'information sur qui agit le plus vite de l'aventurier ou de l'adversaire et on va donc considérer le pire cas qui est que, s'il en a envie, l'adversaire peut toujours agir le plus vite. Autrement dit la stratégie gagnante doit fonctionner quelle que soit la stratégie de l'adversaire.

Par conséquent, il faut en plus que si l'adversaire agit en premier et emmène l'aventurier sur une case via un piège, alors cette case elle aussi est gagnante : après le piège il est toujours possible de gagner.

Avec cette petite modification, l'algorithme fonctionne comme avant : 24 est gagnante donc 19 est gagnante, donc 18 aussi mais pas 14. En effet depuis 14, l'aventurier ne peut pas (pour l'instant) atteindre une case qu'on a déclarée gagnante sans l'aide de l'adversaire. On continue donc : 13 et 17 sont gagnantes, puis 12 et 22 mais toujours pas 14 ! En effet, maintenant depuis 14, l'aventurier peut essayer d'aller en 13, qui est bien gagnante, mais l'adversaire peut le forcer à aller en 9 qui ne l'est pas (encore). Continuons : 7 et 21 sont donc gagnantes, puis 2, 6, et 20; puis 3, et 15 mais pas 5. Comme tout à l'heure pour 14, depuis 5 l'aventurier peut essayer d'aller sur la case 6 qui est gagnante mais l'adversaire peut le forcer à aller en 10 qui ne l'est pas pour l'instant. Mais dès l'itération suivante, on voit que 3 et 10 sont gagnantes, et donc 5 l'est aussi puisque cette fois le piège conduit à une case gagnante, ainsi que 4. Et à l'itération suivante 0 et 9 sont gagnantes. On pourrait s'arrêter là, mais on peut aussi continuer encore un peu puisqu'on a eu de nouvelles cases gagnantes et on trouve enfin que 14 est gagnante car l'aventurier peut essayer d'aller sur une case gagnante par lui-même (13) et les deux pièges mènent vers des cases qui ont été vérifiées gagnantes (9 et 19).

Comme précédemment cet algorithme termine quand  plus aucune nouvelle case gagnante n'est trouvée. On pourrait aussi s'arrêter plus tôt si on trouve que la case initiale est gagnante (c'était aussi le cas sans les pièges).

À chaque case, la stratégie de l'aventurier sera d'essayer d'aller vers une case gagnante qu'il peut atteindre sans aide, et qui pour une case gagnante existe par définition.
  

Conclusion

Cet algorithme, illustré ici sur une exemple simple, est très général et peut s'appliquer à n'importe quel graphe pour lequel on a partitionné les arêtes ou les sommets entre deux joueurs. De nombreuses variantes et extensions existent, dans lesquelles on cherche des stratégies optimales, des stratégies pour rester dans un ensemble de bons sommets (objectif de sûreté), pour forcer des sommets désirables aussi longtemps qu'on veut, voire à l'infini (objectif de vivacité), etc. L'intérêt d'avoir un adversaire réside dans la modélisation de comportements qu'on ne maîtrise pas et qu'on ne peut pas prédire ou modéliser avec des probabilités, par exemple l'interaction avec un processus physique : la stratégie  gagnante si elle existe permet alors de synthétiser un contrôleur qui permet d'assurer que le système modélisé satisfait les propriétés qui nous intéressent.

Ces jeux sur les graphes sont l'objet de recherches très actives de la part de la communauté internationale de la recherche en informatique, notamment en informatique fondamentale, comme au laboratoire LS2N à Nantes.