Partie 1 : Fondement de l’ Intelligence Artificielle
Chapitre 3 : Résolution de problème en IA
Les stratégies de recherche dans les arbres de
jeux : MinMax et Alpha-Beta
1
Plan
❖ Introduction
❖ Arbre de jeu et arbre de recherche
❖ Notion de fonction d'évaluation
❖ Algorithme MinMax
❖ Algorithme Alpha-Beta
❖ Etat de l'art de quelques jeux : dames,
échecs, backgammon,Othello et Go
2
Introduction
Johan Huizinga, historien néerlandais :
❖ « Jouer est le propre de l'homme. »
Depuis le Moyen Age (tournois de gladiateurs)
❖ Jeux : activités comportant des règles précises.
❖ Vainqueur : celui qui a fait preuve d'intelligence
et d'habileté.
But ultime de l'IA
❖ Réaliser un ordinateur qui joue aussi bien, voire
mieux, qu'un humain.
3
Introduction à la théorie des jeux
La théorie des jeux :
● une branche des mathématiques
● technique de recherche opérationnelle
● s'intéresse aux situations dans lesquelles plusieurs
personnes ont à prendre des décisions dont dépend un
résultat qui les concerne.
Problème de jeu = présence de plusieurs centres de
décisions.
Domaines
● économique
● politique
● diplomatique
● militaire
…
4
Introduction à la théorie des jeux
Dans les problèmes de jeux, deux facteurs essentiels :
● Coopération
● Compétition
Trois classes de problèmes :
● Jeux de coopération à l'état pur :
● Étude de décisions concordantes
● Étude des conditions amenant à un intérêt général
● Jeux de compétition à l'état pur :
●duels = jeux à deux joueurs dont les intérêts sont strictement
opposés
● Partie la plus achevée de la théorie des jeux
● Jeux de compétition et de coopération :
● Plus proche des situations réelles
● Étude systématique plus difficile
5
Introduction à la théorie des jeux
Jeux à information complète :
Chaque joueur connaît lors de la prise de décision :
● ses possibilités d'action
● les possibilités d'action des autres joueurs
● les gains résultants de ces actions
● les motivations des autres joueurs
Jeux à information parfaite :
Jeux à mécanisme séquentiel, où chaque joueur a
connaissance en détail de toutes les actions
effectuées avant son choix.
6
Introduction à la théorie des jeux
Jeux à somme nulle :
Jeux où la somme « algébrique » des gains des joueurs est
constante. Ce que gagne l’un est nécessairement perdu par un
autre.
Jeux à somme non nulle :
Jeux dans lesquels certaines issues sont globalement plus
profitables pour tous, ou plus dommageables pour tous.
Jeux synchrones :
Les joueurs décident de leur coup simultanément, sans savoir ce
que les autres jouent.
Jeux asynchrones (alternatifs) :
Les joueurs se décident les uns après les autres, en disposant à
chaque fois de l’information sur le coup des adversaires.
7
Classification de certains jeux
Jeux asynchrones, à somme nulle:
→ Echecs, dames, dominos,
→ Jeux de cartes (Poker, rami, belotte, tarot...),
Jeux synchrones, à somme nulle:
→ Pierre-Papier-Ciseaux...
Tous les jeux ne sont pas adaptés à une étude par des
techniques d'IA.
Les jeux les plus étudiés : jeux à somme nulle, à
information complète et parfaite.
8
Exploration en situation d’adversaire
Soient 2 joueurs : MAX et MIN, jouant à tour de rôle.
MAX joue en 1er.
● Construction de l'espace d'états (arbre de jeu), avec
connaissance parfaite des états :
● Etat initial
● Etats finaux
●Opérateur déterministe de génération des états
successeurs : aucune incertitude sur les effets de
l'opérateur succ.
●Fonction eval, qui indique si un état terminal est gagnant,
perdant ou de résultat nul pour le joueur MAX.
● Choix du meilleur coup : algorithme MinMax ou Alpha-Beta
9
Définition d'un arbre de jeu MinMax
❖ Un arbre de jeu répertorie l'ensemble des coups réalisables
au cours d'une partie, en partant du noeud racine, qui
symbolise la configuration initiale, jusqu'aux noeuds
terminaux : les positions finales.
❖ Chaque noeud de l'arbre représente une position de jeu et
chaque arc un coup possible d'un joueur permettant de
passer d'une position à une autre.
❖ A chaque noeud terminal est associé un score ternaire :
●+1 si MAX gagne
● -1 si MIN gagne
● 0 s'il y a nulle
10
Exemple: jeu Tic Tac Toeobjectes
opérateurs (actions)
espace de recherche
11
Algorithme MinMax
Principe :
Maximiser la valeur d'utilité pour MAX avec l'hypothèse que
MIN joue systématiquement pour la minimiser.
Description :
● étendre l'arbre de jeu
● évaluer chaque noeud terminal
● propager ces valeurs aux noeuds non-terminaux :
● la valeur minimum aux noeuds du joueur MIN
● la valeur maximum aux noeuds du joueur MAX
12
Exemple d’Arbre de jeu MinMax
13
Propriété de l’algorithme MinMax
Complet : si l'arbre de jeu est fini.
Complexité en temps : O( bm )
b = facteur de branchement
m = profondeur de l'arbre total
Complexité en espace : O( bm )
Pour les échecs : b ≈ 35, m ≈ 100...
NB: L'algorithme MinMax est totalement
intraitable pour certains problèmes.
14
MinMax avec profondeur limitée
Principe :
● Etendre l'arbre de jeu jusqu'à une
profondeur N à partir du nœud courant
● Calculer la valeur de la fonction
d'évaluation pour chaque nœud feuille,
pas forcément terminal
● Propager ces valeurs jusqu'aux noeuds
non-terminaux
15
MinMax avec profondeur limitée
1) Etendre l'arbre de jeu à partir de l'état courant, où c'est à MAX de
jouer, jusqu'à une profondeur h
2) Calculer la fonction d'évaluation pour chacune des feuilles
3) Rétro-propager les valeurs des noeuds feuilles vers la racine de
l'arbre, de la manière suivante :
●Un noeud MAX recoit la valeur maximum de l'évaluation de ses
successeurs
●Un noeud MIN recoit la valeur minimum de l'évaluation de ses
successeurs
4)Choisir le mouvement vers le noeud MIN qui possède la valeur
rétro-propagée la plus élevée.
16
Exemple MinMax avec profondeur limitée
1 0 1 1 -1 1 2
-1 0 -1 0 -2
17
Elagage Alpha-Beta
Principe :
● Etendre l'arbre de jeu jusqu'à une profondeur h par une
recherche en profondeur
● Ne plus générer les successeurs d'un noeud dès qu'il est
évident que ce noeud ne sera pas choisi, compte tenu des
noeuds déjà examinés
● Chaque noeud MAX conserve la trace d'une ∞-valeur, qui
est la valeur de son meilleur successeur trouvé jusqu'à
présent
● Chaque noeud MIN conserve la trace d'une ß-valeur, qui
est la valeur de son pire successeur trouvé jusqu'à
présent
● Valeurs initiales : ∞ = -∞ et ß = +∞
18
Elagage Alpha-Beta
Deux règles :
● Interrompre la recherche d'un noeud
MAX si son ∞-valeur ≥ ß-valeur de
son nœud parent.
● Interrompre la recherche d'un noeud
MIN si sa ß-valeur ≤ ∞-valeur de
son nœud parent.
19
Etat de l'art :jeu d'échecs
Position initiale
Quelles sont les règles du jeu ?
20
Règles du jeu
Déplacement du pion
21
Règles du jeu
déplacement du cavalier déplacement du fou
22
Règles du jeu
déplacement de la tour déplacement de la reine
23
Règles du jeu
Echec au roi lorsqu'une pièce attaque le
roi ennemi.
Déplacement du Roi Trois manières de parer un échec :
● Bouger le roi attaqué
● Prendre la pièce attaquant le roi
●Intercaler une pièce entre le roi et
la pièce menaçante
24
Règles du jeu
… encore d’autres règles et contraintes
● Jeu qui a suscité le plus d'attention et d'efforts.
● Au début les progrès ont été très lents.
● 1970 : 1er programme à gagner le championnat ACM
d'échecs informatiques. Il utilisait un élagage a-b, un
répertoire d'ouvertures classiques et un répertoire de fins
de partie.
●1985 : Hitech (Berliner) se classe parmi les 800 meilleurs
joueurs du monde. Il est capable d'analyser plus de 10
Millions de positions par coup.
25
Techniques utilisées pour les échecs
Le milieu de partie
● Royaume de l'Alpha-Beta et de la fonction d'évaluation
● Fonction d'évaluation extrêmement complexe. Prend en compte :
● Valeurs des pièces :
Dame : 9
Tour : 5
Cavalier, fou : 3
Pion : 1
● Sécurité du roi
● Paire de fous
● Domination du centre
● Mobilité
● Cavaliers centralisés
● Tours placées sur des colonnes ouvertes
● Fous placés sur des diagonales ouvertes
● Qualité de la structure de pions
●...
26
Techniques utilisées pour les échecs
L’algorithme Alpha-Beta utilisé dans un programme
d'échecs incorpore quelques améliorations :
● Élagage de futilité
● Test prioritaire des coups meurtriers
● Retour à l'équilibre
● Heuristique du coup nul (Null Move Heuristic)
Fonction d'évaluation généralement de la forme :
eval( s ) = w1 f1( s ) + w2 f2( s )+ ... + wn fn( s ) avec :
● fi( s ) : caractéristique de la position
● wi : poids associé à une caractéristique
27
Inconvénients de Alpha-Beta
Premier défaut : manque total de stratégie
● Programmes utilisant ∞-ß ne sont pas guidés par un plan
●Jouent des positions totalement indépendantes
les unes des autres
● Pas de vision à long terme de la partie
Deuxième défaut : l'effet d'horizon (Berliner, 1974)
● Dû à la nécessité de fixer a priori une profondeur
●Programme ne peut percevoir les effets d'un coup au delà de
la profondeur choisie
●Tendance à repousser au delà de son
horizon une position défavorable
28
