% Document Type: LaTeX
% Master File: TP98_7.tex
% FILE. . . . . /users/formel/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199899/TP98_7.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Localhost
% STARTED ON. . Fri Dec 25 23:24:50 1998


\documentclass{article}
\usepackage[francais]{babel}
\usepackage{a4}
\usepackage{alltt}
\usepackage{graphicx}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}

% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip

\centerline {TP num\'ero 6}
\centerline {semaine du 4 janvier 1999}
\bigskip
\centerline{\bf Programmation en bin\^ome: les algorithmes $MiniMax$ et $\alpha-\beta$}
\stepcounter{section}
\subsection*{Programmer \`a plusieurs}

Si vous avez \`a g\'erer un projet assez important,  il est indispensable de pouvoir
le  d\'ecomposer en sous-projets  dont  les interfaces sont clairement sp\'ecifi\'ees,
pour  permettre  que les diff\'erentes   composantes puissent \^etre  developp\'ees en
parall\`ele tout en garantissant la coh\'erence du r\'esultat final.\\
%
Nous allons faire un essai \`a petite  \'echelle dans le cadre  de ce TP: le but est
de  programmer  des algorithmes classiques de   visite d'arbres de  jeu, d'une
part, et  de programmer  un  jeu particulier d'autre  part.  Ces deux  modules,
ensemble, nous donneront un ``joueur'' automatique pour le jeu voulu. Pour cela,
regroupez vous en bin\^omes (programmeur A,  programmeur  B).

\subsection*{D\'efinition d'un jeu \`a deux joueurs}
%
Un \emph{jeu \`a deux joueurs} est   d\'efini classiquement comme  un arbre  qui a
comme n{\oe}uds des \emph{positions} (la racine est  appel\'ee la ``position initiale
du jeu''). Chaque n{\oe}ud est un n{\oe}ud ``joueur'' (i.e.\ c'est au joueur de jouer
son coup)  ou un n{\oe}ud ``opposant'', et  les joueur s'alternent,  de telle sorte
que un n{\oe}ud joueur a comme fils une liste de n{\oe}uds  opposants, que l'on obtient
\`a partir des diff\'erents coups  disponibles (sym\'etriquement pour opposant). Si un
n{\oe}ud n'a pas de fils, c'est un  n{\oe}ud terminal, et dans ce  cas on associe \`a ce
n{\oe}ud    \`a   l'aide d'une fonction    $h:   n{\oe}udterminal\rightarrow R \cup \{\pm\infty\}$ une
\emph{valeur}    qui indique ce que  le    joueur a gagn\'e ou     perdu. Typiquement, si on s'int\'eresse seulement \`a  des jeux comme les \'echecs,
on aura $+\infty$ pour gain, $-\infty$ pour perte et 0 pour les autres positions (pat et autres nuls), mais il y a  des jeux avec des
structures d'\'evaluation plus complexes, par exemple les jeux o\`u on mise de l'argent.\\

D'une certaine fa\c{c}on, cet  arbre contient toutes les  parties possibles que l'on
peut jouer \`a partir de la position initiale.  Si on  a la possibilit\'e d'explorer
tout l'arbre,  on peut  d\'eterminer s'il  existe  une strat\'egie gagnante  pour le
joueur. Si l'arbre est trop gros (ou si l'on impose des  limites de temps) on se
contente normalement d'explorer le sous-arbre obtenu en tronquant l'arbre de jeu
\`a une certaine profondeur, et  en \'evaluant  les n{\oe}uds  tronqu\'es \`a l'aide  d'une
heuristique $h'$.

Dans  les deux cas,  il est d\'eraisonnable de  supposer  que l'arbre  de jeu est
donn\'e de fa\c{c}on extensive, et on pr\'ef\`ere le pr\'esenter de fa\c{c}on implicite par
des ``r\`egles  de  jeu'' qui disent  comment   obtenir la  liste des  fils d'une
position donn\'ee.

\subsection*{La ``visite MiniMax''}

L'algorithme MiniMax, d\^u  \`a Von Neumann, est tr\`es  simple: on  visite l'arbre de
jeu  pour faire remonter \`a  la racine une  valeur  MiniMax (appelee ``valeur du
jeu'') qui est calcul\'ee r\'ecursivement de la fa\c{c}on suivante:

  \begin{itemize}
    \item $MiniMax(p)=h(p)$ si $p$ est une position terminale
    \item $MiniMax(p_j)=max(MiniMax(o_1),\ldots{},MiniMax(o_n))$ si $p_j$ est une position joueur 
          avec fils $o_1,\ldots{},o_n$
    \item $MiniMax(p_o)=min(MiniMax(p_1),\ldots{},MiniMax(p_m))$ si $p_o$ est une position joueur 
          avec fils $p_1,\ldots{},p_m$
  \end{itemize}

Il est clair que pour appliquer l'algorithme MiniMax il suffit de disposer de

  \begin{itemize}
    \item un type de donn\'ee ``position'' (et une position initiale ``start'')
    \item un type de donn\'ee ``coup''
    \item une fonction $h: position \rightarrow double$ pour \'evaluer les positions terminales 
    \item une fonction $estjoueur: position \rightarrow int$ qui sert \`a d\'eterminer si une position
          est une position joueur ou opposant
    \item une fonction $fils\_de$ qui prenne une position $p$ et retourne  une liste de
          couples $(pacc,coup)$, des positions accessibles par les coups disponibles sur $p$
  \end{itemize}

Cela nous donne notre interface C:

\begin{verbatim}
/* les positions */
typedef struct {
		. . .
		} position;

/* les coups */
typedef struct {
		. . .
		} coup;

/* une couple position, coup */
typedef struct {position fst;
                coup snd;} pc;

/* avec les fontions: fts et snd */
position fst(pc c);
coup snd(pc c);

typedef struct {
	 	. . .
		} pclist;

/* plus, ici, les fonctions habituelles sur les listes: 
   hd, tail, nil et isempty */

/* enfin, les fonctions propres au jeu */

double h(position p);

int estjoueur(position p);

pclist fils_de(position p);
\end{verbatim}

On rajoutera aussi une fonction qui imprime une position, pour visualiser les r\'esultats.

\begin{verbatim}
void imprime(position p);
\end{verbatim}
\newpage
\subsection*{La ``visite $\alpha-\beta$''}

L'algorithme  $\alpha-\beta$ est une optimisation du  MiniMax, qui ``coupe'' des
sousarbres d\`es que leur valeur  devient inint\'eressante aux  fins du calcul de la
valeur MiniMax du jeu. On s'int\'eressera  donc, sur chaque  n{\oe}ud, en plus de la
valeur,   \`a deux autres   quantit\'es,  nomm\'ees $\alpha$   et $\beta$, qui  seront
utilis\'ees pour calculer la valeur du n{\oe}ud.

\begin{description}
  \item[$\alpha$ d'un n{\oe}ud] est une approximation par le bas de la vraie valeur du n{\oe}ud.
       Elle est \'egale \`a la valeur sur les feuilles, et est initialis\'ee \`a $-\infty$ ailleurs.
       Ensuite, sur les n{\oe}uds joueur elle est maintenue \'egale \`a la plus grande valeur obtenue
       sur les fils visit\'es jusque l\`a, et elle est \'egale \`a la valeur $\alpha$ de son pr\'ed\'ecesseur
       sur les n{\oe}uds opposant.
  \item[$\beta$ d'un n{\oe}ud] est une approximation par le haut de la vraie valeur du n{\oe}ud.
       Elle est \'egale \`a la valeur sur les feuilles, et est initialis\'ee \`a $+\infty$ ailleurs.
       Ensuite, sur les n{\oe}uds opposant elle est maintenue \'egale \`a la plus petite valeur obtenue
       sur les fils visit\'es jusque l\`a, et elle est \'egale \`a la valeur $\beta$ de son pr\'ed\'ecesseur
       sur les n{\oe}uds joueur.
\end{description}

L'algorithme ALPHA-BETA peut \^etre d\'ecrit par le pseudo-code suivant:

\begin{alltt}
function ALPHA-BETA(P, A, B) /* ici A est toujours inf\'erieur \`a B */
begin
   si P est une feuille alors
        returner la valeur de P
   sinon
        initialiser Alpha de P \`a -\(\infty\) et Beta de P \`a +\(\infty\);
        si P est un n{\oe}ud Min alors
            pour tout fils Pi de P faire
               Val = ALPHA-BETA(Pi, A, Min(B,Beta of P))
               Beta de P = Min(Beta de P, Val)
               Si A >= Beta de P /*ceci est la coupure alpha */
               alors returner Beta de P 
            finfaire
            returner Beta de P
        sinon
            pour tout fils Pi de P faire
               Val = ALPHA-BETA(Pi, Max(A,Alpha de P), B)
               Alpha de P = Max(Alpha de P, Val)
               Si Alpha de P >= B /*ceci est la coupure beta */
               alors returner Alpha de P
            finfaire
            returner Alpha de P;
end ALPHA-BETA;
\end{alltt}

On sait que la v\'eritable valeur MiniMax $v$ d'un n{\oe}ud est encadr\'ee par $\alpha$
et $\beta$ (i.e.\  $\alpha \leq v  \leq \beta$),  et  si on  appelle la fonction
ALPHA-BETA  avec   les  valeurs  $(P,-\infty,+\infty)$   on  obtient pr\'ecis\'ement
MiniMax(P).  ALPHA-BETA   permets  assez   souvent de    doubler   la profondeur
d'exploration d'un arbre \`a parit\'e de ressources, par rapport \`a MiniMax.

%ALPHA value of a node 

%It  is a value never greater  than the true score  of this node. Initially it is
%the score of that node, if the  node is a leaf, otherwise  it is -infinity. Then
%at a MAX node it is set to the largest of the  scores of its successors explored
%up to now, and at a MIN node to the alpha value of its predecessor.

%BETA value of a node 

%It is a value never smaller  than the true  score of this  node. Initially it is
%the score of that node, if the  node is a leaf,  otherwise it is +infinity. Then
%at a MIN node it is set to the smallest of the scores of its successors explored
%up to now, and at a MAX node to the beta value of its predecessor.

%It is guaranteed that:

%_ The score of a node will always be no less than the alpha value and no greater
%than the beta  value of that node.

%_ As the algorithm evolves, the alpha and beta values of a  node may change, but
%the alpha value will never decrease, and the beta value  will never increase.

%_ When a node is visited last, its score is set to the alpha value of that node,
%if it is a MAX node, otherwise it is set to the beta value.

\newpage 

\subsection{T\^aches du programmeur A}

\begin{exercise}[Programmation de   MiniMax]  \'Ecrivez   une   fonction 
\verb|int val(position p)| qui calcule la valeur  d'un jeu avec  MiniMax, et retourne une
partie    (liste de  positions,coups)  r\'ealisant    cette  valeur, en  utilisant
exclusivement les fonctions dans l'interface.
\end{exercise}

\begin{exercise}[Programmation   de AlphaBeta]  \'Ecrivez  une  fonction 
\verb|int valab(position  p)| qui    calcule   la  valeur d'un    jeu   avec  l'agorithme
$\alpha-\beta$,   et retourne une    partie (liste de positions,coups) r\'ealisant
cette valeur, en utilisant exclusivement les fonctions dans l'interface.
\end{exercise}

\begin{exercise}[Profondeur fixe]
Modifiez vos algorithmes pour permettre de sp\'ecifier la profondeur maximale d'exploration
de l'arbre de jeu.
\end{exercise}

\subsection{T\^aches du programmeur B}
\begin{exercise}[Programmation du jeu Tic-Tac-Toe]
D\'efinissez les  types de donn\'ees et   programmez les fonctions  dans l'interface
d\'efinie plus en haut pour le jeu du Tic-Tac-Toe.
(Rappel : sur une grille $3\times3$, chaque joueur coche \`a tour de r\^ole
une case, celui qui en aligne 3 a gagné.)
\end{exercise}

\begin{exercise}[Programmation du jeu Puissance 4]
D\'efinissez les  types de donn\'ees et   programmez les fonctions  dans l'interface
d\'efinie plus en haut pour le jeu Puissance 4.
(Rappel : sur une grille de 7 colonnes de 6 cases,
chaque joueur met \`a tour de r\^ole un pion dans une colonne, celui-ci
descend en bas de la colonne.  Celui qui en aligne 4 a gagné.)
\end{exercise}

\subsection{T\^aches communes \`a A et B}
\begin{exercise}
Compilez ensembe vos deux modules et \ldots{} jouez.
\end{exercise}


{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
%\clearpage
%\mbox{}
\end{document}



