summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-31 17:16:02 +0200
committerDavid A. Madore <david+git@madore.org>2017-03-31 17:16:02 +0200
commit2ceae34ae7aea08cb1d403c5416243302d65a1ec (patch)
tree7260bb06645b884bc31aff6e64eefd2a40b968bd /notes-mitro206.tex
parent943f4c81351fa2975951991db92112d268e96328 (diff)
downloadmitro206-2ceae34ae7aea08cb1d403c5416243302d65a1ec.tar.gz
mitro206-2ceae34ae7aea08cb1d403c5416243302d65a1ec.tar.bz2
mitro206-2ceae34ae7aea08cb1d403c5416243302d65a1ec.zip
Discuss Conway equivalence of impartial games (equality of Grundy) a bit more.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex31
1 files changed, 30 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 5de1ca7..6559c17 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -5400,6 +5400,35 @@ faculté la consomme pour tout le monde, et le jeu n'est fini qu'une
fois ce tour consommé) : en effet, c'est simplement une reformulation
du jeu $G \oplus *1$.
+\thingy On peut définir une relation d'équivalence $\doteq$ entre jeux
+combinatoires impartiaux bien-fondés par : $G \doteq H$ lorsque le
+second joueur possède une stratégie gagnante au jeu $G\oplus H$
+(c'est-à-dire que [la position initiale de] $G\oplus H$ est une
+P-position, ou encore que sa valeur de Grundy est nulle).
+
+Selon le modèle de \ref{conway-equivalence-on-partizan-games} plus
+bas, on peut montrer que $\doteq$ est une relation d'équivalence et
+qu'elle est compatible avec la somme de nim (c'est-à-dire que si
+$G\doteq G'$ et $H\doteq H'$ alorsq $G\oplus H \doteq G'\oplus H'$) :
+le point crucial est que si le second joueur possède une stratégie
+gagnante à un jeu $G_0$ alors le joueur qui a une stratégie gagnante à
+$G\oplus G_0$ est le même qu'à $G$ (comparer
+avec \ref{basic-facts-on-sum-of-partizan-games} ci-dessous).
+
+Cette relation $\doteq$ sera particulièrement pertinente pour les jeux
+partisans (dont la théorie est esquissée dans la
+section \ref{section-combinatorial-partizan-games} ci-dessous), mais
+dans le cas des jeux impartiaux considérés ici, elle est complètement
+contenue dans la valeur de Grundy : on a $G\doteq H$ si et seulement
+si $\gr(G) = \gr(H)$ (en effet, $G\doteq H$ équivaut par définition au
+fait que le second joueur ait une stratégie gagnante à $G\oplus H$,
+c'est-à-dire $\gr(G\oplus H) = 0$, ce qui
+d'après \ref{nim-sum-for-games-versus-ordinals} signifie $\gr(G)
+\oplus \gr(H) = 0$, autrement dit,
+cf. \ref{nim-sum-has-characteristic-two}, que $\gr(G) = \gr(H)$).
+Bref, les « classes d'équivalence » pour la relation $\doteq$ sont
+précisément données par les ordinaux à travers la valeur de Grundy.
+
\thingy À côté de la somme de nim définie
en \ref{definition-nim-sum-of-ordinals}, il existe aussi une opération
de \index{nim (produit de)|see{produit de nim}}\defin{produit de nim}
@@ -5618,7 +5647,7 @@ strictement plus favorable à Blaise que $H$).
Sous ces conditions :
-\begin{prop}
+\begin{prop}\label{conway-equivalence-on-partizan-games}
La relation $\doteq$ est une relation d'équivalence. Elle est
compatible à la somme (c'est-à-dire que si $G \doteq G'$ et $H \doteq
H'$ alors $G + H \doteq G' + H'$) ainsi qu'aux relations $>$, $\geq$,