Describe chomp and Hackenbush.

1 files changed, 123 insertions, 5 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 1ef6cf7..f50a49d 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -490,11 +490,25 @@ lequel on étudie la théorie combinatoire des jeux impartiaux à
 information parfaite
 (cf. \ref{definition-impartial-combinatorial-game}), et qu'un des
 joueurs a forcément une stratégie gagnante ou bien les deux joueurs
-une stratégie assurant le nul (si le nul est possible).
+une stratégie assurant le nul (si le nul est possible)
+(cf. \ref{determinacy-of-perfect-information-games}).
 
 Dans une variante du jeu, celui qui ne peut plus jouer gagne au lieu
 de perdre : on parle alors de la variante « misère » du jeu.
 
+On peut aussi considérer un graphe dont les arêtes peuvent être
+coloriées de trois couleurs possibles : des arêtes rouges, qui ne
+peuvent être suivies que par Alice, des arêtes bleues, qui ne peuvent
+être suivies que par Bob, et des arêtes vertes (équivalentes à une
+arête rouge \emph{et} une arête bleue entre les mêmes deux sommets),
+qui peuvent être suivies par l'un ou l'autre joueur (le cas précédent
+est donc équivalent à celui d'un graphe entièrement vert).  Il s'agira
+là du cadre général dans lequel on étudie la théorie combinatoire des
+jeux \emph{partiaux} à information parfaite : on verra que, si le nul
+est rendu impossible, quatre cas sont possibles (Alice a une stratégie
+gagnante qui que soit le joueur qui commence, ou Bob en a une, ou le
+premier joueur a une stratégie gagnante, ou le second en a une).
+
 \thingy Le \textbf{jeu de Nim} : un certain nombre d'allumettes sont
 arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
 retirent des allumettes, au moins une à chaque fois, et autant qu'ils
@@ -509,10 +523,114 @@ qui).
 \thingy Jeux de retournement de pièces.  \textcolor{red}{...}
 
 \thingy Le jeu de \textbf{chomp} ou de la tablette de chocolat (ou
-gaufre) empoisonnée.  \textcolor{red}{...}
+gaufre) empoisonnée.
+
+On part d'une « tablette de chocolat » de taille $m\times n$,
+c'est-à-dire le produit $\{0,\ldots,m-1\} \times \{0,\ldots,n-1\}$
+dont les éléments (les couples $(i,j)$ avec $0\leq i<m$ et $0\leq
+j<n$) sont appelés les « carrés » de la tablette ; un état général du
+jeu sera un sous-ensemble de ce produit (l'ensemble des carrés restant
+à manger).  Le carré $(0,0)$ est empoisonné et le but est de ne pas le
+manger.  Un coup consiste à choisir un carré $(i,j)$ où mordre dans la
+tablette, ce qui fait disparaître tous les carrés $(i',j')$ avec
+$i'\geq i$ et $j'\geq j$.  Chaque joueur, tour à tour, effectue un
+coup de la sorte, et le premier à mordre dans la case empoisonnée
+$(0,0)$ a perdu (de façon équivalente, on ne peut pas mordre dedans,
+ce qui se ramène au formalisme général où le premier qui ne peut pas
+jouer a perdu).
+
+On ne sait pas décrire la stratégie gagnante en général, mais on peut
+montrer que, partant d'une tablette rectangulaire (ou carrée) $m\times
+n$ (par opposition à une forme irrégulière quelconque), le
+\emph{premier joueur} a forcément une stratégie gagnante.  En effet,
+en admettant provisoirement
+(cf. \ref{determinacy-of-perfect-information-games}) qu'un des deux
+joueurs a une stratégie gagnante, montrons qu'il s'agit forcément du
+premier ; pour cela, supposons par l'absurde que le second joueur ait
+une stratégie gagnante, et considérons la réponse $(i,j)$ préconisée
+par cette stratégie si le premier joueur joue en mordant la case
+$(m-1,n-1)$ opposée à la case empoisonnée : à partir de l'état obtenu
+en jouant cette réponse (i.e., toutes les cases $(i',j')$ avec $i'\geq
+i$ et $j'\geq j$ ont été mangées), le joueur qui vient de jouer est
+censé avoir une stratégie gagnante ; mais si le premier joueur jouait
+directement en mordant en $(i,j)$, il se ramènerait à cet état, les
+rôles des joueurs étant inversés, donc il aurait une stratégie
+gagnante, et cela signifie qu'il en a une dès le premier tour.
+
+\thingy Le jeu de \textbf{Hackenbush} impartial, bicolore, ou
+tricolore.
+
+Dans ce jeu, l'état est défini par un dessin, plus précisément un
+graphe non orienté, pouvant avoir des arêtes multiples et des arêtes
+reliant un sommet à lui-même, dont certains sommets sont « au sol »
+(graphiquement représentés en les plaçant sur une droite horizontale
+en bas du dessin).  Chaque sommet et chaque arête doit être « relié au
+  sol », c'est-à-dire atteignable depuis un sommet au sol par une
+succession d'arêtes.  De plus, dans le cas de Hackenbush bicolore,
+chaque arête est coloriée rouge ou bleue, dans le cas de Hackenbush
+tricolore elle peut aussi être verte, et dans le cas de Hackenbush
+impartial il n'y a pas de couleur, ou, si on préfère, toutes les
+arêtes sont vertes.
+
+\begin{center}
+\begin{tikzpicture}
+\draw[very thin] (-0.5,0) -- (3.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (1.5,0) {};
+\node (P2) at (0.75,1) {};
+\node (P3) at (0.75,2.5) {};
+\node (P4) at (0,2) {};
+\node (P5) at (1.5,2) {};
+\node (Q0) at (3,0) {};
+\node (Q1) at (3,1.5) {};
+\node (Q2) at (3,3) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw[color=green] (P0) -- (P2);
+\draw[color=green] (P1) -- (P2);
+\draw[color=green] (P2) -- (P3);
+\draw[color=green] (P3) -- (P4);
+\draw[color=green] (P3) -- (P5);
+\draw[color=green] (P3) .. controls (1.0,2.75) and (1.0,3.0) .. (0.75,3.0) .. controls (0.5,3.0) and (0.5,2.75) .. (P3);
+\draw[color=red] (Q0) -- (Q1);
+\draw[color=blue] (Q1) -- (Q2);
+\end{scope}
+\end{tikzpicture}
+\\{\footnotesize (Un état possible de Hackenbush.)}
+\end{center}
 
-\thingy Le jeu de Hackenbush impartial, bicolore, ou
-tricolore. \textcolor{red}{...}
+Alice et Bob jouent tour à tour, chacun efface une arête du dessin, ce
+qui fait disparaître du même coup toutes les arêtes et tous les
+sommets qui ne sont plus reliés au sol.  (Par exemple, dans le dessin
+représenté ci-dessus, si on efface l'arête rouge, l'arête bleue
+au-dessus disparaît immédiatement ; si on efface l'une des deux arêtes
+vertes reliées au sol, les « jambes » du « bonhomme » vert, rien de
+particulier ne se passe mais si on efface la deuxième, toutes les
+arêtes vertes disparaissent.)  Dans le jeu de Hackenbush impartial,
+n'importe quel joueur peut effacer n'importe quelle arête ; dans le
+jeu bicolore, seule Alice peut effacer les arêtes rouges et seul Bob
+peut effacer les arêtes bleues ; dans le jeu tricolore, les arêtes
+vertes sont effaçables par l'un ou l'autre joueur (mais dans tous les
+cas, la disparition des arêtes non reliées au sol est automatique).
+Le jeu se termine quand un joueur ne peut plus jouer, auquel cas il a
+perdu (au Hackenbush impartial, cela signifie que le jeu se termine
+quand un joueur finit de faire disparaître le dessin, auquel cas il a
+gagné ; au Hackenbush bicolore ou tricolore, il se peut bien sûr qu'il
+reste des arêtes de la couleur du joueur qui vient de jouer).
+
+Le jeu de Hackenbush impartial possède une stratégie gagnante soit par
+le premier soit par le second joueur (le dessin formé uniquement des
+arêtes vertes ci-dessus, par exemple, est gagnable par le premier
+joueur, le seul coup gagnant consistant à effacer le « corps » du
+« bonhomme » pour ne laisser que ses jambes).  Le jeu de Hackenbush
+bicolore possède une stratégie gagnante soit pour Alice, soit pour
+Bob, soit pour le second joueur, mais jamais pour le premier (le
+dessin formé par les arêtes rouge et bleue ci-dessus, par exemple, est
+gagnable par Alice).  Le jeu de Hackenbush tricolore possède une
+stratégie gagnante soit pour Alice, soit pour Bob, soit pour le
+premier joueur, soit pour le second (l'ensemble du dessin ci-dessus,
+par exemple, est gagnable par Alice).
 
 \thingy Le \textbf{jeu de l'hydre} : Hercule essaie de terrasser
 l'hydre.  Le joueur qui joue l'hydre commence par dessiner (i.e.,
@@ -1663,7 +1781,7 @@ survivante (c'est-à-dire, permettant d'assurer au moins le nul) pour
 Alice, resp. Bob.
 \end{defn}
 
-\begin{thm}
+\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}