diff options
| -rw-r--r-- | notes-mitro206.tex | 183 |
1 files changed, 150 insertions, 33 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index c391a88..ded15ef 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -441,7 +441,7 @@ espéré est inférieur à $Q$. \thingy Le \textbf{jeu du partage} ou \textbf{de l'ultimatum} : Alice et Bob ont $10$ points à se partager : Alice choisit un $k$ entre $0$ -et $10$ entier (disons), la partie qu'elle se propose de garder pour +et $10$ entier (disons), la part qu'elle se propose de garder pour elle, \emph{puis} Bob choisit, en fonction du $k$ proposé par Alice, d'accepter ou de refuser le partage : s'il accepte, Alice reçoit le gain $k$ et Bob reçoit le gain $10-k$, tandis que si Bob refuse, les @@ -850,7 +850,7 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en a une. -\thingy Les \textbf{jeux de Gale-Stewart} : soit $A$ une partie de +\thingy Les \textbf{jeux de Gale-Stewart} : soit $A$ un sous-ensemble de $\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$. Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans le premier cas) ou de $\{0,1\}$ (dans les deux suivants). Ils jouent @@ -1937,7 +1937,7 @@ $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} -\subsection{Généralités} +\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 @@ -1987,14 +1987,12 @@ impartial à information parfaite comme une fonction de n'importe quelle position de n'importe quel jeu. \begin{defn} -Pour un jeu $G$ comme -en \ref{definition-impartial-combinatorial-game}, une -\textbf{stratégie} 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{partie} de $G$ est une suite finie ou infinie $(x_i)$ de +Soit $G$ un jeu comme +en \ref{definition-impartial-combinatorial-game}. Une \textbf{partie} +ou \textbf{confrontation}\footnote{Le mot « partie » peut + malheureusement désigner soit un sous-ensemble soit une partie d'un + jeu au sens défini ici : le mot « confrontation » permet d'éviter + l'ambiguïté.} 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 @@ -2004,27 +2002,7 @@ 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. Lorsque de plus $\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 $\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$. - -Si $\varsigma$ et $\tau$ sont deux stratégies, 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)$ si $i$ est pair et $\tau(x_i)$ si $i$ est -impair (si $x_{i+1}$ n'est pas défini, la suite s'arrête là). - -La stratégie $\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 survivante -(c'est-à-dire, permettant d'assurer au moins le nul) pour le premier -joueur, resp. le second joueur. +sans gagner. \end{defn} \thingy Il est parfois plus agréable de donner aux joueurs des noms @@ -2049,7 +2027,146 @@ $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. +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 longueur $G$ (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} + +\begin{prop} +Soit $G$ un jeu impartial à information parfaite : +\begin{itemize} +\item le premier joueur (=joueur suivant) possède une stratégie + survivante si et seulement si il existe une option (=voisin sortant) + $x_1$ de la position initiale $x_0$ de $G$ telle que le joueur + précédent possède une stratégie survivante dans le jeu $G_{x_1}$ + joué à partir de $x_1$ (cf. \ref{playing-from-a-position}) ; +\item le second joueur (=joueur précédent) possède une stratégie + survivante si et seulement si pour toute option (=voisin sortant) + $x_1$ de la position initiale $x_0$ de $G$, le joueur suivant + possède une stratégie survivante dans le jeu $G_{x_1}$ joué à partir + de $x_1$. +\end{itemize} +\end{prop} +\begin{proof} +Montrons la première affirmation. Si $\varsigma$ est une stratégie +positionnelle survivante du premier joueur sur $G$, posons $x_1 := +\varsigma(x_0)$. Toute partie de $G_{x_1}$ où le second joueur joue +selon $\varsigma$ définit une partie de $G$ où le premier joueur joue +selon $\varsigma$, donc ce joueur y survit, ce qui montre une +implication. Réciproquement, si $x_1$ est une option de $x_0$ à +partir de laquelle le second joueur a une stratégie positionnelle +survivante, on définit une stratégie historique $\varsigma'$ du +premier joueur sur $G$ qui préconise de jouer en $x_1$ à partir +de $x_0$ au premier coup et ensuite de jouer selon $\varsigma$ +(autrement dit, $\varsigma'(x_0) = x_1$ et +$\varsigma'(z_0,\ldots,z_{\ell-1}) = \varsigma(z_{\ell-1})$ si +$\ell>1$). Il est alors clair que si $x_0,x_1,x_2,\ldots$ est jouée +selon $\varsigma'$ par le premier joueur, alors $x_1,x_2,x_3,\ldots$ +est jouée selon $\varsigma$ par le second joueur, et comme $\varsigma$ +est survivante, c'est que $\varsigma'$ l'est aussi : ceci montre +l'implication réciproque. + +La preuve de la seconde affirmation est semblable. Si $\tau$ est une +stratégie positionnelle survivante du second joueur sur $G$, quelle +que soit l'option $x_1$ de $x_0$, les parties $x_0,x_1,x_2,\ldots$ où +le second joueur joue selon $\tau$ sont des parties $x_1,x_2,\ldots$ +où le premier joue selon $\tau$, donc survécues par ce joueur. Si le +premier joueur a une stratégie positionnelle survivante pour toute +option $y$ de $x_0$, choisissons-en une $\tau_y$, et définissons une +stratégie historique $\tau'$ du second joueur sur $G$ qui préconise de +jouer selon $\tau_y$ où $y$ est le coup joué en premier par le premier +joueur, autrement dit, $\tau'(z_0,\ldots,z_{\ell-1}) = +\tau_{z_1}(z_{\ell-1})$. Il est alors clair que si +$x_0,x_1,x_2,\ldots$ est jouée selon $\tau'$ par le second joueur, +alors $x_1,x_2,x_3,\ldots$ est jouée selon $\tau_{x_1}$ par le premier +joueur, et comme $\tau_{x_1}$ est survivante, c'est que $\tau'$ l'est +aussi : ceci montre l'implication réciproque. +\end{proof} \begin{thm}\label{determinacy-of-perfect-information-games} Soit $G$ un jeu impartial à information parfaite : exactement l'une |