\def\NomChapitre{Le jeu de Chomp}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}


%%%% Rectifier : coordonnées:
%  (x,y), carré empoisonné en bas à gauche, et problème matrice (i,j)
%  (i,j) et carré empoisonné en haut à gauche

Nous suivons en grande partie le TP de Mickaël Péchaud, dont l'original est à
l'adresse :
\href{https://mpechaud.fr/itc.html#dyn}{http://mpechaud.fr} 
% (\href{mailto:mickaelpechaud@protonmail.com}{mickaelpechaud@protonmail.com})

Nous allons jouer à un jeu à 2 joueurs, sans match nul, suffisamment simple
pour que la notion de stratégie gagnante apparaisse naturellement.

\section{Règle du jeu} 


Le jeu du chocolat empoisonné (ou \emph{chomp} en anglais) se joue à deux
joueur·se·s, noté·e·s dans la suite $J_1$ et $J_2$. 

On dispose d'une tablette de chocolat, et l'on suppose que le carré en bas à
gauche est empoisonné.

À tour de rôle, chaque joueur·se, en commençant par $J_1$, doit manger l'un
des carrés (repéré par ses coordonnées),
ainsi que tous ceux qui se
trouvent au dessus et/ou à droite. La personne qui mange le carré
empoisonné meurt et a donc perdu. L'autre joueur·se, qui est resté en
vie, a gagné. On ne peut pas passer son tour.

Le schéma ci-dessous montre le début d'une partie qui démarre d'une tablette
$5\times 3$. 

\medskip


\begin{center}
  \begin{tikzpicture}
    [every node/.style={minimum size=1cm-\pgflinewidth, outer sep=0pt},
    choix/.style={color=white, circle, draw, fill, minimum size=2pt}]
    \scalebox{.75}{
\path[use as bounding box] (0,2.25) rectangle (9.75,-6);
      %%%% 
  \draw[step=1cm] (0,0) grid (5,3);
  \foreach \x in {0,...,4}
  \foreach \y in {0,...,2}
  {
    \node[fill=brown] at (\x+.5,\y+.5) {};
  }
  \node[fill=black!60!red] at (0.5,0.5) {};
  \node[choix] at (3.5,1.5) {};
  \draw[ultra thick] (3,1) rectangle (5,3);

  \foreach \x in {0,...,4}
  \node at (\x+0.5, -0.5) {\x};

  \foreach \y in {0,...,2}
  \node at (-.5, \y+0.5) {\y};

  \node (t1) at (5, 1.5) {};
  \node (t2) at (7.5, 1.5) {};

  \path [->](t1) edge node[above] {$J_1$ joue (3,1)} (t2);
  %%%%
  \draw[step=1cm] (8,0) grid (13,3);
  \foreach \x in {0,...,2}
  \foreach \y in {0,...,2}
  {
    \node[fill=brown] at (8+\x+.5,\y+.5) {};
  }
  \node[fill=brown] at (8+3+.5,0+.5) {};
  \node[fill=brown] at (8+4+.5,0+.5) {};
  
  \node[fill=black!60!red] at (8.5,0.5) {};
  \node[choix] at (8+1.5,2.5) {};
  \draw[ultra thick] (8+1,2) rectangle (8+5,3);

  \foreach \x in {0,...,4}
  \node at (8+\x+0.5, -0.5) {\x};

  \foreach \y in {0,...,2}
  \node at (8-.5, \y+0.5) {\y};

  \node (t3) at (10.5, -1) {};
  \node (t4) at (10.5, -3.5) {};

  \path [->](t3) edge node[left] {$J_2$ joue (1,2)} (t4);
  
  %%%%%
  \draw[step=1cm] (8,0-7) grid (13,3-7);

  \foreach \x in {0,...,2}
  \foreach \y in {0,...,1}
  {
    \node[fill=brown] at (8+\x+.5,\y+.5-7) {};
  }
  \node[fill=brown] at (8+3+.5,0+.5-7) {};
  \node[fill=brown] at (8+4+.5,0+.5-7) {};
  \node[fill=brown] at (8+0+.5,2+.5-7) {};
  
  \node[fill=black!60!red] at (8.5,0.5-7) {};
  \node[choix] at (8+1.5,.5-7) {};
  \draw[ultra thick] (8+1,-7) rectangle (8+5,3-7);

  \foreach \x in {0,...,4}
  \node at (8+\x+0.5, -0.5-7) {\x};

  \foreach \y in {0,...,2}
  \node at (8-.5, \y+0.5-7) {\y};

  \node (t5) at (5, -7+1.5) {};
  \node (t6) at (7.5, -7+1.5) {};

  \path [->](t6) edge node[above] {$J_1$ joue (1,0)} (t5);
  %%%%%%%%% 
  \draw[step=1cm] (0,0-7) grid (5,3-7);

    \foreach \x in {0}
  \foreach \y in {0,...,2}
  {
    \node[fill=brown] at (\x+.5,-7+\y+.5) {};
  }
  \node[fill=black!60!red] at (0.5,-7+0.5) {};

  \foreach \x in {0,...,4}
  \node at (\x+0.5, -7+-0.5) {\x};

  \foreach \y in {0,...,2}
  \node at (-.5, -7+\y+0.5) {\y};
  }
\end{tikzpicture} 
\end{center}
Une « position » est un état de la tablette : nous avons  $4$ positions
successives ci-dessus.

\section{Pratique}

\begin{exo}
~\\\vspace{-1cm}
\begin{enumerate}
\item Dans l'exemple précédent, à partir de la dernière position, $J_2$
  peut-il jouer un coup qui lui permet de  gagner à coup sûr ? 
\item Formez des binômes, découpez des carrés, et jouez
  quelques parties avec différentes tailles de grilles, $2\times 3$, $4\times
  3$, $4\times 4$, pour vous familiariser avec le jeu.
\item Désormais, on s'intéresse au caractère gagnant ou perdant d'une position
  donnée. La définition rigoureuse est ci-dessous.

Que pensez-vous des positions suivantes:
  \begin{enumerate}
  \item Ligne $n\times 1$ ou $1\times n$ (où $n\geq 1$)?
    \begin{tikzpicture}[scale=0.25,every node/.style={scale=0.25, minimum size=1cm-\pgflinewidth, outer sep=0pt}]
      %%%% 
%  \draw[step=1cm,color=grey] (0,0) grid (5,3);
  \foreach \x in {0,...,4}
  {
    \node[fill=brown] at (\x+.5,.5) {};
  }
  \node[fill=black!60!red] at (0.5,0.5) {};  
\end{tikzpicture}

  \item Position en «L» avec les deux branches de même longueur
  \begin{tikzpicture}[scale=0.25,every node/.style={scale=0.25, minimum
      size=1cm-\pgflinewidth, outer sep=0pt}] 
      %%%% 
      % \draw[step=1cm,color=grey] (0,0) grid (5,3);
      \foreach \x in {0,...,2}
      {
        \node[fill=brown] at (\x+.5,.5) {};
        \node[fill=brown] at (.5,\x+.5) {};
      }
      \node[fill=black!60!red] at (0.5,0.5) {};
  \end{tikzpicture}
  
\item Position en «L» avec les deux branches de longueurs différentes
  \begin{tikzpicture}[scale=0.25,every node/.style={scale=0.25, minimum size=1cm-\pgflinewidth, outer sep=0pt}]
      %%%% 
      % \draw[step=1cm,color=grey] (0,0) grid (5,3);
      \foreach \x in {0,...,5}
      {
        \node[fill=brown] at (\x+.5,.5) {};
      }
      \foreach \x in {0,...,2}
      {
        \node[fill=brown] at (.5,\x+.5) {};
      }
      \node[fill=black!60!red] at (0.5,0.5) {};
  \end{tikzpicture}
\item Tablette carrée
  \begin{tikzpicture}[scale=0.25,every node/.style={scale=0.25, minimum size=1cm-\pgflinewidth, outer sep=0pt}]
      %%%% 
      % \draw[step=1cm,color=grey] (0,0) grid (5,3);
      \foreach \x in {0,...,3}
      \foreach \y in {0,...,3}
      {
        \node[fill=brown] at (\x+.5,\y+.5) {};
      }
      \node[fill=black!60!red] at (0.5,0.5) {};
  \end{tikzpicture}
\end{enumerate}
\end{enumerate}
\end{exo}
\begin{deftn}
Les définitions de « position gagnante » et « position perdante »
  sont les suivantes :
\begin{itemize}
\item Une position est \emph{gagnante} si la personne qui joue à
  partir de cette position peut parvenir à gagner en fin de partie
  quels que soient les coups de son adversaire: si c'est à $J_1$ de jouer,
  il existe un coup pour $J_1$, tel que, quel que soit le coup suivant de
  $J_2$, il existe un coup pour $J_1$ etc.. jusqu'au moment où $J_2$ est
  obligé de manger le carré empoisonné.
\item Une position est \emph{perdante} si la personne qui joue à
  partir de cette position ne peut que perdre en fin de partie
  quel que soit les coups qu'elle joue: si c'est à $J_1$ de jouer,
  quel que soit le coup de $J_1$, il existe un coup suivant de
  $J_2$ tel que, quel que soit le coup de $J_1$ etc.. jusqu'au moment où $J_1$
  est obligé de manger le carré empoisonné. 
\end{itemize}
Un définition récursive, équivalente, et plus rigoureuse (sans « etc ») :
\begin{itemize}
\item La position où ne reste que le carré empoisonné est perdante.
\item Pour une position $P$ donnée,
  \begin{itemize}
  \item[$\circ$] s'il existe un coup jouable permettant de passer de $P$ à une
    position perdante, alors $P$ est gagnante, 
  \item[$\circ$] si tout coup jouable à partir de $P$ amène dans une position
    gagnante, alors $P$ est perdante.
  \end{itemize}
\end{itemize}

\end{deftn}

\section{Formalisation du jeu}

\begin{exo}
On considère une tablette $n\times m$, $n,m\in \N^2$.
 Justifiez qu'une partie se termine toujours, et qu'il y a à la fin un·e
  gagnant·e. En combien de coup maximum une partie se termine-t-elle? 
\end{exo}

\begin{exo}[graphe associés à un jeu]
Nous allons construire un graphe représentant les positions et les coups
  possibles. Ce graphe s'appelle l'{\em arène} associée au jeu :
\begin{itemize}
\item Les sommets $s\in \mcS$ du graphe sont les positions possibles.
\item Le couple $(s_1,s_2) \in \mcS^2$ est une  arête s'il existe un coup
  permettant de passer de $s_1$ à $s_2$.
\end{itemize}
Ainsi, l'illustration au début du TP est un morceau du graphe cherché : les
sommets sont des positions, les flèches entre les positions représentent des
arêtes (= les coups). Mais ce n'est qu'un morceau : il manque des sommets
(toutes les positions possibles ne sont pas représentées) 
et il manque donc des arêtes --
mais il manque même des arêtes entre les sommets présents : par exemple, il
existe une arête entre la première et la dernière position.

\medskip

On considère désormais une petite tablette, $2\times 3$.
On notera $\mcS$ l'ensemble des sommets, et $\mcA$ l'ensemble des arêtes. 
\begin{enumerate}
\item Tracer l'arène associée au jeu de Chomp(2,3). 
\item Est-ce qu'il y a un ou des sommets dont ne part aucune arête ? Que
  représente ce sommet ?

Un tel sommet est appelé sommet sans successeur. 
\item Le graphe peut-il avoir des cycles ? 

Rappel : un cycle est une suite de sommets $(s_0,\dots,s_n)$ tels que 
\begin{itemize}
\item $s_0=s_n$
\item $\forall i\in \inte 0{n-1}$, $(s_i,s_{i+1})\in \mcA$.
\end{itemize}
\indic{Associer une valeur entière $n(s)$ à chaque sommet $s\in \mcS$, de façon
  simple. Déterminer une propriété du couple $(n(s_1), n(s_2))$ pour toute
  arête $(s_1,s_2) \in \mcA$.}
\item Montrer qu'un graphe sans cycle\footnote{Un tel graphe est dit {\em
      acyclique}.} possède forcément des sommets sans successeur.
\end{enumerate}
\end{exo}

\begin{exo}[graphe bipartie associés à un jeu]
Désormais, on veut distinguer les positions où c'est à $J_1$ de jouer, de
celles de où c'est à $J_2$.
\begin{enumerate}
\item Tracer l'arène associée au jeu de Chomp(2,3), en remplaçant, pour les
  sommets, les dessins de positions par des numéros (ici, $\inte 08$). 

On numérotera par $0$ la position de départ, et $8$ la position sans
successeur. On gardera une table de 
  correspondance numéro/dessin.
\end{enumerate}
Graphe biparti associé au jeu: Le nouveau graphe associé au jeu aura des sommets contenant
l'information de la position (donc le numéro $n\in\inte 08$) et du joueur 
  qui contrôle la position : le sommet s'appellera $n_a$ ou $n_b$, selon que
  c'est à $J_1$ ou $J_2$ de jouer.

 Exemples : La position de départ $0$ ne peut pas être contrôlée par $J_2$, donc seul le
  sommet $0_a$ existe. Comme $J_1$ et $J_2$ peuvent gagner, $8_a$ et $8_b$
  existent. 

On note $\mcS_a$ les sommets d'indices $a$, contrôlés par $J_1$, et $\mcS_b$
ceux d'indice $b$, contrôlés par $J_2$. 

Remarquons que :
\begin{itemize}
\item $\mcS = \mcS_a\cup \mcS_b$ et $\mcS_a\cap \mcS_b = \emptyset$.
\item Il n'y a aucune arête entre deux sommets de $\mcS_a$, ou entre deux
  sommets de $\mcS_b$.
\end{itemize}
Les deux points ci-dessus sont la définition d'un graphe « biparti ».
\begin{enumerate}[resume]
\item Tracer le graphe biparti associé à Chomp(2,3). Traditionnellement, on
  note les sommets sur $2$ colonnes, les sommets de $\mcS_a$ puis ceux de
  $\mcS_b$. 
\end{enumerate}
\end{exo}

\section{Python}

Nous allons commencer à écrire des fonctions permettant de tester si
une position est gagnante ou perdante. Nous choisissons pour ce faire
de coder une position sous forme d'une liste d'entiers contenant le
nombre de carrés de chocolats dans chaque ligne, les lignes étant
parcourues de bas en haut. Ainsi, les quatre positions successives
données sur la première page correspondent aux listes suivantes:
\begin{itemize}
\item \verb+[5, 5, 5]+
\item \verb+[5, 3, 3]+
\item \verb+[5, 3, 1]+
\item \verb+[1, 1, 1]+
\end{itemize}
Par convention, une telle liste ne contiendra jamais de 0. On écrira donc \verb+[2, 1]+ au lieu de \verb+[2, 1, 0, 0]+.

Dans la suite de l'énoncé, le terme \emph{position} désignera une
telle liste.

Par ailleurs, un \emph{coup} sera codé par le couple de coordonnées
correspondant au carré choisi.

\medskip


\begin{enumerate}
\item Compléter la fonction \verb+tablette(m, n)+ qui prend en
  argument deux entiers non-nuls, et renvoie la position correspondant à
  une tablette à $m$ colonnes et $n$ lignes.
\item Tester la fonction \verb+affiche(pos)+, qui prend en argument une
  position, et l'affiche à l'aide de chaînes de caractères -- $\square$
  désignant un carré commestible, et $\blacksquare$ le carré
  empoisonné.
\item Compléter la fonction \verb+coups_jouables(pos)+, qui prend en
  argument une position et renvoie la liste des coups jouables --
  i.e. la liste des coordonnées de tous les carrés de la position. Par
  convention, $(0,0)$ n'est pas un coup jouable.
\item Compléter la fonction \verb+enleve_0(l)+, qui prend en argument
  une liste \verb+l+ et la modifie par effet de bord en enlevant tous
  les éventuels 0 qu'elle contient à sa fin.
\item Compléter la fonction \verb+joue(pos, coup)+, qui prend en
  argument une position de départ et un coup jouable pour cette
  position, et renvoie une nouvelle position correspondant à la
  position obtenue en jouant le coup à partir de la position de
  départ. Il est conseillé avant de se lancer dans l'écriture du code
  d'effectuer quelques essais à la main.\\ Quelle est la complexité de
  votre fonction?
\item En utilisant la définition récursive de « position gagnante », compléter
  la fonction \verb+gagnante(pos)+ qui prend en argument 
  une position, et teste si elle est gagnante (elle renverra un
  booléen). Penser à la tester sur quelques exemples. 
\item
  \begin{enumerate}
  \item Justifier que votre fonction termine.
  \item Majorer (très grossièrement) le nombre de positions
    accessibles dans une partie démarrant depuis une tablette
    $n\times m$.\footnote{Calculer exactement ce nombre est un bon exercice de dénombrement.}
  \item Afin de compter le nombre d'appels récursifs effectués par
    votre fonction, ajouter au début de celle-ci les lignes suivantes,
    qui permettent d'incrémenter un compteur global, défini à
    l'extérieur de la fonction:
\begin{verbatim}
global compteur
compteur += 1
\end{verbatim}

    Tester alors par exemple avec
\begin{verbatim}
compteur = 0
print(gagnante(tablette(4, 5)))
print(compteur)
\end{verbatim}
    Comparer le résultat obtenu avec celui de la question précédente,
    et commenter.
    
  \end{enumerate}
\end{enumerate}

Afin d'éviter les calculs redondants, on souhaite mémoriser le
caractère gagnant ou perdant des positions déjà rencontrées afin de ne
pas avoir à le recalculer (mémoïsation).

Pour cela, on va utiliser un \emph{dictionnaire}
\begin{itemize}
\item dont les clés correspondent aux positions
\item dont les valeurs sont des booléens indiquant si la position est gagnante ou perdante.
\end{itemize}

Il est impossible d'utiliser une liste \verb+pos+ comme clé d'un dictionnaire,
donc on utilisera à la place un tuple ou une chaîne, que vous pourrez
obtenir à l'aide des fonctions \verb+tuple(pos)+ ou \verb+str(pos)+.

Ainsi, les entrées du dictionnaire ressembleront à
\begin{verbatim}
{
'2' : True,
'2-1' : False,
'2-2' : True,
...
}
\end{verbatim}

\medskip
\begin{enumerate}[resume]
\item Compléter la fonction \verb+gagnante_memo(pos, dict)+, qui prend
  en argument une position et un dictionnaire, en vous inspirant de la
  fonction \verb+gagnante+. Cependant, la nouvelle fonction devra
  commencer par tester si la position apparaît déjà dans le
  dictionnaire, auquel cas il suffira de renvoyer la valeur
  correspondante. Si ça n'est pas le cas, la position et sa valeur
  devront être rajoutées au dictionnaire avant de renvoyer le
  résultat. \verb+dict+ sera donc modifié par effet de bord.
\item Testez votre fonction, et comparez empiriquement son temps
  d'exécution à celui de \verb+gagnante+. Quelle est sa complexité?
\end{enumerate}


%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: FeuilleChomp_2023
%%% End:
