Probleme – Les trois types d'états, et le coût du compteur

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 27 — Jeux, stratégies et recherche heuristique

Énoncé

Sur le graphe ci-dessous, calculer l'attracteur de $J_{1}$ vers $W$ , puis celui de $J_{2}$ vers $L$ , et classer les neuf positions.
Montrer que les positions restantes sont bien des matchs nuls : exhiber, pour chacun des deux joueurs, une stratégie qui évite la défaite.
L'attracteur est-il le complémentaire de l'autre attracteur ?
Justifier le compteur restant du cours en le comparant à un algorithme qui réexamine tous les successeurs.

Corrigé

1. Les deux attracteurs. Pour $J_{1}$ vers $W$ : $p_{1} \in A_{1}$ (il joue vers $W$ ) ; $p_{2}$ est à $J_{2}$ mais ses deux coups mènent à $W$ et $p_{1}$ , tous deux dans $A$ , donc $p_{2} \in A$ ; $p_{7}$ est à $J_{2}$ et ses deux coups mènent à $p_{1}$ et $p_{2}$ , tous deux dans $A$ , donc $p_{7} \in A$ .

Pour $J_{2}$ vers $L$ — on échange les rôles : $p_{3}$ est à $J_{2}$ , il lui suffit d'un coup vers $L$ , donc $p_{3} \in Attr_{2}$ . Et c'est tout : $p_{4}$ est à $J_{1}$ , qui refusera d'aller en $p_{3}$ .

$Attr_{1}$ (gagnants $J_{1}$ )	$Attr_{2}$ (gagnants $J_{2}$ )	le reste (nuls)
$W, p_{1}, p_{2}, p_{7}$	$L, p_{3}$	$p_{4}, p_{5}, p_{6}$

Calcul vérifié par programme.

2. Pourquoi $p_{4}, p_{5}, p_{6}$ sont des nuls. Il faut deux stratégies, une par joueur, et chacune montre qu'on ne perd pas.

Pour $J_{1}$ , depuis $p_{4}$ : jouer vers $p_{5}$ . Et depuis $p_{6}$ : jouer vers $p_{5}$ — c'est le seul coup. $J_{1}$ ne va jamais en $p_{3}$ , donc jamais vers $L$ .
Pour $J_{2}$ , depuis $p_{5}$ : jouer vers $p_{4}$ ou $p_{6}$ , indifféremment. $J_{2}$ ne va jamais vers $p_{1}$ ni $p_{2}$ , donc jamais vers $W$ .

Sous ces deux stratégies, la partie reste à jamais dans ${p_{4}, p_{5}, p_{6}}$ : c'est un cycle, et aucune des deux cibles n'est atteinte. Ce sont bien les états de match nul du programme, et l'on voit ici que « match nul » n'est pas un état particulier du graphe — c'est une propriété de la partie infinie.

3. Non, l'un n'est pas le complémentaire de l'autre, et c'est le point du problème. Le complémentaire de $Attr_{1}$ compte cinq positions ( $L, p_{3}, p_{4}, p_{5}, p_{6}$ ), $Attr_{2}$ n'en compte que deux. Ce que l'on sait, en revanche, c'est que les deux attracteurs sont disjoints — on ne peut pas forcer à la fois $W$ et $L$ — de sorte que les trois ensembles forment une partition. La bonne formulation est donc :

$hors de Attr_{1} ⟺ J_{2} peut e ˊ viter W a ˋ jamais,$

ce qui laisse à $J_{2}$ le choix entre gagner et faire nul. Le complémentaire d'un attracteur est l'ensemble où l'autre joueur peut ne pas perdre, pas celui où il peut gagner.

4. Le compteur. Sans lui, l'algorithme naturel est un balayage répété : tant que quelque chose change, réexaminer toutes les positions et tous leurs successeurs. Chaque balayage coûte $Θ (n + m)$ , et il en faut autant qu'il y a d'étages. Sur une chaîne de $k$ positions de $J_{2}$ où l'attracteur progresse d'un cran par balayage :

$k$	réexamen complet	compteur	$n + m$
$100$	$5050$	$100$	$201$
$200$	$20100$	$200$	$401$
$500$	$125250$	$500$	$1001$
$1000$	$500500$	$1000$	$2001$

Le réexamen fait $k (k + 1) /2$ inspections d'arcs, le compteur en fait $k$ : à $k = 1000$ , un facteur $500$ .

L'idée générale, et elle dépasse ce chapitre : on remplace un test répété — « tous mes successeurs sont-ils marqués ? » — par un compteur décrémenté à chaque événement. Chaque arc est alors examiné une fois et une seule, d'où le $Θ (n + m)$ . C'est le procédé du tri topologique de Kahn (chapitre chap:parcours), qui décrémente le degré entrant, et celui du parcours en largeur : ne jamais redemander ce qu'on peut faire dire à l'événement.

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.