diff options
| -rw-r--r-- | notes-mitro206.tex | 155 |
1 files changed, 152 insertions, 3 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index fa39db5..110789e 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1337,7 +1337,7 @@ premier : formellement, le jeu $G_X^{\mathrm{b}}(A)$ est le même que $G_X^{\mathrm{a}}(X^{\mathbb{N}}\setminus A)$ si ce n'est que les noms des joueurs sont échangés. -\begin{defn} +\begin{defn}\label{definition-strategies-for-gale-stewart-games} Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une \textbf{stratégie} pour le premier joueur (resp. le second joueur) est une fonction $\varsigma$ qui à une suite finie (=position) de longueur @@ -1371,6 +1371,15 @@ joueur a une stratégie gagnante, le jeu $G_X^{\mathrm{a}}(A)$ est dit \textbf{déterminé}. \end{defn} +\thingy Il est clair que les deux joueurs ne peuvent pas avoir +simultanément une stratégie gagnante (il suffit de considérer la suite +$\varsigma \ast \tau$ où $\varsigma$ et $\tau$ seraient des stratégies +gagnantes pour les deux joueurs : elle devrait simultanément +appartenir et ne pas appartenir à $A$). + +En revanche, il faut se garder de croire que les jeux $G_X(A)$ sont +toujours déterminés. + \thingy\label{unshifting-notation} Introduisons la notation suivante : si $\underline{x} := (x_0,\ldots,x_{\ell-1})$ est une suite finie d'éléments de $X$ et si $A$ est un sous-ensemble de $X^{\mathbb{N}}$, @@ -1626,7 +1635,7 @@ Alice. C'est tout simplement qu'on a fait l'hypothèse que \emph{toute} suite commençant par $x_0,\ldots,x_{\ell-1}$ appartient à $A$. -\begin{thm}[D. Gale \& F. M. Stewart, 1953] +\begin{thm}[D. Gale \& F. M. Stewart, 1953]\label{gale-stewart-theorem} Si $A \subseteq X^{\mathbb{N}}$ est ouvert, ou bien fermé, alors le jeu $G_X(A)$ est déterminé. \end{thm} @@ -1752,6 +1761,146 @@ confrontation est gagnée par Bob. \end{proof} +\subsection{Détermination des jeux combinatoires} + +On va définir ici rapidement les notions relatives aux jeux impartiaux +à information parfaite pour expliquer comment ces jeux peuvent se +ramener à des jeux de Gale-Stewart et comment la détermination des +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 +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 + initiale}. Le \textbf{jeu impartial à information parfaite} associé +à ces données est défini de la manière suivante : partant de $x = +x_0$, Alice et Bob choisissent tour à tour un voisin sortant de $x$, +autrement dit, Alice choisit une arête $(x_0,x_1)$ de $G$, puis Bob +choisit une arête $(x_1,x_2)$ de $G$, puis Alice choisit une arête +$(x_2,x_3)$, et ainsi de suite. Si un joueur ne peut plus jouer, il a +perdu ; si la confrontation dure un temps infini, elle est considérée +comme nulle (ni gagnée ni perdue par les joueurs). + +Une \textbf{partie} ou \textbf{confrontation} de ce jeu est une suite +finie ou infinie $(x_i)$ de sommets de $G$ telle que $x_0$ soit la +position initiale et que pour chaque $i$ pour lequel $x_{i+1}$ soit +défini, ce dernier soit un voisin sortant de $x_i$. Lorsque le +dernier $x_i$ défini l'est pour un $i$ pair, on dit que le premier +joueur \textbf{perd} et que les second \textbf{gagne}, tandis que +lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que +le premier joueur gagne et que le second perd ; enfin, lorsque $x_i$ +est défini pour tout entier naturel $i$, on dit que la confrontation +est nulle ou que les deux joueurs \textbf{survivent} sans gagner. +\end{defn} + +\thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme +en \ref{first-definition-impartial-combinatorial-game}, va définir un, +ou plutôt deux, jeux de Gale-Stewart : l'intuition est que si un +joueur enfreint la « règle » du jeu (i.e., choisit un sommet qui n'est +pas un voisin sortant du sommet actuel), il a immédiatement perdu. + +Autrement dit, soit $G$ un graphe orienté et $x_0 \in G$. On pose $X += G$ et on partitionne l'ensemble des suites à valeurs dans $X$ en +trois : +\begin{itemize} +\item l'ensemble $D$ des (confrontations nulles, c'est-à-dire des) + suites $(x_1,x_2,x_3,\ldots)$ telles que pour chaque $i \in + \mathbb{N}$ (y compris $0$) le sommet $x_{i+1}$ soit un voisin + sortant de $x_i$ (c'est-à-dire : $(x_i,x_{i+1})$ est une arête + de $G$) (bref, personne n'a enfreint la règle), +\item l'ensemble $A$ des (confrontations gagnées par Alice, + c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe + $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant + de $x_i$ et que le plus petit tel $i$ soit \emph{impair} (i.e., Bob a + enfreint la règle en premier), +\item l'ensemble $B$ des (confrontations gagnées par Bob, c'est-à-dire + des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe $i \in + \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant + de $x_i$ et que le plus petit tel $i$ soit \emph{pair} (i.e., Alice + a enfreint la règle en premier). +\end{itemize} +(On a choisi ici d'indicer les suites par les entiers naturels non +nuls : il va de soi que ça ne change rien à la théorie des jeux de +Gale-Stewart ! Si on préfère, on peut les faire commencer à $0$, et +mettre dans $A$ toutes les suites qui ne commencent pas par $x_0$.) + +Le jeu de Gale-Stewart $G_X(A)$ est essentiellement identique au jeu +considéré en \ref{first-definition-impartial-combinatorial-game}, à +ceci près que les nuls sont comptés comme des gains de Bob ; le jeu +$G_X(A \cup D)$, pour sa part, est lui aussi identique à ceci près que +les nuls sont comptés comme des gains d'Alice. + +\begin{lem}\label{openness-of-combinatorial-to-gale-stewart} +Avec les notations de \ref{combinatorial-to-gale-stewart}, les parties +$A$ et $B$ sont ouvertes (pour la topologie produit, +cf. \ref{definition-product-topology}). +\end{lem} +\begin{proof} +Soit $(x_1,x_2,x_3,\ldots)$ est une suite d'éléments de $X = G$. Si +la suite appartient à $A$ alors, par définition de $A$, il existe un +$i$ impair tel que $x_{i+1}$ ne soit pas un voisin sortant de $x_i$ et +tel que $x_{j+1}$ soit un voisin sortant de $x_j$ pour tout $j<i$. On +en déduit que le voisinage fondamental formé de toutes les suites qui +coïncident avec $(x_1,x_2,x_3,\ldots)$ jusqu'à $x_{i+1}$ inclus est +contenu dans $A$. La même démonstration fonctionne pour $B$ avec $i$ +pair. +\end{proof} + +\begin{thm}\label{determinacy-of-perfect-information-games} +Soit $(G,x_0)$ un jeu impartial à information parfaite comme +en \ref{first-definition-impartial-combinatorial-game}. Alors +exactement l'une des trois affirmations suivantes est vraie : +\begin{itemize} +\item le premier joueur (Alice) possède une stratégie gagnante, +\item le second joueur (Bob) possède une stratégie gagnante, +\item chacun des deux joueurs possède une stratégie survivante. +\end{itemize} +(La notion de « stratégie » ici doit se comprendre comme pouvant +dépendre de l'histoire des coups joués précédemment : voir +\ref{remark-historical-versus-positional-strategies} ci-dessous.) +\end{thm} +\begin{proof} +Il est évident que les affirmations sont exclusives (si un joueur +possède une stratégie gagnante, l'autre ne peut pas posséder de +stratégie survivante, sinon on aurait une contradiction en les faisant +jouer l'une contre l'autre). + +Avec les notations de \ref{combinatorial-to-gale-stewart}, +d'après \ref{openness-of-combinatorial-to-gale-stewart}, les parties +$A$ et $B$ sont ouvertes, donc \ref{gale-stewart-theorem} montre que +les jeux définis par $A$ et $A \cup D = X\setminus B$ sont déterminés. + +Mais une stratégie gagnante d'Alice dans le jeu défini par $A$ est une +stratégie gagnante dans le jeu d'origine, tandis qu'une stratégie +gagnante de Bob dans ce jeu est une stratégie survivante dans le jeu +d'origine ; ainsi, dans le jeu d'origine, soit Alice a une stratégie +gagnante soit Bob a une stratégie survivante. + +De même, une stratégie gagnante d'Alice dans le jeu défini par $A \cup +D$ est une stratégie survivante dans le jeu d'origine, tandis qu'une +stratégie gagnante de Bob dans ce jeu est une stratégie gagnante dans +le jeu d'origine ; ainsi, dans le jeu d'origine, soit Alice a une +stratégie survivante soit Bob a une stratégie gagnante. + +En mettant ensemble ces deux disjonctions, on voit que l'un des trois +faits énoncés est vrai. +\end{proof} + +\thingy\label{remark-historical-versus-positional-strategies} La +notion de « stratégie » implicite dans le +théorème \ref{determinacy-of-perfect-information-games} est une notion +\emph{historique} : puisque c'est ainsi qu'elles ont été définies +en \ref{definition-strategies-for-gale-stewart-games}, les stratégies +ont le droit de choisir le coup à jouer en fonction de tous les coups +joués antérieurement. Il se trouve en fait qu'on a les mêmes +résultats avec des stratégies \emph{positionnelles}, c'est-à-dire, qui +ne choisissent un coup qu'en fonction du sommet $x \in G$. + +\textcolor{red}{À compléter.} + + % % @@ -2521,7 +2670,7 @@ comprendre que le joueur abandonne la partie). Une \textbf{stratégie historique} est une fonction partielle $\varsigma \big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où $\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des -suites finies de longueur $G$ (i.e., des suites +suites finies de $G$ de longueur non nulle (i.e., des suites $z_0,\ldots,z_{\ell-1}$ d'éléments de $G$ avec $\ell>0$ entier) telle que $\varsigma(z_0,\ldots,z_{\ell-1})$ soit un voisin sortant de $z_{\ell-1}$. |