summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex183
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