Programme autodidactique 212 Collecteurs d`admission á longueur

Intelligence Artificielle et Robotique
Programmation des jeux de reflexion
Damien Pellier
[email protected]
http://www.math-info.univ-paris5.fr/~pellier/
PRES Paris Sorbonne Cit´
e
´
Ecole
D’Ing´
enieur de l’Universit´
e Paris Diderot
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
1 / 28
Sommaire
1
L’algorithme Minimax
2
Limiter les ressources
3
L’´elagage α-β
4
Jeux non-d´eterminsites
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
2 / 28
Programmation des jeux vs. r´esolution de probl`emes
L’adversaire est impr´evisible ⇒ la solution doit ˆetre contingente
Un temps limite est impos´e ⇒ quand il n’est pas possible d’atteindre le but il
faut ˆetre capable de l’approximer
Pistes ´etudi´ees :
1
2
3
algorithme pour joueur parfait (Von Neumann, 1944)
horizon fini, ´evaluation approaximative (Zuse, 1945 ; Shannon 1950)
´elagage pour r´eduire le coˆ
ut de recherche (McCarthy, 1956)
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
3 / 28
Programmation des jeux de r´eflexion
Les jeux de strat´
egies
Les diff´erents types de jeux
imformation
parfaite
d´
eterministe
´echec, reversi, go,
morpion
imparfaite
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
hasard
backgammon,
monopoly
bridge,
pocker,
scrabble
4 / 28
L’arbre de recherche MiniMax
Arbre de jeux du morpion
MAX(X)
X
X
X
X
MIN(O)
X
X
X
X O
X
O
X O X
X O
X
X O
X
X O X
O X
O
-1
X O X
OO X
X X O
0
X O X
X
X OO
+1
MAX(X)
MIN(O)
Terminal
Utilité
Damien Pellier (PRES Paris Sorbonne Cit´
e)
X
X
X
O
Intelligence Artificielle et Robotique
5 / 28
L’algorithme recherche MiniMax
Donne le coup parfait pour un jeu d´eterministe `a information parfaite
Id´ee : choisir le meilleur coup vers la position avec la meilleure valeur
minimax = meilleur valeur possible contre le meilleur jeu de l’adversaire
Exemple d’un jeu `a deux coups :
MAX
3
MIN
3
A3
A2
A1
3
2
2
A11 A12 A13
A21 A22 A23
A31 A32 A33
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
2
4
Intelligence Artificielle et Robotique
6
14
5
2
6 / 28
L’algorithme MiniMax
Algorithme
funtion Minimax-Decision(game) returns an operator
foreach op in Operators[game] do
Value[op] ← Minimax-Value(Apply(op, game), game)
end
return the op with the highest Value[op]
end
funtion Minimax-Value(state, game) returns an utility value
if Terminal-Test[game](state) then
return Utility[game](state)
else if Max is to move in state then
return the highest Minimax-Value of Successors(state)
else
return the lowest Minimax-Value of Successors(state)
end
end
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
7 / 28
L’algorithme MiniMax
Propri´
et´
e de MiniMax
Minimax s’arrˆete toujours si l’arbre est fini
Optimal, si l’adversaire est optimal
Si b est le nombre de coups possibles par situation et m la profondeur
maximale de l’arbre, minimax a une complexit´e en
I
I
temps de O(b m )
en espace O(bm)
Pour les ´echecs par exemple : b ≈ 35, m ≈ 100 ⇒ solution exacte impossible
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
8 / 28
L’algorithme MiniMax
Ressources limit´
ees
Par exemple, on a 100 secondes et on peut explorer 104 nœuds par secondes.
Donc, on peut regarder 106 nœuds par coup.
Approches standard :
I
I
Test d’arrˆet (cutoff) : par exemple limiter la profondeur
Fonction d’´evaluation = valeur estim´ee d’une position
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
9 / 28
L’algorithme MiniMax
Fonction d’´
evaluation
Noir joue
Blanc joue
(blanc en meilleur position)
(noir gagne)
Aux ´echecs on choisit par exemple une somme lin´eaire pond´er´ee de
caract´eristiques.
Eval(s) = w1 f1 (s) + w2 f2 (s) + . . . + wn fn (s)
e.g., w1 = 9 et f1 = (le nombre de reines blanches) - (le nombre de reines noires),
etc.
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
10 / 28
L’algorithme MiniMax
L’effet horizon
Dans cette position Noir peut mettre le roi blanc en ´echec un certain nombre de
fois mais le pion blanc va se transformer in´evitablement en reine. On en s’aper¸coit
tr`es tard.
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
11 / 28
L’algorithme MiniMax
Arrˆ
eter la recherche
On peut facilement modifier l’algorithme minimax en ajoutant un test d’arrˆet
(remplacer Terminal-Test par Cutoff-Test et en rempla¸cant Utility
par Eval.
En pratique : probl`emes de performances, e.g., b m = 106 et b = 35. Donc
m = 4.
I
Aux ´echecs on ne pourrait que regarder 4 demi-coups en avance
F
F
F
Un humain normal ≈ 4 coups d’avance
Un ordinateur classique et un expert humain ≈ 8 coups d’avance
Deep Blue, Kasparov ≈ 12 coups d’avance
´
Id´ee : Elaguer
des branches inutiles
⇒ algorithme α-β
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
12 / 28
L’algorithme α-β
Exemple ´
elagage
3
MAX
3
MIN
3
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
Intelligence Artificielle et Robotique
13 / 28
L’algorithme α-β
Exemple ´
elagage
3
MAX
3
MIN
2
X
3
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
X
2
Intelligence Artificielle et Robotique
13 / 28
L’algorithme α-β
Exemple ´
elagage
3
MAX
3
MIN
2
X
3
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
14
X
2
Intelligence Artificielle et Robotique
14
13 / 28
L’algorithme α-β
Exemple ´
elagage
3
MAX
3
MIN
2
X
3
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
14
5
X
2
Intelligence Artificielle et Robotique
14
5
2
13 / 28
L’algorithme α-β
Exemple ´
elagage
3
MAX
3
MIN
2
X
3
12
Damien Pellier (PRES Paris Sorbonne Cit´
e)
8
14
52
X
2
Intelligence Artificielle et Robotique
14
5
2
13 / 28
L’algorithme α-β
Propri´
et´
es
L’´elagage n’affecte pas le r´esultat final
Un bon choix am´eliore l’efficacit´e de l’´elagage
Avec un choix parfait la complexit´e en temps est O(b m/2 )
⇒ double la profondeur de recherche par rapport `
a Minimax
⇒ peut facilement atteindre des profondeurs de l’ordre de 8 coups d’avance aux
´echecs
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
14 / 28
L’algorithme α-β
Pourquoi ce nom ?
α est la meilleure valeur (la plus
grande) pour MAX trouv´ee
jusqu’`a pr´esent en dehors du
chemin actuel
MAX
MIN
MAX
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Si V est pire que α MAX va
l’´eviter ⇒ ´elaguer la branche
V
D´efinir β d’une mani`ere similaire
pour MIN : β est la meilleur
valeur (la plus petite) pour MIN
jusqu’`a pr´esent
Intelligence Artificielle et Robotique
15 / 28
L’algorithme α-β
L’algorithme Max-Value
Algorithme
funtion Max-Value(state, game, α, β) returns the minimax value of state
input: state, current state in game
game, game description
α, the best score for Max along the path to state
β, the best score for Min along the path to state
if Cutoff-Test(state) then return Eval(state)
foreach s in Successors(state) do
α ← Max(α,Min-Value(s, game, α, β))
if α ≥ β then return β
end
return α
end
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
16 / 28
L’algorithme α-β
L’algorithme Min-Value
Algorithme
funtion Min-Value(state, game, α, β) returns the minimax value of state
input: state, current state in game
game, game description
α, the best score for Max along the path to state
β, the best score for Min along the path to state
if Cutoff-Test(state) then return Eval(state)
foreach s in Successors(state) do
β ← Min(β,Min-Value(s, game, α, β))
if β ≥ α then return α
end
return β
end
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
17 / 28
L’algorithme α-β
Valeur exacte des nœuds n’est pas importante
MAX
1
MIN
1
2
2
2
1
4
1
20
20
20
40
Seulement l’ordre est important
Le comportement est pr´eserv´e pour chaque transformation monotone de la
fonction Eval
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
18 / 28
L’algorithme α-β
Remarques
L’ordre dans lequel on visite les fils est important
Si on trouve rapidement une bonne valeur, on ´elague plus de nœuds
On peut trier les fils par leur utilit´e
Il y a d’autres am´eliorations
√
Au mieux, on visite n nœuds au lieu de n = b m pour minimax
Aux ´echecs on utilise au d´ebut du jeu des bases de donn´ees d’ouverture, au
milieu α-β et `a la fin des algorithmes sp´eciaux
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
19 / 28
L’algorithme SSS*
D´efinition : Une strat´egie (compl`ete) pour le joueur max, ´etant donn´e un
arbre de jeux A, est un sous-arbre, qui
I
I
I
contient la racine de A
dont chaque nœud Max a exactement un fils
dont chaque nœud Min a tous ses fils
Une strat´egie partielle pour le joueur max, ´etant donn´e un arbre de jeux A,
est un sous-arbre de A, qui
I
I
contient sa racine
dont chaque nœud Max a au plus un fils
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
20 / 28
L’algorithme SSS*
Une strat´egie partielle S repr´esente implicitement toutes les strat´egies
compl`etes CS auxquelles on aboutie en d´eveloppant S
La valeur d’une strat´egie est le minimum des valeurs des feuilles
La valeur d’une strat´egie partielle S donne une borne sup´erieur pour toutes
ses strat´egies compl`etes CS
Id´ee : On recherche a compl´eter les strat´egies partielles suivant leur valeur
jusqu’`a pr´esent
Une fois quand a trouv´e la strat´egie optimale compl`ete `a partir d’un nœud x
on ne consid`ere plus les autres de x
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
21 / 28
L’algorithme SSS*
Exemple
MAX
a
b
MIN
MAX
MAX
c
f
e
g
d
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
9
3
7
2
9
3
3
2
9
2
3
8
10
2
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
22 / 28
L’algorithme SSS*
Exemple
MAX
a
b
MIN
MAX
MAX
c
f
e
g
d
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
9
3
7
2
9
3
3
2
9
2
3
8
10
2
Trois strat´egies partielles
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
22 / 28
L’algorithme SSS*
Exemple
MAX
a
b
MIN
MAX
MAX
c
f
e
g
d
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
9
3
7
2
9
3
3
2
9
2
3
8
10
2
On a trouv´e une start´egie compl`ete (par construction la meilleur)
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
22 / 28
L’algorithme SSS*
Exemple
MAX
a
b
MIN
MAX
MAX
c
f
e
g
d
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
9
3
7
2
9
3
3
2
9
2
3
8
10
2
On d´eveloppe la meilleure strat´egie, puis on voit que la troisi`eme pourrait ˆetre
meilleure
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
22 / 28
L’algorithme SSS*
D´
etails de l’algorithme
Successors(x) donne pour tout nœud x la liste des successeurs
Eval(x) donne l’´evaluation d’un noeud x
Max(x) est vrai si et seulement si x est un nœud max
On utilise une pile P pour mettre les nœuds encore `a trait´es
Ordonnate(P, hx, f , hi) met hx, f , hi dans la pile, ordonn´ee en ordre
descendant par les valeurs h. Si dans P il y a d´ej`a un ´el´ement avec la mˆeme
valeur h on range hx, f , hi avant.
Il y a deux types de nœuds :
I
I
f : ferm´e (la strat´egie optimale pour lui est connu)
v : vivant
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
23 / 28
L’algorithme SSS*
L’algorithme
Algorithme
funtion Valeur(x0 : node) returns un r´
eel
P ← (hx0 , v , ∞i)
repeat
hx, s, hi ← First(P) ; P ← Rest(P) ; x1 , x2 , . . . , xm ← S(x)
if s = v then
if m = 0 then Ordonnate(P, hx, f ,Min(h,Eval(x))i)
else
if Max(x) then Stack(P, hx1 , v , hi, . . . , hxm , v , hi)
else Stack(P, hx1 , v , hi)
else
if Max(x) then
if x has a child y then Stack(P, hy , v , hi)
else z ← Parent(x) ; Stack(P, hz, f , hi)
else z ← Parent(x) ; Stack(P, hz, f , hi) ; Remove-All-Child(z)
until P = hx, f , hi
return h
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
24 / 28
L’algorithme SSS*
Traces
ha, v , ∞i
hb, v , ∞ihc, v , ∞ihd, v , ∞i
he, v , ∞ihc, v , ∞ihd, v , ∞i
hl, v , ∞ihm, v , ∞ihc, v , ∞ihd, v , ∞i
hm, v , ∞ihc, v , ∞ihc, v , ∞ihl, f , 9i
hc, v , ∞ihd, v , ∞ihl, f , ∞ihm, f , 3i
hh, v , ∞ihd, v , ∞ihl, f , ∞ihm, f , 3i
hr , v , ∞ihs, v , ∞ihd, v , ∞ihl, f , 9ihm, f , 3i
hs, v , ∞ihd, v , ∞ihl, f , 9ihr , f , 3ihm, f , 3i
hd, v , ∞ihl, f , 9ihr , f , 3ihm, f , 3ihs, f , 2i
hj, v , ∞ihl, f , 9ihr , f , 3ihm, f , 3ihs, f , 2i
hv , v , ∞ihw , v , ∞ihl, f , 9ihr , f , 3ihm, f , 3ihs, f , 2i
hw , v , ∞ihl, f , 9ihv , f , 3ihr , f , 3ihm, f , 3ihs, f , 2i
hl, f , 9ihw , f , 8ihv , f , 3ihr , f , 3ihm, f , 3ihs, f , 2i
etc.
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
25 / 28
Jeux non-d´eterministes
Dans le Backgammon par exemple, le lancer des d´es d´etermine les coups
corrects. Exemple simplifi´e avec lancer d’une pi`ece de monnaie :
MAX
CHANCE
3
0.5
2
0.5
0.5
2
MIN
Damien Pellier (PRES Paris Sorbonne Cit´
e)
-1
4
4
7
0.5
0
4
6
Intelligence Artificielle et Robotique
-2
0
5
-2
26 / 28
Algorithmes pour les jeux non-d´eterministes
Expectimax donne coup parfait comme Minimax
On doit consid´erer les nœuds CHANCE
On doit ajouter dans l’algorithme :
if state is a chance node then return average of Expectimax-Value of
Successors(state)
L’algorithme α-β peut ˆetre adapt´e, si Eval est born´ee.
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
27 / 28
Valeur exacte des nœuds est importante
MAX
A1
CHANCE
A1
A2
2.1
0.9
1.3
2
MIN
2
0.9
0.1
3
2
3
0.1
1
3
1
0.9
4
1
A2
21
4
40.9
20
4
20
0.9
0.1
30
20
30
0.1
1
30
1
40
1
40
40
Le comportement est pr´eserv´e seulement pour chaque transformation positive
et lin´eaire de EVAL
Eval doit ˆetre proportionnelle au gain attendu
Damien Pellier (PRES Paris Sorbonne Cit´
e)
Intelligence Artificielle et Robotique
28 / 28

Download Report