\documentclass{tp-caml-2009}

\usepackage{wasysym}
\usepackage{tikz}
\usetikzlibrary{arrows,decorations,snakes,shadows}
\usepackage{xspace,array,multirow,colortbl,hhline}


\tp{
  title=Jeux et stratégies gagnantes,
  number=Dixième,
  date=Jeudi 20 mars 2010,
  class=MP
}

\newcommand\Attr{\textsf{Attr}}

\newenvironment{indication}
{\small\vspace{-1em}\begin{list}{}
{\leftmargin=0.5cm\labelwidth=0cm\itemindent=0cm}
\item $\vartriangleright$ \textsf{Indication.}
}
{\end{list}\normalfont\medskip}
%{\small\vspace{-1em}\textsf{Indication} $\triangleright$\slshape}
%{\normalfont\medskip}


\begin{document}

\begin{abstract}
  La théorie des jeux est une discipline très sérieuse. Elle trouve des
  applications dans des domaines aussi variés que l'économie, la théorie des
  nombres et l'informatique. En informatique, elle sert à analyser des
  systèmes devant interagir avec un environnement dont on ne connaît pas le
  comportement de manière exacte, par exemple un utilisateur éventuellement
  mal intentionné. On a alors affaire à des jeux combinatoires sur des objets 
  tels que des arbres ou des graphes.
\end{abstract}



\begin{corpus}


% *************************************************************************
%\section{Automates non-déterministes et expressions rationnelles}
%\label{section:nfa}

% -------------------------------------------------------------------------
\section{Graphes de jeux}
%\paragraph{Définitions}

On appelle \emph{jeu} un graphe de ce genre :

\begin{tikzpicture}
  \draw(0,0) node[circle,draw=black,minimum height=8mm] (n0) {$0$};
  \draw(2,1) node[square,draw=black,minimum height=8mm,minimum width=8mm] (n1){$1$};
  \draw(4,1) node[circle,draw=black,minimum height=8mm,minimum width=8mm] (n2){$2$};
  \draw(6,1) node[square,draw=black,minimum height=8mm,minimum width=8mm] (n3){$3$};
  \draw(2,-1) node[square,draw=black,minimum height=8mm,minimum width=8mm] (n4){$4$};
  \draw(4,-1) node[circle,draw=black,minimum height=8mm] (n5){\Large\smiley};
  \draw(6,-1) node[square,draw=black,minimum height=8mm,minimum width=8mm]
  (n6){\Large\smiley};
  \draw[-latex'] (-1,0) -- (n0);
  \draw[-latex'] (n0) -- (n1);
  \draw[-latex'] (n1) -- (n2);
  \draw[-latex'] (n1) -- (n5);
  \draw[-latex'] (n2) -- (n3);
  \draw[-latex'] (n3) -- (n6);
  \draw[-latex'] (n3) -- (n5);
  \draw[-latex'] (n2) -- (n6);
  \draw[-latex'] (n0) -- (n4);
  \draw[-latex'] (n4) -- (n2);
  \draw[-latex'] (n4) -- (n3);
\end{tikzpicture}

O\`u les ronds sont les états appartiennant au joueur 1 et les carrés ceux du
joueur 2.  
Quand un joueur possède un état, c'est lui qui choisit dans lequel des états
possibles on va ensuite.
Les objectifs sont pour le joueur 1 d'arriver à l'état~\tikz{\draw(0,0)
  node[circle,draw=black,minimum height=8mm,minimum width=8mm]{\Large\smiley}}
et à l'état~\tikz{\draw(0,0) node[square,draw=black,minimum height=8mm,minimum
    width=8mm] {\Large\smiley}} 
pour le joueur 2.

Formellement un jeu peut-être représenté par un 6-uplet \(\langle V_1 , V_2 ,
i , E , \Omega_1 , \Omega_2 \rangle \).
Où \( (V_1 \cup V_2 , E) \) est un graphe avec \(V_j\) representant les
états controlés par le joueur \(j\), \( i \in V_1 \cup V_2 \) est l'état
initial, \(\Omega_j \subset V_1 \cup V_2 \) représente l'objectif du joueur
\(j\). 
On dit que le joueur \(j\) gagne si un des états de \(\Omega_j\) est atteint à
la fin de la partie.

On représenteras un jeu de la façon suivante en Caml, sans préciser pour
l'instant le type que prendras nos états.

\begin{caml}
type 'a game =
  { state1 : 'a list ;
    state2 : 'a list ;
    init : 'a ;
    trans: 'a -> 'a list ;
    win1 : 'a list ;
    win2 : 'a list }
\end{caml}

Le champ \lstinline|trans| associe à un état, la liste de ses successeurs
possibles. 

\begin{question}
  Donner la representation en Caml de l'exemple du dessin.
  \begin{prototype}
    val example : int game
  \end{prototype}
\begin{solution-caml}
let example =
  { state1 = [0;2;3;5];
    state2 = [1;4;6];
    init = 0;
    trans = (function 0 -> [1;4] | 1 -> [2;5] | 2 -> [3;6] | 4 -> [2;3] | _ -> []);
    win1 = [5];
    win2 = [6] }
\end{solution-caml}
\end{question}



Une stratégie (sans mémoire) pour le joueur 1 est une fonction qui à chaque
état controlé par joueur 1 associe une transition possible à partir de cet
état. 
Une strategie serait représenté en Caml par le type suivant
\begin{caml}
type 'a strategy = ('a -> 'a)
\end{caml}

Une stratégie est dit \emph{gagnante} si quel que soit la stratégie du second
joueur, on atteint un de nos objectifs.
Par exemple dans le jeu représenté sur le dessin, joueur 2 a une stratégie
gagnante mais pas joueur 1.

\begin{question}
  Représenter en Caml la stratégie gagnante de joueur 2.
  \begin{prototype}
    val winning_strat : int strategy
  \end{prototype}
\begin{solution-caml}
let winning_strat = function 
  | 1 -> 2
  | 4 -> 2
  | 3 -> 6
\end{solution-caml}
\end{question}


\begin{question}
  Écrire un fonction \lstinline|execute| qui étant donné un jeu et deux
  stratégies fait avancer la partie en suivant les instructions donnés par les
  stratégies et s'arrête quand un objectif a été atteint, dans ce cas là on
  renvoit cet état. Dans le cas où une stratégie propose une transition non
  authorisé il faudrat lever une exception. 
  \begin{prototype}
    val execute : 'a game -> 'a strategy -> 'a strategy -> 'a
  \end{prototype}
  Si vous le voulez, vous pouvez d'abord écrire une fonction intermédiaire qui
  réalise seulement une étape.
  Vous pouvez tester cette fonction avec la strategie gagnante de joeur 2 et
  d'autre stratégie de joueur 1 et vérifier que l'on arrive toujours dans
  l'état gagnant de joueur 2.
\begin{solution-caml}
let execute g s1 s2 = 
  let rec aux i =
    if List.mem i g.win1 || List.mem i g.win2 
    then i 
    else 
      let t = if List.mem i g.state1 then s1 i else s2 i
      in 
	if List.mem t (g.trans i) then aux t else failwith "not allowed"
  in aux g.init
\end{solution-caml}
\end{question}

\section{Attracteurs}

Pour décider si un joueur à une stratégie gagnante on procède par un calcul
d'attracteur. 
L'ensemble \(\Attr^j_i\) représente l'ensemble des états du jeu à partir
desquels le joueur \(j\) possède une stratégie qui le fait gagner en \(i\)
étapes ou moins.
Le calcul se fait récursivement :
\begin{itemize}
\item Au rang 0, c'est exactement l'objectif : \(\Attr^j_0 = \Omega_j\)
\item Au rang \(i+1\) on ajoute
  les états controlés par \(j\) où au moins un succeseur est gagnant et les
  états controlés par l'adversaire où tous (et au moins un) successeur est gagnant : 
  \(\Attr^j_{i+1} = \Attr^j_{i} \cup
  \{ s \in V_j \mid \exists (s,s') \in E .\ s' \in \Attr^j_i\} \cup 
  \{ s \in V_{3-j} \mid \exists (s,s') \in E \text{ et } \forall (s,s') \in E .\ s' \in \Attr^j_i\}
\)
\end{itemize}
On s'arrête à partir du rang \(i\) où l'attracteur ne grandit plus :
\(\Attr^j_{i+1} = \Attr^j_{i}\), car à ce moment on a atteint un point fixe et
les états gagnant de \(j\) sont exactement les états de \(\Attr^j_{i} \). 

On aura besoin d'une structure de donnée pour représenter les ensembles.
On a déjà utiliser plusieurs fois des listes pour cela, mais le fait que
l'accès se fasse en temps linéaire les rend peu efficace pour des gros
ensembles. Vous devez aussi connaitre les arbres binaires équilibrés dans
lesquels l'accès et en temps logarithmique.
Le meilleur temps est atteint avec les tableaux pour lesquels l'accès se fait
en temps constant, c'est donc ce qu'il y a de mieux pour des ensembles très
grand. 
En revanche il présente l'inconvenient de ne pouvoir être indéxés que par des
entiers, se qui nous pose un problème pour representer des ensembles d'états
qui peuvent avoir un type quelconque. 
La solution serait d'utiliser des tables de hachage, cette structure ce
comporte comme un tableau (accès en temps constant) mais présente l'avantage
de pouvoir être indéxé par des clés de type quelconque et de ne pas avoir de
taille fixe.
En Caml elles ont le type \lstinline|Hashtbl.t| et se manipule grace aux
fonctions suivantes : 

\begin{itemize}
\item \lstinline|Hashtbl.create n| crée une table déstiné à contenire environ
  \lstinline|n| élements ;
\item \lstinline|Hashtbl.add t a b| ajoute dans la table  \lstinline|t|
  l'élement ayant pour clé \lstinline|a| et pointant vers \lstinline|b|;
\item \lstinline|Hashtbl.find t a| renvoie l'élement pointé par  \lstinline|a|, lève l'exception \lstinline|Not_found| si la clé n'est pas présente dans la table;
%\item \lstinline|Hashtbl.remove t a|
\item \lstinline|Hashtbl.fold f t init| calcul 
  \lstinline|(f kN dN ( ... (f k1 d1 init)))| où les \lstinline|k1 ... kN|
  sont les clés et les \lstinline|d1 ... dN| sont les valeurs de tout les
  élemements présent dans la table.
\end{itemize}

Pour representer les ensembles on pourrat donc utiliser une table a valeur
booléenne.
\begin{caml}
type 'a set = ('a,bool) Hashtbl.t
\end{caml}

\begin{question}
  Implementer les fonctions de base sur les ensembles.
  \begin{prototype}
    val empty_set : unit -> 'a set
    val is_empty : 'a set -> bool
    val add : 'a set -> 'a -> unit
    val mem : 'a set -> 'a -> bool
    val remove : 'a set -> 'a -> unit
    val to_list : 'a set -> 'a list
  \end{prototype}
  \begin{solution-caml}
let empty_set () =  Hashtbl.create 1000
	
let is_empty t =
  Hashtbl.fold (fun x b r -> b || r) t true

let add t a = Hashtbl.add t a true

let mem t a = 
  try Hashtbl.find t a 
  with Not_found -> false

let remove t a = Hashtbl.add t a false

let to_list t =
  Hashtbl.fold (fun x b r -> if b then x :: r else r) t []
  \end{solution-caml}
\end{question}

Pour implémenter le calcul de l'attracteur on va d'abord écrire deux fonctions qui serviront à verifier respectivement que tout les successeurs et au moins un successeur vérifie une certaine propriété.

\begin{question}
  Écrire la fonction \lstinline|forall_succ| qui étant donné un jeu,
  un état et une fonction booléene, renvoie vrai si tout les
  successeurs de cet états sont évalués à vrai par la fonction. De
  même écrire une fonction \lstinline|exists_succ| qui renvoie vrai si
  au moins un successeur de l'état est évalué à vrai.
\begin{prototype}
val forall_succ : 'a game -> 'a -> ('a -> bool) -> bool
val exists_succ : 'a game -> 'a -> ('a -> bool) -> bool
\end{prototype}
\begin{solution-caml}
let forall_succ g s mem = 
  List.fold_left (fun b v -> mem v && b) true (g.trans s)
	
let exists_succ g s mem = 
  List.fold_left (fun b v -> mem v || b) false (g.trans s)
\end{solution-caml}
\end{question}

\begin{question}
Écrire une fonction \lstinline|step| qui prend en argument un jeu, un
joueur et l'attracteur au rang $i$, ajoute à cet ensemble les états
qui doivent appartenir à l'attracteur du joueur donné au rang $i+1$ et
renvoie vrai si des élements ont effectivement été ajouté.
\begin{prototype}
val step : 'a game -> int -> 'a set -> bool
\end{prototype}
\end{question}

\begin{question}
  Écrire une fonction qui calcul l'attracteur pour un joueur
  donné. Tester la ensuite sur l'exemple déjà écrit.
\begin{prototype}
val attractor : 'a game -> int -> 'a set
\end{prototype}
\end{question}

\section{Un exemple : tic-tac-toe}

\section{Strategie gagnante}

\begin{question}
\begin{prototype}
val exists_succ_t : 'a game -> 'a -> ('a -> bool) -> 'a option
val forall_succ_t : 'a game -> 'a -> ('a -> bool) -> 'a option
\end{prototype}
\end{question}

%% \begin{question}
%%   \begin{prototype}
%%   \end{prototype}
%% \begin{solution-caml}
%% \end{solution-caml}
%% \end{question}




\end{corpus}

\end{document}

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