summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-03-23 13:56:22 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-03-23 13:56:22 (GMT)
commit807ea647844b24f5afe9a285312d6fef2a8f2f00 (patch)
treebb24645b0eaca4bc49752e5396446fbfc17e06ed
parente8e5db2025c888744564e0d82960d4775cb1dd1f (diff)
downloadmitro206-807ea647844b24f5afe9a285312d6fef2a8f2f00.zip
mitro206-807ea647844b24f5afe9a285312d6fef2a8f2f00.tar.gz
mitro206-807ea647844b24f5afe9a285312d6fef2a8f2f00.tar.bz2
Start part on impartial combinatorial games. Also, clearly rename top-level sections as "parts".
-rw-r--r--notes-mitro206.tex221
1 files changed, 173 insertions, 48 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index bd89ae5..a9ccf7f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -44,6 +44,8 @@
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\limp}{\Longrightarrow}
+\newcommand{\gr}{\operatorname{gr}}
+\newcommand{\rk}{\operatorname{rk}}
%
\DeclareUnicodeCharacter{00A0}{~}
%
@@ -875,7 +877,7 @@ stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
a une.
\thingy\label{introduction-gale-stewart-games} Les \defin[Gale-Stewart (jeu de)]{jeux de
- Gale-Stewart} (cf. section \ref{gale-stewart-games}) : soit $A$ un sous-ensemble de
+ Gale-Stewart} (cf. partie \ref{section-gale-stewart-games}) : soit $A$ un sous-ensemble de
$\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$.
Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans
le premier cas) ou de $\{0,1\}$ (dans les deux suivants). Ils jouent
@@ -967,7 +969,7 @@ véritablement changer le jeu.
\subsection{Plan}
-La section \ref{section-games-in-normal-form} concerne les jeux en
+La partie \ref{section-games-in-normal-form} concerne les jeux en
forme normale et la notion d'équilibre de Nash : on gardera donc à
l'esprit les exemples tels que le dilemme du
prisonnier (\ref{prisonners-dilemma}), le
@@ -976,15 +978,17 @@ sexes (\ref{battle-of-sexes}). On évoque plus particulièrement les
jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des
jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}).
-La section \ref{gale-stewart-games} introduit la notion de jeux de
+La partie \ref{section-gale-stewart-games} introduit la notion de jeux de
Gale-Stewart et prouve un théorème fondamental de détermination (la
détermination des jeux \emph{ouverts}).
-La section \ref{section-well-founded-induction} introduit la notion de
+La partie \ref{section-well-founded-induction} introduit la notion de
graphe bien-fondée et d'induction bien-fondée qui est essentielle pour
-la suite.
+la suite. La partie \ref{section-ordinals} introduit la notion
+d'ordinaux qui permet de généraliser beaucoup de résultats du fini à
+l'infini.
-La section \ref{section-combinatorial-impartial-games} concerne la
+La partie \ref{section-combinatorial-impartial-games} concerne la
théorie, dite « combinatoire », des jeux impartiaux à information
parfaite, dont le modèle est décrit en \ref{introduction-graph-game}
(sans coloriage) et dont l'archétype est le jeu de nim
@@ -1463,7 +1467,7 @@ joueurs.
%
%
-\section{Jeux de Gale-Stewart et détermination}\label{gale-stewart-games}
+\section{Jeux de Gale-Stewart et détermination}\label{section-gale-stewart-games}
\subsection{Définitions}
@@ -1989,7 +1993,7 @@ On va définir ici rapidement les notions relatives aux jeux impartiaux
ramener à des jeux de Gale-Stewart et comment la détermination des
jeux ouverts peut s'appliquer dans ce contexte :
-\begin{defn}\label{first-definition-impartial-combinatorial-game}
+\begin{defn}\label{definition-impartial-combinatorial-game}
Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une
relation $E$ irréflexive dont les éléments sont appelés arêtes du
graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions
@@ -2018,7 +2022,7 @@ est nulle ou que les deux joueurs \defin[survie]{survivent} sans gagner.
\end{defn}
\thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme
-en \ref{first-definition-impartial-combinatorial-game}, va définir un,
+en \ref{definition-impartial-combinatorial-game}, va définir un,
ou plutôt deux, jeux de Gale-Stewart : l'intuition est que si un
joueur enfreint la « règle » du jeu (i.e., choisit un sommet qui n'est
pas un voisin sortant du sommet actuel), il a immédiatement perdu — il
@@ -2058,7 +2062,7 @@ Gale-Stewart ! Si on préfère, on peut les faire commencer à $0$, et
mettre dans $A$ toutes les suites qui ne commencent pas par $x_0$.)
Le jeu de Gale-Stewart $G_X(A)$ est essentiellement identique au jeu
-considéré en \ref{first-definition-impartial-combinatorial-game}, à
+considéré en \ref{definition-impartial-combinatorial-game}, à
ceci près que les confrontations nulles sont comptées comme des gains
de Bob ; le jeu $G_X(A \cup D)$, pour sa part, est lui aussi identique
à ceci près que les nuls sont comptés comme des gains d'Alice.
@@ -2081,7 +2085,7 @@ pair.
\begin{thm}\label{determinacy-of-perfect-information-games}
Soit $(G,x_0)$ un jeu combinatoire impartial à information parfaite
-comme en \ref{first-definition-impartial-combinatorial-game}. Alors
+comme en \ref{definition-impartial-combinatorial-game}. Alors
exactement l'une des trois affirmations suivantes est vraie :
\begin{itemize}
\item le premier joueur (Alice) possède une stratégie gagnante,
@@ -2137,7 +2141,7 @@ qui va être démontré dans la section suivante.
\thingy Le but de la définition suivante est de formaliser, pour un
jeu combinatoire comme
-en \ref{first-definition-impartial-combinatorial-game}, les notions de
+en \ref{definition-impartial-combinatorial-game}, les notions de
stratégie positionnelle (dans laquelle un joueur ne choisit le coup à
jouer qu'en fonction de la position actuelle), et de stratégie
historique (dans laquelle il fait son choix en fonction de tous les
@@ -2149,7 +2153,7 @@ se contenter de lire celle-ci.
\begin{defn}
Soit $G$ un graphe orienté
-(cf. \ref{first-definition-impartial-combinatorial-game} et \ref{definitions-graphs}).
+(cf. \ref{definition-impartial-combinatorial-game} et \ref{definitions-graphs}).
Une \index{positionnelle (stratégie)}\defin{stratégie positionnelle} sur $G$ est une fonction
partielle $\varsigma\colon G \dasharrow G$ (i.e., une fonction définie
sur un sous-ensemble de $G$) telle que $\varsigma(x)$ soit, s'il est
@@ -2404,7 +2408,7 @@ stratégie positionnelle.)
Soit $G$ un graphe orienté. Quel que soit le sommet $x_0$ de $G$
choisi comme position initiale, dans le jeu combinatoire impartial à
information parfaite considéré
-en \ref{first-definition-impartial-combinatorial-game}, exactement
+en \ref{definition-impartial-combinatorial-game}, exactement
l'une des trois affirmations suivantes est vraie :
\begin{itemize}
\item le premier joueur (Alice) possède une stratégie positionnelle gagnante,
@@ -2525,7 +2529,7 @@ démontré l'existence d'une plus petite $f$).
\section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction}
-Le but de cette section est de présenter les outils fondamentaux sur
+Le but de cette partie est de présenter les outils fondamentaux sur
les graphes orientés bien-fondés (cf. \ref{definitions-graphs})
utiles à la théorie combinatoire des jeux impartiaux. Il
s'agit notamment de la théorie de l'induction bien-fondée
@@ -2767,14 +2771,14 @@ bien-fondée :
Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
qu'un nombre fini de voisins sortants (par exemple, un graphe fini
acyclique). En utilisant le théorème \ref{well-founded-definition},
-on définit alors une fonction $\rho\colon G \to \mathbb{N}$ par
-$\rho(x) = \max\{\rho(y) : y\in\outnb(x)\} + 1$ où il est convenu que
+on définit alors une fonction $\rk\colon G \to \mathbb{N}$ par
+$\rk(x) = \max\{\rk(y) : y\in\outnb(x)\} + 1$ où il est convenu que
$\max\varnothing = -1$ ; formellement, c'est-à-dire qu'on pose
$\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$
-si $x$ est un puits, et qu'on appelle $\rho$ la fonction telle que
-$\rho(x) = \Phi(x, \rho|_{\outnb(x)})$ dont l'existence et l'unicité
-sont garanties par le théorème. Cette fonction $\rho$ s'appelle la
-\defin[rang]{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou
+si $x$ est un puits, et qu'on appelle $\rk$ la fonction telle que
+$\rk(x) = \Phi(x, \rk|_{\outnb(x)})$ dont l'existence et l'unicité
+sont garanties par le théorème. Cette fonction $\rk$ s'appelle la
+\defin[rang]{fonction rang} sur $G$, on dit que $\rk(x)$ est le rang (ou
rang bien-fondé) d'un sommet $x$. (Voir
aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
généralisation.)
@@ -2787,7 +2791,7 @@ tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de
rang exactement $1$, et ainsi de suite.
Il revient au même de définir le rang de la manière suivante : le rang
-$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus
+$\rk(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus
grande longueur possible d'un chemin orienté partant de $x$,
c'est-à-dire, le plus grand $n$ tel qu'il existe une suite
$x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le
@@ -2799,15 +2803,15 @@ Voici un autre exemple de définition par induction bien-fondée :
Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
qu'un nombre fini de voisins sortants. En utilisant le
théorème \ref{well-founded-definition}, on définit alors une fonction
-$\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(y) :
+$\gr\colon G \to \mathbb{N}$ par $\gr(x) = \mex\{\gr(y) :
y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
:= \mathbb{N}\setminus S$ pour le plus petit entier naturel
\emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose
$\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle
-$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
-\gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont
-garanties par le théorème. Cette fonction $\gamma$ s'appelle la
-\defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
+$\gr$ la fonction telle que $\gr(x) = \Phi(x,
+\gr|_{\outnb(x)})$ dont l'existence et l'unicité sont
+garanties par le théorème. Cette fonction $\gr$ s'appelle la
+\defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gr(x)$ est la
valeur de Grundy d'un sommet $x$. (Voir
aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
généralisation.)
@@ -2849,9 +2853,9 @@ N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous
sommet qui a au moins un P-sommet pour voisin sortant}.
\end{defn}
-\thingy Dans un jeu combinatoire comme exposé en
+\thingy\label{discussion-n-and-p-vertices} Dans un jeu combinatoire comme exposé en
\ref{introduction-graph-game} et/ou
-\ref{first-definition-impartial-combinatorial-game}, si le graphe est
+\ref{definition-impartial-combinatorial-game}, si le graphe est
bien-fondé, les P-sommets sont les positions du jeu à partir
desquelles le joueur Précédent (=second joueur) a une stratégie
gagnante, tandis que les N-sommets sont celles à partir desquelles le
@@ -2873,40 +2877,42 @@ en temps fini, et celui qui a joué pour aller vers les P-sommets aura
gagné puisqu'il peut toujours jouer).
\thingy Pour illustrer la technique de démonstration par induction
-bien-fondée, montrons que si $\gamma$ est la fonction de Grundy
+bien-fondée, montrons que si $\gr$ est la fonction de Grundy
introduite en \ref{definition-grundy-function} et si $P$ est la partie
introduite en \ref{definition-grundy-kernel}, alors on a $x \in P$ si
-et seulement si $\gamma(x) = 0$, i.e., les P-sommets sont ceux pour
+et seulement si $\gr(x) = 0$, i.e., les P-sommets sont ceux pour
lesquels la fonction de Grundy est nulle.
Par induction bien-fondé (cf. \ref{scholion-well-founded-induction}),
on peut supposer la propriété (« $x \in P$ si et seulement si
- $\gamma(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du
+ $\gr(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du
sommet $x$ où on cherche à la vérifier. Si $x \in P$, cela signifie
par définition de $P$ que tous ses voisins sortants $y$ de $x$ sont
dans $G \setminus P$, et d'après l'hypothèse d'induction cela signifie
-$\gamma(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire
-$\mex\{\gamma(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et
-seulement si $0 \not\in S$), ce qui signifie $\gamma(x) = 0$. Toutes
+$\gr(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire
+$\mex\{\gr(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et
+seulement si $0 \not\in S$), ce qui signifie $\gr(x) = 0$. Toutes
ces reformulations étaient des équivalences : on a bien montré que $x
-\in P$ équivaut à $\gamma(x) = 0$, ce qui conclut l'induction.
+\in P$ équivaut à $\gr(x) = 0$, ce qui conclut l'induction.
\thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant
sur la notion d'ordinaux introduite dans la
-section \ref{section-ordinals}, la fonction rang peut se généraliser à
+partie \ref{section-ordinals}, la fonction rang peut se généraliser à
n'importe quel graphe bien-fondé (sans hypothèse de nombre fini de
voisins sortants), à condition d'autoriser des valeurs ordinales
-quelconques : précisément, on définit $\rho(x) = \sup\{\rho(y)+1 :
+quelconques : précisément, on définit $\rk(x) = \sup\{\rk(y)+1 :
y\in\outnb(x)\}$ (avec cette fois $\sup\varnothing = 0$ pour garder
-$\rho(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rho(x)$ est le
-plus petit ordinal strictement supérieur à $\rho(y)$ pour tout
+$\rk(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rk(x)$ est le
+plus petit ordinal strictement supérieur à $\rk(y)$ pour tout
$y\in\outnb(x)$.
De même, la fonction de Grundy peut se généraliser à n'importe quel
-graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) :
+graphe bien-fondé en définissant $\gr(x) = \mex\{\gr(y) :
y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal
-\emph{n'appartenant pas} à $S$. Il reste vrai (avec la même
-démonstration) que $\gamma(x)$ est nul si et seulement si $x$ est un
+\emph{n'appartenant pas} à $S$
+(voir \ref{definition-grundy-function-again} pour une écriture
+formelle de cette définition). Il reste vrai (avec la même
+démonstration) que $\gr(x)$ est nul si et seulement si $x$ est un
P-sommet.
On peut donc résumer ainsi la stratégie gagnante « universelle » pour
@@ -3573,11 +3579,12 @@ est obligé de choisir un $N$ fini en formulant le vœu de redevenir
humain, et Jafar peut choisir au moins $N$ vœux et gagne le combat
(ainsi que quelques paquets de carambars).
-\thingy La construction moderne des ordinaux, introduite par
-von Neumann en 1923, est mathématiquement très élégante mais peut-être
+\thingy\label{introduction-von-neumann-ordinals}
+La construction moderne des ordinaux, introduite par
+J. von Neumann en 1923, est mathématiquement très élégante mais peut-être
d'autant plus difficile à comprendre qu'elle est subtile :
\begin{center}
-\emph{un ordinal est l'ensemble des ordinaux strictement plus petits que lui}
+\index{von Neumann (ordinal de)}\emph{un ordinal est l'ensemble des ordinaux strictement plus petits que lui}
\end{center}
— ainsi, l'entier $0$ est défini comme l'ensemble vide $\varnothing$
(puisqu'il n'y a pas d'ordinaux plus petits que lui), l'entier $1$ est
@@ -3701,7 +3708,8 @@ successeurs. Dans la forme normale de Cantor, un ordinal est
successeur si et seulement si le dernier terme (le plus à droite) est
un entier naturel non nul.
-\thingy Les ordinaux vont servir à définir différents jeux qui, pris
+\thingy\label{introduction-nimbers-and-numbers}
+Les ordinaux vont servir à définir différents jeux qui, pris
isolément, sont extrêmement peu intéressants, mais qui ont la vertu de
permettre de « mesurer » d'autres jeux : ces jeux ont en commun que,
partant d'un ordinal $\alpha$, l'un ou l'autre joueur, ou les deux,
@@ -3722,7 +3730,7 @@ ordinal $\alpha$ :
$\beta'<\beta$. Il s'agit du jeu de nim
(cf. \ref{introduction-nim-game}) avec une seule ligne d'allumettes
ayant initialement $\alpha$ allumettes. Ce jeu s'appelle parfois le
- « nimbre » associé à l'ordinal $\alpha$.
+ \index{nimbre}« nimbre » associé à l'ordinal $\alpha$.
\item Deux jeux \emph{partiaux} (=partisans), où un joueur n'a aucun
coup possible (il a donc immédiatement perdu si c'est à son tour de
jouer, ce qui rend le jeu, pris isolément, encore plus inintéressant
@@ -4480,6 +4488,123 @@ de $2^c$ pour des entiers naturels $c$ distincts). À titre d'exemple,
\end{array}
\]
+
+
+%
+%
+%
+
+\section{Jeux combinatoires impartiaux à information parfaite}\label{section-combinatorial-impartial-games}
+
+\subsection{Récapitulations}
+
+\thingy On a introduit en \ref{introduction-graph-game} et plus
+formellement en \ref{definition-impartial-combinatorial-game} la
+notion de \emph{jeu combinatoire impartial} (à information parfaite)
+associé à un graphe $G$ muni d'un sommet initial $x_0$ (c'est le jeu
+où, partant de $x = x_0$, chacun des deux joueurs choisit à son tour
+un voisin sortant de $x$ : si l'un des joueurs ne peut pas jouer, il a
+perdu, tandis que si la confrontation se continue indéfiniment, elle
+est considérée comme nulle) ; on a vu
+en \ref{determinacy-of-perfect-information-games} que ces jeux sont
+déterminés.
+
+On fera dans toute cette partie l'hypothèse supplémentaire que le
+graphe $G$ est bien-fondé (cf. \ref{definitions-graphs}), c'est-à-dire
+qu'aucune confrontation ne peut être nulle (=durer indéfiniement) : il
+arrive forcément un point où l'un des joueurs ne peut plus jouer (et a
+donc perdu), et la détermination signifie qu'un des joueurs a une
+stratégie \emph{gagnante}. On peut qualifier un tel jeu de
+\index{bien-fondé (jeu)}« bien-fondé » ou de \defin[terminant
+ (jeu)]{terminant}.
+
+\thingy\label{combinatorial-positions-as-games} Il va de soi qu'une
+position $x$ d'un jeu combinatoire impartial $G$ peut elle-même être
+considérée comme un jeu combinatoire impartial : le jeu joué \defin{à
+ partir de là}, à savoir celui dont $x$ est la position initiale (on
+avait fait une remarque semblable pour les jeux de Gale-Stewart
+en \ref{gale-stewart-positions-as-games}) et dont l'ensemble des
+positions est $G$ ou, mieux (cf. paragraphe suivant) l'aval de $x$.
+On se permettra souvent d'identifier ainsi une position et un jeu.
+
+Pour éviter des discussions inutiles, on fera aussi souvent
+implicitement l'hypothèse, en parlant d'un jeu combinatoire impartial
+$(G,x_0)$, que tout sommet de $G$ est accessible depuis $x_0$
+(cf. \ref{definition-accessibility-downstream} ; i.e., il n'y a pas de
+positions « inutiles » car inaccessibles) : on peut toujours se
+ramener à cette hypothèse en remplaçant $G$ par l'aval de $x_0$,
+c'est-à-dire, en supprimant les positions inaccessibles.
+
+On rappelle la définition de la fonction de Grundy
+(généralisant \ref{definition-grundy-function} à des valeurs non
+nécessairement finies, comme expliqué
+en \ref{ordinal-valued-rank-and-grundy-function}) :
+
+\begin{defn}\label{definition-grundy-function-again}
+Soit $G$ un graphe orienté bien-fondé. On appelle \defin[Grundy
+ (fonction de)]{fonction de Grundy} sur $G$ la fonction $\gr$
+définie sur $G$ et à valeurs ordinales définie inductivement (en
+utilisant le théorème \ref{well-founded-definition}) par $\gr(x) =
+\mex\{\gr(y) : y\in\outnb(x)\}$ (où $\mex S$ désigne le plus petit
+ordinal n'appartenant pas à $S$, qui existe d'après
+\ref{sets-of-ordinals-are-well-ordered}
+et \ref{sup-and-strict-sup-of-sets-of-ordinals}). On appelle fonction
+(ou valeur) de Grundy du jeu combinatoire impartial (terminant)
+associé à $(G,x_0)$ la valeur $\gr(x_0)$.
+\end{defn}
+
+On rappelle qu'on a vu (cf. \ref{discussion-n-and-p-vertices}
+à \ref{ordinal-valued-rank-and-grundy-function}) que le second joueur
+(=joueur précédent) a une stratégie gagnante si et seulement si la
+valeur de Grundy est $0$, tandis que le premier joueur (=joueur
+suivant) en a une si et seulement si elle est $\neq 0$. La stratégie
+« universelle » consiste toujours à \emph{jouer de façon à annuler la
+ fonction de Grundy} du sommet vers lequel on joue. La signification
+de la valeur exacte de la fonction de Grundy (au-delà du fait qu'elle
+soit nulle ou non nulle) est plus mystérieuse. Pour l'éclaircir, on
+va introduire les \emph{nimbres} (déjà évoqués
+en \ref{introduction-nimbers-and-numbers}) :
+
+\begin{defn}\label{definition-nimber}
+Soit $\alpha$ un ordinal. On appelle alors \defin{nimbre} associé
+à $\alpha$, et on note $*\alpha$, le jeu combinatoire impartial dont
+\begin{itemize}
+\item l'ensemble des positions est l'ensemble des ordinaux $\beta \leq
+ \alpha$ (c'est-à-dire, si on utilise la construction de von Neumann
+ des ordinaux, cf. \ref{introduction-von-neumann-ordinals},
+ l'ensemble $\alpha+1$),
+\item la relation d'arête (définissant le graphe) est $>$,
+ c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les
+ ordinaux $\beta'<\alpha$,
+\item la position initiale est $\alpha$.
+\end{itemize}
+Autrement dit, il s'agit du jeu où, partant de l'ordinal $\beta =
+\alpha$, chaque joueur peut dimininuer l'ordinal $\beta$, c'est-à-dire
+le remplacer par un ordinal $\beta' < \beta$ de son choix (ce jeu
+termine en temps fini d'après
+\ref{decreasing-sequences-of-ordinals-terminate}
+ou \ref{sets-of-ordinals-are-well-ordered}).
+
+On dira aussi que $*\alpha$ est le jeu constituée d'« une rangée de
+ $\alpha$ allumettes » au nim (si $\alpha$ est fini, cela coïncide
+bien avec ce qu'on a dit en \ref{introduction-nim-game}). En accord
+avec la remarque \ref{combinatorial-positions-as-games}, on peut
+identifier les positions du nimbre $*\alpha$ avec les jeux $*\beta$
+pour $\beta\leq\alpha$.
+\end{defn}
+
+\begin{prop}
+La valeur de Grundy du nimbre $*\alpha$ est $\alpha$.
+\end{prop}
+\begin{proof}
+On procède par induction transfinie
+(cf. \ref{scholion-transfinite-induction}) : si on sait que
+$\gr(*\beta) = \beta$ pour tout $\beta<\alpha$, alors
+$\gr(*\alpha)$ est le plus petit ordinal différent de $\beta$
+pour $\beta<\alpha$, c'est donc exactement $\alpha$.
+\end{proof}
+
+
%
%
%