Corrigé Mines-Ponts 2025 Informatique II MPI — Section 2.1 (Q15 à Q18) : Stratégies gagnantes : terminaison, vol de stratégie, trois types d'instances

Fin de partie.

Une partie s'arrête dès que Positus a relié $s$ à $t$ (il a gagné) ou que toutes les arêtes sont marquées (Minus a gagné si $s$ et $t$ ne sont pas reliés par $M^{+}$). Arrêter la partie au moment où Positus relie $s$ à $t$ ne change pas son issue : $M^{+}$ ne fait que croître, donc un chemin de $s$ à $t$ formé d'arêtes de $M^{+}$ le reste jusqu'à la fin.

Q15. Variant : le nombre $r=|E\setminus (M^{+}\cup M^{-})|$ d'arêtes non marquées, qui est le champ gm.nm de la section 1. C'est un entier naturel, et chaque coup marque une arête non marquée, donc le fait décroître de exactement $1$. Il ne peut décroître indéfiniment : après au plus $|E|$ coups, on a $r=0$, aucun coup n'est plus possible et la partie est finie (elle a pu s'arrêter plus tôt si Positus a gagné). Le jeu se termine donc toujours, en au plus $|E|$ coups.

Pas de match nul : à la fin de la partie, ou bien $s$ et $t$ sont reliés dans $(V,M^{+})$ et Positus a gagné, ou bien ils ne le sont pas ; dans ce second cas, la partie ne s'est pas arrêtée sur une victoire de Positus, elle s'est donc arrêtée parce que toutes les arêtes sont marquées, et Minus a gagné. Les deux conditions de victoire étant contraires l'une de l'autre, chaque partie a exactement un vainqueur.

Q16. Une position est la donnée de $(M^{+},M^{-})$ et du joueur qui doit jouer. Une stratégie pour un joueur $J$ est une fonction qui, à chaque début de partie (suite des coups déjà joués) aboutissant à une position non terminale où c'est à $J$ de jouer, associe un coup licite, c'est-à-dire une arête non marquée. Elle est gagnante si toute partie dans laquelle $J$ joue selon cette stratégie est gagnée par $J$, quels que soient les coups de l'adversaire. Une stratégie sans mémoire, celle du cours, ne dépend que de la position courante ; dans ce jeu fini sans cycle, l'existence d'une stratégie gagnante avec ou sans mémoire revient au même (la construction de Q18 fournit une stratégie sans mémoire).

Ce que le correcteur attend : une fonction qui répond à toutes les suites de coups de l'adversaire. Le jury précise qu'une « suite de coups à jouer pour gagner » n'est pas une stratégie gagnante.

Q17. Soit $\sigma$ une stratégie gagnante de Positus jouant en second. Positus, jouant en premier, va jouer une partie imaginaire dans laquelle Minus a commencé et où il applique $\sigma$, en gardant en réserve une arête surnuméraire $x$. L'argument « un coup de plus ne peut qu'aider » ne vaut pas en général ; c'est cette construction qui le justifie ici.