%!TEX encoding = UTF-8 Unicode
\documentclass[12pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\renewcommand{\ttdefault}{lmtt}
\usepackage{amsmath,amssymb}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{pifont}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{shapes,calc,positioning,shadings}
\usetikzlibrary{arrows.meta,topaths}
\usepackage{tikzsymbols}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\hoffset}{-1,4cm}
\setlength{\voffset}{-2,5cm}
\usepackage[frenchb]{babel}
\usepackage[np]{numprint}
\usepackage{chessboard,skak}
\usepackage{chessfss}
\usepackage{yfonts}
\usepackage[pdftitle={Jeux de Nim sur échiquier},pdfauthor={Alain Busser},pdftex,colorlinks=true,bookmarks,hyperindex,hyperfigures]{hyperref}

\newcommand{\sou}[2]{
\fill[left color=gray!50!black,right color=gray!50!black,middle color=gray!50,shading=axis,opacity=1] (1+#1,#2) -- (1+#1,0.3+#2) arc (360:180:1cm and 0.25cm) -- (-1+#1,#2) arc (180:360:1cm and 0.25cm);%bord
\fill[top color=gray!90!,bottom color=gray!2,middle color=gray!30,shading=axis,opacity=1] (#1,0.3+#2) circle (1cm and 0.25cm);%haut
\draw (-1+#1,0.3+#2) -- (-1+#1,#2) arc (180:360:1cm and 0.25cm) -- (1+#1,0.3+#2); 
\draw (#1,0.3+#2) circle (1cm and 0.25cm);
}



\begin{document}
\renewcommand{\labelitemi}{\textbullet}
\setlength\parindent{0mm}
\setchessboard{largeboard,showmover=false}
\def\oui{\dSmiley[3]}
\def\non{\dSadey[3]}
\def\combi{\BasicTree[8]{green!20!black}{green!50!black}{green!70!black}{leaf}}

\begin{center} 
\tikzstyle{cadre}=[very thick, rectangle, rounded corners, draw=black, top color=yellow!10, bottom color=yellow!20!gray]
\begin{tikzpicture}
\node [cadre]{%
    \begin{minipage}[t!]{0.8\textwidth}
	\begin{center}
	\Large {\textbf{Jeux de Nim sur échiquier}}
	\end{center}
	\end{minipage}
};
\end{tikzpicture}
\end{center}

Dans cet article, il sera question de dames blanches, de dames noires, de grenouilles et crapauds, de chevaux fous, mais avant tout d'un trésor de pièces d'argent, que l'on ramasse selon certaines règles. Prêts pour l'aventure?

\section{Nim}
\subsection{Le jeu de Nim}

Le jeu de Nim a été décrit pour la première fois par Charles Bouton, qui a décrit sa stratégie gagnante à l'aide de la numération binaire. Le jeu se joue à deux, avec des jetons (ci-dessous, des pièces d'argent) disposés en tas comme ceci (ici, un tas de 5 pièces, un tas de 3 pièces et un tas de 7 pièces) :

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,5}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{3}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Chaque joueur, à son tour, choisit un des tas de pièces puis enlève de ce tas autant de pièces qu'il veut. Par exemple, le premier joueur peut choisir de vider complètement le tas du milieu:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,5}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Puis le second joueur peut choisir d'enlever 4 pièces du tas de droite:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,5}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Le joueur qui prend la dernière pièce (éventuellement en même temps que d'autres pièces, qui sont au-dessus d'elle) est déclaré gagnant. Par exemple, la partie démarrée ci-dessus est arrivée à un stade où il n'y a plus que deux tas (puisque le troisième tas a été vidé dès le début du jeu) et ce serait une mauvaise idée de prendre toutes les pièces d'un autre tas: L'adversaire n'aurait alors plus qu'à vider le dernier tas et serait gagnant. 



Le joueur dont c'est le tour a une autre stratégie gagnante: Prendre deux pièces du tas de gauche pour arriver à cette situation symétrique:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Et ensuite, il suffit qu'il imite tous les coups de son adversaire pour que la situation reste symétrique: Si l'adversaire prend deux pièces d'un tas, prendre deux pièces d'un autre tas, etc.

\non Le jeu appelé Nim par Charles Bouton n'est donc \emph{pas} le jeu popularisé par le père Fourasse, où on enlève des allumettes \emph{d'un seul tas}, et où on n'enlève pas autant d'allumettes qu'on veut, mais seulement 1, 2 ou 3 à la fois. Le jeu dit "de Fort Boyard" n'est donc pas le jeu de Nim, il sera décrit ci-après sous le nom de "jeu de la soustraction".

\subsection{Jeux de nim avec pions}

\oui On peut aussi jouer à nim, avec des pions alignés au lieu de  pièces entassées. Ou, si on préfère, des pions sur échiquier au lieu d'allumettes alignées :

\subsubsection{Jeu de la soustraction}

Le jeu de la soustraction que l'on verra plus loin (enlever 1, 2 ou 3 pièces du tas de taille initiale 10)

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,10}{ \sou{0}{0.4*\z}}
\end{tikzpicture}
\end{center}


devient celui-ci:

\begin{center}
\chessboard[maxfield=j1,addpieces={pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1,pi1,pj1}]
\end{center}

Chaque joueur, à son tour, enlève 1, 2 ou 3 pions (les plus à droite) de la ligne. Celui qui enlève le dernier pion est le gagnant.

La stratégie gagnante consiste à toujours laisser un nombre de pions divisible par 4. Elle est donc pour le joueur qui joue en premier.

\subsubsection{Jeu de nim}

De même, le jeu de nim vu au début

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,5}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{3}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}


devient, sur échiquier,

\begin{center}
\chessboard[maxfield=i3,addpieces={pa1,pb1,pc1,pd1,pe1, 
pa2,pb2,pc2, 
pa3,pb3,pc3,pd3,pe3,pf3,pg3}]
\end{center}

Chaque jouer, à son tour, enlève autant de pions (les plus à droite possibles) de la ligne de son choix. Celui qui enlève le dernier pion a gagné.

C'est ainsi qu'était programmé le Nimrod, premier ordinateur de jeu, où les pions étaient remplacés par des lumières allumées ou éteintes.


\subsubsection{Chomp}

Cette variante de nim a été inventée par David Gale dans les années 1970:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1, 
pa2,pb2,pc2,pd2,pe2,pf2,pg2,ph2 ,
pa3,pb3,pc3,pd3,pe3,pf3,pg3,ph3,
pa4,pb4,pc4,pd4,pe4,pf4,pg4,ph4,
pa5,pb5,pc5,pd5,pe5,pf5,pg5,ph5}]
\end{center}


Chaque joueur à son tour, enlève un pion ainsi que tous ceux qui sont à droite et au-dessus de celui-ci. Le joueur qui prend le pion blanc est le perdant. Le premier coup peut ressembler à ceci (en jouant e3):

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1, 
pa2,pb2,pc2,pd2,pe2,pf2,pg2,ph2 ,
pa3,pb3,pc3,pd3,
pa4,pb4,pc4,pd4,
pa5,pb5,pc5,pd5}]
\end{center}
 
Le second coup (en jouant b4):

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1, 
pa2,pb2,pc2,pd2,pe2,pf2,pg2,ph2,
pa3,pb3,pc3,pd3,pa4,pa5}]
\end{center}

Et si on joue c2:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1, 
pa2,pb2,pa3,pb3,pa4,pa5}]
\end{center}


puis a3:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pe1,pf1,pg1,ph1, 
pa2,pb2}]
\end{center}

puis e1:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pc1,pd1,pa2,pb2}]
\end{center}

Si le second joueur joue c1:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pa2,pb2}]
\end{center}

le premier peut jouer b2 et gagner:

\begin{center}
\chessboard[maxfield=h5,addpieces={Pa1,pb1,pa2}]
\end{center}

En effet quel que soit le pion qu'enlèvera son adversaire au coup suivant, il enlèvera l'autre pion et ne restera alors que le dernier pion (blanc) pour l'adversaire, qui perd alors\footnote{Exercice: Montrer que si, au début, il y a autant de lignes que de colonnes (chomp sur un carré), il y a une stratégie gagnante pour celui qui joue en premier}.



\subsection{jeu de Welter}

\subsubsection{Description}

C'est un J.P Welter qui a eu cette idée en 1954; la variante de Nim présentée ci-dessous est donc parfois appelée \emph{jeu de Welter}. Mais on va voir que ce jeu est équivalent à Nim. Par exemple, avec le jeu de Nim précédent:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,5}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{3}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

C'est ainsi qu'on représente ce jeu sur un échiquier:
\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pc1, pg2}]
\end{center}

L'échiquier est en fait un repère, où le numéro de chaque tas est porté sur l'axe des ordonnées (à gauche; le premier tas est le numéro 0, donc le troisième tas est le numéro 2) et le numéro de la pièce tout en haut du tas est représenté par l'abscisse d'un pion: Les tas comportant respectivement 5, 3 et 7 pièces, sont donc représentés (de bas en haut) par des pions aux abscisses 5, 3 et 7. En effet, si la pièce tout en haut du premier tas est la numéro 5, c'est qu'il y a 5 pièces dans le tas.

Un pion placé tout à gauche (abscisse 0) représente donc un tas vide au jeu de Nim.

On peut donc dire que l'échiquier ci-dessus est une autre façon de dessiner un jeu de Nim, où les pièces ont subi une symétrie par rapport à la table (les tas vont alors de haut en bas) puis une rotation de 90° dans le sens antihoraire (les tas vont alors de gauche à droite); et enfin on enlève toutes les pièces sauf la dernière (celle qui était tout en haut au début, qui, à elle seule, définit la taille du tas de pièces) et on remplace celle-ci par un pion. Voici alors la nouvelle règle du jeu de Nim (ou de Welter):

\begin{center}
\begin{minipage}{0.8\textwidth}
\textbf{Chaque joueur, à son tour, choisit un des pions, puis le déplace vers la gauche d'autant qu'il veut. Le premier qui ne peut plus déplacer de pion (parce que les pions sont tous collés à gauche) est le perdant.} 
\end{minipage}
\end{center}

Voici ce que devient la partie de Nim décrite ci-avant, en version Welter:

La position initiale du jeu est donc celle-ci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pc1, pg2}]
\end{center}

Le premier joueur déplace un pion tout à gauche ("vider un tas"):

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pZ1, pg2}]
\end{center}

Le second joueur déplace alors le pion du haut, de 4 cases vers la gauche ("enlever 4 pièces du tas"):

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pZ1, pc2}]
\end{center}

Le premier joueur va donc gagner en commençant par rendre la situation symétrique par déplacement du pion du bas pour le mettre en face de celui du haut:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pc0, pZ1, pc2}]
\end{center}

pour ensuite, comme on l'a vu, jouer les caméléons face à son adversaire (imiter sur la ligne du bas tout coup joué sur la ligne du haut, et vice-versa).

\subsubsection{Pour gagner}
\combi La stratégie gagnante de Bouton s'exprime à l'aide des abscisses des pions, avec une notion appelée "Nim-addition", consistant à calculer et modifier la "nimsomme" des abscisses des pions. Pour effectuer une nim-addition (notée $\oplus$), on peut utiliser les faits suivants:

\begin{itemize}
\item La nim-addition est commutative et associative;
\item Pour tout entier naturel $n$, on a $n\oplus 0 = n$;
\item Pour tout entier naturel $n$, on a $n\oplus n = 0$ (tout entier est son propre opposé);
\item Si $n<2^{k}$ alors $2^{k}\oplus n=2^{k}+n$;
\end{itemize}

Par exemple, pour effectuer la nim-addition $6\oplus 3$, on commence par dire que $6=4+2=4\oplus 2$ et $3=2+1= 2\oplus 1$ puis $6\oplus 3=4\oplus 2 \oplus 2 \oplus 1=4 \oplus 1=4+1=5$.

\combi Si on n'a pas le courage de se livrer à ce genre d'entraînement au calcul mental de nimsommes, on peut toujours reprendre la définition originale de Bouton, consistant à écrire les nombres en binaire et ne garder pour la somme, que les chiffres binaires qui apparaissent un nombre impair de fois dans l'addition. Pour $6\oplus 3$, on écrit 6 en binaire: 110, puis 3 en binaire: 11; l'un au-dessous de l'autre:

\begin{center}
\begin{minipage}{5cm}
\begin{flushright}
110

11

----

101
\end{flushright}
\end{minipage}
\end{center}

(11 est en fait 011, le 0 à gauche étant sous-entendu)

Une colonne comprenant deux fois "1" ne compte pas dans la nim-addition, ce qui aboutit dans l'exemple ci-dessus, à l'annulation du chiffre des deuzaines. Or 101 en binaire, c'est 5.

La stratégie gagnante de Bouton se résume alors à ceci:


\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Systématiquement jouer un coup qui annule la nimsomme des abscisses de tous les pions.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Stratégie gagnante};
\end{tikzpicture}
\end{center}

Voilà ce que ça donne sur l'exemple vu ci-avant: 

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pc1, pg2}]
\end{center}

Au départ, la nimsomme est $5\oplus 3 \oplus 7$; or $5 \oplus 2 =7$ donc $5\oplus 7=2$; la nimsomme de départ est donc $3 \oplus 2=1\oplus 2 \oplus 2=1$: Elle est différente de 0 donc il est possible, pour le premier joueur, de gagner, par exemple, comme $3 \oplus 5=3\oplus 4 \oplus 1=4\oplus 3 \oplus 1=4\oplus 2=6$, en déplaçant le pion du haut sur la position 6, on aura une nimsomme égale à $6\oplus 6=0$, et ce coup est gagnant:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pc1, pf2}]
\end{center}

Mais le premier joueur ne l'avait pas vu et avait préféré, on se rappelle, jouer ce coup:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pZ1, pg2}]
\end{center}

La nimsomme de ce jeu est maintenant $5\oplus 7=2$ et il est facile de l'annuler en "remplaçant le 7 par un 5":

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pZ1, pe2}]
\end{center}

Mais dans l'exemple précédent, le second joueur ne l'avait pas fait, il a voulu jouer ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pZ1, pc2}]
\end{center}

La nimsomme de ce jeu est $3\oplus 5=6$, que l'on peut annuler en "remplaçant le 5 par un 3":

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pc0, pZ1, pc2}]
\end{center}

La nimsomme est maintenant $3\oplus 3=0$ et en imitant les coups de son adversaire, le premier joueur aura toujours une nimsomme du type $n \oplus n=0$ après avoir joué, jusqu'à la position finale:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pZ0, pZ1, pZ2}]
\end{center}


\combi Voici une table de nim-addition:

\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|}
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
\hline
1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 & 9 & 8 \\
\hline
2 & 3 & 0 & 1 & 6 & 7 & 4 & 5 & 10 & 11 \\
\hline
3 & 2 & 1 & 0 & 7 & 6 & 5 & 4 & 11 & 10 \\
\hline
4 & 5 & 6 & 7 & 0 & 1 & 2 & 3 & 12 & 13 \\
\hline
5 & 4 & 7 & 6 & 1 & 0 & 3 & 2 & 13 & 12 \\
\hline
6 & 7 & 4 & 5 & 2 & 3 & 0 & 1 & 14 & 15 \\
\hline
7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 15 & 14 \\
\hline
8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 0 & 1 \\
\hline
9 & 8 & 11 & 10 & 13 & 12 & 15 & 14 & 1 & 0 \\
\hline
\end{tabular}
\end{center}

\newpage

\subsection{jeu de la soustraction}

\subsubsection{Welter sur une ligne}

Finalement, on n'a pas vraiment besoin que les pions des jeux de Nim ci-dessus, soient disposés sur des lignes différentes; on peut les mettre tous sur une seule ligne, et le jeu 

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={pe0, pc1, pg2}]
\end{center}


va devenir

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pe0, pc0, pg0}]
\end{center}

Pour que ce jeu soit le même qu'auparavant, il faut autoriser plusieurs pions par case (la stratégie gagnante vue ci-dessus le nécessitait d'ailleurs). 

\subsubsection{Variante}



On peut maintenant imaginer une variante du jeu de Nim où, au contraire, un seul pion maximum peut se trouver sur une case. La position finale n'est alors plus que tous les pions soient sur la case tout à gauche, mais plutôt celle-ci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pZ0, pa0, pb0}]
\end{center}
 
\combi La nimsomme de cette position est $0 \oplus 1 \oplus 2=3$. La stratégie de Bouton deviendrait alors:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Systématiquement jouer un coup qui rend égale à 3, la nimsomme des abscisses de tous les pions.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Stratégie gagnante};
\end{tikzpicture}
\end{center}

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pe0, pc0, pg0}]
\end{center}


Dans l'exemple ci-dessus, la nimsomme de départ est égale à $3\oplus 5 \oplus 7=1$; le joueur qui joue en premier peut donc gagner s'il arrive à transformer cette nimsomme en un 3 sans mettre de pion là où il y en a déjà un. Par exemple en constatant que $5 \oplus 7 = 4 \oplus 1 \oplus 4 \oplus 3=1 \oplus 3=1 \oplus 1 \oplus 2=2$, on voit qu'on peut avoir une nimsomme égale à 3 si on remplace le 3 par un 1:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pa0, pe0, pg0}]
\end{center}

Quoi que fasse l'autre joueur, il ne peut arriver à une nimsomme égale à 3; par exemple s'il joue ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pa0, pd0, pg0}]
\end{center}

La nimsomme est maintenant $1\oplus 4 \oplus 7=1\oplus 4 \oplus 4 \oplus 3=1 \oplus 3=2$; pour transformer ce 2 en 3, on peut simplement annuler le premier terme puisque $4 \oplus 7 = 3$:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pZ0, pd0, pg0}]
\end{center}

Mais si par exemple le second joueur joue ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pZ0, pc0, pg0}]
\end{center}

On ne compte plus le pion de gauche puisqu'il vaut 0, la nimsomme est donc $3\oplus 7=4$. En se rappelant qu'on n'a pas le droit de bouger un pion vers la droite ("nimm" veut dire "enlève" en allemand), on voit qu'un mouvement du pion qui est en 3 va donner $1\oplus 7=6$ ou $2\oplus 7=5$ donc on ne peut pas avoir 3 comme nimsomme, en jouant ce pion-là. Mais il a déjà pour valeur 3, et la seule façon d'avoir 3 en bougeant le pion qui est en 7, serait de mettre celui-ci en 0, ce qui aboutirait à deux pions sur une seule case: La stratégie gagnante ne peut pas toujours être appliquée avec cette variante, ou plutôt elle doit l'être avec précautions: Si lorsqu'on était ici

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pa0, pd0, pg0}]
\end{center}

au lieu de faire 

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pZ0, pd0, pg0}]
\end{center}

on avait fait

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pa0, pd0, pf0}]
\end{center}

on aurait eu aussi une simsomme égale à 3. Mais si maintenant l'adversaire joue

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={pa0, pc0, pf0}]
\end{center}

la nimsomme est maintenant égale à 4, et là encore il n'y a pas moyen de la transformer en 3 sans faire aller un pion vers la droite ou plusieurs pions sur la même case.

Pour ce jeu, la stratégie gagnante n'en est pas une !

\subsubsection{Sur échiquier complet}

On peut jouer à ce jeu sur plusieurs lignes, en convenant qu'à son tour chaque joueur choisisse une ligne et joue au jeu précédent sur cette ligne. 

\begin{center}
\chessboard[addpieces={pd1, pf1, ph1, Pb3, Pc3, Pg3, bb2, be2, bg2, Bc4,Bd4,Bf4,kd5,kf5,kh5,Kb6,Kd6,Kf6,qb7,qc7,qg7,Qc8,Qe8,Qh8}]
\end{center}

Le jeu est fini lorsque toutes les pièces sont sur la case tout à gauche de l'échiquier; ci-dessus, la position finale est de 3 pions noirs en a1, 3 fous noirs en a2, 3 pions blancs en a3, 3 fous blancs en a4, 3 rois noirs en a5, 3 rois blancs en a6, 3 dames noires en a7 et 3 dames blanches en a8. Le jeu ci-dessus a l'air compliqué mais en fait puisque

\begin{center}
\chessboard[maxfield=h1,addpieces={pd1, pf1, ph1}]
\end{center}
 
équivaut à 

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,5}{ \sou{3}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}


du coup, 

\begin{center}
\chessboard[maxfield=h2,addpieces={pd1, pf1, ph1, bb2, be2, bg2}]
\end{center}
 
équivaut à 

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,5}{ \sou{2.5}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{5}{0.4*\z}}
\foreach \z in {1,...,1}{ \sou{7.5}{0.4*\z}}
\foreach \z in {1,...,4}{ \sou{10}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{12.5}{0.4*\z}}
\end{tikzpicture}
\end{center}

et l'échiquier avec ses 24 pièces est donc juste une façon compacte de représenter un jeu de nim à 24 tas de tailles respectives 3, 5, 7, 1, 4, 6, 1, 2, 6, 2, 3, 5, 3, 5, 7, 1, 3, 5, 1, 2, 6, 2, 4 et 7. On peut donc gagner à ce jeu en appliquant la stratégie de Bouton.

Cette construction est appelée \emph{somme} des jeux sur une ligne: Le jeu sur l'échiquier est la somme de 8 jeux de Welter à 3 pions (ou fous ou dames ou rois) chacun. On constate que chaque jeu de nim sur 3 tas est la somme de 3 jeux de nim sur un tas, et que la somme de jeux combinatoires est donc associative. Ce qui amène à une définition:

 \begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{On dit qu'un jeu est \emph{impartial} si les deux joueurs peuvent jouer les mêmes coups au cours de la partie.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Définition};
\end{tikzpicture}
\end{center}
 

Le jeu d'échecs n'est pas impartial puisqu'un joueur ne joue que les pions blancs et l'autre joueur, que les pions noirs. Par contre les jeux décrits ci-dessous sont impartiaux: Chaque fois qu'un joueur manipule un pion ou prend des pièces, l'autre joueur aurait pu manipuler le même pion ou prendre les mêmes pièces. La construction du jeu de nim à 24 tas ci-dessus, se généralise au

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Tout jeu combinatoire impartial est équivalent à une somme de jeux de Nim (généralisés).} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Théorème de Sprague-Grundy};
\end{tikzpicture}
\end{center}


\subsubsection{Le jeu de la soustraction}

Le jeu de Welter peut aussi illustrer le jeu de la soustraction, en modifiant légèrement la règle du jeu:

 \begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Chaque joueur, à son tour, déplace le pion d'une, deux ou trois cases vers la gauche. Le premier qui amène le pion tout à gauche est le gagnant.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Règle du jeu de soustraction};
\end{tikzpicture}
\end{center}

Le jeu consiste en fait à enlever 1, 2 ou 3 sous de ce tas:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,9}{ \sou{0}{0.4*\z}}
\end{tikzpicture}
\end{center}


\oui Le jeu du père Fourasse peut donc être joué lui aussi sur un échiquier:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i0,addpieces={ni0}]
\end{center}

Mais avec la règle ci-dessus: On ne bouge pas le cavalier d'autant qu'on veut, mais de 3 cases maximum. Avec les flèches indiquant les mouvements possibles, on a un \emph{nim sur graphe}:

\begin{center}
\begin{tikzpicture}
\newcount\t
\foreach \s in {0,...,8}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\node (n9) [draw,circle,thick,minimum size=1.2cm] at (13.5,0) {$\BlackKnightOnWhite$};
\foreach \s in {9,...,1}
{
  \t=\s;
  \advance\t by -1;
  \path (n\s) edge[->, ultra thick] (n\the\t);
  }
\foreach \s in {9,...,2}
{
  \t=\s;
  \advance\t by -2;
  \path (n\s) edge[->, ultra thick, bend right=45] (n\the\t);
  }
\foreach \s in {9,...,3}
{
  \t=\s;
  \advance\t by -3;
  \path (n\s) edge[->, ultra thick, bend left=45] (n\the\t);
  }
\end{tikzpicture}
\end{center}

\combi Pour gagner à ce jeu, il faut numéroter les cases du jeu en partant de la fin (la case 0 à gauche), modulo 4: C'est la \emph{fonction de Sprague-Grundy} du graphe. La stratégie gagnante au jeu de la soustraction est celle-ci:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Systématiquement mener le cavalier vers une case de numéro de Sprague-Grundy égal à 0.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Stratégie gagnante};
\end{tikzpicture}
\end{center}

Alors le joueur qui commence la partie gagne (parce que le numéro de Sprague-Grundy de la case tout à droite vaut 1), en allant vers la case de numéro de Sprague-Grundy égal à 0 la plus proche de son lieu actuel (la case 8 parce que 8 est divisible par 4):

\begin{center}
\begin{tikzpicture}
\newcount\t
\foreach \s in {0,...,7}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\node (n8) [draw,circle,thick,minimum size=1.2cm] at (12,0) {$\BlackKnightOnWhite$};
\node (n9) [draw,circle,thick,minimum size=1.2cm] at (13.5,0) {$\;$};
\foreach \s in {9,...,1}
{
  \t=\s;
  \advance\t by -1;
  \path (n\s) edge[->, ultra thick] (n\the\t);
  }
\foreach \s in {9,...,2}
{
  \t=\s;
  \advance\t by -2;
  \path (n\s) edge[->, ultra thick, bend right=45] (n\the\t);
  }
\foreach \s in {9,...,3}
{
  \t=\s;
  \advance\t by -3;
  \path (n\s) edge[->, ultra thick, bend left=45] (n\the\t);
  }
\end{tikzpicture}
\end{center}

Ensuite, les cases accessibles à partir de là portent, de  droite à gauche, les numéros de Sprague-Grundy suivants: 3 (case 7), 2 (case 6) et 1 (case 5); aucun n'est nul, donc quoique joue l'adversaire, il est possible ensuite d'aller à la case 4 (numéro de Sprague-Grundy égal à 0):

\begin{center}
\begin{tikzpicture}
\newcount\t
\foreach \s in {0,...,3}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\node (n4) [draw,circle,thick,minimum size=1.2cm] at (6,0) {$\BlackKnightOnWhite$};
\foreach \s in {5,...,9}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\foreach \s in {9,...,1}
{
  \t=\s;
  \advance\t by -1;
  \path (n\s) edge[->, ultra thick] (n\the\t);
  }
\foreach \s in {9,...,2}
{
  \t=\s;
  \advance\t by -2;
  \path (n\s) edge[->, ultra thick, bend right=45] (n\the\t);
  }
\foreach \s in {9,...,3}
{
  \t=\s;
  \advance\t by -3;
  \path (n\s) edge[->, ultra thick, bend left=45] (n\the\t);
  }
\end{tikzpicture}
\end{center}

Ensuite, le schéma précédent recommence: Les cases accessibles depuis la case 4 ont des numéros de Sprague-Grundy différents de 0 (en fait à ce stade le numéro de Sprague-Grundy est le numéro de la case, soit 1, 2 ou 3), et si par exemple l'adversaire joue ceci

\begin{center}
\begin{tikzpicture}
\newcount\t
\foreach \s in {0,...,2}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\node (n4) [draw,circle,thick,minimum size=1.2cm] at (4.5,0) {$\BlackKnightOnWhite$};
\foreach \s in {4,...,9}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\foreach \s in {9,...,1}
{
  \t=\s;
  \advance\t by -1;
  \path (n\s) edge[->, ultra thick] (n\the\t);
  }
\foreach \s in {9,...,2}
{
  \t=\s;
  \advance\t by -2;
  \path (n\s) edge[->, ultra thick, bend right=45] (n\the\t);
  }
\foreach \s in {9,...,3}
{
  \t=\s;
  \advance\t by -3;
  \path (n\s) edge[->, ultra thick, bend left=45] (n\the\t);
  }
\end{tikzpicture}
\end{center}

il reste une flèche menant directement à l'arrivée qui est la dernière des cases gagnantes:

\begin{center}
\begin{tikzpicture}
\newcount\t
\node (n0) [draw,circle,thick,minimum size=1.2cm] at (0,0) {$\BlackKnightOnWhite$};
\foreach \s in {1,...,9}
{
  \node (n\s) [draw,circle,thick,minimum size=1.2cm] at (1.5*\s,0) {$\;$};
}
\foreach \s in {9,...,1}
{
  \t=\s;
  \advance\t by -1;
  \path (n\s) edge[->, ultra thick] (n\the\t);
  }
\foreach \s in {9,...,2}
{
  \t=\s;
  \advance\t by -2;
  \path (n\s) edge[->, ultra thick, bend right=45] (n\the\t);
  }
\foreach \s in {9,...,3}
{
  \t=\s;
  \advance\t by -3;
  \path (n\s) edge[->, ultra thick, bend left=45] (n\the\t);
  }
\end{tikzpicture}
\end{center}

En mémorisant les distances que peut parcourir le cavalier, le graphe avec ses flèches n'est plus nécessaire, et on peut jouer au jeu de la soustraction sur une ligne de l'échiquier. Ce qui permet alors une généralisation:

\subsubsection{Nim et soustraction ensemble}

On peut faire un jeu de soustraction à 3 tas, où chaque joueur à son tour, enlève 1, 2 ou 3 pièces du tas de son choix:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,9}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,8}{ \sou{3}{0.4*\z}}
\foreach \z in {1,...,7}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Sur l'échiquier, on bouge un des trois cavaliers, d'une, deux ou trois cases vers la gauche:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={ni0,nh1,ng2}]
\end{center}

Le gagnant est le premier qui aboutit à la position finale que voici:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nZ0,nZ1,nZ2}]
\end{center}

\combi On constate que la nimsomme des numéros des cases d'arrivée des trois cavaliers est nulle ($0 \oplus 0 \oplus 0=0$). En fait on peut gagner à ce jeu en utilisant à la fois la nim-addition et les numéros de Sprague-Grundy:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Systématiquement jouer un coup qui annule la nimsomme des numéros de Sprague-Grundy des trois cavaliers.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Stratégie gagnante};
\end{tikzpicture}
\end{center}

Comme les cavaliers sont initialement sur les cases 9, 8 et 7, la nim-somme du départ est $1\oplus 0 \oplus 3=2$ qui est non nulle. Le joueur qui commence va gagner. Comme le cavalier de la 2e ligne est sur une case de numéro (de Sprague-Grundy) nul, on peut annuler la nimsomme en déplaçant le cavalier du bas sur la même case que celui du haut (nouvelle nimsomme: $3 \oplus 0 \oplus 0=0$:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={ng0,nh1,ng2}]
\end{center}

Si l'adversaire joue ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={ng0,nh1,nd2}]
\end{center}

la nouvelle nimsomme sera $3 \oplus 0 \oplus 0$; on peut l'annuler en "remplaçant le 3 par un 0" (ce qui revient d'ailleurs à imiter le coup précédent):

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nd0,nh1,nd2}]
\end{center}

Si ensuite l'adversaire essaye ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nd0,nf1,nd2}]
\end{center}

la nouvelle nimsomme sera égale à $0 \oplus 2 \oplus 0=2$; on peut l'annuler soit en déplaçant le cavalier du milieu sur une case de numéro de Sprague-Grundy égal à 0 (la case 4), soit en déplaçant un des deux autres cavaliers vers une case de numéro de Sprague-Grundy égal à 2 pour "neutraliser" l'autre 2. Par exemple

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nd0,nf1,nb2}]
\end{center}
   
Ensuite, si par exemple l'adversaire joue ceci:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nd0,nf1,nZ2}]
\end{center}

la nimsomme redevient égale à 2, et on l'annule ainsi:

\begin{center}
\chessboard[zero,labelbottomformat=\arabic{filelabel},maxfield=i2,addpieces={nd0,nd1,nZ2}]
\end{center}

Ensuite il suffit de répéter chaque mouvement de l'adversaire, sur la ligne opposée à celle qu'il vient de choisir: Ainsi on aura des nimsommes du type $n\oplus n=0$ et on gagne. 

\subsection{Tiouk tiouk}





Dans ce jeu, chaque joueur peut déplacer un de ses pions verticalement, d'autant de cases qu'il veut, du moment qu'il ne va pas vers une case occupée:

\begin{center}
\chessboard[addpieces={Ra1,Rb1,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg8,rh8}]
\end{center}

Cette position est équivalente à ce jeu de Nim:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,6}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{2.2}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{4.4}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{6.6}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{8.8}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{11}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{13.2}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{15.4}{0.4*\z}}
\end{tikzpicture}
\end{center}

Chaque tas est codé par le nombre de cases vides dans une colonne, ainsi cette position

\begin{center}
\chessboard[addpieces={Ra1,Rb1,Rc1,Rd1,Re4,Rf1,Rg1,Rh7,
ra8,rb6,rc5,rd8,re5,rf8,rg2,rh8}]
\end{center}

peut être codée par 


\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,6}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,4}{ \sou{2.2}{0.4*\z}}
\foreach \z in {1,...,3}{ \sou{4.4}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{6.6}{0.4*\z}}
%\foreach \z in {1,...,6}{ \sou{8.8}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{11}{0.4*\z}}
\end{tikzpicture}
\end{center}

Mais le tas de la colonne e, qui a été vidé parce que les tours se touchent, peut être réalimenté par le prochain joueur, qui peut reculer sa tour d'1, 2 ou 3 cases et ainsi reconstruire un tas d'1, 2 ou 3 pièces. 


\combi Néanmoins, lorsque toutes les tours d'une couleur sont bloquées en bout de course par des tours de l'autre couleur, la nimsomme des colonnes est égale à 0 et la stratégie de Bouton reste applicable à cette variante de nim où on peut aussi sous certaines conditions, augmenter la taille du tas. Dans le cas présent, la stratégie de Bouton permet à celui qui joue en deuxième, de gagner ainsi:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Systématiquement jouer le symétrique du coup précédent par rapport au centre de l'échiquier.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Stratégie gagnante};
\end{tikzpicture}
\end{center}

Voici un exemple de partie de ce jeu; aux blancs de jouer: 

\begin{center}
\chessboard[addpieces={Ra1,Rb1,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg8,rh8}]
\end{center}

Ils commencent par coincer complètement une tour noire:

\begin{center}
\chessboard[addpieces={Ra7,Rb1,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg8,rh8}]
\end{center}

Les noirs appliquent la stratégie gagnante:

\begin{center}
\chessboard[addpieces={Ra7,Rb1,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg8,rh2}]
\end{center}

Les blancs essayent alors ceci:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg8,rh2}]
\end{center}

Et les noirs appliquent le symétrique de ce coup:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd1,Re1,Rf1,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg2,rh2}]
\end{center}

Les blancs insistent:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd1,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc8,rd8,re8,rf8,rg2,rh2}]
\end{center}


Les noirs aussi:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd1,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc2,rd8,re8,rf8,rg2,rh2}]
\end{center}


Les blancs comprennent que ce n'est pas la meilleure façon de s'y prendre alors il essayent

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd6,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc2,rd8,re8,rf8,rg2,rh2}]
\end{center}

Mais c'est peine perdue:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd6,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc2,rd8,re3,rf8,rg2,rh2}]
\end{center}


Dernière tentative des blancs:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd7,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc2,rd8,re3,rf8,rg2,rh2}]
\end{center}


Et victoire des noirs:

\begin{center}
\chessboard[addpieces={Ra7,Rb7,Rc1,Rd7,Re1,Rf7,Rg1,Rh1,
ra8,rb8,rc2,rd8,re2,rf8,rg2,rh2}]
\end{center}

En effet, dès que les blancs reculent une de leurs tours, les noirs peuvent y coller jusqu'à ce que la tour soit coincée.


\section{Le jeu de Dawson}

\subsection{Sur échiquier}

\subsubsection{Dawson}

T.R. Dawson était un auteur sur le jeu d'échec mais aussi des variantes du style jeu d'échecs en 3D, et celle-ci qui ressemble à un jeu d'échecs simplifié (publiée en 1938 dans \emph{Caissa's wild roses}):

\begin{center}
\def\dawson{Pa1,Pb1,Pc1,Pd1,Pe1,Pf1,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pc3,pd3,pe3,pf3,pg3,ph3,pi3,pj3}
\chessboard[maxfield=j3,addpieces=\dawson]
\end{center}

\subsubsection{règle du jeu}

On joue comme aux échecs mais seulement avec des pions. Les pions ne peuvent pas reculer; si on peut prendre un pion pour l'empêcher d'aller au bout et de se transformer en une autre pièce, on est \emph{obligé} de le faire\footnote{Exercice: Prouver qu'à ce jeu il n'y a jamais de pion qui va à l'autre bout.}. 

\subsubsection{hexapawn}

En mars 1962, Martin Gardner a décrit cette version particulière du jeu d'échecs de Dawson, avec seulement 3 colonnes:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa1,Pb1,Pc1,pa3,pb3,pc3}]
\end{center}



Ce jeu est plus facile à analyser: Les blancs ne peuvent jouer que le bord ou le centre. S'ils jouent le bord:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa2,Pb1,Pc1,pa3,pb3,pc3}]
\end{center}

les noirs doivent prendre:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pb1,Pc1,pa3,pa2,pc3}]
\end{center}

Mais les blancs doivent prendre à leur tour:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa2,Pc1,pa3,pc3}]
\end{center}

Le pion noir en a3 est maintenant bloqué, et les noirs n'ont d'autre choix que de jouer le coup gagnant:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa2,Pc1,pa3,pc2}]
\end{center}

En effet les blancs ne peuvent plus bouger et ont donc perdu.

Finalement ils auraient mieux fait de commencer par le centre:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa1,Pb2,Pc1,pa3,pb3,pc3}]
\end{center}

Le pion blanc en b2 menace maintenant deux pions noirs, en a3 et en c3. Celui en a3 par exemple doit donc prendre le pion blanc:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pa1,pb2,Pc1,pb3,pc3}]
\end{center}

Maintenant c'est un pion blanc qui doit prendre ce pion en b2:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pb2,Pc1,pb3,pc3}]
\end{center}

Les noirs sont à leur tour obligés de prendre ce pion:

\begin{center}
\chessboard[maxfield=c3,addpieces={pb2,Pc1,pb3}]
\end{center}

Enfin les blancs n'ont plus d'autre choix que de prendre ce pion en b2, et gagner la partie:

\begin{center}
\chessboard[maxfield=c3,addpieces={Pb2,pb3}]
\end{center}

En résumé, les blancs, qui commencent, ont tout intérêt à jouer plutôt le milieu, que l'un des bords...

\subsection{version nim}

Mais en général au jeu de Dawson, il faut savoir que jouer en plein milieu aboutit à un vide autour du pion joué: On passe de ça

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pd1,Pe2,Pf1,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pc3,pd3,pe3,pf3,pg3,ph3,pi3,pj3}]
\end{center}


à ça, après les prises de pions (4 victimes du massacre):

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pe2,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pc3,pe3,pg3,ph3,pi3,pj3}]
\end{center}

Chaque fois qu'une paire de pions est tête contre tête ainsi, elle est nécessairement isolée\footnote{Exercice: Prouver ceci.}, et ne compte pas comme un tas. L'échiquier ci-dessus est donc équivalent à ceci:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,4}{ \sou{6}{0.4*\z}}
\end{tikzpicture}
\end{center}

Chaque alignement de pions non encore joués est représenté par un tas de pièces, dont la taille est le nombre de pions alignés. Les pions isolés ne comptent pas puisque personne ne peut plus les jouer. Alors

\begin{itemize}
\item avancer un pion en plein milieu d'une rangée a pour effet de casser le tas de pièces en deux morceaux après en avoir retiré 3 pièces (ce qui a été fait ci-dessus: On est passé de 10 pièces à deux tas de tailles respectives 3 et 4);
\item avancer un pion presque au bord d'une rangée a pour effet d'enlever trois pièces du tas représenté par cette rangée;
\item avancer un pion tout au bord d'une rangée a pour effet d'enlever deux pièces du tas représenté par cette rangée; ci-dessous, les noirs avancent le pion en g2:

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pe2,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pc3,pe3,pg2,ph3,pi3,pj3}]
\end{center}

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pe2,Pg1,Pi1,Pj1,
pa3,pb3,pc3,pe3,Pg2,ph3,pi3,pj3}]
\end{center}

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pe2,Pg1,Pi1,Pj1,
pa3,pb3,pc3,pe3,pg2,pi3,pj3}]
\end{center}

\end{itemize}

La séquence de coups précédents s'illustre donc ainsi sur le tas de pièces (initialement 10 pièces):

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,10}{ \sou{0}{0.4*\z}}
\end{tikzpicture}
\end{center}

Les blancs, en avançant le pion en e1, déclenchent une série d'évènements qui aboutit à retirer 3 pièces du tas et casser le tas résultant en deux:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,4}{ \sou{3}{0.4*\z}}
\end{tikzpicture}
\end{center}

Les noirs, en avançant le pion en g3, retirent simplement deux pièces du second tas:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,3}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,2}{ \sou{3}{0.4*\z}}
\end{tikzpicture}
\end{center}

Cette variante du jeu de nim aide les blancs à gagner: S'ils jouent le pion en b1, en i1 ou en j1, ils vont vider un des deux tas et les noirs vont gagner en vidant l'autre tas; ils vont donc jouer le pion en a1 ou en c1 pour que le premier tas ne soit pas entièrement vide; par exemple ils jouent le pion en a1:

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa2,Pc1,Pe2,Pg1,Pi1,Pj1,
pa3,pc3,pe3,pg2,pi3,pj3}]
\end{center}

Les noirs ne peuvent maintenant que vider le tas d'une pièce (pion en c3) ou le tas de deux pièces (pion en i3 ou j3) et après ça, les blancs gagnent.

Remarque: Si, au lieu de réduire le tas de 4, les noirs avaient vidé totalement le tas de 3, ils auraient gagné; arrivé là:

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pe2,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pc3,pe3,pg3,ph3,pi3,pj3}]
\end{center}


Coup des noirs en deuxième: Pion b3:

\begin{center}
\chessboard[maxfield=j3,addpieces={Pb1,Pe2,Pg1,Ph1,Pi1,Pj1,
pb2,pe3,pg3,ph3,pi3,pj3}]
\end{center}

Il ne reste alors plus qu'un jeu de Dawson à 8 pions (sur les colonnes g à j) et les blancs ne peuvent plus casser ce tas de 4 en 2, mais seulement le réduire à un tas de 2 ou 3, que les noirs vont vider d'un coup: Les noirs gagnent.

Ceci ne veut pas dire que les blancs n'avaient pas de stratégie gagnante, seulement que casser le tas de 10 en deux tas de 3 et 4 n'était pas le meilleur coup. Les blancs pouvaient tenter ceci:

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pd2,Pf1,Pg1,Ph1,Pi1,Pj1,
pa3,pb3,pd3,pf3,pg3,ph3,pi3,pj3}]
\end{center}

Mais dans ce cas les noirs peuvent réduire le tas de 5 en tas de 2 ou 3 et on revient à situation précédente. Alors le premier coup pour les blancs doit être de seulement réduire, et non casser, le tas de 10. Par exemple

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pc1,Pd1,Pe1,Pf1,Pg1,Pi2,
pa3,pb3,pc3,pd3,pe3,pf3,pg3,pi3}]
\end{center}

Les noirs héritent alors d'un jeu de Dawson à 14 pions (colonnes a à g); ils cassent alors le tas de 7 (réduit à 4 après prélèvement de 3 pièces):

\begin{center}
\chessboard[maxfield=j3,addpieces={Pa1,Pb1,Pd1,Pf1,Pg1,Pi2,
pa3,pb3,pd2,pf3,pg3,pi3}]
\end{center}

Quoique jouent les blancs, ils vont vider un des deux tas de 2 résultants (a-b ou f-g), et les noirs, en vidant l'autre tas, gagnent: Ce jeu est donc gagnant pour les noirs. On a vu que le jeu de Dawson à 3 colonnes ("hexapawn") est gagnant pour celui qui joue en premier, alors que le jeu à 10 colonnes est gagnant pour celui qui joue en deuxième. La question se pose alors, de la généralisation à $n$ colonnes. On a ceci:


\begin{center}
\begin{tabular}{|c|c|}
\hline 
nombre de colonnes & gagnant \\ 
\hline 
1 & blancs \\ 
\hline 
2 & blancs \\ 
\hline 
3 & blancs \\ 
\hline 
4 & noirs \\ 
\hline 
5 & blancs \\ 
\hline 
6 & blancs \\ 
\hline 
7 & blancs \\ 
\hline 
8 & noirs \\ 
\hline 
9 & blancs \\ 
\hline 
10 & noirs \\ 
\hline 
\end{tabular} 
\end{center}

 
\section{La dame de Wythoff}

\subsection{Le jeu de Wythoff}

C'est quelques années après l'article de Bouton que Wythoff a publié un article sur cette variante du jeu de nim à deux tas:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Chaque joueur, quand c'est à son tour, retire autant de pièces qu'il veut d'un des deux tas, ou le même nombre de pièces des deux tas en même temps. Le joueur qui prend la dernière pièce a gagné.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Règle du jeu};
\end{tikzpicture}
\end{center}

Voici un exemple de partie de ce jeu:

Au départ, il y a deux tas, respectivement de 7 pièces et de 6 pièces:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,7}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,6}{ \sou{3}{0.4*\z}}
\end{tikzpicture}
\end{center}

Le premier joueur décide d'enlever 5 pièces de \emph{chacun} des tas:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,2}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,1}{ \sou{3}{0.4*\z}}
\end{tikzpicture}
\end{center}

Si le second joueur vide un des deux tas, il perd (en permettant à son adversaire de vider l'autre tas). Alors il ne prend qu'une pièce du tas de gauche:

\begin{center}
\begin{tikzpicture}
\foreach \z in {1,...,1}{ \sou{0}{0.4*\z}}
\foreach \z in {1,...,1}{ \sou{3}{0.4*\z}}
\end{tikzpicture}
\end{center}

Mais comme son adversaire peut enlever un même nombre de pièces des deux tas en même temps, il vide le jeu d'un seul coup, et gagne quand même.

\subsection{sur échiquier}

\subsubsection{coordonnées}

En considérant le premier tas comme l'abscisse d'une dame, et le second tas comme l'ordonnée de la même dame, on obtient un jeu sur échiquier:

\begin{center}
\tikzstyle{mybox} = [draw=black, fill=yellow!10, very thick,
    rectangle, rounded corners, inner sep=10pt, inner ysep=20pt]
\tikzstyle{fancytitle} =[fill=black!90, text=white, very thick, rounded corners, draw=black, rectangle]
%
\begin{tikzpicture}
\node [mybox] (box) {%
    \begin{minipage}[t!]{0.8\textwidth}
\textbf{Une dame est posée sur un échiquier. Chaque joueur, à son tour, déplace la dame, soit vers la gauche (comme une tour), soit vers le bas (comme une tour), soit en diagonale (comme un fou) à la fois vers le bas et la gauche. Le premier qui réussit à mener la dame sur la case a1 a gagné.} 
    \end{minipage}
    };
\node[fancytitle] at (box.north) {Règle du jeu};
\end{tikzpicture}
\end{center}


Voici les correspondances entre le jeu de Wythoff et la dame de Wythoff:

\begin{center}
\begin{tabular}{|c|c|}
\hline 
nim de Wythoff & dame de Wythoff \\ 
\hline 
enlever $n$ pièces du tas de gauche & déplacer la dame de $n$ cases vers la gauche \\ 
\hline 
enlever $n$ pièces du tas de droite & déplacer la dame de $n$ cases vers le bas \\ 
\hline 
enlever $n$ pièces de chacun des tas & déplacer la dame de $n$ cases en diagonale \\ 
\hline 
\end{tabular} 
\end{center}

Les coordonnées (7,6) correspondant à la case h7 (on compte à partir de 0), le jeu précédent devient ceci sur un échiquier:

\begin{center}
\chessboard[addpieces={qh7}]
\end{center}

Le premier joueur prend 5 pièces de chaque tas:

\begin{center}
\chessboard[addpieces={qc2}]
\end{center}

Le second joueur prend une pièce du tas de gauche:

\begin{center}
\chessboard[addpieces={qb2}]
\end{center}

Le premier joueur prend une pièce de chaque tas:

\begin{center}
\chessboard[addpieces={qa1}]
\end{center}

Le premier joueur gagne donc.

La partie peut d'ailleurs être dessinée toute entière sur un seul échiquier, sous forme de positions successives de la dame:

\begin{center}
\chessboard[addpieces={qh7,qc2,qb2,qa1}]
\end{center}


\subsubsection{positions gagnantes}

Mais on peut aussi mettre des pions pour signaler les cases perdantes (celles où il ne faut pas aller parce que depuis une telle case, l'adversaire gagne). Une case est perdante si elle permet d'aller à une case gagnante, et une case est gagnante si elle ne permet d'aller qu'à des cases perdantes. Pour commencer, la case a1 est gagnante, et le autres cases vont être triées entre gagnantes et perdantes, par récursivité vers la droite et vers le haut. On va marquer les cases gagnantes d'une dame blanche, et les cases perdantes de pions noirs. Au début, on a ceci:

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8}]
\end{center}
 
On voit alors deux autres cases gagnantes:

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8,
Qc2,Qb3}]
\end{center}

Ces deux cases gagnantes engendrent pas mal de nouvelles cases perdantes (tout ce qui est à la verticale, à l'horizontale ou à la diagonale de l'une d'entre elles):

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8,
Qc2,Qb3,pd2,pe2,pf2,pg2,ph2,pb4,pb5,pb6,pb7,pb8,
pd3,pe4,pf5,pg6,ph7,pc4,pd5,pe6,pf7,pg8,
pe3,pf3,pg3,ph3,pc5,pc6,pc7,pc8}]
\end{center}

On en déduit deux nouvelles positions gagnantes:

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8,
Qc2,Qb3,pd2,pe2,pf2,pg2,ph2,pb4,pb5,pb6,pb7,pb8,
pd3,pe4,pf5,pg6,ph7,pc4,pd5,pe6,pf7,pg8,
pe3,pf3,pg3,ph3,pc5,pc6,pc7,pc8,Qf4,Qd6}]
\end{center}

et d'autres positions perdantes:

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8,
Qc2,Qb3,pd2,pe2,pf2,pg2,ph2,pb4,pb5,pb6,pb7,pb8,
pd3,pe4,pf5,pg6,ph7,pc4,pd5,pe6,pf7,pg8,
pe3,pf3,pg3,ph3,pc5,pc6,pc7,pc8,Qf4,Qd6,
pd7,pd8,pe7,pf8,pg4,pg5,ph4,ph6}]
\end{center}

Ce qui donne encore deux autres positions gagnantes:

\begin{center}
\chessboard[addpieces={Qa1,pa2,pa3,pa4,pa5,pa6,pa7,pa8,
pb1,pc1,pd1,pe1,pf1,pg1,ph1,pb2,pc3,pd4,pe5,pf6,pg7,ph8,
Qc2,Qb3,pd2,pe2,pf2,pg2,ph2,pb4,pb5,pb6,pb7,pb8,
pd3,pe4,pf5,pg6,ph7,pc4,pd5,pe6,pf7,pg8,
pe3,pf3,pg3,ph3,pc5,pc6,pc7,pc8,Qf4,Qd6,
pd7,pd8,pe7,pf8,pg4,pg5,ph4,ph6,Qe8,Qh5}]
\end{center}

Il y a donc 7 cases (6 en réalité, la case a1 ne permet aucun jeu) sur l'échiquier sur lesquelles placer la dame pour que celui qui joue en second puisse gagner, la dame étant en position gagnante sur une de ces cases (celui qui doit la jouer ne peut, par définition, la mener que vers une case perdante). La stratégie gagnante pour le second joueur consiste alors à mener la dame vers une case marquée d'une dame blanche:

\begin{center}
\chessboard[addpieces={Qa1,Qc2,Qb3,Qf4,Qd6,Qh5,Qe8}]
\end{center}
 

Les autres cases sont celles où placer la dame au début, pour que celui qui joue en premier, dispose d'une stratégie gagnante (aller vers une dame blanche).

On remarque que les dames blanches sont presque alignées sur deux droites symétriques l'une de l'autre par rapport à la diagonale de l'échiquier. Les coefficients directeurs de ces droites sont le nombre d'Or et son inverse.










\section{Grenouilles et crapauds}

\non Le jeu décrit ici n'est pas un jeu de nim\footnote{Ce jeu a été créé par Richard Guy, un grand spécialiste des jeux combinatoires}, mais comme il se joue sur un échiquier, on va le décrire quand même; et "la dame de Wythoff et les grenouilles", ça fait un peu conte de fées, et constituerait un bon titre pour cet article. Comme il n'y a ni grenouille ni crapaud parmi les pièces classiques du jeu d'échecs, on va les remplacer par des chevaux de deux couleurs, qui peuvent sauter les uns par-dessus les autres comme les grenouilles:


\subsection{Règle du jeu}

L'un des joueurs a les chevaux blancs, l'autre, les chevaux noirs. Chacun son tour choisit un de ses chevaux, puis le glisse vers la case adjacente si elle est vide (les chevaux blancs, vers la droite, les chevaux noirs, vers la gauche); ou alors, saute par-dessus un cheval de l'autre couleur (toujours vers la droite pour les blancs et la gauche pour les noirs), à condition que la case suivante soit libre. Lorsqu'on saute par dessus un autre cheval, on ne le prend pas. Mais le premier joueur qui est bloqué (ne peut plus jouer) a perdu.

\subsection{Exemple de partie}



Au début, on a 2 chevaux par joueur, disposés ainsi:
 

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\WhiteEmptySquare
\BlackKnightOnBlack
\BlackKnightOnWhite
}
\end{center}

Les blancs commencent, et comme le cheval en a1 n'a pas le droit de sauter par-dessus un cheval de sa couleur, le seul mouvement possible est celui-ci:

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\WhiteEmptySquare
\BlackKnightOnBlack
\BlackKnightOnWhite
}
\end{center}

Pour la même raison, le premier mouvement des noirs ne peut être que celui-ci:

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Maintenant les blancs peuvent choisir le cheval à avancer, par exemple s'ils choisissent celui en a1:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Les noirs aussi ont le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Maintenant les blancs n'ont pas le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Les noirs peuvent avancer le cheval qui est encore à l'écurie ou faire sauter le cheval du milieu; ils font ce choix:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Du coup les blancs n'ont à nouveau plus le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

Le cheval noir de gauche pourrait aller à l'arrivée en sautant par-dessus le blanc, mais les noirs préfèrent sortir l'autre cheval de l'écurie\footnote{Le but du jeu n'est pas d'arriver le premier, mais de bloquer l'adversaire}:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
\WhiteEmptySquare
}
\end{center}

Les blancs ont aussi le choix entre un saut et une avancée, par exemple ils sautent:

\begin{center}
\framebox {
\BlackEmptySquare
\WhiteEmptySquare
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnWhite}
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
\WhiteEmptySquare
}
\end{center}

Maintenant le cheval noir le plus avancé mettra plus de temps pour arriver au bout:

\begin{center}
\framebox {
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
\WhiteEmptySquare
}
\end{center}

Les blancs n'ont à nouveau plus le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
}
\end{center}


Ce qui augmente momentanément la mobilité des noirs:

\begin{center}
\framebox {
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\WhiteEmptySquare
}
\end{center}

Les blancs n'ont de nouveau plus le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
}
\end{center}

Les noirs pour ne pas être bloqués trop vite, choisissent de commencer à avancer lentement, sans sauter:

\begin{center}
\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
}
\end{center}

Mais, hélas pour eux, les blancs imitent cette stratégie:

\begin{center}
\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

Les noirs sont donc obligés de sauter:

\begin{center}
\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

La partie se finit toute seule: Les blancs avancent:

\begin{center}
\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

puis les noirs:

\begin{center}
\framebox {
\BlackKnightOnBlack
\BlackKnightOnWhite
\BlackEmptySquare
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

puis les blancs:

\begin{center}
\framebox {
\BlackKnightOnBlack
\BlackKnightOnWhite
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

Et les noirs, ne pouvant plus jouer, ont perdu.

\subsection{analyse du jeu}

\subsubsection{cas général}

Avec une rangée de 8 cases, il y a $3^8=6561$ débuts de parties possibles (3 choix par case, à savoir, case vide, cheval noir ou cheval blanc). Mais beaucoup sont inintéressants comme ceux-ci qui mènent à des parties injouables parce que les chevaux sont bloqués depuis le début:

Chevaux déjà arrivés: 

\begin{center}
\framebox {
\BlackKnightOnBlack
\BlackKnightOnWhite
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\WhiteEmptySquare
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

Pas de place:

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\BlackKnightOnWhite
\BlackKnightOnBlack
\BlackKnightOnWhite
}
\end{center}

\subsubsection{Jeux minimaux}

Dans ce jeu, le premier qui joue gagne:

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
}
\end{center}

En effet, la partie se joue seule, les blancs n'ayant pas le choix:

\begin{center}
\framebox {
\BlackEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\BlackKnightOnBlack
}
\end{center}

Les noirs n'ont pas le choix non plus:

\begin{center}
\framebox {
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnBlack}
\BlackEmptySquare
}
\end{center}

Les blancs ne peuvent plus rien faire qu'avancer:

\begin{center}
\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
}
\end{center}

Dans ce jeu aussi, c'est celui qui commence qui gagne le jeu:

\begin{center}
\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\BlackKnightOnWhite
}
\end{center}

En effet:

\begin{itemize}
\item Si les blancs commencent, on a cette partie:

\begin{center}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\BlackKnightOnWhite
}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\BlackKnightOnWhite
}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\BlackKnightOnWhite
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}
\end{center}

Les noirs sont bloqués, ils ne peuvent plus jouer.

\item Si ce sont les noirs qui commencent, malgré le fait qu'ils n'ont qu'un cheval, celui-ci n'est pas facile à bloquer:

\begin{center}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackEmptySquare
\BlackKnightOnWhite
}

\framebox {
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
\BlackKnightOnBlack
\WhiteEmptySquare
}


\framebox {
\reflectbox{\WhiteKnightOnBlack}
\WhiteEmptySquare
\BlackKnightOnBlack
\reflectbox{\WhiteKnightOnWhite}
}


\framebox {
\reflectbox{\WhiteKnightOnBlack}
\BlackKnightOnWhite
\BlackEmptySquare
\reflectbox{\WhiteKnightOnWhite}
}

\framebox {
\BlackEmptySquare
\BlackKnightOnWhite
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
}


\framebox {
\BlackKnightOnBlack
\WhiteEmptySquare
\reflectbox{\WhiteKnightOnBlack}
\reflectbox{\WhiteKnightOnWhite}
}

\end{center}

Les blancs sont bloqués, ils ne peuvent plus bouger et ont donc perdu.

\end{itemize}







\section{Références et chronologie}

\begin{itemize}
\item Claude Gaspard Bachet de Méziriac a décrit, \textit{dans problèmes plaisans et délectables}, en 1612, un jeu dit "de poursuite" ou "de l'addition", qui est équivalent au jeu de soustraction décrit dans cet article: Au lieu de soustraire 1, 2 ou 3 au nombre courant, on additionne 1, 2 ou 3 jusqu'à atteindre ou dépasser un seuil. La stratégie gagnante est la même.
\item Charles Leonard Bouton a publié en 1901 un article titré \textit{Nim, a game with a complete mathematical theory}, où est utilisé pour la première fois le nom de "nim", pour décrire le jeu à plusieurs tas.
\item C'est en 1907 que W.A. Wythoff publie la variante de Nim où on peut aussi enlever un même nombre de pièces des deux tas.
\item En 1936, Roland Sprague a découvert une généralisation de la stratégie gagnante de Bouton, au cas où il y a des restrictions sur le nombre d'objets que l'on peut prélever. L'article fut publié à Berlin sous le titre \textfrak{Über mathematische Kampfspiele}.
\item Thomas Rayner Dawson était un spécialiste britannique du jeu des échecs. En 1938 il a publié un livre titré \textit{Caissa's Wild Roses}, composé de poèmes sur le jeu d'échecs et de descriptions de variantes du jeu, parmi lesquelles le jeu dit "Dawson's chess". 
\item En 1939, toujours en Grande-Bretagne, Patrick Grundy redécouvre la stratégie de Roland Sprague, qui s'appelle désormais \emph{stratégie de Sprague-Grundy}. C'est dans \textit{Mathematics and games} qu'il a publié ce résultat.
\item En 1952, aux Pays-Bas, Fred Schuh décrivait une variante du jeu de la soustraction, où on divise au lieu de soustraire. son article est titré \textit{Spel van delers}.
\item En 1954, aux Pays-Bas, C.P. Welter publia un article titré \textit{the theory of a class of games on a sequence of squares, in terms of the advancing operation in a special group}, décrivant le jeu de Welter sur une seule ligne de l'échiquier.
\item C'est en 1962 que Martin Gardner, célèbre chroniqueur de jeux mathématiques, publie dans \textit{Pour la science} la description d'hexapawn (il s'agit d'une machine mécanique pouvant apprendre à jouer à ce jeu).
\item En 1965, dans \textit{differential games}, Rufus Issacs décrit une variante du jeu de Wythoff: La dame de Wythoff sur échiquier.
\item Elwyn Berlekamp est connu dans le monde de l'algèbre (comme auteur d'un algorithme de factorisation de polynômes); en 1972 il a donné des renseignements supplémentaires sur le jeu de Welter dans \textit{Some recent results on the combinatorial game called Welter's Nim}.
\item En 1973, David Gale (mathématicien de l'économie) réinventait le jeu de Fred Schuh, sous forme géométrique. L'article est titré \textit{on curious nim-type games}, mais  le jeu est rebaptisé "chomp" par Martin Gardner dans \textit{Pour la science}.
\item En 1982, Berlekamp ainsi que le célèbre mathématicien John Conway, et le spécialiste des jeux Richard Guy, publie le livre \textit{Winning ways for your mathematical plays}, qui est une mine d'informations sur les jeux combinatoires et plus particulièrement nim et ses variantes. 

\end{itemize}



\end{document}
