Intelligence Artificielle & Données
Intelligence Artificielle & Données
Les jeux, recherche avec horizon
(II)
Akka Zemmari
LaBRI, Université de Bordeaux
2022 - 2023
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
αβ
Élagage efficace de l’arbre
Élagage admissible
On veut trouver la même valeur d’évaluation finale du noeud
racine sans développer tout l’arbre. Il faut donc élaguer des parties
de l’arbre de recherche qui sont sans conséquence sur l’évaluation
d’un noeud.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
αβ
Élagage efficace de l’arbre
Élagage admissible
On veut trouver la même valeur d’évaluation finale du noeud
racine sans développer tout l’arbre. Il faut donc élaguer des parties
de l’arbre de recherche qui sont sans conséquence sur l’évaluation
d’un noeud.
Intuitivement
Soit un noeud n dans l’arbre de recherche, tel que Joueur peut
joueur en n.
S’il existe pour Joueur un choix m meilleur que n (soit à partir du
noeud parent de n, soit plus haut dans l’arbre), n ne sera jamais
effectivement joué.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
αβ
Elagage efficace de l’arbre II
Deux types de coupes : α et β
▶ α : le meilleur choix à un instant donné pour Max sur le
chemin développé. La valeur α est croissante
▶ β : le meilleur choix à un instant donné pour Min sur le
chemin développé. La valeur β est décroissante
Les coupes auront lieu dès que α est supérieur à β
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
Algorithme αβ
La première fonction : MaxValue
1: Fonction MaxValue(etat, α, β)) ▷ Évaluation niveau AMI
2: etat : Plateau de jeu courant
3: α : Meilleur évaluation courante pour AMI
4: β : Meilleur évaluation courante pour ENNEMI
5: Si EstFeuille(etat) Alors
6: Retourner evalue(etat) ▷ Évaluation heuristique
7: Fin Si
8: Pour Tout successeur s de etat Faire
9: α ← max(α,MinValue(s, α, β))
10: Si α ≥ β Alors ▷ Coupe β
11: Retourner β
12: Fin Si
13: Fin Pour
14: Retourner α . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
Algorithme αβ
La suite : MinValue
Remarque. - Pour évaluer un plateau, on appelle MaxValue avec :
plateau à évaluer, α = −∞ et β = +∞. Les variables α et β sont bien
locales, elles sont changées par l’intermédiaire des valeurs de retour.
1: Fonction MinValue(etat, α, β)) ▷ Évaluation niveau ENNEMI
2: etat : Plateau de jeu courant
3: α : Meilleur évaluation courante pour AMI
4: β : Meilleur évaluation courante pour ENNEMI
5: Si EstFeuille(etat) Alors
6: Retourner evalue(etat) ▷ Évaluation heuristique
7: Fin Si
8: Pour Tout successeur s de etat Faire
9: β ← min(β,MaxValue(s, α, β))
10: Si α ≥ β Alors ▷ Coupe α
11: Retourner α
12: Fin Si
13: Fin Pour
14: Retourner β
15: Fin Fonction
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
Algorithme αβ, Les deux fonctions ensembles
Fonction MaxValue(etat, α, β)) ▷ Niveau AMI
Si EstFeuille(etat) Alors
Retourner evalue(etat) ▷ Évaluation heuristique
Fin Si
Pour Tout successeur s de etat Faire
α ← max(α,MinValue(s, α, β))
Si α ≥ β Alors ▷ Coupe β
Retourner β
Fin Si
Fin Pour
Retourner α
Fin Fonction
Fonction MinValue(etat, α, β))
Si EstFeuille(etat) Alors
Retourner evalue(etat) ▷ Niveau ENNEMI
Fin Si
Pour Tout successeur s de etat Faire
β ← min(β,MaxValue(s, α, β))
Si α ≥ β Alors ▷ Coupe α
Retourner α
Fin Si
Fin Pour
Retourner β
Fin Fonction
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
Exemple d’arbre de jeu
. . . . . . . . . . . . . . . . . . . .
8 7 2 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2. .
1 . 2. 3
. . .
9. 7
. . .
2 16
. . . . .
6 .4 . . .
Intelligence Artificielle & Données
Élagage Alpha-Beta
Propriétés de αβ
Efficacité théorique
Si on suppose que les fils sont ordonnées idéalement (ou presque) :
▶ La recherche peut aller deux fois plus loin dans l’arbre
Améliorations possibles
▶ Comment couper encore plus lors de la recherche ?
▶ Recherche aspirante : α et β sont initialisés.
▶ Si la valeur finale est bien dans [α, β] la recherche reste
admissible
▶ ... D’autres encore à venir !
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
