summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex84
1 files changed, 48 insertions, 36 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 8bd781f..d30e163 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1982,14 +1982,15 @@ 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).
+ initiale}. Le \textbf{jeu combinatoire 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
@@ -2007,27 +2008,36 @@ est nulle ou que les deux joueurs \textbf{survivent} sans gagner.
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.
+pas un voisin sortant du sommet actuel), il a immédiatement perdu — il
+n'y a manifestement pas grande différence entre avoir un jeu où un
+joueur \emph{ne peut pas} faire un certain coup et un jeu où si ce
+joueur fait ce coup il a immédiatement perdu (quoi qu'il se passe par
+la suite). On va définir deux jeux de Gale-Stewart plutôt qu'un parce
+qu'un jeu de Gale-Stewart a forcément un gagnant (il n'y a pas de
+partie nulle), donc on va définir un jeu où les parties nulles sont
+comptées au bénéfice de Bob et un autre où elles sont comptées au
+bénéfice d'Alice.
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).
+\item l'ensemble $D$ des (confrontations nulles dans le jeu
+ combinatoire, 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 dans le jeu
+ combinatoire, 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 dans le jeu
+ combinatoire, 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
@@ -2036,9 +2046,9 @@ 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.
+ceci près que les confrontations nulles sont comptées 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
@@ -2057,8 +2067,8 @@ 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
+Soit $(G,x_0)$ un jeu combinatoire 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,
@@ -2078,13 +2088,15 @@ 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.
+les jeux définis par l'ouvert $A$ et le fermé $A \cup D = X\setminus
+B$ sont déterminés.
+
+Mais une stratégie gagnante d'Alice dans le jeu de Gale-Stewart défini
+par $A$ est une stratégie gagnante dans le jeu combinatoire d'origine,
+tandis qu'une stratégie gagnante de Bob dans ce jeu de Gale-Stewart
+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