diff options
| -rw-r--r-- | notes-mitro206.tex | 123 |
1 files changed, 86 insertions, 37 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index a8df1eb..dc00f6f 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1673,7 +1673,7 @@ stratégie gagnante, $\tau$, dans $G_X^{\mathrm{a}}(A)$ (où il joue en second). \end{proof} -\thingy En utilisant la +\thingy\label{strategies-forall-exists-reformulation} En utilisant la terminologie \ref{gale-stewart-winning-positions}, la proposition \ref{strategies-forall-exists-lemma} peut se reformuler de la façon suivante : @@ -1979,7 +1979,7 @@ jeux ouverts peut s'appliquer dans ce contexte : \begin{defn}\label{first-definition-impartial-combinatorial-game} Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une -relation $E$ irreflexive dont les éléments sont appelés arêtes du +relation $E$ irréflexive dont les éléments sont appelés arêtes du graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions générales) dont les sommets seront appelés \textbf{positions} de $G$, et soit $x_0$ un sommet de $G$ qu'on appellera \textbf{position @@ -2121,7 +2121,7 @@ ne choisissent un coup qu'en fonction du sommet $x \in G$. C'est ce qui va être démontré dans la section suivante. -\subsection{Détermination pour les stratégies positionnelles} +\subsection{Détermination pour les stratégies positionnelles}\label{subsection-positional-strategies-determinacy} \thingy Le but de la définition suivante est de formaliser, pour un jeu combinatoire comme @@ -2335,7 +2335,7 @@ amènera à une position où on a une stratégie gagnante). Enfin, on note $D := G\setminus(N\cup P)$ l'ensemble des sommets restants. -\begin{prop} +\begin{prop}\label{positional-strategies-forall-exists-lemma} Avec les notations introduites en \ref{set-of-everywhere-winning-positional-strategies} et \ref{notation-n-and-p-sets-for-combinatorial-games}, \begin{itemize} @@ -2469,11 +2469,11 @@ $D\supseteq D^*$. En particulier, si on utilise le théorème \ref{non-well-founded-definition} ci-dessous pour définir la \emph{plus petite} (pour l'inclusion) fonction partielle $f\colon G -\dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$ telle que $f(x)$ vaille -$\mathrm{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel -$f(y) = \mathrm{N}$, et que $f(x)$ vaille $\mathrm{N}$ ssi pour tout -voisin sortant $y$ de $x$ on a $f(y) = \mathrm{P}$, alors $f(x)$ vaut -$\mathrm{P}$ ou bien $\mathrm{N}$ ou bien est indéfinie lorsque +\dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ telle que $f(x)$ vaille +$\mathtt{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel +$f(y) = \mathtt{N}$, et que $f(x)$ vaille $\mathtt{N}$ ssi pour tout +voisin sortant $y$ de $x$ on a $f(y) = \mathtt{P}$, alors $f(x)$ vaut +$\mathtt{P}$ ou bien $\mathtt{N}$ ou bien est indéfinie lorsque respectivement le premier joueur a une stratégie gagnante, le second joueur en a une, ou les deux ont une stratégie survivante. \end{prop} @@ -2491,15 +2491,15 @@ $P^*$ ou $D^*$ il ne peut pas perdre non plus : donc $P^* \cup D^* \subseteq P \cup D$, ce qui signifie exactement $N^* \supseteq N$. Le deuxième paragraphe est une reformulation de la même affirmation : -la fonction $f \colon G \dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$ -définie par $f(x) = \mathrm{P}$ lorsque $x \in P$ et $f(x) = -\mathrm{N}$ lorsque $x \in N$ est la plus petite fonction partielle +la fonction $f \colon G \dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ +définie par $f(x) = \mathtt{P}$ lorsque $x \in P$ et $f(x) = +\mathtt{N}$ lorsque $x \in N$ est la plus petite fonction partielle vérifiant les propriétés qu'on a dites, i.e., la plus petite telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ avec les notations du théorème \ref{non-well-founded-definition} et $\Phi(x, g)$ valant -$\mathrm{N}$ si $g(y)$ est défini et vaut $\mathrm{N}$ pour au moins -un $y \in \outnb(x)$ et $\mathrm{P}$ si $g(y)$ est défini et vaut -$\mathrm{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente +$\mathtt{N}$ si $g(y)$ est défini et vaut $\mathtt{N}$ pour au moins +un $y \in \outnb(x)$ et $\mathtt{P}$ si $g(y)$ est défini et vaut +$\mathtt{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente en la seconde variable, on est bien dans le cas d'application duthéorème \ref{non-well-founded-definition}, même si ici on a déjà démontré l'existence d'une plus petite $f$). @@ -2526,7 +2526,7 @@ et \ref{scholion-well-founded-definition}). Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit -d'un ensemble $G$ muni d'une relation $E$ irreflexive. Les éléments +d'un ensemble $G$ muni d'une relation $E$ irréflexive. Les éléments de $G$ s'appellent \textbf{sommets} et les éléments de $E$ \textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de @@ -2821,26 +2821,63 @@ Soit $G$ un graphe orienté bien-fondé. En utilisant le théorème \ref{well-founded-definition}, on définit alors une partie $P \subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P = \varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x) -\to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la -valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la -fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence -et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x -\in G : f(x) = 0\}$. - -Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou -P-positions) de $G$, tandis que les éléments du complémentaire -$G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions) -de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins - sortants sont des N-sommets, et un N-sommet est un sommet qui a au - moins un P-sommet pour voisin sortant}. +\to \{\mathtt{P},\mathtt{N}\}$ on définit $\Phi(x, g)$ comme valant +$\mathtt{N}$ si $g$ prend la valeur $\mathtt{P}$ et $\mathtt{N}$ si +$g$ vaut constamment $\mathtt{P}$ (y compris si $g$ est la fonction +vide), et qu'on appelle $f$ la fonction telle que $f(x) = \Phi(x, +f|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le +théorème, et enfin on pose $P = \{x \in G : f(x) = \mathtt{P}\}$. + +Les éléments de $P$ (i.e., les $x$ tels que $f(x) = \mathtt{P}$) +seront appelés les \textbf{P-sommets} (ou P-positions) de $G$, tandis +que les éléments du complémentaire $G\setminus P$ (i.e., les $x$ tels +que $f(x) = \mathtt{N}$) seront appelés \textbf{N-sommets} (ou +N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous + les voisins sortants sont des N-sommets, et un N-sommet est un + sommet qui a au moins un P-sommet pour voisin sortant}. \end{defn} -On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si -le graphe est bien-fondé, les P-sommets sont les positions du jeu à -partir desquelles le joueur précédent a une stratégie gagnante, tandis -que les N-sommets sont celles à partir desquelles le joueur suivant -(`N' comme « Next ») a une stratégie gagnante (consistant, justement, -à jouer vers un P-sommet). +\thingy Dans un jeu combinatoire comme exposé en +\ref{introduction-graph-game} et/ou +\ref{first-definition-impartial-combinatorial-game}, si le graphe est +bien-fondé, les P-sommets sont les positions du jeu à partir +desquelles le joueur Précédent (=second joueur) a une stratégie +gagnante, tandis que les N-sommets sont celles à partir desquelles le +joueur suivant (`N' comme « Next », =premier joueur) a une stratégie +gagnante (consistant, justement, à jouer vers un P-sommet) : ceci +résulte de \ref{strategies-forall-exists-lemma} +ou \ref{strategies-forall-exists-reformulation} (ou encore +de \ref{positional-strategies-forall-exists-lemma} dans le cadre plus +général de la +section \ref{subsection-positional-strategies-determinacy}). + +On peut donc résumer ainsi la stratégie gagnante « universelle » pour +n'importe quel jeu combinatoire impartial à connaissance parfaite dont +le graphe est bien-fondé : \emph{jouer vers un P-sommet}, après quoi +l'adversaire sera obligé de jouer vers un N-sommet (si tant est qu'il +peut jouer), et on pourra de nouveau jouer vers un P-sommet, et ainsi +de suite (et comme le graphe est bien-fondé, le jeu termine forcément +en temps fini, et celui qui a joué pour aller vers les P-sommets aura +gagné puisqu'il peut toujours jouer). + +\thingy Pour illustrer la technique de démonstration par induction +bien-fondée, montrons que si $\gamma$ est la fonction de Grundy +introduite en \ref{definition-grundy-function} et si $P$ est la partie +introduite en \ref{definition-grundy-kernel}, alors on a $x \in P$ si +et seulement si $\gamma(x) = 0$, i.e., les P-sommets sont ceux pour +lesquels la fonction de Grundy est nulle. + +Par induction bien-fondé (cf. \ref{scholion-well-founded-induction}), +on peut supposer la propriété (« $x \in P$ si et seulement si + $\gamma(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du +sommet $x$ où on cherche à la vérifier. Si $x \in P$, cela signifie +par définition de $P$ que tous ses voisins sortants $y$ de $x$ sont +dans $G \setminus P$, et d'après l'hypothèse d'induction cela signifie +$\gamma(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire +$\mex\{\gamma(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et +seulement si $0 \not\in S$), ce qui signifie $\gamma(x) = 0$. Toutes +ces reformulations étaient des équivalences : on a bien montré que $x +\in P$ équivaut à $\gamma(x) = 0$, ce qui conclut l'induction. \thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant sur la notion d'ordinaux introduite dans la @@ -2856,14 +2893,26 @@ $y\in\outnb(x)$. De même, la fonction de Grundy peut se généraliser à n'importe quel graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) : y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal -\emph{n'appartenant pas} à $S$. Il reste vrai que $\gamma(x)$ est nul -si et seulement si $x$ est un N-sommet. +\emph{n'appartenant pas} à $S$. Il reste vrai (avec la même +démonstration) que $\gamma(x)$ est nul si et seulement si $x$ est un +P-sommet. + +On peut donc résumer ainsi la stratégie gagnante « universelle » pour +n'importe quel jeu combinatoire impartial à connaissance parfaite dont +le graphe est bien-fondé : \emph{jouer de façon à annuler la fonction + de Grundy} (c'est-à-dire, jouer vers un P-sommet), après quoi +l'adversaire sera obligé de jouer vers un sommet dont la valeur de +Grundy est non-nulle, et on pourra de nouveau jouer vers zéro, et +ainsi de suite (et comme le graphe est bien-fondé, le jeu termine +forcément en temps fini, et celui qui a joué pour annuler la fonction +de Grundy aura gagné puisqu'il peut toujours jouer). \thingy\label{well-founded-induction-algorithm} Lorsque $G$ est \emph{fini} et bien-fondé, i.e., est un graphe fini acyclique (cf. \ref{finite-graph-is-well-founded-iff-acyclic}), la fonction $f$ définie par le théorème \ref{well-founded-definition} peut se calculer -algorithmiquement de la façon suivante : +algorithmiquement de la façon suivante (si tant est que $\Phi$ +elle-même est calculable) : \begin{itemize} \item utiliser un algorithme de \textbf{tri topologique} (en ayant inversé le sens des arêtes pour se ramener à la convention usuelle) |