Un attracteur à la main

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 20 — L'étude des jeux : attracteurs et minmax

Énoncé

Soit l'arène définie par : $S_{1} = {a, c, e}$ , $S_{2} = {b, d}$ , arcs : $a \to b$ , $a \to d$ , $b \to c$ , $b \to e$ , $c \to d$ , $d \to e$ , $d \to g$ , $e \to f$ . Les états finals sont $f \in F_{1}$ (gagnant pour $J_{1}$ ) et $g \in F_{2}$ (gagnant pour $J_{2}$ ). Dérouler pas à pas le calcul de l'attracteur $Attr_{1} ({f})$ . Conclure sur le statut de l'état $a$ .

Corrigé

Initialisation : $A = {f}$ .
Itération 1 : On cherche les sommets hors de $A$ pouvant entrer dans l'attracteur.
Le sommet $e \in S_{1}$ possède un unique successeur $f \in A$ . Par la règle 2, $e$ entre dans $A$ (choix du coup gagnant : $e \to f$ ). $A = {f, e}$ .
Itération 2 :
Le sommet $d \in S_{2}$ possède les successeurs $e \in A$ et $g \in / A$ . La règle 3 impose que tous les successeurs soient dans $A$ . Comme $g \in / A$ , $d$ n'entre pas.
Le sommet $b \in S_{2}$ a pour successeurs $c \in / A$ et $e \in A$ . De même, $b$ n'entre pas.
Le sommet $c \in S_{1}$ a pour successeur $d \in / A$ , il n'entre pas.
Le sommet $a \in S_{1}$ a pour successeurs $b, d \in / A$ , il n'entre pas.
Fin : L'ensemble $A$ ne change plus. $Attr_{1} ({f}) = {f, e}$ .
Analyse de l'état $a$ : L'état $a$ n'appartient pas à l'attracteur $Attr_{1}$ , il n'est donc pas gagnant pour $J_{1}$ . Calculons l'attracteur de $J_{2}$ pour $F_{2} = {g}$ :
$A_{2} = {g}$ .
Le sommet $d \in S_{2}$ a pour successeurs $e$ et $g \in A_{2}$ . Pour $J_{2}$ , un seul successeur suffit $⟹ d$ entre dans $A_{2}$ . $A_{2} = {g, d}$ .
Le sommet $c \in S_{1}$ a pour unique successeur $d \in A_{2}$ . Pour $J_{1}$ , tous les successeurs doivent être dans $A_{2} ⟹ c$ entre dans $A_{2}$ . $A_{2} = {g, d, c}$ .
Le sommet $b \in S_{2}$ a pour successeurs $c \in A_{2}$ et $e \in / A_{2} ⟹ b$ entre dans $A_{2}$ (car $J_{2}$ peut choisir d'aller en $c$ ). $A_{2} = {g, d, c, b}$ .
Le sommet $a \in S_{1}$ a pour successeurs $b, d \in A_{2}$ . Tous ses successeurs sont dans $A_{2} ⟹ a$ entre dans $A_{2}$ . L'état $a$ appartient à $Attr_{2} ({g})$ . L'état $a$ est donc une position gagnante pour le joueur $J_{2}$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.