Computing winning positions in a game

Reading time20 min

En bref

Résumé de l’article

Dans cet article, nous vous expliquons comment trouver les positions gagnantes dans un jeu, c’est-à-dire comment trouver des configurations qui mèneront sûrement à la victoire.

Points clés

  • Gagner un jeu consiste à atteindre une configuration de jeu où le jeu est gagné.

  • Plus largement, les régions gagnantes désignent des configurations à partir desquelles une configuration gagnante peut sûrement être atteinte.

  • Les régions gagnantes peuvent être construites à partir des configurations gagnantes.

  • Des algorithmes tels que Maximin peuvent être utilisés pour trouver une bonne stratégie dans un jeu.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez également lire la transcription si vous préférez.

Information

Bonjour ! Bienvenue dans la leçon d’aujourd’hui, dans laquelle je vais vous montrer comment identifier les positions gagnantes dans un jeu. Cela vous aidera à améliorer la stratégie de votre intelligence artificielle dans PyRat.

Stratégies et positions gagnantes

Comme vous le savez, PyRat est un jeu à deux joueurs entre un rat et un python, où chaque joueur doit naviguer dans un labyrinthe pour trouver des morceaux de fromage cachés dans le labyrinthe.

On dit qu’une stratégie pour le rat est "gagnante" si le rat est sûr de gagner la partie, quel que soit le déplacement choisi par le python. En d’autres termes, c’est une stratégie telle que, pour toute stratégie de l’adversaire, le jeu est gagné.

Au début d’une partie de PyRat, il n’y a pas de stratégie gagnante pour aucun des joueurs, car le labyrinthe est symétrique. Par conséquent, si les deux joueurs choisissent la même stratégie, alors le résultat sera une égalité.

Mais une fois la partie commencée, et si à un moment donné les joueurs font des mouvements différents et brisent la symétrie, la partie qui suit admettra probablement des stratégies gagnantes pour l’un des joueurs.

Déterminer si une stratégie gagnante existe est un problème computationnel très complexe. Pour cela, il faut considérer deux facteurs combinatoires imbriqués, qui sont les stratégies possibles du rat, et les stratégies possibles du python. En conséquence, le nombre de parties possibles dans PyRat est énorme.

En pratique, cela signifie que le calcul des stratégies gagnantes ne peut être effectué que lorsque la variabilité du jeu est réduite, par exemple lorsqu’il ne reste que quelques morceaux de fromage dans le labyrinthe.

Revenons maintenant au concept d’arène. Vous vous souvenez probablement de la leçon précédente que l’arène est un graphe où chaque sommet résume l’état actuel du jeu.

Un sommet dans l’arène est une position gagnante pour un joueur si, à partir de ce sommet, le joueur dispose d’une stratégie gagnante.

Bien sûr, un sommet ne peut pas être gagnant pour les deux joueurs. Si c’était le cas, cela signifierait que les deux joueurs ont une stratégie qui gagne contre toute stratégie de l’adversaire. Cela impliquerait que lorsqu’ils jouent tous deux avec leurs stratégies gagnantes, ils gagnent tous les deux, ce qui est impossible. Donc un sommet ne peut être gagnant que pour un seul joueur.

Calcul des stratégies gagnantes

Voyons maintenant comment calculer les stratégies gagnantes. Prêt ?

Si vous êtes à un sommet donné dans l’arène, pour trouver le meilleur coup, celui qui vous maintient dans la région gagnante de l’arène, vous devez prendre en compte tous les choix possibles ultérieurs de l’adversaire. Dans un jeu comme PyRat, le nombre de telles combinaisons est probablement trop grand pour être traité.

Imaginez une partie de PyRat limitée à 2 000 décisions pour chaque joueur. À chaque étape, les deux joueurs choisissent une direction dans laquelle se déplacer. Au minimum, chaque joueur a l’un des deux choix suivants : se déplacer ou ne pas se déplacer. Dans ce cas, le nombre de parties possibles est au moins $(2 \cdot 2)^{2000}$, ce qui est énorme.

Une meilleure approche consiste à stocker des connaissances partielles sur les stratégies et positions gagnantes. Ce type d’approche s’appelle la “programmation dynamique”.

Il est possible de caractériser l’état d’un jeu par la position du rat, la position du python, les emplacements des morceaux de fromage restants, et le score de chaque joueur.

Encore une fois, imaginez une instance de PyRat dans laquelle le labyrinthe contient $15 \times 11$ cases, soit 165 cases, et disons qu’il y a 7 morceaux de fromage. Notez que nous n’avons pas besoin de retenir les emplacements exacts des morceaux de fromage, puisqu’ils ne bougeront pas pendant la partie, mais seulement de retenir lesquels ont été mangés et lesquels sont encore dans le labyrinthe. Donc dans cet exemple, il y a 2 configurations possibles pour chacun des 7 morceaux de fromage, ce qui fait un total de $2^7$ configurations possibles. De plus, il y a 165 positions possibles pour chaque joueur. Concernant les scores, il suffit de stocker le score d’un seul joueur, car cela, avec les morceaux de fromage restants, permet de retrouver le score de l’autre joueur. Il y a donc 5 scores possibles pour un joueur, entre 0 et 4. Enfin, il y a au maximum $2^7 \cdot 165 \cdot 165 \cdot 5 \approx 17~\text{millions}$ de sommets dans l’arène.

Rappelez-vous que les sommets dans l’arène représentent des configurations de jeu.

Une façon de calculer les stratégies gagnantes commence par identifier les sommets dans l’arène, ici représentés par le rectangle, dans lesquels le jeu est déjà gagné pour un joueur. Dans l’exemple précédent, cela revient à déterminer tous les sommets où l’un des joueurs, par exemple le python, a un score de 4.

Nous pouvons maintenant essayer d’identifier d’autres sommets de l’arène où un des joueurs est assuré de gagner.

Par exemple, ce sont tous les sommets à partir desquels le joueur peut choisir un coup tel que, quel que soit le choix de l’adversaire, le joueur atteint un sommet dans l’arène déjà identifié comme gagnant.

En répétant ce processus jusqu’à ce qu’aucun sommet supplémentaire ne puisse être ajouté à la liste des sommets gagnants, on construit en fait une stratégie gagnante pour le joueur et en même temps on calcule sa région gagnante dans l’arène.

Dans la région restante de l’arène, quoi que fasse le python, le rat peut toujours se déplacer de manière à éviter d’entrer dans la région bleue de l’arène. Par conséquent, il n’y a pas de stratégie gagnante pour le python dans la région rouge.

Vous devez noter que cette façon de construire une stratégie gagnante ne peut être calculée que pour un petit labyrinthe avec un nombre limité de morceaux de fromage, et n’est pas vraiment réalisable pour de grands labyrinthes. Pour les grands labyrinthes, une meilleure approche consisterait à faire des hypothèses sur les décisions de l’adversaire, ce qui réduirait les facteurs combinatoires.

Mots de conclusion

Cela termine la leçon d’aujourd’hui. Vous avez appris comment les stratégies gagnantes peuvent être générées, mais aussi que, pour des jeux plus grands et certains problèmes computationnels, il peut être nécessaire de prendre en compte la stratégie de l’adversaire.

C’est maintenant à vous d’implémenter tout cela dans votre IA dans PyRat !

Malheureusement, cette vidéo était la dernière de ce MOOC. J’ai vraiment apprécié explorer les sujets de ce cours avec vous ! Vincent, Nicolas et moi espérons que vous avez appris beaucoup de choses fascinantes sur les algorithmes, et que votre IA sera assez intelligente pour battre de nombreux adversaires.

Que le fromage soit avec vous !

Pour aller plus loin

2 — L’algorithme maximin

En théorie des jeux (plus précisément dans les jeux à information complète et somme nulle), l’algorithme maximin vise à trouver le meilleur coup à jouer à chaque étape, en supposant que l’adversaire jouera de manière optimale. Le but de l’adversaire est donc de minimiser notre gain, tandis que le nôtre est de le maximiser.

Concrètement, l’idée principale de l’algorithme est de partir des feuilles de l’arbre des solutions, et d’attribuer un score à chacune de ces feuilles, correspondant au gain qu’elle nous procure.

Ensuite, on remonte l’arbre jusqu’à la racine, en alternant minimisations des scores et maximisations. Cette alternance modélise les choix soit du joueur, soit de l’adversaire.

2.1 — Exemple

Décrivons ce qui se passe sur un exemple, tiré de la page Wikipédia française sur l’algorithme Minimax (minimax est juste le problème symétrique de maximin dans lequel on cherche à minimiser une fonction de perte plutôt qu’à maximiser un gain) :

Ici, nous avons un arbre des exécutions possibles d’un jeu, dans lequel les profondeurs modélisées par des carrés indiquent notre tour de jouer, et les cercles indiquent le tour de l’adversaire.

Pour chaque nœud cercle, l’adversaire va essayer de minimiser notre gain, en choisissant l’action qui mène au gain minimum pour nous. Par conséquent, l’algorithme minimax supposera les choix suivants :

Cela signifie maintenant que, si j’atteins l’état du jeu $B1$, l’adversaire jouera de manière à ce que notre gain total soit 3, obtenu à partir de l’état $C3$. Si nous faisons aller le jeu à l’état $B2$, notre adversaire peut jouer de manière à ce que le gain soit 5 en imposant l’état $C4$. Enfin, si nous jouons pour atteindre la situation $B3$, l’adversaire peut jouer de manière à ce que le gain soit 2 en imposant l’état $C8$.

Le choix optimal pour nous est donc de maximiser le gain, et de jouer de manière à atteindre l’état $B2$. En faisant ce choix, le meilleur gain que l’on peut espérer face à un adversaire optimal est 5 :

L’algorithme minimax consiste à alterner ces étapes de minimisations et maximisations, afin de maximiser le gain que nous pouvons finalement attendre en prenant une décision.

Il est important de noter que l’algorithme maximin ne renverra pas la séquence de coups qui mène au gain le plus élevé possible (qui dans l’exemple ci-dessus serait $C9$ avec un gain de 12), mais la séquence de jeu la moins mauvaise, c’est-à-dire celle qui mène réalistement à notre meilleur gain.

Pour conclure, remarquez qu’ici nous alternons les décisions entre les joueurs, ce qui implique qu’ils prennent leurs décisions à tour de rôle. Il existe cependant des résultats équivalents pour les jeux simultanés tels que PyRat.

Pour aller plus loin