\documentclass[11pt]{article}

\usepackage{fullpage,french,epsf,fancyheadings}

\pagestyle{fancy}
\lhead{Algorithmes pour les jeux : stratégie min-max}
\rhead{Jean-Christophe Filliâtre}

\reversemarginpar
\newcommand{\question}{\marginpar{\hfill$\Box$}}

\begin{document}

\begin{center}
  \LARGE\bf Algorithmes pour les jeux \\
            Stratégie min-max
\end{center}
\bigskip

Considérons un  jeu  à deux joueurs,  appelons-les $A$  et $B$,  où la
configuration d'une partie est  une donnée finie,  et où chaque joueur
n'a, à chaque tour, qu'un nombre fini de coups possibles. C'est le cas
de la majorité des jeux de plateau à deux joueurs.
On se propose ici de programmer un algorithme classique pour les jeux :
\emph{la stratégie min-max} (également appelée \emph{alpha-beta}\/).

\subsection*{Principe}

On appelle  {\em  configuration\/} une description complète  de l'état
d'une partie. Par exemple, au {\em puissance 4\/}, une configuration
est une description de la grille et l'information ``c'est à $X$ de jouer''.
Aux échecs, une configuration est une description 
de l'échiquier, l'information ``c'est aux blancs de jouer'' (ou aux noirs),
tels pions ont avancé de 2 cases initialement, mais aussi toutes les
configurations précédentes (pour les répétitions de position),
éventuellement le temps de jeu de chaque joueur, etc.

On suppose que l'on dispose également d'une {\em fonction
  d'évaluation\/}, qui associe à toute configuration une valeur
réelle, avec des valeurs particulières pour la défaite, la victoire,
et la partie nulle éventuellement. Comme son nom l'indique, cette fonction
évalue la position d'un joueur : plus cette valeur est grande et plus
le joueur est en bonne position.
Il est clair que chaque joueur essaie de maximiser sa fonction d'évaluation
et de minimiser celle de l'autre joueur. 

La stratégie min-max est basée sur cette idée. Supposons que nous sommes
dans une configuration $c$ et que c'est au joueur $A$ de jouer.
Soit $f$ la fonction d'évaluation de $A$.
L'arbre des coups possibles à partir de $c$ est représenté ci-dessous :

\medskip
\hfil\epsfbox{minmax.eps}\hfil
\medskip

Si $A$ joue le coup $i$, qui le mène en position $c_i$, alors $B$
cherchera à minimiser la fonction d'évaluation de $A$ au coup suivant,
c'est-à-dire choisira la configuration $c_{i,j}$ qui minimise $f$.
$A$ a donc intérêt à choisir le coup $i$ qui maximise ce minimum.
C'est la stratégie min-max. $A$ choisit donc de jouer le coup $i_0$
tel que
$$ \min_{1 \le j \le k_{i_o}} f(c_{i_0,j})
=  \max_{1 \le i \le n} \min_{1 \le j \le k_{i}} f(c_{i,j}) $$

On peut itérer plus loin cette méthode, en prenant comme évaluation
sur la configuration $c_{i,j}$ non pas la fonction $f$ mais 
l'évaluation rendue par la méthode min-max elle-même.
L'itérer $n$ fois, c'est prévoir $2n$ coups à l'avance.

\section{Préliminaires}

\noindent
Ecrire \question une fonction \texttt{minimize} qui prend une fonction
de comparaison \texttt{comp} (de type \verb!'a -> 'a -> bool!), une fonction
d'évaluation \texttt{f} (de type \verb!'b -> 'a!), une liste \texttt{l}
d'objets de type \verb!'b! et qui rend le couple \verb!(x,v)!
où \verb!x! est un élément de \texttt{l} minimisant la fonction \texttt{f}
pour la relation \texttt{comp}, et \texttt{v} la valeur de \verb!(f x)!.


\medskip\noindent
En déduire \question deux fonctions \texttt{min\_list} et \texttt{max\_list}
qui prennent une fonction \texttt{f} de type \verb!'a -> float!
et une liste \texttt{l} de type \verb!'a list! et qui rende un
couple \verb!(x,v)! qui minimise \texttt{f}.


\section{Stratégie min-max}

Soit \verb!'a! le type des configurations du jeu.
Soit \texttt{eval} la fonction d'évaluation, de type \verb!'a -> float!.
On suppose que cette fonction rend \verb!0.0! pour une défaite,
\verb!1.0! pour une victoire, et un réel de $]0,1[$ sinon.
On suppose également qu'il n'y a pas de partie nulle.
Soit \texttt{suiv} une fonction, de type
\verb!'a -> 'a list! rendant, pour une configuration donnée, la liste des
configurations suivantes possibles, c'est-à-dire la liste des coups
possibles.

\medskip\noindent
Ecrire \question une fonction \texttt{minmax} prenant en arguments
\texttt{eval}, \texttt{suiv} et une configuration \texttt{c} et rendant
le coup à jouer par la stratégie min-max, pour un seul niveau
d'analyse (c'est-à-dire 2 coups).

\medskip\noindent
Ecrire \question une fonction \texttt{minmax\_n} prenant les même
arguments, et un entier \texttt{n}, et rendant le coup à jouer
pour une analyse sur 2\texttt{n} coups.


\section{Application : le jeu des allumettes}

On va appliquer la stratégie précédente au jeu bien connu des allumettes :
Initialement, il y a un certain nombre d'allumettes sur la table.
Chaque joueur, à son tour, prend 1, 2 ou 3 allumettes.
Celui qui prend la dernière allumette a perdu.
Il y a une stratégie gagnante pour ce jeu, et nous allons avoir que 
la méthode min-max permet de la trouver.

\medskip
On choisit comme type des configurations le couple d'un booléen,
qui indique quel joueur doit jouer, et une entier qui indique combien
il reste d'allumettes sur la table.
\begin{verbatim}
     type configuration == bool * int 
\end{verbatim}

\medskip\noindent
Ecrire \question une fonction \texttt{affiche\_configuration} affichant
une configuration. Par exemple, la configuration \verb!(true,13)! pourra
être affichée :
$$\mbox{\texttt{au joueur 1 : |||||||||||||}}$$

\medskip\noindent
Ecrire \question une fonction \texttt{suiv} rendant, pour une configuration,
la liste des configurations suivantes possibles.

\medskip\noindent
Ecrire \question une fonction \texttt{eval} d'évaluation d'une
configuration.

\medskip\noindent
Ecrire \question une fonction \texttt{joue} qui associe à une configuration
la configuration suivante, obtenue avec la stratégie min-max appliquée
à une profondeur suffisante pour trouver la stratégie gagnante (si elle
existe).

\medskip\noindent
En déduire \question enfin un programme où l'ordinateur fait jouer les deux
joueurs, et un programme où vous affrontez l'ordinateur.


\section*{S'il vous reste du temps\dots}

S'il vous reste du temps, vous pouvez appliquer la méthode min-max
à d'autres jeux. Voici quelques possibilités :

\begin{itemize}
  \item le puissance 4 ;

  \item le morpion (prendre une petite grille) ;

  \item la reine contre les pions : sur un échiquier, les pions noirs
    affrontent la reine blanche. La reine gagne si elle croque tous les
    pions, et les pions gagnent s'ils croquent la reine ou si l'un d'eux
    arrive à la promotion.
\end{itemize}



\end{document}
