Introduction à la théorie des jeux

Pr. EL HADIQ Zouhair

Jeux d'accessibilité à deux joueurs · Attracteurs · Stratégies · Minimax

CPGE MP / PSI — Informatique — 2ᵉ période

1 / 12

De quoi parle-t-on ?INTRO

La théorie des jeux étudie des décisions en interaction. On se limite ici aux jeux d'accessibilité à deux joueurs, fortement liés à la théorie des graphes.

Une position = un sommet d'un graphe orienté.
Un coup = se déplacer le long d'un arc.
Une partie = un chemin dans le graphe.

Objectif du chapitre. Modéliser un jeu par un graphe biparti, calculer qui gagne (attracteurs), construire les stratégies, et approcher les jeux trop gros par Minimax.

2 / 12

Le jeu d'accessibilitéDÉFINITIONS

Deux joueurs : le Joueur 0 veut atteindre une cible $F$ ; le Joueur 1 veut l'éviter pour toujours.

Notion	Signification
État initial $v_0$	position de départ de la partie
États gagnants $F$	positions cibles à atteindre
Partie	suite $v_0, v_1, v_2,\dots$ reliée par des arcs
Stratégie	règle de choix du coup sur chaque position contrôlée

Victoire. Le Joueur 0 gagne si la partie atteint $F$ ; sinon c'est le Joueur 1.

3 / 12

L'arène : un graphe bipartiMODÈLE

On partitionne les positions selon le joueur qui doit jouer :

$G=(V_0\cup V_1,\;E)$

$V_0$ : positions du Joueur 0 (cercles)
$V_1$ : positions du Joueur 1 (carrés)

Les joueurs alternent : chaque arc relie $V_0$ et $V_1$ ⇒ le graphe est biparti.

4 / 12

Positions gagnantes : l'attracteurCŒUR

Une position est gagnante pour le Joueur 0 s'il peut forcer l'arrivée dans $F$ quoi que fasse l'adversaire. Cet ensemble est l'attracteur $\mathrm{Attr}_0(F)$.

Construction par couches : $\mathrm{Attr}^0=F$, puis on ajoute $u$ si

$u$ contrôlée par	Condition d'ajout
Joueur 0 ($u\in V_0$)	$\exists$ un successeur déjà gagnant
Joueur 1 ($u\in V_1$)	$\forall$ les successeurs déjà gagnants

Intuition. Sur $V_0$ il choisit ⇒ une bonne issue suffit. Sur $V_1$ il joue contre nous ⇒ il faut que toutes les issues soient gagnantes.

5 / 12

Attracteur : formule de point fixeFORMULE

$$\mathrm{Attr}^{k+1}=\mathrm{Attr}^{k}\;\cup\;\{u\in V_0:\exists\,(u\to v),\,v\in \mathrm{Attr}^{k}\}\;\cup\;\{u\in V_1:\forall\,(u\to v),\,v\in \mathrm{Attr}^{k}\}$$

La suite $(\mathrm{Attr}^k)$ est croissante, bornée par $V$ : elle se stabilise.

$$\mathrm{Attr}_0(F)=\bigcup_{k\ge 0}\mathrm{Attr}^{k}$$

Détermination. Les positions hors de $\mathrm{Attr}_0(F)$ sont exactement celles gagnantes pour le Joueur 1.

6 / 12

Algorithme (induction arrière)CODE

def attracteur(V0, V1, succ, pred, F): attr = set(F) # Attr^0 = F file = list(F) reste = {u: len(succ[u]) for u in V1} while file: v = file.pop() # v déjà gagnant for u in pred[v]: if u in attr: continue if u in V0: # ∃ : un suffit attr.add(u); file.append(u) else: # ∀ : décompter reste[u] -= 1 if reste[u] == 0: attr.add(u); file.append(u) return attr

Complexité $O(|V|+|E|)$. Chaque arc est examiné une seule fois.

7 / 12

Stratégies gagnantesSTRATÉGIE

On note $\mathrm{rang}(u)$ la première couche contenant $u$ (nombre minimal de coups pour forcer $F$).

Joueur 0 sur $u\in V_0\cap\mathrm{Attr}_0(F)$ : jouer vers un successeur $v$ avec $\mathrm{rang}(v)=\mathrm{rang}(u)-1$. Le rang décroît ⇒ on atteint $F$.

Joueur 1 sur $u\in V_1$ hors attracteur : jouer vers un successeur lui aussi hors attracteur (il en existe toujours) ⇒ on n'atteint jamais $F$.

Les deux stratégies sont sans mémoire : elles ne dépendent que de la position courante.

8 / 12

Pourquoi Minimax ?PASSAGE À L'ÉCHELLE

L'attracteur suppose qu'on explore tout le graphe. Pour les échecs, les dames, Puissance 4… ce graphe est gigantesque : impossible à construire.

Idée Minimax. On explore l'arbre des coups sur une profondeur limitée et on évalue les positions atteintes par une heuristique.

Joueur MAX (nous) : choisit la valeur maximale.
Joueur MIN (adversaire) : choisit la valeur minimale.

9 / 12

Minimax : pseudo-codeCODE

def minimax(position, profondeur, joueurMax): if profondeur == 0 or terminale(position): return heuristique(position) if joueurMax: valeur = -infini for coup in coups(position): valeur = max(valeur, minimax(jouer(position, coup), profondeur-1, False)) return valeur else: valeur = +infini for coup in coups(position): valeur = min(valeur, minimax(jouer(position, coup), profondeur-1, True)) return valeur

MAX joue à la racine le coup réalisant le max.

10 / 12

L'arbre MinimaxEXEMPLE

Les valeurs remontent du bas vers le haut :

feuilles : valeurs de l'heuristique ;
nœud MIN : minimum des enfants ;
nœud MAX : maximum des enfants.

Lien attracteur. Avec profondeur infinie et scores exacts $\pm\infty$, Minimax retrouve « gagnant / perdant » : l'heuristique n'est qu'une approximation.

11 / 12

À retenirBILAN

Jeu d'accessibilité = graphe biparti $G=(V_0\cup V_1,E)$ + cible $F$.
Attracteur $\mathrm{Attr}_0(F)$ : $\exists$ un successeur gagnant sur $V_0$, $\forall$ les successeurs sur $V_1$. Calcul en $O(|V|+|E|)$.
Le jeu est déterminé : chaque position est gagnante pour exactement un joueur ; stratégies sans mémoire.
Minimax + heuristique : pour les graphes trop gros, exploration en profondeur limitée (MAX maximise, MIN minimise).

Fil rouge. Tout le chapitre relie un objet « jeu » à un objet « graphe » — et le résoudre, c'est analyser ce graphe.

12 / 12