La Théorie des jeux à somme nulle

Zainab Habbassi

Zainab Habbassi La Théorie des jeux à somme nulle 1/28

PLAN

1 Introduction
2 Jeux à somme nulle
3 Èquilibre de Nash
Théoréme de Nash :
Stratégies mixtes :
Critére minmax et maxmax :
4 thèorème de minmax
Definition :
Application Jeu d’echecs :
5 Èvaluation et algorithmique

Zainab Habbassi La Théorie des jeux à somme nulle 2/28

Introduction

Zainab Habbassi La Théorie des jeux à somme nulle 3/28

Jeux à somme nulle

Problématique :
1 Comment maximiser le gain dans un jeu à somme nulle ?

2 Comment anticiper les mouvements de son adversaire ?

3 Comment traduire mathématiquement les défis affrontés

en prenant partie dans un jeu à somme nulle ?

Zainab Habbassi La Théorie des jeux à somme nulle 4/28

Jeux à somme nulle

Définition
1 Deux joueurs X et Y s’affrontent (ils jouent un nombre
fini de fois).
2 Le jeu
 est déterminé parla matrice des gains :
a11 · · · a1n
 .. . . . 
A= . . ..  =aij
am1 · · · amn
aij est la valeur que le joueur Y donne au joueur X.

3 Si X joue sa stratégie i, Y joue sa stratégie j.

Zainab Habbassi La Théorie des jeux à somme nulle 5/28

Introduction à l’équilibre de Nash :

C’est une position stable qui me dit que je n’ai pas intérêt à
changer ma stratégie et mon adversaire non plus. L’analogie se
fait avec une bille dans un creux qui, si on la déplace un peu,
revient à sa position de départ.

Zainab Habbassi La Théorie des jeux à somme nulle 6/28

Théoreme de Nash

Définition 1.1
soit un jeu à n joueurs, et :
s*=(s1 ∗,.....,sn ∗)
une combinaison de choix stratégiques de ces n joueurs
où si ∗ est le meilleur choix stratégique du joueur i. Soit
Ui (s1 ∗, s2 ∗, ......, sn ∗) le gain du joueur i lorsque s* est
sélectionné.
Une combinaison de choix stratégiques s* est un équilibre
de Nash si et seulement si :
Ui (s1 ∗, s2 ∗, .., si ∗, ...., sn ∗) ≥Ui (s1 ∗, s2 ∗, .., si , ...., sn ∗)

Zainab Habbassi La Théorie des jeux à somme nulle 7/28

le jeu de cerf :
Le jeu de cerf Deux chasseurs choisissent sans se concerter
si chacun part chasser un lièvre, ou s’il préfère chasser un cerf.
Un cerf apporte un plus gros gain, mais ne peut se chasser
qu’à deux.
Joueur A
cerf liévre

1 0
cerf
Joueur B

2 0

0 2
liévre
0 1

Zainab Habbassi La Théorie des jeux à somme nulle 8/28

Déterminer l’equilibre de nash à partir de la
matrice de gains

gA (cerf , cerf ) = 1
(1)
gB (cerf , cerf ) = 2

gA (cerf , lievre) = 0
(2)
gB (cerf , lievre) = 0


gA (lievre, cerf ) = 0
(3)
gB (lievre, cerf ) = 0

gA (lievre, lievre) = 2
(4)
gB (lievre, lievre) = 1

Zainab Habbassi La Théorie des jeux à somme nulle 9/28

Stratégies mixtes :

L’utilisation de stratégies mixtes peut être trouvée dans

plusieurs domaines, des sports à la politique, et même
dans notre vie [Link] stratégies ont un impact
significatif sur la prise de décision et peuvent nous aider à
maximiser nos résultats tout en considérant les choix de
l’adversaire.
La prise en compte de stratégies mixtes pourrait faire
apparaitre d’autres possibilités de meilleure réponse

Zainab Habbassi La Théorie des jeux à somme nulle 10/28

Probabilités de gain :
Reprenons l’exemple du jeu de cerf :
Supposons que le joueur A choisit de chasser Cerf avec
une probabilité de p et de chasser Liévre avec une
probabilité de [Link] joueur B choisit également de
chasser un Cerf avec une probabilité de q et de chasser
un Liévre avec une probabilité de 1-q.
Joueur A
cerf p liévre 1-p

1 0
cerf
Joueur B

q 2 0

0 2
liévre
1-q 0 1
Zainab Habbassi La Théorie des jeux à somme nulle 11/28
Fonctions de meilleure réponse et équilibre de
nash :

La prise en compte des stratégies mixtes pourrait faire

apparaitre d’autres possibilités avec de meilleures
réponses.
Notons la stratégie mixte des deux joueurs :
p1 = (p, 1 − p)
p2 = (q, 1 − q) , avec (p,q) dans [0, 1 ]

Zainab Habbassi La Théorie des jeux à somme nulle 12/28

Critére de Maxmin et de Maxmax :

Considérons un jeu à deux stratégies propres (S1 , S2 ) et

notons l’utilité respective :

U(S1 P, S2 (1 − P))

L’esperance de gain s’exprime alors comme suit :

E=U(S1 P, S2 (1 − P))=PU(S1 )+U(S2 )(1-P)

Objectif :Trouver la meilleure stratégie quand

P=0(Maxmin),P=1(Maxmax).

Zainab Habbassi La Théorie des jeux à somme nulle 13/28

Espérances de gain :
Avec les valeurs numériques,le gain espéré du joueur B
devient alors :
Cerf :EB (p1 , p2 ) = 1 × q + 0 × (1 − q) = q
Liévre :EB (p1 , p2 ) = 0 × q + 2 × (1 − q) = 2 − 2q
comparons les espérances des deux stratégies :
2
q >(2-2q) =⇒ q>
3

2


 1 Si q>

 3
2

[0, 1 ] si q= (5)
 3

 2
0 si q<


3

Zainab Habbassi La Théorie des jeux à somme nulle 14/28

Espérances de gain :
Avec les valeurs numériques,le gain espéré du joueur A
devient alors :
Cerf :EA (p1 , p2 ) = 2 × p + 0 × (1 − p) = 2p
Liévre :EA (p1 , p2 ) = 0 × p + 1 × (1 − p) = 1 − p
comparons les espérances des deux stratégies :
1
2p >(1-p) =⇒ p>
3

1


 1 Si p>

 3
1

[0, 1 ] si p= (6)
 3

 1
0 si p<


3

Zainab Habbassi La Théorie des jeux à somme nulle 15/28

Représentation graphique :
1
Courbe 1
Courbe 2
0.8
Joueur A

0.6

0.4

0.2

0
0 0.2 0.4 0.6 0.8 1
Joueur B

Zainab Habbassi La Théorie des jeux à somme nulle 16/28

Existence de l’équilibre :

Analyse graphique et contraintes :

Les points d’intersection sont les équilibres.
On a bien nos deux équilibres en stratégies (cerf,cerf) et
(liévre,liévre).
2 1
Un nouvel équilibre en stratégies mixtes apparait( , ).
3 3
S’il y a de forte discontinuités dans les fonctions de
réaction, la non existence de l’ equilibre devient possible.
l’ensemble des stratégies de chaque joueur est convexe et
compact.

Zainab Habbassi La Théorie des jeux à somme nulle 17/28

Algorithme Minimax :

Définition :
L’algorithme minimax (aussi appelé algorithme MinMax) est
un algorithme qui s’applique à la théorie des jeux pour les jeux
à deux joueurs à somme nulle, consistant à minimiser la perte
maximum (c’est-à-dire dans le pire des cas).

Zainab Habbassi La Théorie des jeux à somme nulle 18/28

Construction de l’arbre :

configuration actuelle

configuration aprés un coup

configuration aprés deux coups

configuration aprés trois coups

Zainab Habbassi La Théorie des jeux à somme nulle 19/28

Jeu d’échecs :

Il donc possible de programmer une Intelligence Artificielle du

jeu d’échecs qui va réfléchir à la conséquence de ses actes en
regardant les mouvements possibles d’un joueur pour pouvoir
jouer à sa place.
Afin de prendre les meilleures décisions, l’IA a besoin de
connaître la valeur stratégique de chaque pièce.

Zainab Habbassi La Théorie des jeux à somme nulle 20/28

fonction d’evaluation :

Nom de Piéce Valeur

Reine 10
pion 1
Fou 3
Tour 5
Cavalier 3
Roi ∞
L’évaluation est d’autant plus élevée que la position est
meilleure.
La "fonction d’evaluation" correspond à la valeur totale
des pièces d’une couleur.
P
f (c) = Valeurpiece ∗ Nombrepiece

Zainab Habbassi La Théorie des jeux à somme nulle 21/28

Évaluation sur les feuilles :

max
5

min min
5 -10

10 5 -10 1

Zainab Habbassi La Théorie des jeux à somme nulle 22/28

Application de l’algorithme minimax
On applique alors un algorithme qui sert à parcourir l’arbre et
déterminer le meilleur coup à jouer :

Zainab Habbassi La Théorie des jeux à somme nulle 23/28

Algorithme Minimax :

On a donc l’algorithme suivant :

Zainab Habbassi La Théorie des jeux à somme nulle 24/28

Complexité :

Si le parcours de l’arbre de jeu se fait en profondeur on a

donc la complexité est O(bP).(soit P la profondeur de
l’arbre et b le nombre de coups possibles pour chaque
joueur).

Zainab Habbassi La Théorie des jeux à somme nulle 25/28

MERCI POUR VOTRE ATTENTION

Zainab Habbassi La Théorie des jeux à somme nulle 26/28

Annexe :

Zainab Habbassi La Théorie des jeux à somme nulle 27/28

Annexe :

Figure – code latex du graphe

Zainab Habbassi La Théorie des jeux à somme nulle 28/28