summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-25 18:00:43 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-02-25 18:00:43 (GMT)
commit9edf96a06b84c8c1d739c69c9bc276aff4347a16 (patch)
tree07d999028994935c3be5ec69942d69c1ea6182e4 /notes-mitro206.tex
parent043e8a416ff9da0dabb6416d5d0af54a434502a6 (diff)
downloadmitro206-9edf96a06b84c8c1d739c69c9bc276aff4347a16.zip
mitro206-9edf96a06b84c8c1d739c69c9bc276aff4347a16.tar.gz
mitro206-9edf96a06b84c8c1d739c69c9bc276aff4347a16.tar.bz2
Determinacy of perfect information games from Gale-Stewart games.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex155
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}$.