\def\NomChapitre{Jeux}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}


\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\tikzstyle{pre}=[->,>=stealth,semithick] % arêtes orientées.
\tikzstyle{j1} =[circle,thick,inner sep=0pt,minimum size=6mm,node distance=20mm,draw=black!50,fill=blue!5]
\tikzstyle{j2}=[circle,thick,inner sep=0pt,minimum size=6mm,node distance=20mm,draw=black!50,fill=red!5]



\section{Jeu de Chom(2,3)} 
Le but de ce TP est de faire tourner l'algorithme Max-Min sur le graphe
biparti du jeu de chomp(2,3) vu en cours. 

\begin{exo}[Graphe de départ]
Ce graphe est aussi appelé arène, il ne contient pas l'information « qui joue
». 
\begin{center}
\includegraphics[height=150pt]{Chomp2.jpg}
\end{center}

Créer une liste d'adjacence \lstinline$G0$ codant le graphe ci-dessus.

\end{exo}

\begin{exo}[Création du graphe biparti]
  Nous allons coder le graphe biparti à l'aide d'un dictionnaire, en essayant
  de structurer le code.
Voici le graphe biparti :

\begin{center}
\begin{tikzpicture}[>=stealth,scale=1]
  \node[j1]   (0a)  at (0,-0)  {$0_a$};
  \node[j1]   (1a)  at (0,-1)  {$1_a$};
  \node[j1]   (3a)  at (0,-3)  {$3_a$};
  \node[j1]   (4a)  at (0,-4)  {$4_a$};
  \node[j1]   (5a)  at (0,-5)  {$5_a$};
  \node[j1]   (6a)  at (0,-6)  {$6_a$};
  \node[j1]   (7a)  at (0,-7)  {$7_a$};
  \node[j1]   (8a)  at (0,-8)  {$8_a$};
  \node[j2]   (1b)  at (3,-1)  {$1_b$};
  \node[j2]   (2b)  at (3,-2)  {$2_b$};
  \node[j2]   (3b)  at (3,-3)  {$3_b$};
  \node[j2]   (4b)  at (3,-4)  {$4_b$};
  \node[j2]   (5b)  at (3,-5)  {$5_b$};
  \node[j2]   (6b)  at (3,-6)  {$6_b$};
  \node[j2]   (7b)  at (3,-7)  {$7_b$};
  \node[j2]   (8b)  at (3,-8)  {$8_b$};
% Légende :
  \node[j1, label={Joueur $1$}]   ()  at (7,-2)  {$ $};
  \node[j2, label={Joueur $2$}]   ()  at (7,-5)  {$ $};
% flèches soulignées.
\begin{pgfonlayer}{background}

\end{pgfonlayer}
% flèches et numéros
  \draw[pre] (0a) to (1b) ;
  \draw[pre] (0a) to (2b) ;
  \draw[pre] (0a) to (3b) ;
  \draw[pre] (0a) to (4b) ;
  \draw[pre] (0a) to (5b) ;
  \draw[pre] (1a) to (4b) ;
  \draw[pre] (1a) to (5b) ;
  \draw[pre] (1a) to (6b) ;
  \draw[pre] (3a) to (5b) ;
  \draw[pre] (3a) to (6b) ;
  \draw[pre] (3a) to (7b) ;
  \draw[pre] (4a) to (7b) ;
  \draw[pre] (4a) to (8b) ;
  \draw[pre] (5a) to (8b) ;
  \draw[pre] (6a) to (5b) ;
  \draw[pre] (6a) to (7b) ;
  \draw[pre] (7a) to (8b) ;
  \draw[pre] (1b) to (4a) ;
  \draw[pre] (1b) to (5a) ;
  \draw[pre] (1b) to (6a) ;
  \draw[pre] (2b) to (1a) ;
  \draw[pre] (2b) to (3a) ;
  \draw[pre] (2b) to (4a) ;
  \draw[pre] (2b) to (5a) ;
  \draw[pre] (3b) to (5a) ;
  \draw[pre] (3b) to (6a) ;
  \draw[pre] (3b) to (7a) ;
  \draw[pre] (4b) to (7a) ;
  \draw[pre] (4b) to (8a) ;
  \draw[pre] (5b) to (8a) ;
  \draw[pre] (6b) to (5a) ;
  \draw[pre] (6b) to (7a) ;
  \draw[pre] (7b) to (8a) ;
%\draw[pre,bend right=20] (y) to node[auto,swap] {$3$} (t) ;
\end{tikzpicture}
\end{center}


\begin{enumerate}
\item Dans un premier temps, on code les arêtes des sommets $x_a$ vers les
  sommets $y_b$ par une liste d'adjacence $G_a$ : 
\lstinline$Ga[0]$ contient la liste 
\lstinline$[1, 2, 3, 4, 5]$ car le joueur $J_1$, depuis le sommet $0$, peut
aller vers les sommets $1$ à $5$. 


Vous êtes invités à utiliser 
\lstinline$G0$ construit à l'exercice précédent autant que possible.

Dans un premier temps, plutôt qu'une absence de sommet $2_a$, on codera un
sommet isolé : la liste des flèches depuis $2_a$ sera vide, {\em id est}
\lstinline$Ga[2]==[]$.

\item Créer la liste $G_b$ des flèches des sommets $y_b$ vers les sommets
  $x_a$. 
\item Créer un dictionnaire \lstinline$G$ dont les clefs sont les sommets du
  graphe biparti au format chaine de caractère
(\lstinline$'0a'$), et les valeurs associées aux clefs des listes de clefs :

\begin{lstlisting}[frame=single,linewidth=10cm]
>>> G['1b']
['4a', '5a', '6a']
\end{lstlisting}
\item (Bonus) Créer une fonction qui prend un graphe de jeu (donné par une
  liste d'adjacence sous forme de liste de liste, comme
  \lstinline$G0$) et qui retourne le graphe biparti associé sous forme de
  dictionnaire.
\end{enumerate}
\end{exo}

\begin{exo}[Max-Min]
Le but de l'exercice est de coder l'algorithme Max-Min décrit dans le cours :
Lors d'un parcours en profondeur du graphe, on remonte les valeurs
alternativement minimales (si c'est $J_2$ qui joue) ou maximales (si c'est
$J_1$):

\begin{enumerate}
\item Écrire une fonction \lstinline$h(s)$ qui prend en argument un sommet
  \lstinline$s$ du graphe biparti -- donc une clef du dictionnaire construit à
  l'exercice précédent -- et qui retourne $1$ si le sommet est
  un état final pour $J_1$, $-1$ si c'est un état final pour $J_2$, et $0$
  sinon.
\item Écrire une fonction, 
\lstinline$maximin(s)$  qui retourne \lstinline$h(s)$ si le sommet
\lstinline$s$ n'a pas de successeurs, et sinon le maximum sur les successeurs
$u$ de \lstinline$s$ du (minimum sur les successeurs $u'$ de $u$ du (maximum
sur les successeurs de $u'$ etc)) : on s'aidera d'une fonction 
\lstinline$minimax(s)$.
\item Modifier les fonctions précédentes pour que les appels récursifs
  s'arrêtent au bout de $n$ étapes : 
\lstinline$maximin(s, n)$ et 
\lstinline$minimax(s, n)$.
\end{enumerate}
On testera toutes ses fonctions sur le graphe précédent.
\end{exo}



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