\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}