Taille Alpha Bêta en IA

L’élagage Alpha beta est une technique d’optimisation pour l’algorithme minimax. Au cours de ce blog, nous discuterons de ce que signifie l’élagage alpha bêta, nous discuterons de l’algorithme minimax, des règles pour trouver un bon ordre, et plus encore.

1. Introduction
2. Algorithme Minimax
3. Points clés de l’Élagage Alpha-bêta
4. Fonctionnement de l’Élagage Alpha-bêta
5. Déplacer l’ordre dans l’Élagage
6. Règles pour trouver un bon ordre
7. Codes en Python

Introduction

Le mot « élagage » signifie couper les branches et les feuilles. En science des données, l’élagage est un terme très utilisé qui fait référence à l’élagage post et pré-élagage dans les arbres décisionnels et les forêts aléatoires. La taille alpha-bêta n’est rien d’autre que la taille de branches inutiles dans les arbres décisionnels. Cet algorithme d’élagage alpha-bêta a été découvert indépendamment par des chercheurs dans les années 1900.

L’élagage alpha-bêta est une technique d’optimisation de l’algorithme minimax qui est discutée dans la section suivante. La nécessité de l’élagage vient du fait que, dans certains cas, les arbres de décision deviennent très complexes. Dans cet arbre, certaines branches inutiles augmentent la complexité du modèle. Donc, pour éviter cela, l’élagage Alpha-Bêta vient jouer pour que l’ordinateur n’ait pas à regarder l’arbre entier. Ces nœuds inhabituels ralentissent l’algorithme. Par conséquent, en supprimant ces nœuds, l’algorithme devient rapide.

En savoir plus sur un algorithme *.

Algorithme Minimax

Minimax est une technique classique de recherche en profondeur pour un jeu séquentiel à deux joueurs. Les deux joueurs s’appellent MAX et MIN. L’algorithme minimax est conçu pour trouver le mouvement optimal pour MAX, le joueur au nœud racine. L’arborescence de recherche est créée en développant récursivement tous les nœuds de la racine d’une manière en profondeur jusqu’à la fin du jeu ou jusqu’à ce que la profondeur de recherche maximale soit atteinte. Explorons cet algorithme en détail.

Comme déjà mentionné, il y a deux joueurs dans le jeu, à savoir Max et Min. Max joue la première étape. La tâche de Max est de maximiser sa récompense tandis que la tâche de Min est de minimiser la récompense de Max, augmentant sa propre récompense en même temps. Disons que Max peut prendre des actions a, b ou c. Laquelle d’entre elles donnera à Max la meilleure récompense à la fin du jeu? Pour répondre à cette question, nous devons explorer l’arbre du jeu à une profondeur suffisante et supposer que Min joue de manière optimale pour minimiser la récompense de Max.

Voici un exemple. Quatre pièces sont dans une rangée et chaque joueur peut ramasser une pièce ou deux pièces à son tour. Le joueur qui ramasse la dernière pièce gagne. En supposant que Max joue en premier, quel mouvement doit faire Max pour gagner?

Si Max choisit deux pièces, il ne reste que deux pièces et Min peut choisir deux pièces et gagner. Ainsi, ramasser 1 pièce maximisera la récompense de Max.

Comme vous l’avez peut-être remarqué, les nœuds de l’arbre de la figure ci-dessous ont des valeurs inscrites dessus, celles-ci sont appelées valeur minimax. La valeur minimax d’un nœud est l’utilité du nœud s’il s’agit d’un nœud terminal.

Si le nœud est un nœud Max non terminal, la valeur minimax du nœud est la valeur maximale des valeurs minimax de tous les successeurs du nœud. D’autre part, si le nœud est un nœud Min non terminal, la valeur minimax du nœud est le minimum des valeurs minimax de tous les successeurs du nœud.

Maintenant, nous allons discuter de l’idée derrière la taille alpha bêta. Si nous appliquons l’élagage alpha-bêta à l’algorithme minimax standard, il donne la même décision que celle de l’algorithme standard mais il élagage ou coupe les nœuds inhabituels dans l’arbre de décision, c’est-à-dire qui n’affectent pas la décision finale prise par l’algorithme. Cela aidera à éviter la complexité de l’interprétation des arbres complexes.

Voir comment fonctionne l’algorithme KNN.

Discutons maintenant de l’intuition derrière cette technique. Essayons de trouver la décision minimax dans l’arbre ci-dessous :

Dans ce cas,

Ici, dans le résultat ci-dessus, vous devez avoir un doute dans votre esprit que comment pouvons-nous trouver le maximum de la valeur manquante. Donc, voici également la solution de votre doute:

Dans le deuxième nœud, nous choisissons la valeur minimale comme c qui est inférieure ou égale à 2, c’est-à-dire c < = 2. Maintenant, Si c < = 3 et que nous devons choisir le maximum de 3, c, 2, la valeur maximale sera 3.

Nous avons pris une décision sans regarder ces nœuds. Et c’est là que l’élagage alpha-bêta entre en jeu.

Points clés de l’élagage Alpha-bêta

• Alpha: Alpha est le meilleur choix ou la valeur la plus élevée que nous ayons trouvée à n’importe quelle instance le long du chemin de Maximizer. La valeur initiale pour alpha est -∞.

• Beta: Beta est le meilleur choix ou la valeur la plus basse que nous ayons trouvée à n’importe quelle instance sur le chemin de Minimizer. La valeur initiale pour alpha est +∞.

• La condition pour l’Élagage Alpha-bêta est que α > = β.

• Chaque nœud doit garder une trace de ses valeurs alpha et bêta. Alpha ne peut être mis à jour que lorsque c’est le tour de MAX et, de même, la bêta ne peut être mise à jour que lorsque c’est la chance de MIN.

• MAX mettra à jour uniquement les valeurs alpha et MIN player mettra à jour uniquement les valeurs bêta.

• Les valeurs des nœuds seront transmises aux nœuds supérieurs au lieu des valeurs alpha et bêta lors de l’inversion de l’arborescence.

• Les valeurs Alpha et Bêta ne sont transmises qu’aux nœuds enfants.

Travail d’Élagage Alpha-bêta

1. Nous commencerons d’abord par le mouvement initial. Nous définirons initialement les valeurs alpha et bêta comme le pire des cas, c’est-à-dire α =-∞ et β = +∞. Nous ne taillerons le nœud que lorsque alpha deviendra supérieur ou égal à bêta.

2. Comme la valeur initiale d’alpha est inférieure à celle de bêta, nous ne l’avons pas taillée. Maintenant, c’est au tour de MAX. Ainsi, au nœud D, la valeur d’alpha sera calculée. La valeur d’alpha au nœud D sera max (2, 3). Ainsi, la valeur d’alpha au nœud D sera de 3.

3. Maintenant, le prochain mouvement sera sur le nœud B et son tour pour MIN maintenant. Ainsi, au nœud B, la valeur d’alpha beta sera min(3, ∞). Ainsi, au nœud B, les valeurs seront alpha =–∞ et bêta sera 3.

Dans l’étape suivante, les algorithmes parcourent le successeur suivant du noeud B qui est le noeud E, et les valeurs de α =-∞, et β = 3 seront également passées.

4. Maintenant, c’est au tour de MAX. Donc, au nœud E, nous chercherons MAX. La valeur actuelle d’alpha à E est -∞ et elle sera comparée à 5. Donc, MAX (-∞, 5) sera 5. Donc, au nœud E, alpha = 5, Bêta = 5. Maintenant, comme nous pouvons le voir, alpha est supérieur à bêta, ce qui satisfait la condition d’élagage, nous pouvons donc élaguer le bon successeur du nœud E et l’algorithme ne sera pas traversé et la valeur au nœud E sera 5.

6. À l’étape suivante, l’algorithme revient au nœud A à partir du nœud B. Au nœud A, l’alpha sera changé en valeur maximale comme MAX (-∞, 3). Alors maintenant, la valeur d’alpha et de bêta au nœud A sera (3, +∞) respectivement et sera transférée au nœud C. Ces mêmes valeurs seront transférées au nœud F.

7. Au nœud F, la valeur d’alpha sera comparée à la branche gauche qui est 0. Ainsi, MAX(0, 3) sera 3 puis comparé au bon enfant qui est 1, et MAX(3,1) = 3 reste toujours α 3, mais la valeur du nœud de F deviendra 1.

8. Maintenant, le nœud F renverra la valeur du nœud 1 à C et se comparera à la valeur bêta à C. Maintenant, son tour pour MIN. Donc, MIN (+∞, 1) sera 1. Maintenant, au noeud C, α = 3 et β = 1 et alpha est supérieur à bêta qui satisfait à nouveau à la condition d’élagage. Donc, le prochain successeur du nœud C, c’est-à-dire G sera élagué et l’algorithme n’a pas calculé la totalité du sous-arbre G.

Maintenant, C retournera la valeur du nœud à A et la meilleure valeur de A sera MAX (1, 3) sera 3.

L’arbre représenté ci-dessus est l’arbre final qui montre les nœuds qui sont calculés et les nœuds qui ne sont pas calculés. Ainsi, pour cet exemple, la valeur optimale du maximiseur sera 3.

Regardez les bibliothèques Python open source.

Ordre de déplacement dans l’élagage

L’efficacité de l’élagage alpha–bêta est basée sur l’ordre dans lequel le nœud est examiné. L’ordre des mouvements joue un rôle important dans l’élagage alpha-bêta.

Il existe deux types d’ordre de déplacement dans la taille Alpha bêta:

1. Pire ordre: Dans certains cas d’élagage alpha bêta, aucun nœud élagué par l’algorithme ne fonctionne comme l’algorithme minimax standard. Cela prend beaucoup de temps en raison des facteurs alpha et bêta et ne donne aucun résultat efficace. C’est ce qu’on appelle le pire ordre dans la taille. Dans ce cas, le meilleur mouvement se produit du côté droit de l’arbre.
2. Ordre idéal : Dans certains cas d’élagage alpha bêta lot des nœuds élagués par l’algorithme. C’est ce qu’on appelle la commande idéale en taille. Dans ce cas, le meilleur mouvement se produit sur le côté gauche de l’arbre. Nous appliquons DFS donc il recherche d’abord à gauche de l’arbre et va en profondeur deux fois plus que l’algorithme minimax dans le même laps de temps.

Règles pour trouver un bon ordre

• Le meilleur coup se produit à partir du nœud le plus bas
• Utilisez la connaissance du domaine tout en trouvant le meilleur coup
• L’ordre des nœuds doit être tel que les meilleurs nœuds soient calculés en premier

Consultez ce tutoriel Python pour les débutants

Codes en Python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

Dans ce document, nous avons vu une composante importante de la théorie des jeux. Bien que les performances de l’algorithme minimax soient bonnes, l’algorithme est lent. Donc, pour le rendre rapide, nous utilisons un algorithme d’élagage alpha-bêta qui réduira les nœuds inhabituels de l’arbre de décision pour améliorer les performances. De nos jours, un algorithme rapide et bien exécuté est largement utilisé.

Découvrez ces cours d’Intelligence Artificielle et d’Apprentissage automatique allant du Grand Apprentissage à la mise à niveau dans le domaine et maîtrisez l’élagage Alpha Bêta et d’autres algorithmes de ce type.

Pour en savoir plus

1. A * Algorithme de Recherche en Intelligence Artificielle (IA)
2. Algorithme d’Arbre de Décision Expliqué avec des Exemples
3. Meilleur Premier Algorithme de Recherche en IA | Concept, Implémentation, Avantages, Inconvénients
4. Qu’est-ce que l’Intelligence Artificielle? Comment fonctionne l’IA, ses types et son avenir ?