# Élagage alpha-bêta

Un article de Wikipédia, l'encyclopédie libre.
Élagage alpha-bêta

En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax.

L'algorithme minimax effectue en effet une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre est généralement suffisante : lors de l'exploration, il n'est pas nécessaire d'examiner les sous-arbres qui conduisent à des configurations dont la valeur ne contribuera pas au calcul du gain à la racine de l'arbre. L’élagage αβ nous permet de réaliser ceci. Plus simplement, l'élagage αβ évite d'évaluer des nœuds dont on est sûr que leur qualité sera inférieure à un nœud déjà évalué, il permet donc d'optimiser grandement l'algorithme minimax sans en modifier le résultat.

Il est très utilisé dans le cas de jeux à 2 joueurs, comme les échecs ou les dames[réf. souhaitée].

## Principe[modifier | modifier le code]

On prend α et β appartenant au domaine d’arrivée de la fonction d’évaluation tel que α < β. On définit la fonction AlphaBeta ainsi :

- AlphaBeta(P, α, β) = g(P) si P est une feuille de l'arbre et g la fonction d'évaluation du nœud
- AlphaBeta(P, α, β) = min(β, max(-AlphaBeta( O i {\displaystyle O_{i}} , -β, -α))) où les O i {\displaystyle O_{i}} sont les enfants du nœud P

On appelle fenêtre αβ le couple (α, β) où α et β sont les deux paramètres d’appel de la fonction. Les nœuds élagués sont ceux qui seraient appelés avec une fenêtre tel que α ≥ β. Il existe 3 types de nœuds ne pouvant donc pas être élagués :

- Nœud de type 1 : fenêtre d’appel : (-∞, +∞)
- Nœud de type 2 : fenêtre d’appel : (-∞, β) avec β ≠ +∞
- Nœud de type 3 : fenêtre d’appel : (α, +∞) avec α ≠ -∞

Le schéma ci-dessus présente les deux types de coupures possibles. Les nœuds Min sont représentés par un rond bleu et les nœuds Max par un carré gris. Rappel : les nœuds Min prennent la valeur minimum de leurs enfants (et respectivement maximum pour les nœuds Max).

Coupure Alpha : le premier enfant du nœud Min V vaut 4 donc V vaudra au plus 4. Le nœud Max U prendra donc la valeur 5 (maximum entre 5 et une valeur inférieure ou égale à 4).

Coupure Bêta : le premier enfant du nœud Max V vaut 4 donc V vaudra au minimum 4. Le nœud Min U prendra donc la valeur 3 (minimum entre 3 et une valeur supérieure ou égale à 4).

## Pseudocode[modifier | modifier le code]

Ci-dessous le pseudocode de l'algorithme alpha-bêta : α est initialisé à -∞ et β à +∞

    fonction alphabeta(nœud, α, β) /* α est toujours inférieur à β */
       si nœud est une feuille alors
           retourner la valeur de nœud
       sinon si nœud est de type Min alors
               v = +∞
               pour tout fils de nœud faire
                   v = min(v, alphabeta(fils, α, β))
                   si α ≥ v alors  /* coupure alpha */
                       retourner v
                   β = Min(β, v)
        sinon
               v = -∞
               pour tout fils de nœud faire
                   v = max(v, alphabeta(fils, α, β))
                   si v ≥ β alors /* coupure beta */
                       retourner v
                   α = Max(α, v)
        retourner v

De la même manière que l'algorithme minimax peut être remplacé par NegaMax, on simplifie Alpha-Beta. Cela donne l’algorithme suivant :

    fonction alphabeta(nœud, A, B) /* A < B */
       si nœud est une feuille alors
           retourner la valeur de nœud
       sinon
           meilleur = –∞
           pour tout fils de nœud faire
               v = -alphabeta(fils,-B,-A)
               si v > meilleur alors
                   meilleur = v
                   si meilleur > A alors
                       A = meilleur
                       si A ≥ B alors
                           retourner meilleur
           retourner meilleur

## Exemple[modifier | modifier le code]

Nous allons illustrer l’algorithme sur l’arbre ci-dessous déjà étiqueté avec les valeurs d’un minimax. Le résultat obtenu est le schéma ci-dessous.

Minimax avec élagage alpha-bêta

Plusieurs coupures ont pu être réalisées. De gauche à droite :

1. Le nœud MIN vient de mettre à jour sa valeur courante à 4. Celle-ci, qui ne peut que baisser, est déjà inférieure à α=5, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant la valeur la plus grande possible, ne la choisira donc de toute façon pas.
2. Le nœud MIN vient de mettre à jour sa valeur courante à 6. Celle-ci, qui ne peut que baisser, est déjà égale à α=6, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant une valeur supérieure, il ne mettra de toute façon pas à jour sa valeur que ce nœud vaille 6 ou moins.
3. Le nœud MIN vient de mettre à jour sa valeur courante à 5. Celle-ci, qui ne peut que baisser, est déjà inférieure à α=6, la valeur actuelle du nœud MAX précédent. Celui-ci cherchant la valeur la plus grande possible, ne la choisira donc de toute façon pas.

## Améliorations possibles[modifier | modifier le code]

La plupart des améliorations d'alpha-bêta sont destinées à augmenter le nombre de coupes pour augmenter les nœuds qui ne sont pas examinés. Cela s'obtient grâce à des heuristiques comme l'exploration en premier des coups qui ont permis d'effectuer des coupes dans des nœuds du même niveau (killer move) ; d'autres améliorations permettent de rétrécir l'intervalle de départ entre les valeurs alpha et bêta utilisées dans le nœud racine et débouchent sur des améliorations comme Negascout ou MTD-F.

On peut trier les positions à tester à chaque profondeur testée, pour améliorer le temps ou la profondeur totale de calcul à chaque demi-coup, selon la limitation en profondeur totale ou en temps de calcul à chaque demi-coup.

## Applications de la technique[modifier | modifier le code]

Alpha-béta est largement utilisé par les programmes qui jouent aux jeux de réflexion.

## Annexes[modifier | modifier le code]

### Bibliographie[modifier | modifier le code]

- A. Aho, J. Hopcroft, J. Ullman, Structures de données et algorithmes, Paris, InterEditions, 1987, 450 p. (ISBN 2-7296-0194-5), « Conceptions et stratégies algorithmiques »

### Voir aussi[modifier | modifier le code]

- Séparation et évaluation

### Notes[modifier | modifier le code]

### Lien externe[modifier | modifier le code]

- Tristan Cazenave, « Des optimisations de l'Alpha-Beta », Actes du colloque de Berder,‎ 2000 (lire en ligne [archive] [PDF])

[masquer] v · m Théorie des jeux
Définitions | Jeu sous forme normale · Extensive-form game (en) · Escalation of commitment (en) · Graphical game (en) · Jeu coopératif · Succinct game (en) · Information set (en) · Hierarchy of beliefs (en) · Préférence
Équilibre économique (concepts) | Équilibre de Nash · Équilibre parfait en sous-jeux · Mertens-stable equilibrium (en) · Bayesian Nash equilibrium (en) · Jeu bayésien · Trembling hand (en) · Proper equilibrium (en) · Epsilon-equilibrium (en) · Équilibre corrélé · Équilibre séquentiel · Quasi-perfect equilibrium (en) · Stratégie évolutivement stable · Risk dominance (en) · Core (en) · Valeur de Shapley · Optimum de Pareto · Gibbs equilibrium (en) · Quantal response equilibrium (en) · Self-confirming equilibrium (en) · Strong Nash equilibrium (en) · Markov perfect equilibrium (en)
Stratégies (en) | Dominance stratégique · Pure strategy (en) · Coopération-réciprocité-pardon · Grim trigger (en) · Collusion · Raisonnement rétrograde · Forward induction (en) · Markov strategy (en)
Classes de jeux | Symmetric game (en) · Perfect information (en) · Simultaneous game (en) · Sequential game (en) · Repeated game (en) · Signaling game (en) · Screening game (en) · Conversation libre · Jeu à somme nulle · Théorie des mécanismes d'incitation · Bargaining problem (en) · Stochastic game (en) · n-player game (en) · Large Poisson game (en) · Nontransitive game (en) · Global game (en) · Strictly determined game (en) · Jeu de potentiel
Jeux | Dilemme du prisonnier · Optional prisoner's dilemma (en) · Traveler's dilemma (en) · Coordination game (en) · Chicken (en) · Jeu du mille-pattes · Volunteer's dilemma (en) · Dollar auction (en) · Jeu de la guerre des sexes · Stag hunt (en) · Matching pennies (en) · Jeu de l'ultimatum · Pierre-papier-ciseaux · Jeu du pirate · Jeu du dictateur · Public goods game (en) · Blotto game (en) · War of attrition (en) · Problème du bar d'El Farol · Partage équitable · Fair cake-cutting (en) · Cournot game · Deadlock (en) · Diner's dilemma (en) · Guess 2/3 of the average (en) · Kuhn poker (en) · Nash bargaining game (en) · Prisoners and hats puzzle (en) · Trust game (en) · Princess and Monster game (en) · Monty Hall problem (en) · Rendezvous problem (en)
Theorèmes | Algorithme minimax · Équilibre de Nash · Purification theorem (en) · Folk theorem (en) · Revelation principle (en) · Théorème d'impossibilité d'Arrow
Personnalités | Albert W. Tucker · Amos Tversky · Ariel Rubinstein · Daniel Kahneman · David K. Levine (en) · David M. Kreps · Donald B. Gillies (en) · Drew Fudenberg (en) · Eric Maskin · Harold W. Kuhn · Herbert Simon · Hervé Moulin · Jean Tirole · Jean-François Mertens (en) · John Harsanyi · John Maynard Smith · Antoine-Augustin Cournot · John Nash · John von Neumann · Kenneth Arrow · Kenneth Binmore · Leonid Hurwicz · Lloyd Shapley · Melvin Dresher (en) · Merrill M. Flood (en) · Oskar Morgenstern · Paul Milgrom · Peyton Young (en) · Reinhard Selten · Robert Axelrod · Robert Aumann · Robert B. Wilson (en) · Roger Myerson · Samuel Bowles (en) · Thomas Schelling · William Vickrey
Voir aussi | All-pay auction (en) · Élagage alpha-bêta · Bertrand paradox (en) · Rationalité limitée · Théorie des jeux combinatoires · Confrontation analysis (en) · Coopétition · List of game theorists (en) · List of games in game theory (en) · No-win situation (en) · Topological game (en) · Tragédie des biens communs · Tyrannie des petites décisions

- Portail de l'informatique théorique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Élagage_alpha-bêta&oldid=145941836 ».
Catégories :

- Théorie des jeux
- Algorithme d'optimisation
- Intelligence artificielle

[+]
Catégories cachées :

- Article à référence souhaitée
- Article contenant un appel à traduction en anglais
- Portail:Informatique théorique/Articles liés
- Portail:Informatique/Articles liés
- Projet:Mathématiques/Articles
- Bon article en allemand