summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-22 18:33:02 +0100
committerDavid A. Madore <david+git@madore.org>2016-02-22 18:33:02 +0100
commit1daaad9046fe0606a213b0a2678ea269ddeeec36 (patch)
tree09cc90062372bf6f88ecc3b05de98699a23358bf
parentfa3b195b70dadf6a9d920826b6432b03546f875c (diff)
downloadmitro206-1daaad9046fe0606a213b0a2678ea269ddeeec36.tar.gz
mitro206-1daaad9046fe0606a213b0a2678ea269ddeeec36.tar.bz2
mitro206-1daaad9046fe0606a213b0a2678ea269ddeeec36.zip
More clarifications on impartial p.i. games (and player naming).
-rw-r--r--notes-mitro206.tex110
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}