diff options
| -rw-r--r-- | notes-mitro206.tex | 123 |
1 files changed, 115 insertions, 8 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 11fd8c2..35ddb9c 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -283,7 +283,8 @@ que fasse l'autre joueur). intéressant d'essayer d'exploiter le fait que les humains ont des générateurs aléatoires assez mauvais, et d'arriver à prédire leurs coups pour gagner. Ceci est particulièrement amusant avec des petits -enfants. Voir aussi le film \textit{Princess Bride} à ce sujet.) +enfants. Voir aussi la « battle of wits » du film \textit{Princess + Bride} à ce sujet.) \thingy Le jeu de \textbf{pierre-papier-ciseaux} : Alice et Bob choisissent simultanément un élément de l'ensemble @@ -384,6 +385,18 @@ chaque joueur a intérêt à faire le contraire de ce que fait l'autre (si Bob joue faucon, Alice a intérêt à jouer colombe, et si Bob joue colombe, Alice a intérêt à jouer faucon). +(Pour justifier le nom de « jeu du trouillard », on peut évoquer le +scénario d'une course de voitures vers une falaise, à la façon du film +\textit{La Fureur de vivre} : jouer colombe, c'est arrêter sa voiture +avant d'arriver à la falaise, et jouer faucon, c'est ne pas s'arrêter +sauf si l'autre s'est arrêté : celui qui s'arrête passe pour un +trouillard et perd le jeu, mais si aucun ne s'arrête, les deux +voitures tombent dans la falaise, ce qui est pire que de passer pour +un trouillard.) + +Ce jeu présente par exemple un intérêt en biologie, notamment pour ce +qui est de l'évolution des comportements. + On pourra se convaincre que ce jeu a trois équilibres de Nash (cf. \ref{definition-best-response-and-nash-equilibrium} ; en gros, il s'agit d'une situation dans laquelle aucun des joueurs n'améliorerait @@ -411,6 +424,10 @@ Boxe&$0,0$&$1,2$\\ Ou plus généralement, en remplaçant $2,1,0$ par trois nombres $P$ (préféré), $Q$ (autre), $N$ (nul) tels que $P>Q>N$. +Ce jeu présente par exemple un intérêt en sociologie, notamment pour +ce qui est de la synchronisation aoutour d'une ressource commune (par +exemple l'adoption d'un standard). + On pourra se convaincre que ce jeu a trois équilibres de Nash (cf. \ref{definition-best-response-and-nash-equilibrium}) : l'un où les deux joueurs vont à l'alpinisme, un deuxième où les deux vont à la @@ -509,18 +526,108 @@ 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 +\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 veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui retire la dernière allumette (de façon équivalente, le perdant est -celui qui ne peut pas jouer). Il s'agit ici d'un jeu à deux joueurs +celui qui ne peut pas jouer). Autrement dit, une position du jeu de +nim est une suite finie $(n_1,\ldots,n_r)$ d'entiers naturels +(représentant le nombre d'allumettes de chaque ligne), et un coup +possible à partir de cette position consiste à aller vers l'état +$(n'_1,\ldots,n'_r)$ où $n'_i = n_i$ pour tout $i$ sauf exactement un +pour lequel $n'_i < n_i$. Il s'agit ici d'un jeu à deux joueurs impartial à connaissance parfaite (un cas particulier du jeu général -défini en \ref{introduction-graph-game}) : on verra que la théorie de -Grundy permet de décrire exactement la stratégie gagnante (et pour -qui). - -\thingy Jeux de retournement de pièces. \textcolor{red}{...} +défini en \ref{introduction-graph-game}). On verra que la théorie de +Grundy permet de décrire exactement la stratégie gagnante : en +anticipant sur la suite, il s'agit de calculer le XOR (= « ou + exclusif », appelé aussi \textit{somme de nim} dans ce contexte des +nombres $n_i$ d'allumettes des différentes lignes (écrits en +binaire) : ce XOR s'appelle la \textit{fonction de Grundy} de la +position, et le jeu est gagnable par le second joueur (c'est-à-dire, +celui qui \emph{vient de} jouer) si et seulement cette fonction de +Grundy vaut $0$. (À titre d'exemple, la position de départ la plus +courante du jeu de nim est $(1,3,5,7)$, et comme $\mathtt{001} \oplus +\mathtt{011} \oplus \mathtt{101} \oplus \mathtt{111} = \mathtt{000}$ +en binaire, en notant $\oplus$ pour le XOR, le second joueur a une +stratégie gagnante.) + +On peut aussi jouer à la variante « misère » du jeu : celui qui prend +la dernière allumette a perdu (cf. le film \textit{L'année dernière à + Marienbad}) ; néanmoins, elle se ramène assez facilement à la +variante « normale » (où celui qui prend la dernière allumette a +gagné), cette dernière ayant plus d'intérêt mathématique. + +Le jeu de nim apparaît sous différents déguisements. On peut par +exemple évoquer le suivant, complètement équivalent à ce qu'on vient +de dire : on place $r$ jetons sur un plateau formé d'une seule ligne +dont les cases sont numérotées $0,1,2,3,\ldots$ (de la gauche vers la +droite, pour fixer les idées). Chacun tour à tour déplace un jeton +vers la gauche ; plusieurs jetons ont le droit de se trouver sur la +même case, et ils peuvent passer par-dessus l'un l'autre. Le perdant +est celui qui ne peut plus jouer (parce que tous les jetons sont sur +la case la plus à gauche, $0$). Il s'agit exactement du jeu de nim, +en considérant que la position où les jetons sont sur les cases +$n_1,\ldots,n_r$ correspond à celle du jeu de nim où il y a +$n_1,\ldots,n_r$ allumettes sur les différentes lignes. C'est ce +point de vue qui suggère le type de jeux suivant : + +\thingy Jeux de \textbf{retournement de pièces}. Ici une position est +une rangée de pièces (qui pourront être numérotées, de la gauche vers +la droite, de $0$ à $N-1$ ou de $1$ à $N$, selon la commodité du jeu), +chacune en position « pile vers le haut » (qu'on notera $\mathtt{0}$) +ou « face vers le haut » ($\mathtt{1}$). Chaque joueur tour à tour va +retourner certaines pièces selon des règles propres au jeu, avec +toujours la règle générale que \textit{au moins une pièce est + retournée, et la plus à droite à être retournée doit passer de face + à pile} (d'autres pièces peuvent passer de pile à face, et d'autres +pièces plus à droite peuvent rester sur pile ou rester sur face, mais +la plus à droite parmi les pièces qui se font retourner devait être +face avant le mouvement et devient du coup pile). Cette règle +générale assure que le nombre binaire formé de l'ensemble des pièces, +lues de la droite vers la gauche, diminue strictement à chaque coup, +et donc que le jeu termine forcément en temps fini. Le joueur qui ne +put plus jouer a perdu. + +Il faut bien sûr mettre des règles supplémentaires restreignant les +retournements possibles, sinon le jeu n'a aucun intérêt (le premier +joueur met toutes les pièces à montrer pile et gagne immédiatement). +Quelques exemples de telles règles peuvent être : +\begin{itemize} +\item On ne peut retourner qu'une pièce à chaque coup. Dans ce cas, + seul importe le nombre de pièces montrant face, et les joueurs n'ont + essentiellement aucun choix dans le coup à jouer : peu importe la + pièce retournée (qui passe forcément de face à pile) ; si le nombre + de pièces montrant face est pair, le second joueur gagne, tandis que + s'il est impair, c'est le premier qui gagne. Ce jeu est très peu + intéressant. +\item On retourne exactement deux pièces à chaque coup (toujours avec + la règle générale que la plus à droite des deux passe de face à + pile). Il s'agit de nouveau du jeu de nim déguisé (mais un peu + mieux) : si les pièces sont numérotées à partir de $0$ (la plus à + gauche), retourner les pièces $n$ et $n'<n$ peut se comprendre comme + faire passer une ligne d'allumettes de $n$ à $n'$ allumettes, avec + la différence que deux lignes identiques disparaissent mais on peut + montrer que cette différence n'a aucun impact sur le jeu de nim + (essentiellement parce que deux lignes identiques s'« annulent » : + si un joueur prend des allumettes de l'une, l'autre peut faire le + même coup sur l'autre). +\item On retourne \emph{une ou deux} pièces (toujours avec la règle + générale que la plus à droite des deux passe de face à pile). Il + s'agit encore une fois de nim déguisé, mais cette fois en numérotant + les pièces à partir de $1$ (retourner une seule pièce revient à + vider une ligne de nim, en retourner deux revient à diminuer le + nombre de pièces d'une ligne). +\item On retourne \emph{au plus trois} pièces (toujours avec la règle + générale). On peut décrire la stratégie gagnante dans ce jeu en + rapport avec le code de parité binaire. Plus généralement, les jeux + où on retourne au plus $s$ pièces peuvent, pour les petites valeurs + de $s$, être reliés à des codes correcteurs remarquables. +\item On retourne n'importe quel nombre de pièces, mais elles doivent + être consécutives (et toujours avec la règle générale que la pièce + retournée la plus à droite passe de face à pile). Il est assez + facile de décrire la stratégie gagnante de ce jeu. +\end{itemize} \thingy Le jeu de \textbf{chomp} ou de la tablette de chocolat (ou gaufre) empoisonnée. |