Algorithmes de jeux

III. REPRÉSENTATION ET RÉSOLUTION DE PROBLÈMES

LES ALGORITHMES

DE JEUX

INTELLIGENCE ARTIFICIELLE ET SYSTÈMES EXPERTS

Mohamed Heny SELMI [email protected]

TYPES DE JEUX

Les jeux simples où une analyse exhaustive est possible : Tic-Tac-Toe, Reversi, Moulin, Les Allumettes,

ESPRIT 2012-2013

Mohamed Heny SELMI ©

TYPES DE JEUX

Des jeux plus complexes : dames, échecs, Othello, Awalé…

des algorithmes spécifiques des méthodes heuristiques de recherche

ESPRIT 2012-2013


TYPES DE JEUX

Des jeux à information partielle : Bridge, Poker, Belote, Dominos…

Des raisonnements de type probabiliste

ESPRIT 2012-2013


LES MÉTHODES DE RECHERCHES DES JEUX

► Les jeux à deux joueurs et à informations complètes utilisent des techniques semblables à la représentation par graphe d’états :

On utilise des systèmes de production pour générer les états

Les nœuds d’un arbre de jeux : les configurations du damier

Les branches : le passage d’une situation de jeu à un autre

ESPRIT 2012-2013


► Un arbre du jeu représente le déplacement de deux adversaires

► Un arbre d’espace de recherche représente le déplacement d’un agent de résolution de problème (ou planificateur)

NÉCESSITÉ D’UN ALGORITHME DE RECHERCHE

ESPRIT 2012-2013


Du fait de la présence de deux joueurs ayant des objectifs antagonistes, la recherche dans ces arbres ne peut se faire en utilisant des algorithmes de recherche de type A*

Contrairement aux systèmes de résolution de problèmes, le planificateur ne dispose pas de la maitrise complète de l’enchainement des opérateurs, puisque des décisions extérieures à lui sont prises par l’adversaire

Il est impossible, dans la plupart des jeux de générer l’ensemble de tout l’espace d’état

Un arbre de jeu pour les dames, plus difficiles que le Morpion, moins difficile que

l’échec, est estimé à 1040 nœuds.

Si ces nœuds étaient produits à une cadence de 3 milliards/s alors la construction

entière prendrait près de 1021 siècles

LES STRATÉGIES SPÉCIFIQUES

ESPRIT 2012-2013


Il n’existe aucun moyen infaillible d’ordonner les éléments d’un ensemble de situations possibles sur un damier

aucune formule permettant d’ordonner ne peut être calculée

Si ce moyen existait on pourrait choisir le coup conduisant à la meilleur situation possible à l’issue d’un coup unique

On peut utiliser un algorithme de recherche

La décompte des pièces peut être un facteur de choix pour le jeu de dames, mais cette mesure donne en général de mauvais résultats

Une autre stratégie est nécessaire !

► A partir d’une position (état) donnée, on génère l’ensemble des positions qu’on peut atteindre en jouant un coup (niv. de profondeur1)

► A partir de chacune des positions de niveau1, on génère l’ensemble des positions que l’adversaire peut atteindre (niv. de profondeur2)

► On peut recommencer l’opération aussi longtemps que le permet la puissance de calcul (générer niveaux 3,4,5…n)

► L’arbre complet représente toutes les possibilités du jeu. On construit ainsi l’arbre de l’EE du Pb

► L’arbre du graphe d’états du Pb représente une partie possible du jeu

LES STRATÉGIES SPÉCIFIQUES

ESPRIT 2012-2013


Il n’existe aucun moyen infaillible d’ordonner les éléments d’un ensemble de situations possibles sur un damier

aucune formule permettant d’ordonner ne peut être calculée

Si ce moyen existait on pourrait choisir le coup conduisant à la meilleur situation possible à l’issue d’un coup unique

On peut utiliser un algorithme de recherche

La décompte des pièces peut être un facteur de choix pour le jeu de dames, mais cette mesure donne en général de mauvais résultats

Une autre stratégie est nécessaire !

► L’analyse d’une situation ne soit entreprise qu’après développement du jeu sur plusieurs niveaux de coups et de réponses

► Si le développement se termine à une profondeur raisonnable, on peut comparer les situations terminales et déduire une option pour le coup suivant

► On doit limiter l’exploration à une profondeur maximale de résolution

► À cette profondeur on attribue aux (pseudo) feuilles une valeur correspondante à

l’estimation de la position à travers une fonction d’évaluation

MINMAX

ESPRIT 2012-2013


PRINCIPE

i. Cette estimation peut se faire du point de vue d’un joueur fixe

ii. il doit à partir du niveau0 (racine)

iii. jouer le coup de niveau1 qui lui garantit le gain maximal contre toute défense de

son adversaire

iv. il suppose que son adversaire utilise aussi une stratégie optimale; jouer le coup de

niveau2 qui minimise son gain (le mettre dans la + grande difficulté)

v. jouer le coup de niveau3 qui lui garantit le gain maximal, etc.

ESPRIT 2012-2013


fonction d’évaluation

PROPRIÉTÉS

Chaque joueur a une information explicite sur la position de son adversaire (jeu de dames, jeu d’échec, allumettes, etc.) y comprisses choix et mouvements possibles

2 joueurs effectuent alternativement un déplacement ou une opération, aucun élément n’est laissé au hasard

A chaque tour, les règles de jeu définissent:

Quels mouvements sont acceptés

Effets de chaque mouvement possible

Choisir parmi les fils, le « meilleur » coup à jouer, c.-à-d. anticiper sur des situations(pas de calcul à court terme, calcul des coups en avant)

Le joueur commence par une configuration initiale de pions

Finir par une victoire, une défaite ou un abandon (états finaux)

Le nœud racine est l’état initial au quel c’est au tour du premier joueur d’effectuer un déplacement, ses successeurs sont les états atteints par ce joueur, leurs successeurs sont les états résultants des réponses possibles de l’adversaire, etc.

Chaque chemin de la racine au nœud terminal représente une partie complète et possible du jeu

ESPRIT 2012-2013


STRATÉGIE DE RECHERCHE

ESPRIT 2012-2013


la stratégie MinMax : exploration en profondeur limitée

2 joueurs O(ordinateur) et H(adversaire) : illustration de la def. de l’IA

Une fonction h évalue la qualité d’une pos. terminale du pt de vue O

A chaque niveau où O a la main, il choisira le coup de valeur maximale pour lui

(on parle de joueur ou nœud Max)

A chaque niveau où H a la main, O suppose que son adversaire H essaie de le

mettre dans la plus grande difficulté et choisit donc le coup de valeur minimale

pour O; minimiser son gain, (joueur ou nœud Min)

EXEMPLE

Les feuilles indiquent au processus MIN qu’il peut envisager des scores de 2 à 1

Connaissant ces scores, le processus MAX se déplace vers le branchement à partir du quelle le processus MIN ne pourra pas faire mieux que d’abaisser le score à 2

Le processus MAX espère arriver à la situation donnant le score8, mais il sait que le processus MIN ne le permettra pas. Ce dernier peut choisir un coup conduisant à 1

ESPRIT 2012-2013


ALGORITHME MINMAX

Function MINMAX-DECISION(state) returns an action

v MAX-VALUE(state)

return the action in SUCCESSORS(state) with value v

Function MAX-VALUE (state) returns a utility value

if TERMINAL-TEST (state) then return UTILITY (state)

v - ∞

for s in SUCCESSORS (state) do

v MAX(v, MIN-VALUE (s) )

return v

Function MIN-VALUE (state) returns a utility value


v + ∞


v MIN(v, MAX-VALUE (s) )

return v

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20

APPLICATION

L M N S R Q O P X V U T Z A’ Y W

J K I

E H G F

B C

D

A Max

Max

Min

v = - ∞

v = - ∞

v = + ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = - 3

v = - ∞

v = + ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = + ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = + ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = 15

v = - ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = 15

v = - 10

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = 15

v = 3

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = - ∞

v = 3

v = 3

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = + ∞

v = - ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = + ∞

v = 4

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = + ∞

v = 6

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = 6

v = 6

Mohamed Heny Selmi © ESPRIT

15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = 6

v = 6

v = - ∞

Mohamed Heny Selmi © ESPRIT

15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = 6

v = 6

v = -7

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = 6

v = 6

v = 12

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 3

v = 3

v = 3

v = 6

v = 6

v = 12

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = + ∞

v = - ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = + ∞

v = 4

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = + ∞

v = 8

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = - ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = - ∞

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 6

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 8

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = 20

ESPRIT 2012-2013


15 -3 -5 -10 3 4 6 -7 12 4 8 12 30 20 10 20


J K I

E H G F

B C

D

A Max

Max

Min

v = 15

v = 8

v = 3

v = 3

v = 6

v = 6

v = 12

v = 8

v = 8 v = 30

v = 20

ESPRIT 2012-2013


EXEMPLE ‘TIC-TAC-TOE’

Un processus MIN

Un processus MAX

ESPRIT 2012-2013


ARBRE DU JEUX

MAX

MIN

Etat final (victoire de MAX)

Ici, on néglige les états “symétriques” afin de réduire la taille de l’arbre

Nœuds MIN

Nœuds MAX

ESPRIT 2012-2013


INDICATIONS PRATIQUES

► On prend la convention suivante :

- une situation gagnante pour le joueur MAX vaut + valeur

- une situation perdante pour le joueur MIN vaut - valeur

- une situation nulle vaut 0

► Le MinMax assigne une valeur à chaque feuille, puis fait remonter ces valeurs avec l'hypothèse

que chaque joueur choisit le meilleur coup pour lui. Cela signifie en pratique que :

- MAX choisit le coup amenant à l'état de plus grande valeur

- MIN choisit le coup amenant à l'état de plus petite valeur

ESPRIT 2012-2013



► Le MinMax parcourt un arbre de configurations (graphe d’états)

► Lorsqu‘il arrive à une feuille de l'arbre, il utilise la fonction d'évaluation pour

donner une valeur à la configuration

► Pour les nœuds qui ne sont pas des feuilles, il utilise

soit le minimum des valeurs des fils si le nœud représente le choix de

l'adversaire (c'est donc un nœud Min)

soit le maximum des valeurs des fils si le nœud représente le choix du

joueur MAX (c'est donc un nœud Max)

ESPRIT 2012-2013



► Dans un programme de jeu, une classe Joueur possède un membre : joueurCourant

► La classe joueur Courant représente le type du Joueur pour pouvoir calibrer correctement la fonction d'évaluation

► Si dans le jeu de Morpion, la classe joueurcourant joue X et que les X gagnent, alors la fonction devrait rendre +1

► Si le type de la classe joueurCourant est O mais c'est toujours les X qui gagnent alors on devrait obtenir -1

► On utilise le MinMax avec une profondeur bornée :

- On interrompt l'exploration avant d'avoir atteint la fin de partie

- On évalue l'état du jeu à un instant quelconque

- On utilise une heuristique h(e,J) qui évalue la configuration (l’état) e pour le joueur J

- Il existe plusieurs heuristiques pour un même jeu (influencent la stratégie de jeu

ESPRIT 2012-2013


IDÉE DE BASE : CHOIX D’UNE ACTION

i. En considérant chaque état actuel comme étant état initial,

on construit pour chaque processus actif (MAX ou MIN) l’arbre du jeu

avec une profondeur maximale h (horizon) afin de limiter le temps

d’exécution

ii. Evaluer les états « nœud fils »

iii. Appliquer le principe du MINMAX

ESPRIT 2012-2013


FONCTION D’ÉVALUATION

On associe à chaque nœud S un nombre e(S)

e(S) est une heuristique qui estime à quel point S est favorable pour le processus MAX

e(S) > 0 : S est favorable pour MAX

e(S) < 0 : S est favorable pour MIN

e(S) = 0 : S est neutre

ESPRIT 2012-2013


EXEMPLE DE FONCTION D’ÉVALUATION

e(S) = nombre des colonnes, lignes ou diagonales ouverts

pour le processus MAX - nombre des colonnes, lignes ou

diagonales ouverts pour le processus MIN

8X-8O= 0 (3+3+2)

6X-4O = 2 3X-3O = 0

ESPRIT 2012-2013


UTILITÉ DE LA SAUVEGARDE DES VALEURS

Minmax permet d’obtenir la meilleure évaluation d’une cellule qu’on peut obtenir en supposant que MIN va jouer son meilleur coup

La valeur de minmax obtenue au niveau d’une cellule non-feuille sera meilleure à la valeur obtenue en appliquant directement la fonction d’évaluation e

ESPRIT 2012-2013


ALPHABETA

ESPRIT 2012-2013


APERÇU GÉNÉRAL DE L’AMÉLIOARATION

ESPRIT 2012-2013


b = 2

2

La valeur beta de MIN est supérieure à la valeur finale sauvegardée : elle ne peut jamais augmenter


ESPRIT 2012-2013


1

b = 1

2

La valeur beta de MIN est supérieure à la valeur finale sauvegardée : elle ne peut jamais augmenter


ESPRIT 2012-2013


a = 1

La valeur alpha de MAX est inférieure à la valeur finale sauvegardée : Elle ne peut jamais diminuer

1

b = 1

2


ESPRIT 2012-2013


a = 1

1

b = 1

2 -1

b = -1


ESPRIT 2012-2013


a = 1

1

b = 1

2 -1

b = -1

La recherche peut être cessée au-dessous de n'importe quel noeud de MIN dont la valeur bêta est moins qu'ou égale à la valeur alpha d'un de ses ancêtres de MAX


ESPRIT 2012-2013


PRINCIPE DE L’ALGORITHME ALPHA-BÊTA

L’algorithme α-β élague une partie de l’arbre du jeu. Il s’agit d’une procédure

qui se charge de réduire le nombre de branches de l’arbre à développer à celui

d’évaluation nécessaires

L’idée ressemble plus au moins à celle de la recherche heuristique dans le sens

où l’on déterminera que certains chemins sont mauvais, sans qu’on ait à les

suivre jusqu’à la limite de prévision

ESPRIT 2012-2013



ESPRIT 2012-2013


L’algorithme MinMax a déjà parcouru les 2 premières branches et va s’engager dans la 3ème branche

Durant l’exploration de la 3ème branche, on évalue la 1ère feuille, qui retourne une valeur de 1, son père Min, ne va pas pouvoir dépasser la valeur 1, ceci les valeurs des deux fils inexplorés

Le joueur Max à la racine a garantit une valeur égale à 3 (un de ses fils a déjà été évalué à 3)

Comme le maximiseur sait qu‘il est assuré d’un score de 3 en passant par la branche du milieu, tout ce qu’il a besoin de savoir sur la branche droite est qu’il ne peut pas espérer obtenir un score supérieur à 1 en la prenant

Pour modifier la valeur de la racine (le coup à jouer) il faudrait que ce nœud dépasse la valeur 3

Les deux feuilles restantes sont inintéressantes et ne seront pas explorées par α-β

L’α-β détermine la valeur MinMax de la racine de l’arbre de jeu en traversant l’arbre dans un ordre prédéterminé (de gche à dte) sautant tous les nœuds qui ne peuvent plus influencer la valeur MinMax de la racine

La stratégie α-β nécessite l’entretien de 2 valeurs :

Une borne inf. sur la valeur qu’un nœud maximisant peut se voir attribuer (α)

Une borne sup. sur la valeur qu’un nœud minimisant peut se voir attribuer(β)

ESPRIT 2012-2013



Le seuil α pour un nœud MIN « n » est égal à la +grande valeur (connue) de tous les nœuds MAX ancêtres de « n ». Si « n » atteint une valeur < à α, l’exploration de sa descendance devient inutile

Le seuil β pour un nœud MAX « n » est égale à la +petite valeur (connue) de tous les nœuds MIN ancêtres de « n ». Si « n » atteint une valeur > à β, l’exploration de sa descendance devient inutile


Les nœuds sautés se trouvant à un niveau MAX (resp.MIN), sont appelés des nœuds élagués par une coupure α (resp. β).

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5 ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0 -3

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0 -3

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0 -3

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0 -3 3

3

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0 -3 3

3

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

5

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

5

0

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

0

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

0

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

0

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

0

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

-5

-5

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

-5

-5

0

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

-5

-5

1

1

ESPRIT 2012-2013


EXEMPLE

0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

-5

-5

2

2

2

2

1

1

EXEMPLE

ESPRIT 2012-2013


0 5 -3 2 5 -2 3 2 -3 0 3 3 -5 0 1 -3 5 0 1 -5 5 3 2 -3 5

0

0

0

0 -3 3

3

0

2

2

2

2

1

1

-3

1

1

-5

-5

-5

1

2

2

2

2

1

ESPRIT 2012-2013


EXEMPLE

L’ALGORITHME ALPHA-BÊTA

Function ALPHA-BETA-SEARCH(state) returns an action

v MAX-VALUE(state, -∞, +∞)

return the action in SUCCESSORS(state) with value v

Function MAX-VALUE (state, α, β) returns a utility value


v - ∞


v MAX(v, MIN-VALUE (s, α, β) )

if (v ≥ β) then return v

α MAX(v, α)

return v

Function MIN-VALUE (state, α, β) returns a utility value


v + ∞


v MIN(v, MAX-VALUE (s, α, β) )

if (v ≤ α) then return v

β MIN(v, β)

return v

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8

Q R S T Y X W U V A6 A5 A4 A3 A2 A1 Z A8 A9 A7

O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(- ∞, + ∞)

v = - ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(- ∞, + ∞)

v = - ∞

(- ∞, + ∞)

v = + ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(- ∞, + ∞)

v = - ∞

(- ∞, 3)

v = 3

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(- ∞, + ∞)

v = - ∞

(- ∞, 3)

v = 3

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = - ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = - ∞

(3, + ∞)

v = + ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = - ∞

(3, + ∞)

v = 0

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = - ∞

(3, 0)

v = 0

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = 0

(3, + ∞)

v = 0

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = 0

(3, + ∞)

v = 0

(3, + ∞)

v = + ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = 0

(3, + ∞)

v = 0

(3, 5)

v = 5

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(3, + ∞)

v = 0

(3, + ∞)

v = 0

(3, 5)

v = 5

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, + ∞)

v = + ∞

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = - ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = - ∞

(3,5)

v = ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = - ∞

(3,5)

v = 7

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = - ∞

(3,5)

v = 7

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(3,5)

v = - ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(3,5)

v = - ∞

(3,5)

v = ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(3,5)

v = - ∞

(3,4)

v = 4

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(3,5)

v = - ∞

(3,4)

v = 4

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = ∞

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 5)

v = 5

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(3, + ∞)

v = 3

(- ∞, 3)

v = 3

(3, 4)

v = 4

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(4, + ∞)

v = 4

(- ∞, 3)

v = 3

(3, 4)

v = 4

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


7

3 5

0 3 10 5 6 7 8 8 10 -3 -12 4 2 6 4 5 2 8


O P N I L M K J

T2 T3

T1

D E F H G

Max

Max

Min

Min

(4, + ∞)

v = 4

(- ∞, 3)

v = 3

(3, 4)

v = 4

(5, + ∞)

v = 5

(3, + ∞)

v = 0

(3, 5)

v = 5

(3,5)

v = 7

(3,5)

v = 7

(4,5)

v = 4

(3,4)

v = 4

(4,5)

v = 2

ESPRIT 2012-2013


Max

Max

Min

EXERCICE

1. Quel est le meilleur coup pour le joueur Max avec le MinMax?

2. Dans cette arbre de jeu, quels noeuds n’auraient pas besoin d’être examinés en utilisant la procédure α-β ?

7 6 8 5 2 3 0 -2 6 2 5 8 9 2

ESPRIT 2012-2013


Max

Max

Min

INDICATION

7 6 8 5 2 3 0 -2 6 2 5 8 9 2

7 3 8 0 6 8 9

8

3 8 0

ESPRIT 2012-2013


Max

Max

Min

7 6 8 5 2 3 0 -2 6 2 5 8 9 2

7 3 8 0 6 8 9

8

3 8 0

ESPRIT 2012-2013


INDICATION

COMBIEN GAGNONS-NOUS ?

3

a = 3

-1

b=-1

(4)

3

a = 3

4

b=4

-1

ESPRIT 2012-2013


CONCLUSION

L’algorithme α-β détermine la valeur MinMax de la racine de l’arbre de jeu en traversant l’arbre en profondeur d’abord, sautant tous les nœuds qui ne peuvent plus influencer la valeur MinMax de la racine

La valeur exacte des nœuds n’est pas importante

L’ordre dans le quel on visite les fils est important

Au mieux, on visite √n nœuds au lieu de n=bd pour MinMax

ESPRIT 2012-2013


Science

Algorithmes de jeux