Intelligence Artificielle
Algorithmes pour jeux
Emmanuel ADAM
Universit
e de Valenciennes et du Hainaut-Cambr
esis
UVHC/ISTV-LAMIH
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
1 / 21
Plan
Presentation des jeux
Algorithme MiniMax - NegaMax
Evaluation des coups en MiniMax
Exemple de MiniMax
Algorithme MiniMax
Algorithme NegaMax
Algorithme Alpha - Beta
Algorithme
Evaluation
Exemple sur Othello
Adaptation
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
2 / 21
Pr
esentation des jeux
Jeux `a deux joueurs
Caracteristiques des jeux
Les deux adversaires (O et H) jouent `a tour de role,
La situation globale du jeu est connue de chacun des joueurs,
La chance nintervient pas,
`a somme nulle
Les jeux sont dits `
nulle : les gains dun joueur
representent exactement les pertes de lautre joueur.
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
3 / 21
Algorithme MiniMax - NegaMax
Algorithme MiniMax - NegaMax
Algorithme MiniMax - NegaMax
Complexite : dimension de lespace detats
Morpion : facteur de branchement 3, nb de demi-coups = 9
au plus
dimension 39 = 19683
Echec : facteur de branchement 35, nb de demi-coups 30
dimension 3530 ! ! !
Necessite dune profondeur maximale de resolution
Necessite dune fonction devaluation pour estimer les noeuds
non feuilles
Chaque joueur joue le coup de gain maximal pour lui,
lui
en sachant que, et en prenant en compte que, ladversaire fera
de meme
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
4 / 21
Algorithme MiniMax - NegaMax
Evaluation des coups en MiniMax
Evaluation dans lalgorithme MiniMax - NegaMax
Evaluation
Strategie : profondeur limitee
Lheuristique h evalue la qualite dun noeud terminal (feuille
ou de profondeur maximale)
Comportement du joueur Ordi :
O parcourt en profondeur et note les noeuds terminaux de
niveau n dune branche
O transmet les notes au noeud n 1 et selectionne :
le noeud de valeur maximale si le trait appartient `
a O (etape
maximisante)
le noeud de valeur minimale si le trait appartient `
a H (etape
minimisante)
O transmet la note du noeud n 1 au noeud n 2 et note les
autres noeuds de niveau n 1
O poursuit sa notation pour pouvoir choisir parmi les noeuds
de niveau 1
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
5 / 21
Algorithme MiniMax - NegaMax
Exemple de MiniMax
Exemple de MiniMax 1/4
Evaluation
Arbre presentant lespace detats pour O.
O cherche `a maximiser ses gains
sachant que H cherchera `a lui les minimiser
noeud final
maximise
minimise
3
1
E. ADAM
University of Valenciennes
8
8
11
Intelligence Artificielle
UVHC/ISTV-LAMIH
6 / 21
Algorithme MiniMax - NegaMax
Exemple de MiniMax
Exemple de MiniMax 2/4
Evaluation
Arbre presentant lespace detats pour O.
O cherche `a maximiser ses gains
sachant que H cherchera `a lui les minimiser
noeud final
maximise
minimise
1
1
E. ADAM
3
5
University of Valenciennes
8
8
2
9
11
Intelligence Artificielle
8
2
1
1
UVHC/ISTV-LAMIH
7 / 21
Algorithme MiniMax - NegaMax
Exemple de MiniMax
Exemple de MiniMax 3/4
Evaluation
Arbre presentant lespace detats pour O.
O cherche `a maximiser ses gains
sachant que H cherchera `a lui les minimiser
noeud final
maximise
minimise
3
1
1
E. ADAM
2
8
3
University of Valenciennes
8
8
8
2
11
Intelligence Artificielle
8
2
1
1
UVHC/ISTV-LAMIH
8 / 21
Algorithme MiniMax - NegaMax
Exemple de MiniMax
Exemple de MiniMax 4/4
Evaluation
Arbre presentant lespace detats pour O.
O cherche `a maximiser ses gains
sachant que H cherchera `a lui les minimiser
noeud final
maximise
minimise
3
1
1
E. ADAM
8
3
University of Valenciennes
8
8
8
2
11
Intelligence Artificielle
8
2
1
1
UVHC/ISTV-LAMIH
9 / 21
Algorithme MiniMax - NegaMax
Algorithme MiniMax
Exemple dalgorithme MiniMax I
procedure Minimax(s : situation)
minimax; valSousArbre : entier ;
if estFeuille(s) then
retourner(h(s))
end if
if estMax(s) then
minimax
for all s 0 [Link] do
valSousArbre MiniMax(s)
if (minimax < valSousArbre) then
minimax valSousArbre
end if
end for
retourner(minimax)
end if
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
10 / 21
Algorithme MiniMax - NegaMax
Algorithme MiniMax
Exemple dalgorithme MiniMax II
if estMin(s) then
minimax +
for all s 0 [Link] do
valSousArbre MiniMax(s)
if (minimax > valSousArbre) then
minimax valSousArbre
end if
end for
retourner(minimax)
end if
end procedure
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
11 / 21
Algorithme MiniMax - NegaMax
Algorithme NegaMax
Exemple dalgorithme NegaMax I
LAlgorithme du NegaMax est simplifie :
O prend le gain minimal de H en prenant lopose de son NegaMax
et inversement
procedure NegaMax(s : situation)
minimax; valSousArbre : entier ;
if estFeuille(s) then
retourner(h(s))
end if
minimax
for all s 0 [Link] do
valSousArbre NegaMax(s)
if (minimax < valSousArbre) then
minimax valSousArbre
end if
end for
retourner(minimax)
end procedure
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
12 / 21
Algorithme Alpha - Beta
Algorithme Alpha - Beta
Algorithme Alpha - Beta
Probl`eme du MiniMax : Exploration compl`ete de larbre, de
lespace detats
Possibilite delaguer des branches en fonction des decouvertes
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
13 / 21
Algorithme Alpha - Beta
Alpha - Beta
et
On distingue deux seuils, appeles (pour les noeuds Min) et
(pour les noeuds Max) :
le seuil , pour un noeud Min s, est egal `a la plus grande
valeur (dej`a determinee) de tous les noeuds Max ancetres de
s. Si la valeur de s devient inferieure ou egale `a ,
lexploration de sa descendance peut etre arretee ;
le seuil , pour un noeud Max s, est egal `a la plus petite
valeur (dej`a determinee) de tous les noeuds Min ancetres de s.
Si la valeur de s devient superieure ou egale `a , lexploration
de sa descendance peut etre arretee.
et sont initialises reciproquement `a et +.
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
14 / 21
Algorithme Alpha - Beta
Algorithme
Exemple dalgorithme I
procedure AlphaBeta(s : situation, : entier, : entier)
minimax; valSousArbre : entier ;
if estFeuille(s) then retourner(h(s))
end if
if estMax(s) then
minimax
for all s 0 [Link] do
valSousArbre AlphaBeta(s, minimax, )
if (minimax < valSousArbre) then
minimax valSousArbre
end if
if (minimax ) then retourner(minimax)
end if
end for
retourner(minimax)
end if
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
15 / 21
Algorithme Alpha - Beta
Algorithme
Exemple dalgorithme II
if estMax(s) then
minimax
for all s 0 [Link] do
valSousArbre AlphaBeta(s, , minimax)
if (minimax > valSousArbre) then
minimax valSousArbre
end if
if (minimax ) then retourner(minimax)
end if
end for
retourner(minimax)
end if
end procedure
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
16 / 21
Algorithme Alpha - Beta
Algorithme
Exemple dalgorithme simplifie
Voici lalgorithme simplifie sur base du NegaMax :
procedure AlphaBetaNega(s : situation, : entier, : entier)
if estFeuille(s) then
retourner(h(s))
else
for all s 0 [Link] do
max(, ALPHABETANEGA(s 0 , , ))
if then
retourner()
end if
max(, )
end for
retourner()
end if
end procedure
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
17 / 21
Evaluation
Fonction devaluation
Heuristique
Dans le cadre des jeux, lheuristique depend souvent des
crit`eres lies :
au materiel (jetons, . . .) ;
`a la mobilite (nombre de coups possibles) ;
`a la position (des pi`eces, . . .).
h = pmateriel cmateriel + pmobilite cmobilite + pposition cposition
les ponderations peuvent evoluer en cours de partie
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
18 / 21
Exemple sur Othello
Exemple sur Othello
Othello
Grille de 64 cases dont 4 sont occupees : le jeu prend fin au
plus tard apr`es 60 coups.
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
19 / 21
Exemple sur Othello
Heuristique pour Othello
Heuristique pour Othello
Reprenons les 3 crit`eres definissant lheuristique pour un jeu,
ici pour une couleur :
le materiel = nombre de pions de la couleur,
la mobilite = nombre de cases jouables par la couleur,
la valeur dune position = somme des valeurs des cases
occupees par la couleur.
On utilise une grille evaluant la valeur dune case, adaptee au
jeu :
E. ADAM
500
-150
30
10
10
30
-150
500
University of Valenciennes
-150
-250
0
0
0
0
-250
-150
30
0
1
2
2
1
0
30
10
0
2
16
16
2
0
10
10
0
2
16
16
2
0
10
30
0
1
2
2
1
0
30
Intelligence Artificielle
-150
-250
0
0
0
0
-250
-150
500
-150
30
10
10
30
-150
500
UVHC/ISTV-LAMIH
20 / 21
Exemple sur Othello
Adaptation
Strategie pour Othello
Strategie
Evolution de limportance (du poids) des 3 crit`eres en cours
de jeu
debut : mobilite et position favorisees (pmobilite au maximum et
pposition important)
milieu de partie : importance de conquerir bords et points :
pposition au maximum
fin de partie : importance du nombre de jetons de la bonne
couleur : pmateriel au maximum
Evolution du facteur de branchement : plus faible vers la fin
donc possibilite daugmenter la profondeur de calcul
Possibilite devaluer le niveau du joueur adverse
E. ADAM
University of Valenciennes
Intelligence Artificielle
UVHC/ISTV-LAMIH
21 / 21
