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