1 of 43

Plan du cour

  • Chapitre 1 : Concepts de base
      • Définitions
      • Classification des jeux
      • Représentation des jeux

Chapitre 2 : Jeux sous forme stratégique

      • Définitions
      • L'équilibre en stratégies dominantes
      • L'équilibre par élimination itérative des stratégies dominées
      • L'équilibre de Nash.
          • L'équilibre de Nash en stratégies pures
          • L'équilibre de Nash en stratégies mixtes

​

Chapitre 3 : Jeux sous forme extensive

      • Représentation
      • L’algorithme MiniMax
      • L’élagage Alpha-Beta.

​

Théorie des jeux

2 of 43

Chapitre 1 : Concepts de base

Théorie des jeux:

​

Permet une analyse formelle des problèmes posés par

l’interaction stratégique d’un groupe d’agents ( joueurs )

rationnels poursuivant des buts qui leur sont propres.

​

☞ Objectif : étude des comportements rationnels des

individus en situation de conflit.

Définitions:

​

Situations où des individus sont conduits à faire des

choix parmi un certain nombre d’actions possibles, et

dans un cadre défini à l’avance. ➠ Situations de conflit.

Jeux:

3 of 43

Chapitre 1 : Concepts de base

Définitions:

Joueur :

​

Toute personne qui participe au conflit et capable de prendre une décision.

Stratégie :

​

Un choix parmi la liste des décisions possibles.

      • Le choix de tous les joueurs constitue un profil

d’actions du jeu.

Gain :

​

Bénéfice qui résulte des choix de tous les joueurs

Rationalité :

​

Une règle de maximisation du profit individuel

4 of 43

Chapitre 1 : Concepts de base

Classification des jeux:

      • Plusieurs critères

​

​

  • Jeux à somme nulle (strictement compétitifs) / Jeux à

somme non-nulle .

  • Jeux à information complète / Jeux à information

incomplète .

  • Jeux à information parfaite / Jeux à information

imparfaite .

  • Jeux coopératifs / Jeux non-coopératifs .
  • Jeux à 2 joueurs / Jeux à n joueurs.
  • Jeux répétés / Jeux non-répétés .

​

5 of 43

Chapitre 1 : Concepts de base

Classification des jeux:

Jeux simultanés et jeux séquentiels

​

​

  • Dans un jeu simultané, les joueurs décident en même

temps de leur stratégie.

  • Au contraire, dans un jeu séquentiel, on peut spécifier

l'ordre des décisions de sorte qu'un joueur peut

décider de sa stratégie conditionnellement à ce qu'ont

joué les autres joueurs précédemment.

​

6 of 43

Chapitre 1 : Concepts de base

Classification des jeux:

Jeux à information complète /Jeux à information incomplète

​

​

  • S’il y a de l’information pour chacun des joueurs sur

l’ensemble de la structure du jeu, on est dans un jeu à

information complète.

  • Si au moins un joueur n’a pas d’informations sur un

élément de la structure du jeu, on est dans un jeu à

informations incomplètes.

​

Structure du jeu :

      • le nombre de joueurs.
      • les actions ou stratégies possibles.
      • les règles.
      • les gains.

7 of 43

Chapitre 1 : Concepts de base

Classification des jeux:

Jeux à information parfaite/Jeux à information imparfaite.

​

  • La distinction repose sur un seul élément de la structure

du jeu , l’information sur les décisions prises par les autres

joueurs.

​

  • Si chaque joueur au moment de jouer connaît les

décisions que l’autre joueur prise antérieurement, on est

dans un jeu à information parfaite.

  • Si, au contraire, au moins un joueur n’a pas d’information

sur ce qu’a joué l’autre joueur, on est dans un jeu à

information imparfaite.

8 of 43

Chapitre 1 : Concepts de base

Représentation des jeux:

Forme normale (stratégique)

​

  • Utilisation d’une matrice

9 of 43

Chapitre 1 : Concepts de base

Représentation des jeux:

Forme extensive

​

  • Utilisation d’un arbre

10 of 43

Chapitre 2 : Jeux sous forme stratégiques

Définitions:

Notation:

11 of 43

Chapitre 2 : Jeux sous forme stratégiques

Définitions:

Exemple:

12 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre en stratégies dominantes:

​

  • Une stratégie si est (strictement) dominante pour le

joueur i si pour tous les profils S−i et pour toutes les

autres stratégies si’ :

µi (si , S−i ) > µi (si’ , S−i )

​

  • Un profil de stratégies S* = { s1* , s2*,..si* ,..., sn* } est

un équilibre en stratégies dominantes si pour chaque

joueur i :

      • si * est la stratégie dominante.

13 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre en stratégies dominantes:

  • Si l’équilibre en stratégies dominantes existe, il est

unique.

Remarques:

  • Ce type d’équilibre fournit une prédiction très clair

et intuitive du résultat d’un jeu.

  • L’équilibre en stratégies dominantes n’existe que

pour très peu de jeux.

      • Solution : Comme tous les joueurs sont rationnels et

savent que leurs adversaires le sont , chacun peu

supprimer ses propres stratégies dominées et de

nouvelles stratégies dominées peuvent apparaitre

dans le nouveau jeu……..

14 of 43

Chapitre 2 : Jeux sous forme stratégiques

Elimination itérée des stratégies dominées:

15 of 43

Chapitre 2 : Jeux sous forme stratégiques

Elimination itérée des stratégies dominées:

16 of 43

Chapitre 2 : Jeux sous forme stratégiques

Exemple:

Elimination itérée des stratégies dominées:

17 of 43

Chapitre 2 : Jeux sous forme stratégiques

Problème:

Exemple:

Elimination itérée des stratégies dominées:

18 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

19 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

Propriétés:

  • Elimination itérée des stratégies dominées

20 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

Propriétés:

21 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

Propriétés:

22 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

Propriétés:

23 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash:

Propriétés:

24 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Stratégie mixte :

25 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

26 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Gains :

27 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Meilleures réponses:

28 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Meilleures réponses:

29 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Représentation graphique du jeu :

30 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

Représentation graphique du jeu :

31 of 43

Chapitre 2 : Jeux sous forme stratégiques

Equilibre de Nash en stratégies mixtes :

32 of 43

Chapitre 3 : Jeux sous forme extensive

Concepts de base:

  • Mouvements alternés : un joueur après l’autre, jusqu’à

la fin du jeu

  • Somme nulle : les gains d’un joueur sont exactement

l’opposé des gains de l’autre joueur

  • Information complète : lors de sa prise de décision ,

chaque joueur connaît précisément :

      • Ses possibilités d’action
      • Les possibilités d’action de son opposant
      • Les gains résultants de ces actions

33 of 43

Chapitre 3 : Jeux sous forme extensive

Exemple : Jeu Tic Tac Toe

Arbre du jeu

​

34 of 43

Chapitre 3 : Jeux sous forme extensive

Exemple : Jeu Tic Tac Toe

  • A chaque coup, les joueurs tentent de maximiser leur

gain minimum et donc de minimiser le gain maximal de

leur adversaire

Algorithme MinMax

35 of 43

Chapitre 3 : Jeux sous forme extensive

Algorithme MinMax :

  • Le joueur concerné choisit les coups qui maximisent une

fonction d’évaluation : Joueur Max

      • Fonction d’évaluation : Une fonction prend une

position en paramètre et retourne une valeur

estimant la qualité de cette position (estimation de

la probabilité du gain )

​

  • L’adversaire choisit les coups qui minimiseront la fonction

d’évaluation: Joueur Min

​

36 of 43

...

...

5

5

-1

10

7

10

4

20

-15

10

-5

-3

-3

-3

10

20

10

4

8

11

-12

-9

-9

11

-9

10

Max

Min

Max

Etendre l’arbre de jeu jusqu’à une profondeur autorisée

Calculer la valeur de la fonction d’évaluation pour chaque nœud terminal

Propager ces valeurs aux noeuds parents en affectant à un nœud :

la valeur maximum de ses fils lorsqu’il s’agit d’un nœud Max

la valeur minimum de ses fils lorsqu’il s’agit d’un nœud Min

Coup à jouer

Chapitre 3 : Jeux sous forme extensive

Algorithme MinMax :

Etapes :

37 of 43

Eviter la génération des sous branches inutiles de l’arbre

afin de diminuer l’espace de recherche

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta :

L’idée :

  • Résultat: 13 nœuds ignorés sur 31 nœuds

​

  • 42 %

38 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta :

Coupure 01:

Règle 01: Interrompre la recherche d'un nœud MIN si :

sa valeur ≤ valeur de son père

Max

5

Min

5

4

4

?

?

*

*

39 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta :

Coupure 02:

Max

3

Min

7

7

?

Règle 02: Interrompre la recherche dans un nœud MAX si :

sa valeur ≥ valeur de son père

?

3

*

*

40 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta

Principe :

Basé sur l’utilisation de deux valeurs auxiliaires :

  • nœud Max: Alpha

conserve la valeur de son meilleur successeur

trouvé jusqu`à présent

  • nœud Min: Beta

conserve la valeur de son pire successeur

trouvé jusqu`à présent

​

41 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta

Algorithme :

42 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta

Algorithme :

43 of 43

Chapitre 3 : Jeux sous forme extensive

Elagage AlphaBeta

Exemple :