27
Intelligence Artificielle et Jeux ECM 2A 2018-2019 Thierry Artières

Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Intelligence Artificielle et Jeux ECM 2A 2018-2019

Thierry Artières

Page 2: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Partie II Exploration avec

adversaire

2

Page 3: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 3

Jeux vs. problèmes de recherche ●  Adversaire “imprédictible" ⇒  Prévoir un coup pour chaque coup possible de l’adversaire

●  Limites de temps ⇒  Peu de chances de trouver le but, donc on approxime

Page 4: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 4

Arbre de jeu (2 joueurs, déterministe, tours)

Page 5: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 5

●  Décisions optimales ●  Elagage par α-β ●  Imparfait, mais temps réel possible

Page 6: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 6

Arbre de jeu (2 joueurs, déterministe, tours)

Page 7: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 7

Minimax

●  Jeu parfait pour des jeux déterministes ●  Idée: Choisir le coup avec la meilleure valeur de minimax

= meilleur situation atteignable contre le meilleur coup ●  E.g., jeu à 2 joueurs:

Page 8: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 8

Algorithm Minimax

Page 9: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 9

Propriétés de minimax ●  Complet? Oui (si l’arbre est fini) ●  Optimal? Oui (contre un adversaire optimal) ●  Complexité en temps ? O(bm) ●  Complexité en mémoire ? O(bm) (profondeur d’abord)

●  Echecs : b ≈ 35, m ≈100 pour des parties "raisonnables" à solution exacte non calculable

Page 10: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 10

Elagage α-β : exemple

Page 11: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 11

Elagage α-β : exemple

Page 12: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 12

Elagage α-β : exemple

Page 13: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 13

Elagage α-β : exemple

Page 14: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 14

Elagage α-β : exemple

Page 15: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Alpha-Beta Pruning Example

12 5 13 2

8

14

≥8

3 ≤2 ≤1

3

a is MAX’s best alternative here or aboveb is MIN’s best alternative here or above

IA et Jeux - ECM 2A - T. Artières 15

Page 16: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 16

Pourquoi α-β?

●  α est la valeur de la meilleure (i.e., + grande valeur) alternative trouvée pour le joueur max jusqu’ici le long du chemin jusqu’au noeud courant

●  β est la valeur de la meilleure (i.e., + petite valeur) alternative trouvée pour le joueur min jusqu’ici le long du chemin jusqu’au noeud courant

●  Si en explorant les fils d’un noeud max on remonte une valeur supérieure à β, on arrête l’exploration et on remonte cette valeur

●  Car le noeud calcule un max des valeurs remontées par ses fils

⇒ On sait qu’on remontera une valeur moins favorable que celle qui a été trouvée par ailleurs

⇒ On élimine la branche

Page 17: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Pourquoi α-β? Alpha-Beta Pruning Example

12 5 13 2

8

14

≥8

3 ≤2 ≤1

3

α is MAX’s best alternative here or aboveβ is MIN’s best alternative here or above

α=-∞β=+∞

α=-∞β=+∞

α=-∞β=+∞

α=-∞β=3

α=-∞β=3

α=-∞β=3

α=-∞β=3

α=8β=3

α=3β=+∞

α=3β=+∞

α=3β=+∞

α=3β=+∞

α=3β=2

α=3β=+∞

α=3β=14

α=3β=5

α=3β=1

IA et Jeux - ECM 2A - T. Artières 17

Page 18: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 18

L’algorithme α-β

Page 19: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 19

L’ algorithme α-β

Page 20: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 20

Propriétés de α-β ●  L’élagage n’affecte pas le résultat final

●  Un bon ordonnancment des coups améliore l’efficacité de l’élagage

●  Avec “un tri parfait," compléxité en temps = O(bm/2)

à permet de doubler la profondeur de recherche

●  Exemple de raisonnement sur la pertinence de certains calculs (sorte de métaraisonnement)

Page 21: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 21

Problème de ressources limitées

Supposons qu’on dispose de 100 secs, et qu’on explore 104 noeuds/sec à 106 noeuds par coup

Approche standard: ●  Test d’arrêt :

e.g., profondeur limite ●  Fonction d’évaluation

= estimation de l’utilité d’une position ●  Perte de garantie sur l‘optimalité

Resource Limits

! Cannot search to leaves! Depth-limited search

! Instead, search a limited depth of tree! Replace terminal utilities with an eval

function for non-terminal positions

! Guarantee of optimal play is gone! Example:

! Suppose we have 100 seconds, can explore 10K nodes / sec

! So can check 1M nodes per move! α-β reaches about depth 8 – decent

chess program? ? ? ?

-1 -2 4 9

4min min

max-2 4

Page 22: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 22

=> Fonctions d’évaluation

●  Pour les échecs, typiquement une combinaison linéaire de caractéristiques

Eval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s) ●  e.g., w1 = 9 avec

f1(s) = (Nombre de tours noires) – (nombre de tours blanches), etc.

Evaluation Functions! Function which scores non-terminals

! Ideal function: returns the utility of the position! In practice: typically weighted linear sum of features:

! e.g. f1(s) = (num white queens – num black queens), etc.

Page 23: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 23

Ressources limitéess Supposons qu’on dispose de 100 secs, et qu’on explore 104 noeuds/sec

à 106 noeuds par coup

Approche standard:

●  Test d’arrêt :

e.g., profondeur limite

●  Fonction d’évaluation

= Estimation de l’utilité d’une position

Page 24: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 24

Recherche avec test d’arrêt MinimaxCutoff est identique à MinimaxValue sauf que

1.  Final? est remplacé par Arrêt?

2.  Utilité est remplacé par Eval

En pratique:

bm = 106, b=35 à m=4

Exploration à un horizon de 4 coups => très mauvais joueur d’échecs

○  Horizon à 4 coups ≈ novice

○  Horizon à 8 coups ≈ typique PC

○  Horizon à 12 coups ≈ Deep Blue, Kasparov

Page 25: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

IA et Jeux - ECM 2A - T. Artières 25

Jeux déterministes en pratique ●  Dames: Chinook a gagné le championnat du monde en 1994. utilise une base

des coups idéaux pour toutes les positions avec moins de 8 pièces, 444 milliards de positions.

●  Echecs: Deep Blue a battu Garry Kasparov en 1997. Deep Blue évalue 200 million positions par seconde, et utilise des stratégies explorant jusqu’à 40 coups.

●  Othello: Les champions humains de jouent pas contre les ordinateurs, trop bons.

●  Go [2010]: Les champions humains de jouent pas contre les ordinateurs, trop mauvais. Au go, b > 300.

●  Go [2015] : AlphaGo (Google Deepmind) bat le champion du monde de Go

Page 26: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Jeux avec résultats d’actions non déterministes Stochastic Single-Player

! What if we don’t know what the result of an action will be? E.g.,! In solitaire, shuffle is unknown! In minesweeper, mine locations

10 4 5 7

max

average! Can do expectimax search

! Chance nodes, like actions except the environment controls the action chosen

! Max nodes as before! Chance nodes take average

(expectation) of value of children

IA et Jeux - ECM 2A - T. Artières 26

Cas d’un joueur aléatoire

-  Résultat d’une action non déterministe

⇒  Ajout de noeuds Chance pour lesquels on moyenne les scores des fils

⇒  Sinon algos identiques à Minimax

Page 27: Intelligence Artificielle et Jeux - LIS lab · chess program? ? ? ?-1 -2 4 9 4 min min max-2 4. IA et Jeux - ECM 2A - T. Artières 22 => Fonctions d’évaluation Pour les échecs,

Cas d’un jeu avec aléatoire (par ex. BackGammon)

⇒  Algo Expectminimax

⇒  L’environnement est un joueur (noeuds Chance) qui joue après chaque joueur et qui calcule l’espérance.

IA et Jeux - ECM 2A - T. Artières 27

Stochastic Two-Player

! E.g. backgammon! Expectiminimax (!)

! Environment is an extra player that moves after each agent

! Chance nodes take expectations, otherwise like minimax