More clarifications on impartial p.i. games (and player naming).

1 files changed, 79 insertions, 31 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index c8d954c..c391a88 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1951,9 +1951,13 @@ et vérifiant de plus :
 \item pour un jeu « non nécessairement terminant » : (aucune
   hypothèse).
 \end{itemize}
-On supposera de plus que tout sommet de $G$ est accessible à partir
-de $x_0$ (si ce n'est pas le cas, il reviendra au même de supprimer
-tous les sommets inaccessibles, assurant du coup cette hypothèse).
+Les sommets de $G$ sont aussi appelés les \textbf{positions} de $G$,
+et les voisins sortants d'une position $x \in G$ sont aussi appelés
+les \textbf{options} à partir de $x$.
+
+On supposera que tout sommet de $G$ est accessible à partir de $x_0$ ;
+si ce n'est pas le cas, il reviendra au même de supprimer tous les
+sommets inaccessibles, assurant du coup cette hypothèse.
 \end{defn}
 
 La terminologie est malheureusement peu standardisée : la plupart des
@@ -1964,53 +1968,97 @@ l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait
 que cela signifie que $x_0$ appartient à la partie bien-fondée
 (cf. \ref{definition-wfpart}) du graphe $G$.
 
+\thingy\label{playing-from-a-position} Si $G$ est un jeu comme
+en \ref{definition-impartial-combinatorial-game}, et $x \in G$ une
+position quelconque de $G$, on définit le jeu joué \textbf{à partir}
+de $x$ comme l'aval de $x$ (c'est-à-dire l'ensemble des positions
+accessibles à partir de $x$,
+cf. \ref{definition-accessibility-downstream}) considéré comme un
+graphe (le sous-graphe induit) et muni du sommet $x$ lui-même comme
+position initiale.  Ceci définit un nouveau jeu qui sera parfois noté
+$G_x$ et qui sera parfois identifié à $x$ quand aucune confusion ne
+peut en résulter.  (Ainsi, $G_{x_0}$ est exactement $G$.)
+
+De façon moins formelle : on peut toujours considérer une position $x$
+quelconque d'un jeu $G$ comme position initiale d'un nouveau jeu (le
+jeu joué si une fois atteinte la position $x$).  Cette remarque
+triviale permet de considérer n'importe quelle fonction d'un jeu
+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 est forfait).
+le joueur abandonne la partie).
 
 Une \textbf{partie} 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
-un $i$ pair, on dit qu'Alice \textbf{perd} et que Bob \textbf{gagne},
-tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair,
-on dit qu'Alice gagne et que Bob 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 qu'Alice 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 Bob a joué la partie
-selon la stratégie $\tau$.
+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$ (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 Alice joue $\varsigma$ et Bob
-joue $\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 Alice} lorsque
-Alice gagne toute partie où elle joue selon $\varsigma$.  La stratégie
-$\tau$ est dite \textbf{gagnante pour Bob} lorsque Bob 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
-Alice, resp. Bob.
+\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.
 \end{defn}
 
+\thingy Il est parfois plus agréable de donner aux joueurs des noms
+comme « Alice » et « Bob ».  Il faut néanmoins se rappeler, dans la
+théorie des jeux \emph{impartiaux} considérée dans cette section, que
+l'identité des joueurs n'est inscrite nulle part dans le jeu : ils ont
+tous les deux toutes les options possibles depuis chaque position
+(comparer le jeu de Hackenbush impartial avec les autres
+en \ref{introduction-hackenbush}).
+
+Plutôt que de parler de « premier » et de « second » joueur, on peut
+aussi parler de \textbf{joueur suivant} et de \textbf{joueur
+  précédent} : le joueur suivant est celui qui doit jouer,
+c'est-à-dire le premier, et le joueur précédent est celui qui vient de
+jouer, c'est-à-dire le second.  (Ceci est d'ailleurs très malheureux
+compte tenu des initiales de ces quatre mots...)  Il peut paraître
+bizarre de dire que le second joueur « vient de jouer » quand on
+commence la partie, mais c'est logique vu que c'est à l'autre de
+jouer, et c'est cohérent avec la
+convention \ref{playing-from-a-position} : si on a atteint la position
+$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.
+
 \begin{thm}\label{determinacy-of-perfect-information-games}
 Soit $G$ un jeu impartial à information parfaite : exactement l'une
 des trois affirmations suivantes est vraie :
 \begin{itemize}
-\item Alice possède une stratégie gagnante,
-\item Bob possède une stratégie gagnante,
-\item Alice et Bob possèdent une stratégie survivante — ce cas ne
-  pouvant pas se produire si $G$ est terminant.
+\item le premier joueur (=joueur suivant) possède une stratégie gagnante,
+\item le second joueur (=joueur précédent) possède une stratégie gagnante,
+\item chacun des deux joueurs possède une stratégie survivante — ce
+  cas ne pouvant pas se produire si $G$ est terminant.
 \end{itemize}
 \end{thm}
 \begin{proof}