summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-22 15:32:37 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-02-22 15:32:37 (GMT)
commitd227a889dead368877ec40f2f9f4307b78730633 (patch)
tree83a69c8771195ec417fc8cd293bbd85d3dfe026a /notes-mitro206.tex
parent362ce5d5dc7aa081696c0707d52111947a69c31a (diff)
downloadmitro206-d227a889dead368877ec40f2f9f4307b78730633.zip
mitro206-d227a889dead368877ec40f2f9f4307b78730633.tar.gz
mitro206-d227a889dead368877ec40f2f9f4307b78730633.tar.bz2
Various clarifications and additions (notably, coin-turning games).
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex123
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.