From d227a889dead368877ec40f2f9f4307b78730633 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 22 Feb 2016 16:32:37 +0100
Subject: Various clarifications and additions (notably, coin-turning games).

---
 notes-mitro206.tex | 123 +++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 115 insertions(+), 8 deletions(-)

(limited to 'notes-mitro206.tex')

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.
-- 
cgit v1.2.3

