diff options
| -rw-r--r-- | notes-mitro206.tex | 84 |
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 |