Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

La Recherche Adversariale en Intelligence Artificielle

Par Seifeddine AMMAR Publié le 14/02/2020 à 01:40:57 Noter cet article:
(0 votes)
En attente de relecture par le comité de lecture

Cet article est une traduction de mon article "Adversarial Research in Artificial Intelligence" disponible sur : https://www.supinfo.com/articles/single/10312-adversarial-research-in-artificial-intelligence

Introduction

Vous êtes-vous déjà demandé comment un ordinateur peut jouer intelligemment à des jeux comme les échecs, X / O, Go, etc.?

Dans cet article, nous verrons comment créer des jeux de plateau en utilisant l'un des algorithmes d'intelligence artificielle Min-Max.

Qu'est-ce que la recherche adversariale?

La recherche adversariale est une méthode de recherche pour trouver le meilleur coup dans un jeu composé de deux joueurs.Cette méthode est utilisée dans les jeux où l'avance d'un joueur sur l'autre est mesurable, et la victoire d'un joueur est une perte pour l'autre, donc la somme est 0 d'où l'appellation somme-nulle (zero-sum). Cette méthode est généralement utilisée dans les jeux de plateau tels que X / O, les échecs, etc.

L'algorithme Min-Max est commun dans ce domaine et il existe une version améliorée de celui-ci appeléeAlpha-Beta Pruning.

Commençons par définir des termes que nous allons rencontrer dans cet algorithme avant de passer à l'explication du fonctionnement de l'algorithme:

État initial: il s'agit de l'état du jeu avant la mise en œuvre de l'algorithme.

Fonction Successeur: c'est la fonction responsable de la génération de mouvements possibles (mouvements légaux) pour un état particulier du jeu.

Test Terminal: c'est un test qui détermine si le jeu a atteint sa fin par la victoire d'un joueur ou un match nul.

Fonction d'évaluation: fonction qui donne une valeur numérique à une évaluation qui identifie le joueur en avance durant un état particulier du jeu.

Pendant l'application de l'algorithme, les principaux problèmes que nous serons menés à résoudre sont:

  • Trouver un moyen pour représenter le plateau du jeu.

  • Générez tous les mouvements légaux(Legal Moves).

  • Évaluez une situation particulière, déterminez le joueur en avance et évaluez son écart.

Comment fonctionne cet algorithme ?

L'algorithme est basé sur deux principes:

  1. Quand c'est mon tour de jouer (l'ordinateur), j'essaierai de choisir un coup qui augmentera mon évaluation et mes chances de gagner.

  2. Quand c'est au tour de mon adversaire de jouer, il essaiera de choisir un mouvement qui réduira mon évaluation et mes chances de gagner.

Ces deux principes sont à l'origine de la dénomination Min-Max, Max est quand j'essaie de maximiser mon évaluation et Min est quand l'adversaire essaie de la minimiser.

Afin de choisir le mouvement, l'algorithme teste toutes les possibilités en utilisant la fonction Successeur, et pour chacun de ces mouvements, les prochains mouvements possibles sont testés et ainsi de suite, jusqu'à ce que nous atteignions une certaine profondeur définie précédemment. Lorsque cette profondeur est atteinte, l'état du jeu est évalué par la fonction d'évaluation. Le meilleur coup est celui qui a conduit à l'état du jeu avec l'évaluation la plus élevée.

Pour faciliter le sujet, nous pouvons représenter le processus avec une arborescence de jeu, de sorte que:

  • Les nœuds représenteront les états du jeu

  • Les branches représenteront les mouvements disponibles qui feront passer le jeu d'un état à un autre.

  • Le nœud racine représentera l'état initial.

    L'état initial signifie que c'est à l'ordinateur de jouer, il doit donc choisir le coup qui lui donnera la meilleure évaluation, c'est pourquoi le nœud de ce niveau est un nœud Max.

    Le niveau qui précède le nœud racine sera le mouvement de l'adversaire, nous supposerons donc que l'adversaire choisira son meilleur mouvement, ce qui diminuera l'évaluation de l'ordinateur, alors nous appellerons les nœuds de ce niveau nœuds Min.

    Ce cycle se poursuit jusqu'à ce que la profondeur souhaitée soit atteinte ou que le jeu se termine.

    Les feuilles ou les nœuds terminaux seront les nœuds où nous évaluerons l'état du jeu.

Nous allons essayer d'illustrer davantage avec des images, prenons l'arborescence de jeu suivante à partir d'un jeu X / O en cours:

Dans ce jeu, l'ordinateur prendra le rôle de X.

Comme nous l'avons dit précédemment, la racine représente l'état actuel du jeu et l'état dans lequel l'ordinateur doit effectuer un mouvement. L'algorithme va essayer tous les mouvements possibles pour choisir le mouvement qui lui donne la meilleure évaluation, et pour chacun des ces mouvements, il essaiera les mouvements possibles qui suivent et supposera que l'adversaire choisira son meilleur mouvements qui sera le coup qui donne la pire évaluation à l'ordinateur et ainsi de suite.

Dans l'image, les étiquettes à gauche Max et Min à chaque niveau montrent la nature du mouvement à choisir à cet état. Au premier niveau "Root", le mouvement qui donne à l'ordinateur la meilleure note sera choisi, donc l'étiquette est Max.

Au deuxième niveau, c'est le tour de l'adversaire. L'algorithme essaiera de choisir le coup qui donne la pire évaluation à l'ordinateur, l'étiquette est alors Min. Les tours se suivent jusqu'à ce que nous atteignions la profondeur souhaitée ou la fin du jeu.

Lorsque nous arrivons à la feuille, le nœud 4 par exemple, l'état du jeu est évalué. Parce que l'ordinateur a gagné, il obtient une note à l'infini. Comme le nœud 3 est Max, la valeur la plus élevée et l'unique en provenance du nœud 4 sera choisie.

Prenons le nœud numéro 2 comme autre exemple. C'est un nœud Min, l'algorithme choisira la pire évaluation entre les nœuds 3 et 5, mais le choix est insignifiant car les deux nœuds ont une valeur infinie qui exprime la victoire de l'ordinateur, ce qui signifie que la défaite de l'adversaire est inévitable.

Le nœud 7, parce qu'il s'agit d'un nœud Min,la pire évaluation attribuée entre les nœuds 8 et 9 sera choisie.La feuille 8 a une valeur négative d'infini qui exprime la défaite de l'ordinateur et annonce la victoire de l'adversaire donc elle sera choisie.

Dans le nœud 11, qui est un nœud Min, l'algorithme choisira la valeur la plus basse attribuée entre les nœuds 12 et 13, il choisira donc 12 car elle porte la valeur de l'infini négatif.

Revenons maintenant au nœud racine, où l'ordinateur doit choisir son prochain mouvement. Il y a 3 options disponibles qui sont l'infini (nœud 2) et l'infini négatif (nœuds 7 et 11). Comme le nœud racine est un nœud Max, l'algorithme choisira la valeur la plus élevée qui est l'infini positif provenant du nœud 2.

L'algorithme a décidé que le meilleur mouvement pour l'ordinateur est de mettre le X au milieu comme le nœud 2, comme indiqué dans la figure ci-dessous.

Maintenant que nous comprenons comment fonctionne l'algorithme, regardons ensemble un peu de code:

 function minimax(node, depth, maximizingPlayer) is 
    
    if depth = 0 or node is a terminal node then    
        return the heuristic value of node
        
    if maximizingPlayer then 
        value := -∞ 
        for each child of node do 
            value := max(value, minimax(child, depth - 1, FALSE))
        return value
        
    else (* minimizing player *)
        value := +∞ 
        for each child of node do 
            value := min(value, minimax(child, depth - 1, TRUE))
        return value
                

L'algorithme reçoit en entrée l'état actuel du jeu (représenté par un nœud) et la profondeur requise.

La variable maximizingPlayer détermine si le nœud actuel est un nœud Max ou le nœud Min.

À la ligne 2, nous vérifions si nous atteignons la profondeur souhaitée ou si le jeu a atteint une fin avec la victoire ou le match nul d'un joueur, si c'est le cas, nous retournerons la note du nœud (en utilisant la fonction d'évaluation comme mentionné).

À la ligne 4, la partie codage du nœud Max commence. L'algorithme passera par tous les mouvements disponibles (mouvements légaux) à partir du nœud actuel, et dans chaque mouvement, nous appelons la même fonction avec le changement de la valeur de maximizingPlayer à FALSE parce que le prochain tour sera le mouvement de l'adversaire qui est un nœud Min.

A chaque itération, la valeur de Depth ('la variable qui représente la profondeur') doit être diminuée de 1. Après que tous les coups aient reçu une évaluation, le coup qui donne à l'ordinateur la meilleure évaluation sera choisi.

Quant au nœud Min, il n'est pas très différent du précédent. L'algorithme doit voir à travers tous les mouvements disponibles à partir du nœud actuel, et à chaque mouvement, nous appelons la même fonction avec le changement de la valeur de maximizingPlayer à TRUE puisque le prochain tour sera pour l'ordinateur (Max Node).

À chaque itération, la valeur de Depth est diminuée de 1. Une fois que tous les coups ont reçu une évaluation, nous supposerons que l'adversaire jouera son meilleur coup, le coup qui donne à l'ordinateur la pire évaluation qu'il choisira.

Conclusion

La difficulté du jeu peut être contrôlée en sélectionnant la profondeur. Plus la valeur de la profondeur est élevée, plus le jeu sera difficile et vice versa. Dans X / O, il y a très peu de mouvements légaux, cela s'appelle le facteur de branchement ( Branching Factor ) dans la représentation de l'arbre de jeu, il est donc possible de régler la profondeur à 9 afin que l'algorithme puisse toujours atteindre la fin du jeu sans remarquer de ralentissement avec le jeu contrairement aux jeux complexes où le nombre de coups est beaucoup plus élevé, comme les échecs par exemple.

C'est pourquoi il existe une optimisation de l'algorithme Min-Max qui ignore les calculs des nœuds inutiles. Cet algorithme est appelé Alpha-Beta Pruning.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels