From a8371529dd9d8dde664b3778386a4bc08b8a4bd5 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 8 Mar 2016 16:54:29 +0100 Subject: Determinacy of combinatorial games for positional strategies (fairly tedious). --- notes-mitro206.tex | 581 +++++++++++++++++++++++++++++++++++------------------ 1 file changed, 387 insertions(+), 194 deletions(-) (limited to 'notes-mitro206.tex') diff --git a/notes-mitro206.tex b/notes-mitro206.tex index d30e163..2c4cf75 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -2113,22 +2113,396 @@ 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 +ont le droit de choisir le coup à jouer en fonction de \emph{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$. +ne choisissent un coup qu'en fonction du sommet $x \in G$. C'est ce +qui va être démontré dans la section suivante. -\textcolor{red}{À compléter.} -% Note: if we consider the tree of the historical strategy, all of its -% branches are finite (because an infinite branch would be a draw). +\subsection{Détermination pour les stratégies positionnelles} -% Note: consider a maximal winning-from-were-defined positional -% strategy (Zorn), show that it is defined on all "positional N" -% positions. All inductive P resp. N are positional P resp. N by -% minimality, and all inductive D are positional D by explicit -% strategy, and ditto for s/positional/historical/, so they all -% coincide. +\thingy Le but de la définition suivante est de formaliser, pour un +jeu combinatoire comme +en \ref{first-definition-impartial-combinatorial-game}, les notions de +stratégie positionnelle (dans laquelle un joueur ne choisit le coup à +jouer qu'en fonction de la position actuelle), et de stratégie +historique (dans laquelle il fait son choix en fonction de tous les +coups joués antérieurement), sachant qu'on veut montrer au final que +cette distinction a peu d'importance. Mais la définition sur laquelle +on va vraiment travailler est formulée +en \ref{set-of-everywhere-winning-positional-strategies}, donc on peut +se contenter de lire celle-ci. + +\begin{defn} +Soit $G$ un graphe orienté +(cf. \ref{first-definition-impartial-combinatorial-game} et \ref{definitions-graphs}). +Une \textbf{stratégie positionnelle} sur $G$ est une fonction +partielle $\varsigma\colon G \dasharrow G$ (i.e., une fonction définie +sur un sous-ensemble de $G$) telle que $\varsigma(x)$ soit, s'il est +défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut +comprendre que le joueur abandonne la partie). Une \textbf{stratégie + historique} sur $G$ 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 $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}$. + +Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ (à +partir d'une position initiale $x_0$) on a $\varsigma(x_i) = x_{i+1}$ +pour chaque $i$ pair pour lequel $x_i$ est défini, on dit que le +premier joueur a joué la partie selon la stratégie positionnelle +$\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour chaque $i$ +impair pour lequel $x_i$ est défini, on dit que le second joueur a +joué la partie selon la stratégie $\tau$. Pour une stratégie +historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$ et $\tau(x_i) += x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et +$\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement. + +La position initiale $x_0 \in G$ ayant été fixée, si $\varsigma$ et +$\tau$ sont deux stratégies (positionnelles ou historiques), on +définit $\varsigma \ast \tau$ comme la confrontation jouée lorsque le +premier joueur joue selon $\varsigma$ et le second joue selon $\tau$ : +autrement dit, $x_0$ est la position initiale, et, si $x_i$ est +défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ ou +$\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou +$\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas +défini, la suite s'arrête là). + +La stratégie (positionnelle ou historique) $\varsigma$ est dite +\textbf{gagnante pour le premier joueur} à partir de la position +initiale $x_0$ lorsque le premier joueur gagne toute confrontation où +il joue selon $\varsigma$, c'est-à-dire que la confrontation est finie +et que le dernier $x_i$ défini l'est pour un $i$ impair. On définit +de même une stratégie $\varsigma$ \textbf{survivante} (c'est-à-dire, +permettant d'assurer au moins le nul) pour le premier joueur à partir +d'une position initiale $x_0$, c'est-à-dire que dans toute +confrontation où il joue selon $\varsigma$, soit la confrontation est +infinie (donc nulle) soit le dernier $x_i$ défini l'est pour un $i$ +impair. +\end{defn} + +\thingy La notion de stratégie pour le second joueur peut être définie +de façon analogue, bien sûr, mais la notion n'a pas beaucoup +d'intérêt : une stratégie gagnante pour le second joueur à partir de +$x_0$ est la même chose qu'une stratégie gagnante pour le premier +joueur à partir de tout voisin sortant de $x_0$. Pour travailler avec +les stratégies positionnelles, il vaut mieux supposer qu'elles sont, +en fait, gagnantes partout où elles sont définies, ce qui amène à +faire la définition suivante : + +\thingy\label{set-of-everywhere-winning-positional-strategies} Dans ce +qui suit, on va fixer un graphe orienté $G$ et on aura besoin +d'introduire l'ensemble $\mathcal{S}$ de ce qu'on pourrait appeler les +« stratégies positionnelles gagnantes partout où définies », +c'est-à-dire des stratégies positionnelles $\varsigma$ gagnantes pour +le premier joueur à partir de n'importe quel point $x_0$ où +$\varsigma$ est défini ; autrement dit, il s'agit de l'ensemble des +fonctions partielles $\varsigma\colon G \dasharrow G$ telles que +\begin{itemize} +\item si $\varsigma(x)$ est défini alors il est un voisin sortant + de $x$, et que +\item si $\varsigma(x_0)$ est défini et si $(x_i)$ est une suite + (\textit{a priori} finie ou infinie) partant de $x_0$, dans laquelle + $\varsigma(x_i) = x_{i+1}$ pour $i$ impair, et $x_{i+1}$ est voisin + sortant de $x_i$ pour tout $i$, alors la suite est de longueur finie + et le dernier $x_i$ défini l'est pour un $i$ impair +\end{itemize} +(i.e., le premier joueur gagne n'importe quelle confrontation à partir +d'une position initiale $x_0$ du domaine de définition de $\varsigma$ +et où il joue selon $\varsigma$). + +L'ensemble $\mathcal{S}$ est partiellement ordonné par l'inclusion (si +$\varsigma,\tau \in \mathcal{S}$, on dit que $\varsigma$ +\textbf{prolonge} $\tau$ et on note $\varsigma \supseteq \tau$ ou +$\tau \subseteq \varsigma$, lorsque l'ensemble de définition de +$\varsigma$ contient celui de $\tau$ et que $\varsigma$ et $\tau$ +coïncident là où $\tau$ est définie : ceci signifie bien que +$\varsigma \supseteq \tau$ en tant qu'ensembles). + +\begin{lem}\label{positional-strategies-merging-lemma} +Si $\varsigma,\varsigma' \in \mathcal{S}$ avec la notation introduite +en \ref{set-of-everywhere-winning-positional-strategies}, alors il +existe $\varsigma'' \in \mathcal{S}$ qui prolonge $\varsigma$ et qui +est également définie en tout point où $\varsigma'$ l'est. +\end{lem} +\begin{proof} +Définissons $\varsigma''$ par $\varsigma''(x) = \varsigma(x)$ si +$\varsigma(x)$ est définie et $\varsigma''(x) = \varsigma'(x)$ si +$\varsigma(x)$ n'est pas définie mais que $\varsigma'(x)$ l'est. Il +est évident que $\varsigma''$ prolonge $\varsigma$ et est également +définie en tout point où $\varsigma'$ l'est : il reste à voir que +$\varsigma'' \in \mathcal{S}$. Mais si $x_0,x_1,x_2,\ldots$ +(\textit{a priori} finie ou infinie) est une confrontation jouée par +le premier joueur selon $\varsigma''$, montrons qu'elle est +nécessairement gagnée par le premier joueur : or le premier joueur a +soit joué selon $\varsigma$ tout du long, soit selon $\varsigma'$ tout +du long, soit selon $\varsigma'$ puis $\varsigma$, mais dans tous les +cas il gagne. De façon détaillée : soit $x_0$ est domaine de +définition de $\varsigma$ auquel cas tous les $x_i$ pairs le sont et +la confrontation est gagnée par le premier joueur ; soit $x_0$ est +dans le domaine de définition de $\varsigma'$ mais pas de $\varsigma$, +auquel cas il n'existe qu'un nombre fini de $i$ pairs tels que $x_i$ +ne soit pas dans domaine de définition de $\varsigma$ (puisque +$\varsigma'$ ne peut pas donner une partie nulle) et si $j$ est le +plus grand d'entre eux, $x_{j+1}$ est défini, et soit $x_{j+2}$ n'est +pas défini (auquel cas le premier joueur a gagné) soit $x_{j+2}$ est +dans le domaine de définition de $\varsigma$ et de nouveau le premier +joueur gagne à partir de là. +\end{proof} + +\begin{lem}\label{positional-strategies-union-lemma} +Si $\varsigma_i \in \mathcal{S}$ pour chaque $i\in I$ avec la notation +introduite en \ref{set-of-everywhere-winning-positional-strategies}, +et si pour tous $i,j$ les fonctions $\varsigma_i$ et $\varsigma_j$ +coïncident là où elles sont toutes deux définies, alors la fonction +$\bigcup_{i\in I} \varsigma_i$ (c'est-à-dire la fonction définie sur +la réunion des ensembles de définition des $\varsigma_i$ et qui +coïncide avec n'importe quel $\varsigma_i$ sur l'ensemble de +définition de celui-ci) appartient encore à $\mathcal{S}$. +\end{lem} +\begin{proof} +Si $x_0,x_1,x_2,\ldots$ (\textit{a priori} finie ou infinie) est une +confrontation jouée par le premier joueur selon $\varsigma := +\bigcup_{i\in I} \varsigma_i$, alors en fait elle est jouée tout du +long selon $\varsigma_i$ où $i$ est n'importe quel indice tel que +$\varsigma_i(x_0)$ soit définie. Comme $\varsigma_i \in \mathcal{S}$, +cette confrontation est gagnée par le premier joueur. +\end{proof} + +Le résultat ensembliste suivant sera admis (même si on pourrait s'en +sortir en appliquant \ref{fixed-point-lemma-for-partial-functions} à +la place) : +\begin{lem}[principe maximal de Hausdorff]\label{hausdorff-maximal-principle} +Soit $\mathscr{F}$ un ensemble de parties d'un ensemble $A$. On +suppose que $\mathscr{F}$ est non vide et que pour toute partie non +vide $\mathscr{T}$ de $\mathscr{F}$ totalement ordonnée par +l'inclusion (c'est-à-dire telle que pour $P,P' \in \mathscr{T}$ on a +soit $P \subseteq P'$ soit $P \supseteq P'$) la réunion $\bigcup_{P + \in \mathscr{T}} P$ soit contenue dans un élément de $\mathscr{F}$. +Alors il existe dans $\mathscr{F}$ un élément $M$ maximal pour +l'inclusion (c'est-à-dire que si $P \supseteq M$ avec $P \in +\mathscr{F}$ alors $P=M$). +\end{lem} + +\begin{prop}\label{existence-of-maximal-positional-strategy} +Avec la notation introduite +en \ref{set-of-everywhere-winning-positional-strategies}, il existe +$\varsigma \in \mathcal{S}$ maximal pour l'inclusion (au sens où si +$\varsigma \subseteq \varsigma'$ avec $\varsigma' \in \mathcal{S}$ +alors $\varsigma = \varsigma'$) ; de plus, si $\varsigma' \in +\mathcal{S}$, alors $\varsigma$ est défini en tout point où +$\varsigma'$ l'est. +\end{prop} +\begin{proof} +L'existence de $\varsigma \in \mathcal{S}$ maximal pour l'inclusion +découle immédiatement de \ref{hausdorff-maximal-principle} en +utilisant \ref{positional-strategies-union-lemma} pour constater que +si $\mathscr{T} \subseteq \mathcal{S}$ est totalement ordonné pour +l'inclusion alors la réunion $\bigcup_{\varsigma\in\mathscr{T}} +\varsigma$ appartient à $\mathcal{S}$. + +Une fois trouvé $\varsigma \in \mathcal{S}$ maximal pour l'inclusion, +si $\varsigma' \in \mathcal{S}$, +d'après \ref{positional-strategies-merging-lemma}, on peut trouver +$\varsigma''$ prolongeant $\varsigma$ et défini partout où +$\varsigma'$ l'est, et comme $\varsigma$ est maximal, on a +$\varsigma'' = \varsigma$, donc $\varsigma$ est bien défini partout où +$\varsigma'$ l'est. +\end{proof} + +\thingy\label{notation-n-and-p-sets-for-combinatorial-games} En +contituant les notations introduites +en \ref{set-of-everywhere-winning-positional-strategies}, on fixe +maintenant $\varsigma \in \mathcal{S}$ maximal pour l'inclusion (dont +l'existence est garantie par la +proposition \ref{existence-of-maximal-positional-strategy}). Soit $N$ +l'ensemble des sommets $x$ de $G$ où $\varsigma(x)$ est défini (i.e., +le domaine de définition de $\varsigma$) ; on vient de voir que $N$ +est aussi l'ensemble des points où un élément quelconque de +$\mathcal{S}$ est défini, i.e., l'ensemble des positions à partir +desquelles le premier joueur a une stratégie positionnelle gagnante. +Soit $P$ l'ensemble des sommets $x\in G$ dont tous les voisins +sortants appartiennent à $N$ (y compris s'il n'y a pas de voisin +sortant, i.e., si $x$ est un puits) : clairement, $P$ est l'ensemble +des positions à partir desquelles le second joueur a une stratégie +positionnelle gagnante (quel que soit le coup du joueur adversaire, il +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} +Avec les notations introduites en +\ref{set-of-everywhere-winning-positional-strategies} et \ref{notation-n-and-p-sets-for-combinatorial-games}, +\begin{itemize} +\item[(i)]un sommet $x\in G$ appartient à $N$ si et seulement si il a + au moins un voisin sortant qui appartient à $P$, +\item[(ii)]un sommet $x\in G$ appartient à $P$ si et seulement si tous + ses voisins sortants appartiennent à $N$. +\end{itemize} +\end{prop} +\begin{proof} +L'affirmation (ii) est la définition même de $P$ et n'a donc pas à +être prouvée. Il s'agit donc de montrer (i). + +Si $x\in N$ alors $y := \varsigma(x)$ est un voisin sortant de $x$ qui +appartient à $P$ puisque $\varsigma \in \mathcal{S}$. Réciproquement, +si $x$ a un voisin sortant $y$ qui appartient à $P$, et si +$\varsigma(x)$ n'était pas défini, on pourrait étendre $\varsigma$ en +posant $\varsigma(x) = y$, ce qui donnerait un élément de +$\mathcal{S}$ (toute partie jouée à partir de $x$ conduit à $y$ et de +là à des points où $\varsigma$ est définie, donc est gagnée par le +premier joueur), contredisant la maximalité de $\varsigma$ ; c'est +donc que $\varsigma(x)$ était bien défini, i.e., $x\in N$. +\end{proof} + +\thingy Par contraposée, sur l'ensemble $D := G\setminus(N\cup P)$ des +sommets restants de $G$, on a les propriétés suivantes : $x\in G$ +appartient à $D$ si et seulement si +\begin{itemize} +\item[(i*)]tous les voisins sortants de $x$ sont dans $N\cup D$ + \emph{et} +\item[(ii*)]au moins l'un d'entre eux appartient à $D$. +\end{itemize} + +On définit alors une stratégie positionnelle $\tau$ étendant +$\varsigma$ de la façon suivante : si $\varsigma(x)$ est défini (i.e., +$x \in N$), on pose $\tau(x) = \varsigma(x)$, et si $x \in D$ on +choisit pour $\tau(x)$ un voisin sortant de $x$ qui appartienne à $D$ +(lequel voisin existe d'après (ii*)). À partir d'un sommet $x_0$ +dans $D$, si l'un ou l'autre joueur joue selon $\tau$, ce joueur +survit, puisque soit son adversaire le laisse toujours dans $D$ auquel +cas le joueur considéré peut toujours jouer (selon $\tau$) en restant +dans $D$, soit son adversaire quitte $D$ et d'après (i*) joue +vers $N$, et alors le joueur considéré gagne puisqu'il joue +selon $\varsigma$. + +Bref, à partir d'un sommet de $N$ le premier joueur a une stratégie +\emph{positionnelle} gagnante, à partir d'un sommet de $P$ c'est le +second joueur qui en a une, et à partir d'un sommet de $D$ les deux +joueurs ont une stratégie positionnelle survivante. (Dans tous les +cas, on peut utiliser le $\tau$ qu'on vient de construire comme +stratégie positionnelle.) + +\begin{thm}\label{positional-determinacy-of-perfect-information-games} +Soit $G$ un graphe orienté. Quel que soit le sommet $x_0$ de $G$ +choisi comme position initiale, dans le jeu combinatoire impartial à +information parfaite considéré +en \ref{first-definition-impartial-combinatorial-game}, exactement +l'une des trois affirmations suivantes est vraie : +\begin{itemize} +\item le premier joueur (Alice) possède une stratégie positionnelle gagnante, +\item le second joueur (Bob) possède une stratégie positionnelle gagnante, +\item chacun des deux joueurs possède une stratégie positionnelle survivante. +\end{itemize} + +En particulier, l'existence d'une stratégie positionnelle gagnante ou +survivante est équivalente à celle d'une stratégie historique de même +nature. + +De plus, si $N,P,D$ sont les ensembles de sommets $x_0$ à partir +desquels chacune des trois affirmations ci-dessus est vraie, +\begin{itemize} +\item un sommet $x\in G$ appartient à $N$ si et seulement si il a + au moins un voisin sortant qui appartient à $P$, +\item un sommet $x\in G$ appartient à $P$ si et seulement si tous + ses voisins sortants appartiennent à $N$, +\item un sommet $x\in G$ appartient à $D$ si et seulement si tous ses + voisins sortants appartiennent à $N\cup D$ et au moins l'un d'eux + appartient à $D$. +\end{itemize} +\end{thm} +\begin{proof} +L'existence des stratégies positionnelles a déjà été montré ci-dessus, +ainsi que les propriétés sur $N,P,D$. L'équivalence entre stratégies +positionnelles et historiques vient du fait que toute stratégie +positionnelle peut être vue comme une stratégie historique (en +ignorant l'historique) et du fait que les trois cas sont exclusifs +aussi bien pour les stratégies historiques que positionnelles. +\end{proof} + +\thingy On a en particulier redémontré le +théorème \ref{determinacy-of-perfect-information-games}, même si la +démonstration suivie ici (consistant à prendre une stratégie +positionnelle maximale pour l'inclusion) n'est peut-être pas très +éclairante. + +En utilisant la notion d'ordinaux, on pourrait donner une autre +démonstration, plus explicite, du +théorème \ref{positional-determinacy-of-perfect-information-games} : +elle consiste à reprendre la seconde démonstration qui a été donnée du +théorème \ref{determinacy-of-perfect-information-games} et à constater +qu'en la modifiant à peine elle conduit maintenant à définir une +stratégie positionnelle ; un peu plus précisément, on définit par +induction sur l'ordinal $\alpha$ les positions gagnantes en $\alpha$ +coups par le premier joueur et les positions gagnantes en $\alpha$ +coups par le second joueur, et une stratégie gagnante consiste à jouer +d'une position gagnante en $\alpha$ coups pour le premier joueur vers +une position gagnante en $\beta<\alpha$ coups pour le second joueur +(pour les stratégies survivantes, on complète en jouant d'une position +non étiquetée vers une position non étiquetée, mais le problème de la +survie est de toute façon plus simple). + +Dans le cas des jeux définis par un graphe bien-fondé +(cf. \ref{definitions-graphs}), c'est-à-dire que le nul est +impossible, la détermination est beaucoup plus simple à démontrer en +on en verra encore une nouvelle démonstration dans le cadre de la +théorie de Grundy. + +Un bonus au +théorème \ref{positional-determinacy-of-perfect-information-games} est +l'affirmation suivante : + +\begin{prop} +Dans le contexte du +théorème \ref{positional-determinacy-of-perfect-information-games}, si +$N^*,P^*,D^*$ est une partition de $G$ en trois parties vérifiant les +trois propriétés qui ont été énoncées pour $N,P,D$ (en remplaçant +$N,P,D$ par $N^*,P^*,D^*$ respectivement), alors on a $N\subseteq N^* +\subseteq N\cup D$ et $P\subseteq P^* \subseteq P\cup D$ et bien sûr +$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 +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} +\begin{proof} +Si $N^*,P^*,D^*$ ont les mêmes propriétés que $N,P,D$, on peut définir +une stratégie (positionnelle) consistant à jouer à partir de $N^*$ +dans $P^*$ (c'est-à-dire à choisir pour chaque sommet de $N^*$ un +voisin sortant dans $P^*$) et à partir de $D^*$ dans $D^*$ : si le +premier joueur suit cette stratégie à partir d'un sommet dans $N^*$ ou +$D^*$ ne peut pas perdre puisque les propriétés des parties font que +son coup sera toujours défini : donc $N^* \cup D^* \subseteq N \cup +D$, ce qui signifie en passant au complémentaire $P^* \supseteq P$, et +si le second joueur suit cette stratégie à partir d'un sommet dans +$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 +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 +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$). +\end{proof} @@ -2568,7 +2942,7 @@ partout sur la partie bien-fondée de $G$. La démonstration du théorème repose crucialement sur le lemme suivant, dont on va donner deux démonstrations : -\begin{lem} +\begin{lem}\label{fixed-point-lemma-for-partial-functions} Soient $X$ et $Z$ deux ensembles quelconques : notons $\mathscr{D}$ l'ensemble des fonctions partielles $X\dasharrow Z$, qu'on verra comme des parties de $X\times Z$ ne contenant jamais deux couples $(x,z_1)$ @@ -2791,187 +3165,6 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$). % % -\section{Théorie combinatoire des jeux impartiaux à information parfaite}\label{section-combinatorial-impartial-games} - -\textcolor{red}{Section à refondre.} - -\subsection{Généralités sur les jeux et stratégies} - -\begin{defn}\label{definition-impartial-combinatorial-game} -Un jeu \textbf{impartial à information parfaite} est un graphe -orienté $G$ muni d'un sommet $x_0$ appelé \textbf{position initiale} -et vérifiant de plus : -\begin{itemize} -\item pour un jeu « court » : $G$ est fini acyclique (ou de façon - équivalente, fini et bien-fondé) ; -\item pour un jeu « terminant » : $G$ est bien-fondé ; -\item pour un jeu « fini à boucles » : $G$ est fini. -\item pour un jeu « non nécessairement terminant » : (aucune - hypothèse). -\end{itemize} -Les sommets de $G$ sont aussi appelés les \textbf{positions} de $G$, -et les voisins sortants d'une position $x \in G$ sont aussi appelés -les \textbf{options} à partir de $x$. - -On supposera que tout sommet de $G$ est accessible à partir de $x_0$ ; -si ce n'est pas le cas, il reviendra au même de supprimer tous les -sommets inaccessibles, assurant du coup cette hypothèse. -\end{defn} - -La terminologie est malheureusement peu standardisée : la plupart des -auteurs font implicitement une des deux hypothèses -(« bien-fondé »=« terminant », et/ou « fini ») sur le jeu $G$, le cas -« court » étant la conjonction des deux. Ici, on fera le plus souvent -l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait -que cela signifie que $x_0$ appartient à la partie bien-fondée -(cf. \ref{definition-wfpart}) du graphe $G$. - -\thingy\label{playing-from-a-position} Si $G$ est un jeu comme -en \ref{definition-impartial-combinatorial-game}, et $x \in G$ une -position quelconque de $G$, on définit le jeu joué \textbf{à partir} -de $x$ comme l'aval de $x$ (c'est-à-dire l'ensemble des positions -accessibles à partir de $x$, -cf. \ref{definition-accessibility-downstream}) considéré comme un -graphe (le sous-graphe induit) et muni du sommet $x$ lui-même comme -position initiale. Ceci définit un nouveau jeu qui sera parfois noté -$G_x$ et qui sera parfois identifié à $x$ quand aucune confusion ne -peut en résulter. (Ainsi, $G_{x_0}$ est exactement $G$.) - -De façon moins formelle : on peut toujours considérer une position $x$ -quelconque d'un jeu $G$ comme position initiale d'un nouveau jeu (le -jeu joué si une fois atteinte la position $x$). Cette remarque -triviale permet de considérer n'importe quelle fonction d'un jeu -impartial à information parfaite comme une fonction de n'importe -quelle position de n'importe quel jeu. - -\begin{defn} -Soit $G$ un jeu comme -en \ref{definition-impartial-combinatorial-game}. Une \textbf{partie} -ou \textbf{confrontation} de $G$ 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$ (ce qui ne peut pas se produire si $G$ est bien-fondé), on -dit que la partie est nulle ou que les deux joueurs \textbf{survivent} -sans gagner. -\end{defn} - -\thingy Il est parfois plus agréable de donner aux joueurs des noms -comme « Alice » et « Bob ». Il faut néanmoins se rappeler, dans la -théorie des jeux \emph{impartiaux} considérée dans cette section, que -l'identité des joueurs n'est inscrite nulle part dans le jeu : ils ont -tous les deux toutes les options possibles depuis chaque position -(comparer le jeu de Hackenbush impartial avec les autres -en \ref{introduction-hackenbush}). - -Plutôt que de parler de « premier » et de « second » joueur, on peut -aussi parler de \textbf{joueur suivant} et de \textbf{joueur - précédent} : le joueur suivant est celui qui doit jouer, -c'est-à-dire le premier, et le joueur précédent est celui qui vient de -jouer, c'est-à-dire le second. (Ceci est d'ailleurs très malheureux -compte tenu des initiales de ces quatre mots...) Il peut paraître -bizarre de dire que le second joueur « vient de jouer » quand on -commence la partie, mais c'est logique vu que c'est à l'autre de -jouer, et c'est cohérent avec la -convention \ref{playing-from-a-position} : si on a atteint la position -$x$ d'un jeu $G$, le second joueur pour le jeu $G_x$ partant de $x$ -est bien le joueur qui vient de jouer pour amener à la position $x$. -L'avantage de parler de joueur suivant et de joueur précédent est -qu'on se rappelle plus facilement qu'ils échangent leurs rôles à -chaque tour. À l'inverse, quand on nomme les joueurs Alice et Bob, on -entend généralement que l'un ou l'autre peut commencer mais qu'ils -gardent leur identité d'un tour sur l'autre. - -\medbreak - -Définissons maintenant la notion de stratégie. On distinguera les -stratégies positionnelles, où le choix d'un coup à effectuer dépend -uniquement de l'état du jeu, et les stratégies historiques, où le -choix dépend de tous les coups joués jusqu'à ce point : - -\begin{defn} -Pour un jeu $G$ comme -en \ref{definition-impartial-combinatorial-game}, une -\textbf{stratégie positionnelle} est une fonction partielle -$\varsigma\colon G \dasharrow G$ telle que $\varsigma(x)$ soit, s'il -est défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut -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 $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}$. - -Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ on -a $\varsigma(x_i) = x_{i+1}$ pour chaque $i$ pair pour lequel $x_i$ -est défini, on dit que le premier joueur a joué la partie selon la -stratégie positionnelle $\varsigma$ ; tandis que si $\tau(x_i) = -x_{i+1}$ pour chaque $i$ impair pour lequel $x_i$ est défini, on dit -que le second joueur a joué la partie selon la stratégie $\tau$. Pour -une stratégie historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$ -et $\tau(x_i) = x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et -$\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement. - -Si $\varsigma$ et $\tau$ sont deux stratégies (positionnelles ou -historiques), on définit $\varsigma \ast \tau$ comme la partie jouée -lorsque le premier joueur joue selon $\varsigma$ et le second joue -selon $\tau$ : autrement dit, $x_0$ est la position initiale du jeu, -et, si $x_i$ est défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ ou -$\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou -$\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas -défini, la suite s'arrête là). - -La stratégie (positionnelle ou historique) $\varsigma$ est dite -\textbf{gagnante pour le premier joueur} lorsque le premier joueur -gagne toute partie où il joue selon $\varsigma$. La stratégie $\tau$ -est dite \textbf{gagnante pour le second joueur} lorsque le second -joueur gagne toute partie où il joue selon $\tau$. On définit de même -une stratégie \textbf{survivante} (c'est-à-dire, permettant d'assurer -au moins le nul) pour le premier joueur, resp. le second joueur. -\end{defn} - -Le résultat suivant explique que, au moins pour les stratégies -survivantes, la différence entre stratégies positionnelles et -stratégies historiques est sans importance (ce sera aussi le cas pour -les stratégies gagnantes, mais on le verra plus loin) : -\begin{prop} -Soit $G$ un jeu impartial à information parfaite : un joueur possède -une stratégie positionnelle survivante si et seulement si ce même -joueur possède une stratégie historique survivante. -\end{prop} -\begin{proof} -Si $\varsigma$ est une stratégie positionnelle, on en déduit une -stratégie historique $\varsigma_\sharp$ par -$\varsigma_\sharp(z_0,\ldots,z_{\ell-1}) = \varsigma(z_{\ell-1})$ -(i.e., en ignorant l'historique). Comme une partie est jouée selon -$\varsigma_\sharp$ si et seulement si elle l'est selon $\varsigma$, il -est évident que $\varsigma_\sharp$ est survivante si $\varsigma$ -l'est. Traitons l'autre implication. Mettons pour fixer les idées -que le joueur considéré est le premier. - -Si $\varsigma$ est une stratégie historique, définissons une stratégie -positionnelle $\varsigma_\flat$ de la façon suivante : si $y \in G$, -s'il existe au moins une partie (=confrontation) -$x_0,\ldots,x_{\ell-1}$ dans laquelle le premier joueur joue selon -$\varsigma$ et vérifiant $x_{\ell-1} = y$, alors on pose -$\varsigma_\flat(y) = \varsigma(x_0,\ldots,x_{\ell-1})$ pour un choix -quelconque de $x_0,\ldots,x_{\ell-1}$ (et sinon, $\varsigma_\flat(y)$ -n'est pas défini). Soit $x_0,x_1,x_2,\ldots$ une confrontation où le -premier joueur joue selon $\varsigma_\flat$ : pour chaque $i$, la -confrontation $x_0,\ldots,x_{2i}$ (s'arrêtant à $2i$) est jouée par le -premier joueur selon $\varsigma$, et le fait que $\varsigma$ soit une -stratégie survivante pour le premier joueur impose que -$\varsigma(x_0,\ldots,x_{2i})$ soit défini, ce qui impose à son tour -que $\varsigma_\flat(x_{2i})$ soit défini, i.e., $x_{2i+1}$ est -toujours défini : donc le premier joueur survit. -\end{proof} - % % % -- cgit v1.2.3