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