Chapitre 1 Recherche Adversariale en Intelligence Artificielle PDF

Chapitre 1 : Recherche Adversariale en Intelligence Artificielle Table des matières 1. Recherche....................................................................................................................................... 2 1.1. Résolution des Problèmes de Recherche...............

Chapitre 1 : Recherche Adversariale en Intelligence Artificielle Table des matières 1. Recherche....................................................................................................................................... 2 1.1. Résolution des Problèmes de Recherche............................................................................. 4 1.2. Recherche en profondeur (Depth-First Search)................................................................. 5 1.3. Recherche en largeur (Breadth-First Search)..................................................................... 6 2. Recherche Gloutonne Best-First (Greedy Best-First Search)................................................... 7 2.1. Recherche A*......................................................................................................................... 8 3. Recherche Adversariale................................................................................................................ 8 3.1. Minimax................................................................................................................................. 8 3.2. Comment fonctionne l'algorithme :..................................................................................... 9 3.3. Minimax dans le Morpion..................................................................................................... 9 3.4. Élagage Alpha-Bêta............................................................................................................. 11 3.5. Minimax à Profondeur Limitée............................................................................................. 12  1 Introduction La recherche en intelligence artificielle (IA) est au cœur de nombreuses problématiques dans le domaine des jeux et des systèmes décisionnels. Contrairement aux approches classiques de recherche, où un algorithme doit simplement trouver une solution à un problème donné, la recherche adversariale introduit une dimension supplémentaire : la compétition contre un adversaire intelligent. Ce type de recherche est particulièrement pertinent dans les jeux à somme nulle, où les actions d'un joueur influencent directement les possibilités de l'autre. À travers des algorithmes tels que Minimax et ses optimisations, comme l'élagage Alpha-Bêta, l'IA est capable de prendre des décisions optimales en anticipant les mouvements de l’adversaire et en simulant les états futurs du jeu. Ce chapitre se propose d’explorer les principes fondamentaux de la recherche adversariale, avec un accent particulier sur l'algorithme Minimax et son application dans des jeux tels que le tic-tac-toe. Intelligence Artificielle L'intelligence artificielle (IA) couvre un ensemble de techniques qui permettent à l'ordinateur d'adopter un comportement semblant être intelligent. Par exemple, l'IA est utilisée pour reconnaître des visages sur vos photos de réseaux sociaux, battre le champion du monde aux échecs, ou encore comprendre votre voix lorsque vous parlez à Siri ou Alexa sur votre téléphone. Dans ce cours, nous allons explorer certaines des idées qui rendent l'IA possible : ∙ Recherche Trouver une solution à un problème, comme une application de navigation  qui trouve le meilleur itinéraire entre votre point de départ et votre destination, ou comme jouer à un jeu et décider du prochain mouvement à effectuer. ∙ Connaissance Représenter des informations et en tirer des inférences. ∙ Incertitude Gérer des événements incertains à l'aide des probabilités. ∙ Optimisation Trouver non seulement une solution correcte à un problème, mais une meilleure, voire la meilleure solution possible. ∙ Apprentissage Améliorer les performances en se basant sur l'accès aux données et l'expérience. Par exemple, votre email peut distinguer les spams des emails légitimes en fonction des expériences passées. ∙ Réseaux de Neurones Une structure de programme inspirée du cerveau humain qui est capable de réaliser des tâches efficacement. ∙ Langage Traiter le langage naturel, produit et compris par les humains. 1. Recherche Les problèmes de recherche impliquent un agent qui reçoit un état initial et un état objectif, et qui retourne une solution sur la manière de passer de l’un à l’autre. Une application de navigation utilise un processus de recherche typique, où l'agent (la partie réfléchissante du programme) reçoit en entrée votre position actuelle et votre destination, et, à l'aide d'un algorithme de recherche, retourne un itinéraire suggéré. Cependant, il existe de nombreuses autres formes de problèmes de recherche, comme des puzzles ou des labyrinthes. Le puzzle 15 Trouver une solution à un puzzle 15 nécessiterait l'utilisation d'un algorithme de recherche. 2 1. Agent Une entité qui perçoit son environnement et agit sur celui-ci. Dans une application de navigation, par exemple, l'agent serait une représentation d'une voiture qui doit décider quelles actions entreprendre pour arriver à destination. 2. État Une configuration de l'agent dans son environnement. Par exemple, dans un puzzle 15, un état est une manière dont les chiffres sont arrangés sur le plateau. 3. État Initial L'état à partir duquel l'algorithme de recherche commence. Dans une application de navigation, il s'agirait de l'emplacement actuel. 4. Actions Les choix qui peuvent être faits dans un état donné. Plus précisément, les  actions peuvent être définies comme une fonction. Lorsqu'il reçoit l'état s en entrée, Actions(s) retourne en sortie l'ensemble des actions qui peuvent être exécutées dans l'état s. Par exemple, dans un puzzle 15, les actions possibles d'un état donné sont les façons dont vous pouvez faire glisser les cases dans la configuration actuelle (4 si la case vide est au milieu, 3 si elle est à côté d'un bord, 2 si elle est dans un coin). 5. Modèle de Transition Une description de l'état résultant de l'exécution d'une action applicable dans un état donné. Plus précisément, le modèle de transition peut être défini comme une fonction. Lorsqu'il reçoit l'état s et l'action a en entrée, Résultats(s, a) retourne l'état résultant de l'exécution de l'action a dans l'état s. Par exemple, étant donné une certaine configuration d'un puzzle 15 (état s), déplacer une case dans une direction (action a) entraînera une nouvelle configuration du puzzle (le nouvel état). 6. Espace des États L'ensemble de tous les états atteignables à partir de l'état initial par n'importe quelle séquence d'actions. Par exemple, dans un puzzle 15, l'espace des états se compose de toutes les 16!/2 configurations du plateau pouvant être atteintes à partir de n'importe quel état initial. L'espace des états peut être visualisé comme un graphe orienté avec les états, représentés par des nœuds, et les actions, représentées par des flèches entre les nœuds. 3 7. Test de But La condition qui détermine si un état donné est un état objectif. Par exemple, dans une application de navigation, le test de but consisterait à vérifier si l'emplacement actuel de l'agent (la représentation de la voiture) est à la destination. Si  c'est le cas, le problème est résolu. Si ce n'est pas le cas, nous continuons à rechercher. 8. Coût du Chemin Un coût numérique associé à un chemin donné. Par exemple, une application de navigation ne se contente pas de vous amener à votre destination ; elle le fait tout en minimisant le coût du chemin, trouvant le moyen le plus rapide possible pour vous amener à l'état objectif. 1.1. Résolution des Problèmes de Recherche ∙ Solution Une séquence d'actions qui mène de l'état initial à l'état objectif. ∙ Solution Optimale Une solution qui présente le coût de chemin le plus bas parmi toutes les solutions. Dans un processus de recherche, les données sont souvent stockées dans un nœud, une structure de données qui contient les informations suivantes : ∙ Un état ∙ Son nœud parent, à travers lequel le nœud actuel a été généré ∙ L'action qui a été appliquée à l'état du parent pour arriver au nœud actuel ∙ Le coût du chemin depuis l'état initial jusqu'à ce nœud Les nœuds contiennent des informations qui les rendent très utiles pour les algorithmes de recherche. Ils contiennent un état, qui peut être vérifié à l'aide du test de but pour voir s'il s'agit de l'état final. S'il l'est, le coût du chemin du nœud peut être comparé à celui d'autres nœuds, ce qui permet de choisir la solution optimale. Une fois le nœud choisi, en vertu de la conservation du nœud parent et de l'action qui a conduit du parent au nœud actuel, il est possible de retracer chaque étape depuis l'état initial jusqu'à ce nœud, et cette séquence d'actions constitue la solution. 4 Cependant, les nœuds sont simplement une structure de données — ils ne font pas de recherche, ils contiennent des informations. Pour effectuer une recherche, nous utilisons la frontière, le mécanisme qui "gère" les nœuds. La frontière commence par contenir un état initial et un ensemble vide d'éléments explorés, puis elle répète les actions suivantes jusqu'à ce qu'une solution soit trouvée : Répétez : 1. Si la frontière est vide, Arrêtez. Il n'y a pas de solution au problème. Retirez un nœud de la frontière. C'est le nœud qui sera examiné. 2. Si le nœud contient l'état objectif, 3. Retournez la solution. Arrêtez. Sinon, 4. Développez le nœud (trouvez tous les nouveaux nœuds accessibles depuis ce nœud), et ajoutez les nœuds résultants à la frontière. 5. Ajoutez le nœud actuel à l'ensemble des éléments explorés. 1.2. Recherche en profondeur (Depth-First Search) Dans la description précédente de la frontière, un point n'a pas été mentionné. À l'étape 2 dans le pseudocode ci-dessus, quel nœud doit être retiré ? Ce choix a des implications sur la qualité de la solution et sur la rapidité à laquelle elle est atteinte. Il existe plusieurs façons d’aborder la question de savoir quels nœuds doivent être examinés en premier, deux d'entre elles pouvant être représentées par les structures de données pile (dans la recherche en profondeur) et file (dans la recherche en largeur, avec une petite démonstration amusante pour illustrer la différence entre les deux). Commençons par l'approche de la recherche en profondeur (DFS). Un algorithme de recherche en profondeur épuise chaque direction avant d'en essayer une autre. Dans ces cas, la frontière est gérée comme une structure de pile. La phrase à retenir ici est "dernier entré, premier sorti". Après que des nœuds aient été ajoutés à la frontière, le premier nœud à retirer et à examiner est le dernier à avoir été ajouté. Cela donne un algorithme de recherche qui va aussi profondément que possible dans la première direction qui se présente tout en laissant les autres directions pour plus tard. (Un exemple hors cours : imaginez que vous cherchez vos clés. Dans une approche de recherche en profondeur, si vous commencez par fouiller dans votre pantalon, vous passerez en revue chaque poche, en vidant chacune d'entre elles et en examinant soigneusement leur contenu. Vous n'arrêterez de chercher dans votre pantalon et ne commencerez à chercher ailleurs que lorsque vous aurez complètement fouillé chaque poche.) Avantages : ∙ Dans le meilleur des cas, cet algorithme est le plus rapide. S'il "a de la chance" et choisit toujours le bon chemin vers la solution (par hasard), alors la recherche en profondeur prend le moins de temps possible pour arriver à une solution. Inconvénients : ∙ Il est possible que la solution trouvée ne soit pas optimale. 5 ∙ Dans le pire des cas, cet algorithme explorera tous les chemins possibles avant de trouver la solution, ce qui prendra le plus de temps possible. Exemple de code : python Copier le code # Définir la fonction qui retire un nœud de la frontière et le renvoie. def remove(self): # Terminer la recherche si la frontière est vide, car cela signifie qu'il n'y a pas de solution. if self.empty(): raise Exception("frontière vide") else: # Sauvegarder le dernier élément de la liste (qui est le nœud le plus récemment ajouté) node = self.frontier[-1] # Sauvegarder tous les éléments de la liste sauf le dernier (c.-à-d. retirer le dernier nœud) self.frontier = self.frontier[:-1] return node 1.3. Recherche en largeur (Breadth-First Search) L'opposé de la recherche en profondeur est la recherche en largeur (BFS). Un algorithme de recherche en largeur explorera plusieurs directions en même temps, en prenant un pas dans chaque direction possible avant de prendre un second pas dans chaque direction. Dans ce cas, la frontière est gérée comme une structure de file. La phrase à retenir ici est "premier entré, premier sorti". Dans ce cas, tous les nouveaux nœuds s'ajoutent en ligne, et les nœuds sont examinés en fonction de celui qui a été ajouté en premier (premier arrivé, premier servi !). Cela donne un algorithme de recherche qui fait un pas dans chaque direction possible avant de prendre un second pas dans l'une d'elles. (Un exemple hors cours : imaginez que vous cherchez vos clés. Dans ce cas, si vous commencez par fouiller dans votre pantalon, vous chercherez dans votre poche droite. Ensuite, au lieu de chercher dans votre poche gauche, vous examinerez un tiroir. Ensuite, sur la table. Et ainsi de suite, dans chaque endroit auquel vous pouvez penser. Ce n'est qu'après avoir épuisé tous les endroits que vous reviendrez à votre pantalon et chercherez dans la poche suivante.) Avantages : ∙ Cet algorithme garantit de trouver la solution optimale. Inconvénients : ∙ Cet algorithme prend presque toujours plus de temps que le temps minimal d'exécution. ∙ Dans le pire des cas, cet algorithme prend le plus de temps possible pour s'exécuter. Exemple de code : python Copier le code # Définir la fonction qui retire un nœud de la frontière et le renvoie. def remove(self): # Terminer la recherche si la frontière est vide, car cela signifie qu'il n'y a pas de solution. 6 if self.empty(): raise Exception("frontière vide") else: # Sauvegarder le premier élément de la liste (qui est le premier ajouté) node = self.frontier # Sauvegarder tous les éléments de la liste sauf le premier (c.-à-d. retirer le premier nœud) self.frontier = self.frontier[1:] return node 2. Recherche Gloutonne Best-First (Greedy Best-First Search) Les recherches en largeur (breadth-first) et en profondeur (depth-first) sont toutes deux des algorithmes de recherche non informés. Cela signifie que ces algorithmes n'utilisent aucune connaissance supplémentaire sur le problème qu'ils n'ont pas acquise par leur propre exploration. Cependant, il arrive souvent que des connaissances sur le problème soient effectivement disponibles. Par exemple, lorsqu'un humain qui résout un labyrinthe arrive à une intersection, il peut voir quelle direction va dans le sens général de la solution et laquelle ne le fait pas. L'IA peut faire de même. Un type d'algorithme qui prend en compte des connaissances supplémentaires pour améliorer ses performances est appelé un algorithme de recherche informé. La recherche gloutonne best-first développe le nœud le plus proche de l'objectif, tel que déterminé par une fonction heuristique h(n). Comme son nom l'indique, cette fonction estime à quelle distance se trouve le prochain nœud de l'objectif, mais elle peut se tromper. L'efficacité de l'algorithme glouton best-first dépend de la qualité de la fonction heuristique. Par exemple, dans un labyrinthe, un algorithme peut utiliser une fonction heuristique basée sur la distance de Manhattan entre les nœuds possibles et la fin du labyrinthe. La distance de Manhattan ignore les murs et compte le nombre d'étapes vers le haut, vers le bas ou sur les côtés qu'il faudrait pour aller d'un point à l'autre. Il s'agit d'une estimation simple que l'on peut dériver à partir des coordonnées (x, y) de la position actuelle et de la position de l'objectif. 7 Distance de Manhattan Cependant, il est important de souligner que, comme pour toute heuristique, elle peut être incorrecte et entraîner l'algorithme sur un chemin plus lent qu'il ne l'aurait fait autrement. Il est possible qu'un algorithme de recherche non informé fournisse une meilleure solution plus rapidement, mais cela est moins probable qu'avec un algorithme informé. 2.1. Recherche A* Un développement de l'algorithme glouton best-first, la recherche A* prend en compte non seulement h(n), le coût estimé de la position actuelle à l'objectif, mais aussi g(n), le coût accumulé jusqu'à la position actuelle. En combinant ces deux valeurs, l'algorithme dispose d'un moyen plus précis de déterminer le coût de la solution et d'optimiser ses choix en temps réel. L'algorithme suit (le coût du chemin jusqu'à présent + le coût estimé jusqu'à l'objectif), et dès qu'il dépasse le coût estimé d'une option précédente, l'algorithme abandonne le chemin actuel et revient à l'option précédente, évitant ainsi de suivre un long chemin inefficace que h(n) avait incorrectement désigné comme le meilleur. Encore une fois, comme cet algorithme repose sur une heuristique, il est aussi bon que l'heuristique qu'il utilise. Il est possible que, dans certaines situations, il soit moins efficace que la recherche gloutonne best-first ou même que les algorithmes non informés. Pour que la recherche A* soit optimale, la fonction heuristique, h(n), doit être : ∙ Admissible, c'est-à-dire qu'elle ne doit jamais surestimer le coût réel, et ∙ Consistante, ce qui signifie que le coût estimé du chemin vers l'objectif d'un nouveau nœud, en plus du coût de la transition depuis le nœud précédent, est supérieur ou égal au coût estimé du chemin vers l'objectif du nœud précédent. Formellement, h(n) est consistante si, pour chaque nœud n et son successeur n’ avec un coût de transition c, h(n) ≤ h(n’) + c. 3. Recherche Adversariale Jusqu'à présent, nous avons discuté d'algorithmes qui cherchent une réponse à une question. Dans la recherche adversariale, l'algorithme est confronté à un adversaire qui essaie d'atteindre l'objectif opposé. Souvent, les IA qui utilisent la recherche adversariale sont rencontrées dans des jeux, comme le morpion (tic-tac-toe). Alors que, précédemment, nous avons discuté d'algorithmes cherchant une réponse à une question, dans la recherche adversariale, l'algorithme fait face à un adversaire qui essaie d'atteindre l'objectif opposé. L'IA utilisant la recherche adversariale est souvent rencontrée dans des jeux, tels que le morpion (tic-tac-toe). 3.1. Minimax Un type d'algorithme dans la recherche adversariale, le Minimax, représente les conditions de victoire comme (-1) pour un côté et (+1) pour l'autre. Les actions suivantes seront déterminées par ces conditions, la partie minimisante essayant d'obtenir le score le plus bas et la partie maximisante essayant d'obtenir le score le plus élevé. 8 Représentation d'une IA pour le morpion : ∙ S₀ : état initial (dans notre cas, un plateau 3X3 vide) ∙ Players(s) : une fonction qui, étant donné un état s, renvoie à quel joueur c'est le tour (X ou O). ∙ Actions(s) : une fonction qui, étant donné un état s, renvoie tous les coups légaux dans cet état (quelles cases sont libres sur le plateau). ∙ Result(s, a) : une fonction qui, étant donné un état s et une action a, renvoie un nouvel état. C'est le plateau résultant de l'action a effectuée dans l'état s (effectuer un coup dans le jeu). ∙ Terminal(s) : une fonction qui, étant donné un état s, vérifie si c'est la dernière étape du jeu, c'est-à-dire si quelqu'un a gagné ou s'il y a égalité. Renvoie Vrai si le jeu est terminé, Faux sinon. ∙ Utility(s) : une fonction qui, étant donné un état terminal s, renvoie la valeur utilitaire de  l'état : -1, 0 ou 1. 3.2. Comment fonctionne l'algorithme : Récursivement, l'algorithme simule tous les jeux possibles qui peuvent se dérouler à partir de l'état actuel jusqu'à ce qu'un état terminal soit atteint. Chaque état terminal est évalué comme étant (-1), 0 ou (+1). 3.3. Minimax dans le Morpion Connaissant, selon l'état, à qui c'est le tour de jouer, l'algorithme peut savoir si le joueur actuel, en jouant de manière optimale, choisira l'action qui mène à un état avec une valeur plus basse ou plus haute. De cette manière, en alternant entre minimiser et maximiser, l'algorithme crée des valeurs pour l'état résultant de chaque action possible. Pour donner un exemple plus concret, on peut imaginer que le joueur maximisant se demande à chaque tour : « Si je fais cette action, un nouvel état en résultera. Si le joueur minimisant joue de manière optimale, quelle action 9 prendra-t-il pour obtenir la valeur la plus basse ? » Cependant, pour répondre à cette question, le joueur maximisant doit se demander : « Pour savoir ce que fera le joueur minimisant, je dois simuler le même processus dans l'esprit du minimiseur : le joueur minimisant se demandera : "Si je fais cette action, quelle action pourra prendre le joueur maximisant pour obtenir la valeur la plus élevée ?" » C'est un processus récursif, et il peut être difficile à appréhender ; consulter le pseudo-code ci-dessous peut aider. Finalement, à travers ce raisonnement récursif, le joueur maximisant génère des valeurs pour chaque état qui pourrait résulter de toutes les actions possibles dans l'état actuel. Après avoir ces valeurs, le joueur maximisant choisit la plus haute. Algorithme Minimax Le Maximisateur considère les valeurs possibles des états futurs. En pseudo-code, l'algorithme Minimax fonctionne de la manière suivante : Étant donné un état s : ∙ Le joueur maximisant choisit l'action a dans Actions(s) qui produit la plus grande valeur de Min-Value(Result(s, a)). ∙ Le joueur minimisant choisit l'action a dans Actions(s) qui produit la plus petite valeur de Max-Value(Result(s, a)). Fonction Max-Value(état) : v = -∞ si Terminal(état) : retourner Utility(état) pour chaque action dans Actions(état) : 10 v = Max(v, Min-Value(Result(état, action))) retourner v Fonction Min-Value(état) : v=∞ si Terminal(état) : retourner Utility(état)  pour chaque action dans Actions(état) : v = Min(v, Max-Value(Result(état, action))) retourner v 3.4. Élagage Alpha-Bêta Une manière d'optimiser Minimax, l'élagage Alpha-Bêta permet d'éviter certaines des calculs récursifs qui sont clairement défavorables. Après avoir établi la valeur d'une action, si des preuves initiales montrent que l'action suivante peut donner un meilleur score à l'adversaire que l'action déjà établie, il n'est pas nécessaire de poursuivre l'exploration de cette action, car elle sera indiscutablement moins favorable. Cela est facilement illustré par un exemple : un joueur maximisant sait qu'à l'étape suivante, le joueur minimisant cherchera à atteindre le score le plus bas. Supposons que le joueur maximisant ait trois actions possibles, et que la première ait une valeur de 4. Ensuite, le joueur commence à générer la valeur de la prochaine action. Pour cela, il génère les valeurs des actions du minimiseur si le joueur actuel fait cette action, sachant que le minimiseur choisira la plus basse. Cependant, avant de terminer le calcul pour toutes les actions possibles du minimiseur, le joueur voit qu'une des options a une valeur de 3. Cela signifie qu'il n'y a aucune raison de continuer à explorer les autres actions possibles du minimiseur. Peu importe la valeur de l'action non encore évaluée, qu'elle soit 10 ou (-10). Si la valeur est 10, le minimiseur choisira l'option la plus basse, 3, qui est déjà pire que la valeur préétablie de 4. Si l'action non encore évaluée s'avérait être (-10), le minimiseur choisirait cette option (-10), ce qui est encore plus défavorable pour le maximiseur. Par conséquent, calculer des actions supplémentaires pour le minimiseur à ce stade est inutile pour le maximiseur, car ce dernier a déjà une option incontestablement meilleure dont la valeur est 4. 11  3.5. Minimax à Profondeur Limitée Il existe un total de 255 168 jeux possibles pour le morpion, et 10²⁹⁰⁰⁰ jeux possibles pour les échecs. L'algorithme Minimax, tel que présenté jusqu'à présent, nécessite de générer tous les jeux hypothétiques depuis un certain point jusqu'à la condition terminale. Bien que le calcul de tous les jeux de morpion ne pose aucun défi pour un ordinateur moderne, cela est actuellement impossible pour les échecs. Le Minimax à profondeur limitée ne considère qu'un nombre prédéfini de coups avant de s'arrêter, sans jamais atteindre un état terminal. Cependant, cela ne permet pas d'obtenir une valeur précise pour chaque action, car la fin des jeux hypothétiques n'a pas été atteinte. Pour résoudre ce problème, le Minimax à profondeur limitée repose sur une fonction d'évaluation qui estime l'utilité attendue du jeu à partir d'un état donné, ou, en d'autres termes, attribue des valeurs aux états. Par exemple, dans une partie d'échecs, une fonction d'utilité prend en entrée la configuration actuelle de l'échiquier, tente d'évaluer son utilité attendue (en fonction des pièces que chaque joueur possède et de leur position sur l'échiquier), puis renvoie une valeur positive ou négative qui représente à quel point le plateau est favorable pour un joueur par rapport à l'autre. Ces valeurs peuvent être utilisées pour décider de la bonne action, et plus la fonction d'évaluation est précise, plus l'algorithme Minimax qui s'appuie dessus sera performant. Conclusion En conclusion, la recherche adversariale constitue un aspect essentiel du développement de l'intelligence artificielle dans des environnements compétitifs. L'algorithme Minimax, en particulier, offre une solution élégante pour modéliser et résoudre des problèmes où les joueurs ont des objectifs opposés. Grâce à des améliorations comme l’élagage Alpha-Bêta, il est possible d’optimiser le temps de calcul tout en garantissant des décisions de qualité. Bien que l’application dans des jeux simples comme le tic-tac-toe illustre les concepts de manière 12 didactique, la complexité de cette approche augmente de façon exponentielle dans des jeux comme les échecs. Des techniques telles que Minimax à profondeur limitée et l’utilisation de fonctions d’évaluation permettent de contourner cette complexité, ouvrant la voie à des IA capables de rivaliser avec des joueurs humains dans des contextes variés. 13