\documentclass[12pt,a4paper,notitlepage]{report}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{ifthen}
\usepackage{chessboard}
\usepackage[top=2.5cm,bottom=2.5cm,left=2.5cm,
right=2.5cm]{geometry}
\author{Alain Busser\\IREMI 974}
\usepackage{tikz}
\usetikzlibrary{automata,shapes,arrows,shadings}
\tikzset{
v/.style={circle,draw,ultra thick,minimum width=1.4cm},
a/.style={rectangle,draw,ultra thick,minimum width=1.4cm,minimum height=1.4cm},
rouge/.style={->,>=stealth',ultra thick,color=red},
bleu/.style={->,>=stealth',ultra thick,color=blue},
arc/.style={->,>=stealth',ultra thick}
}

\usepackage{comment}

\setcounter{chapter}{4}


\title{Construction du nombre par John Conway\\4. L'écho des kos de go}
\begin{document}
\renewcommand{\labelitemi}{$\bullet$}
\renewcommand{\labelitemii}{$\circ$}

\maketitle
\vfill

\hfill
\includegraphics[scale=0.2]{LogoIREMI}

\newpage

%\begin{comment}




\section{Jeux infiniment grands}

\subsection{Les nombres ordinaux}


Le jeu ci-dessous contient tous les nombres ordinaux, aussi Conway l'appelle-t-il \emph{on} (comme «~\textbf{o}rdinal \textbf{n}umbers~»)~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,1) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\end{tikzpicture}
\end{center}

En effet, comme même si on oblige Bleu à avancer un million de fois le pion avant de commencer le jeu, on a exactement le même jeu, cela signifie que \emph{on} est supérieur à un million. En fait \emph{on} est supérieur à tous les ordinaux, même infinis.

On rappelle que dans le jeu \emph{on} ci-dessus, Rouge ne peut pas bouger du tout alors que Bleu peut jouer aussi longtemps qu'il le veut.

Comme \emph{on} est supérieur à tous les nombres, \emph{on} est positif.

\subsection{L'opposé de on}

On obtient l'opposé d'un jeu en intervertissant les rôles de Rouge et Bleu. Le jeu ci-dessous, où Bleu ne peut pas jouer alors que Rouge peut jouer aussi souvent qu'elle veut, est donc l'opposé de \emph{on}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,1) {$\BlackPawnOnWhite$};
\draw[rouge,loop right] (a) to (a);
\end{tikzpicture}
\end{center}

Conway décide d'appeler \emph{off} l'opposé de \emph{on}. Le jeu \emph{off} est donc négatif, et même inférieur à tous les nombres, même infinis.

Comme \emph{on} et \emph{off} sont opposés, on peut imaginer que leur somme est égale à zéro (le jeu nul). En fait il n'en est rien~:

\subsection{Un premier ko}

Le jeu ci-dessous est $on + off = dud$~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,1) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,loop right] (a) to (a);
\end{tikzpicture}
\end{center}
 
Le nom de \emph{dud} est une abréviation de \textbf{d}eathless \textbf{u}niversal \textbf{d}raw qu'on pourrait traduire en français par «~partie nulle universelle et immortelle~» soit l'archétype du ko. En version «~jeu à deux joueurs~» cela donne~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,fill=blue!20,accepting] (a) at (-2,0) {};
\node[a] (b) at (-1,0) {};
\node[v] (c) at (0,0) {};
\node[a,fill=red!20,accepting] (d) at (1,0) {};
\draw[arc] (b) to (a);
\draw[arc,bend left] (b) to (c);
\draw[arc,bend left] (c) to (b);
\draw[arc] (c) to (d);
\end{tikzpicture}
\end{center}

\emph{dud} a la propriété qu'en lui additionnant n'importe quel jeu, la somme est encore \emph{dud}. Il est infini mais ni positif, ni négatif.

Par exemple $dud + on = dud$~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (-3,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,loop right] (a) to (a);
\draw[bleu,loop left] (b) to (b);
\end{tikzpicture}
\end{center}
 
$dud + dud = dud$~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (-3,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,loop right] (a) to (a);
\draw[bleu,loop left] (b) to (b);
\draw[rouge,loop right] (b) to (b);
\end{tikzpicture}
\end{center}
 
Voici une incarnation de \emph{dud} sur un échiquier~:

\begin{center}
\chessboard[maxfield=c2,addpieces={ka1,Kc1},showmover=false]{}
\end{center}

\subsection{Entiers naturels}

Voici les entiers naturels définis à partir de \emph{on}.

\subsubsection{zéro}

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge] (b) to (a);
\end{tikzpicture}
\end{center}

\subsubsection{un}

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge] (b) to (a);
\draw[bleu] (c) to (b);
\draw[rouge,bend right] (c) to (a);
\end{tikzpicture}
\end{center}

\subsubsection{deux}

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\node[v] (d) at (2,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge] (b) to (a);
\draw[bleu] (c) to (b);
\draw[bleu] (d) to (c);
\draw[rouge,bend right] (d) to (a);
\end{tikzpicture}
\end{center}





\section{Jeux infiniment petits} 

\subsection{over et under}

\subsubsection{over}

Ce jeu est d'une certaine manière l'inverse multiplicatif de \emph{on}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (b) at (-1,0) {};
\draw[rouge,loop right] (a) to (a);
\draw[bleu] (a) to (b);
\end{tikzpicture}
\end{center}

Ce jeu est appelé \emph{over} par Conway. Il est positif mais infinitésimal. Il est plus grand que $\uparrow$, que $\uparrow \uparrow$, que $\uparrow \uparrow \uparrow$, que $\uparrow \uparrow \uparrow \uparrow$ etc.

\subsubsection{under}

Le jeu \emph{under} est l'opposé de \emph{over}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (b) at (1,0) {};
\draw[bleu,loop left] (a) to (a);
\draw[rouge] (a) to (b);
\end{tikzpicture}
\end{center}

Le jeu \emph{under} est négatif (c'est Rouge qui gagne) mais infinitésimal. Il est plus petit que $\downarrow$, $\downarrow \downarrow$ etc.

Que \emph{over} et \emph{under} sont opposés ne signifie pas que leur somme est nulle (ce qui voudrait dire que dans $over+under$ le premier qui joue perd le jeu). En effet si Rouge et Bleu jouent au mieux à $over+under$~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (b) at (0,0){};
\node[v] (c) at (1,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,loop right] (c) to (c);
\draw[rouge] (a) to (b);
\draw[bleu] (c) to (b);
\end{tikzpicture}
\end{center}

On voit bien qu'au des deux joueurs n'a intérêt à mener un des pions à l'arrivée car alors l'autre joueur gagnerait en faisant pareil. Donc les joueurs font indéfiniment passer un pion sur une boucle. Pour autant $over+under$ n'est pas égal à $dud$ non plus. Par contre la somme de \emph{over} et d'un infinitésimal positif (ou d'un nimber) est \emph{over}.



\subsection{upon}

On rappelle que $\uparrow$, même s'il est plus grand que beaucoup de nombres positifs infinitésimaux, est un infinitésimal. Par conséquent, $\uparrow^{2}$ est infiniment plus petit que $\uparrow$, $\uparrow^{3}$ est encore plus petit etc. Que dire alors de $\uparrow^{on}$~?

\subsubsection{upon*}

Ce jeu est la somme de l'étoile et d'un jeu baptisé \emph{upon}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (b) at (1,0) {};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,bend right] (a) to (b);
\draw[bleu,bend left] (a) to (b);
\end{tikzpicture}
\end{center}

Si c'est à Bleu de jouer, il gagne, et si c'est à Rouge de jouer, elle gagne, en menant le pion à l'arrivée~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {};
\node[v,accepting] (b) at (1,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,bend right] (a) to (b);
\draw[bleu,bend left] (a) to (b);
\end{tikzpicture}
\end{center}

Ce jeu ressemble donc beaucoup à l'étoile, mais ce n'est pas l'étoile. En effet $*+*=0$ mais la somme du jeu ci-dessus et de l'étoile~: 

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (b) at (1,0) {};
\node[v] (c) at (2,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop left] (a) to (a);
\draw[rouge,bend right] (a) to (b);
\draw[bleu,bend left] (a) to (b);
\draw[rouge,bend right] (c) to (b);
\draw[bleu,bend left] (c) to (b);
\end{tikzpicture}
\end{center}

n'est pas zéro~: si c'est à Rouge de jouer, elle perd en amenant un des pions à l'arrivée (Bleu amène l'autre pion à l'arrivée juste après, pour gagner). Mais si c'est à Bleu de jouer, il joue le pion de gauche en lui faisant parcourir une boucle, et gagne. Ce jeu est donc positif, c'est celui que Conway appelle \emph{upon}.

\subsubsection{upon}

Voici le jeu \emph{upon}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (1,0) {};
\node[v,accepting] (c) at (2,0) {};
\draw[bleu,loop left] (a) to (a);
\draw[rouge] (a) to (b);
\draw[rouge,bend right] (b) to (c);
\draw[bleu,bend left] (b) to (c);
\end{tikzpicture}
\end{center}

Son nom vient du fait que

\begin{itemize}
\item $upon>\uparrow$
\item $upon>\uparrow+\uparrow^{2}$
\item $upon>\uparrow+\uparrow^{2}+\uparrow^{3}$
\item $upon>\uparrow+\uparrow^{2}+\uparrow^{3}+\uparrow^{4}$
\item $upon>\uparrow+\uparrow^{2}+\uparrow^{3}+\uparrow^{4}+\uparrow^{5}$
\item $upon>\uparrow+\uparrow^{2}+\uparrow^{3}+\uparrow^{4}+\uparrow^{5}+\uparrow^{6}$
\item etc
\item $upon>\uparrow+\uparrow^{2}+\uparrow^{3}+\uparrow^{4}+\uparrow^{5}+\uparrow^{6}+...+\uparrow^{on}$
\end{itemize}

Mais pourtant la limite n'est pas atteinte puisque $upon<\uparrow\uparrow$.

\section{Tiny et miny}

Jusqu'ici, on avait réservé le nom de \emph{tiny} au jeu que Conway notait $+_{1}$ et on a vu qu'il y avait d'autres jeux très petits (d'autres $tiny$). En fait plus $n$ est grand, et plus $+_{n}$ est petit. Le jeu que Conway nommait \emph{tiny} (sans indice) est en fait $+_{on}$. Comme \emph{on} est plus grand que tous les autres ordinaux, \emph{tiny} est 

\begin{itemize}
\item strictement positif
\item strictement inférieur à tous les jeux strictement positifs.
\end{itemize}

C'est la plus petite valeur (positive) possible.

\subsection{tiny}

Voici ce jeu extraordinaire~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (z) at (0,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\draw[bleu,bend left] (a) to (z);
\draw[bleu] (b) to (z);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[rouge,loop above] (c) to (c);
\end{tikzpicture}
\end{center}

\subsection{miny}

Bien entendu, l'opposé de \emph{tiny}, appelé \emph{miny}, est de façon analogue le plus grand des jeux négatifs~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (z) at (0,1) {};
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {$\BlackPawnOnWhite$};
\draw[bleu,loop above] (a) to (a);
\draw[bleu] (b) to (a);
\draw[rouge] (b) to (z);
\draw[bleu] (c) to (b);
\draw[rouge,bend right] (c) to (z);
\end{tikzpicture}
\end{center}

\subsection{hot, ono et oof}

Conway ne s'arrête pas là. Il y a des jeux infiniment grands appelés respectivement \emph{hot}, \emph{ono} et \emph{oof}.

\subsubsection{hot}

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (c) at (1,0) {};
\draw[bleu,loop left] (a) to (a);
\draw[bleu] (b) to (a);
\draw[rouge] (b) to (c);
\draw[rouge,loop right] (c) to (c);
\end{tikzpicture}
\end{center}

Le jeu $hot$ peut être considéré comme la moitié de $dud$ puisque $hot+hot=dud$.

\subsubsection{hi et lo}

Conway introduit aussi ces jeux~:

Le jeu \emph{hi}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (z) at (0,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu,bend left] (a) to (z);
\draw[bleu,loop above] (z) to (z);
\draw[bleu] (b) to (z);
\draw[rouge,loop above] (c) to (c);
\end{tikzpicture}
\end{center}

Le jeu \emph{lo} est l'opposé de \emph{hi}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (z) at (0,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[rouge,bend left] (a) to (z);
\draw[rouge,loop above] (z) to (z);
\draw[rouge] (b) to (z);
\draw[bleu,loop above] (c) to (c);
\end{tikzpicture}
\end{center}

\subsubsection{ono}

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (-1,0) {};
\node[v] (b) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (c) at (1,0) {};
\draw[bleu,loop left] (a) to (a);
\draw[bleu] (b) to (a);
\draw[rouge] (b) to (c);
\end{tikzpicture}
\end{center}

Le jeu \emph{ono} peut être considéré comme la moitié de \emph{on} puisque $ono+ono=on$.

\subsection{oof}

Le jeu \emph{oof} (la moitié de \emph{off}) est l'opposé de \emph{ono}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (a) at (-1,0) {};
\node[v] (b) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (c) at (1,0) {};
\draw[rouge,loop right] (c) to (c);
\draw[bleu] (b) to (a);
\draw[rouge] (b) to (c);
\end{tikzpicture}
\end{center}

\section{Cartes}

La suite démarrée par les jeux \emph{off}, \emph{oof} et \emph{tiny} continue par cette suite de cartes~:

\begin{enumerate}
\item As (\textit{ace} en anglais)~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (z) at (0,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\node[v] (d) at (2,0) {};
\draw[bleu,bend left] (a) to (z);
\draw[bleu] (b) to (z);
\draw[bleu,bend right] (c) to (z);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[rouge] (c) to (d);
\draw[rouge,loop above] (d) to (d);
\end{tikzpicture}
\end{center}

Le poids atomique de ce jeu est 1.

\item Deux (\textit{deuce} en anglais)~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (z) at (0.5,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\node[v] (d) at (2,0) {};
\node[v] (e) at (3,0) {};
\draw[bleu,bend left] (a) to (z);
\draw[bleu] (b) to (z);
\draw[bleu] (c) to (z);
\draw[bleu,bend right] (d) to (z);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[rouge] (c) to (d);
\draw[rouge] (d) to (e);
\draw[rouge,loop above] (e) to (e);
\end{tikzpicture}
\end{center}

Le poids atomique de ce jeu est 2. D'ailleurs $ace+ace=deuce$.

\item Trois (\textit{trey} en anglais)~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (z) at (1,1) {};
\node[v] (a) at (-1,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (0,0) {};
\node[v] (c) at (1,0) {};
\node[v] (d) at (2,0) {};
\node[v] (e) at (3,0) {};
\node[v] (f) at (4,0) {};
\draw[bleu,bend left] (a) to (z);
\draw[bleu] (b) to (z);
\draw[bleu] (c) to (z);
\draw[bleu] (d) to (z);
\draw[bleu,bend right] (e) to (z);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[rouge] (c) to (d);
\draw[rouge] (d) to (e);
\draw[rouge] (e) to (f);
\draw[rouge,loop above] (f) to (f);
\end{tikzpicture}
\end{center}

Le poids atomique de ce jeu est 3. D'ailleurs $deuce+ace=trey$.

\end{enumerate}

L'étude de ces jeux de poids atomique entier fait intervenir un autre jeu, que Conway baptise \emph{joker}~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v,accepting] (o) at (0,0) {};
\node[v] (a) at (-1.4,0) {$\BlackPawnOnWhite$};
\node[v] (b) at (-1,-1) {};
\node[v] (c) at (0,-1.4) {};
\node[v] (d) at (1,-1) {};
\node[v] (e) at (1.4,0) {};
\node[v] (f) at (1,1) {};
\node[v] (g) at (0,1.4) {};
\node[v] (h) at (-1,1) {};
\draw[bleu] (a) to (o);
\draw[bleu] (b) to (o);
\draw[bleu] (c) to (e);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[rouge] (c) to (d);
\draw[bleu] (e) to (f);
\draw[bleu] (f) to (g);
\draw[bleu] (g) to (h);
\draw[rouge] (e) to (o);
\draw[rouge] (f) to (o);
\draw[rouge] (g) to (o);
\draw[rouge,loop right] (d) to (d);
\draw[bleu,loop left] (h) to (h);
\end{tikzpicture}
\end{center}

Ce jeu est strictement positif et strictement inférieur à \emph{ace}.















 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
\end{document}

