Jeux sans hasard et modules






Description des algorithmes

1  Définition d'un jeu à deux joueurs

Un jeu à deux joueurs est défini classiquement comme un arbre qui a comme nœuds des positions (la racine est appelée la « position initiale du jeu »). Chaque nœud est un nœud « joueur » (i.e. c'est au joueur de jouer son coup) ou un nœud « opposant », et les joueurs s'alternent, de telle sorte qu'un nœud joueur a comme fils une liste de nœuds opposants, que l'on obtient à partir des différents coups disponibles (et symétriquement pour l'opposant). Si un nœud n'a pas de fils, c'est un nœud terminal, et dans ce cas on associe à ce nœud à l'aide d'une fonction h: noeudterminal -> R U {±infini;} une valeur qui indique ce que le résultat de la partie. Typiquement, si on s'intéresse seulement à des jeux comme les échecs, on aura +infini pour gain, -infini pour perte et 0 pour les autres positions (pat et autres nuls), mais il y a des jeux avec des structures d'évaluation plus complexes, par exemple les jeux où l'on mise de l'argent.

D'une certaine façon, cet arbre contient toutes les parties possibles que l'on peut jouer à partir de la position initiale. Si on a la possibilité d'explorer tout l'arbre, on peut déterminer s'il existe une stratégie 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 à une certaine profondeur, et en évaluant les nœuds tronqués à l'aide d'une heuristique h'.

Dans les deux cas, il est déraisonnable de supposer que l'arbre de jeu est donné de façon extensive, et on préfère le présenter de façon implicite par des « règles de jeu » qui disent comment obtenir la liste des fils d'une position donnée.

2  La visite MinMax

L'algorithme MinMax, dû à Von Neumann, est très simple : on visite l'arbre de jeu pour faire remonter à la racine une valeur (appelée « valeur du jeu ») qui est calculée récursivement de la façon suivante :

On peut vérifier que MinMax(p) est la meilleure valeur possible à partir de la position p, si l'opposant joue de façon optimale. Il est clair que pour appliquer l'algorithme MinMax il suffit de disposer de

3  La visite alpha-beta

L'algorithme alpha-beta est une optimisation du MinMax, qui « coupe » des sous-arbres dès que leur valeur devient inintéressante aux fins du calcul de la valeur MinMax du jeu. Cette optimisation permet souvant de diviser par deux le temps de calcul. En première lecture vous pouvez passer la description détaillée de cet algorithme. Les détails se trouvent ici

Modules et foncteurs

Pour permettre de réutiliser le code écrit et de partager le travail en binômes, nous allons organiser l'écriture d'un jeu en plusieurs modules.

Les jeux

La première étape consiste en la desription des jeux. Les jeux doivent implémenter les fonctions nécessaires à l'algorithme MinMax (et alpha-beta) et aussi les fonctions d'affichage et d'interface avec un joueur humain. En revanche l'implémentation effective utilisée pour représenter une position n'a pas à être connue en dehors du module de jeux, c'est pourquoi nous utiliserons un type abstrait. Les jeux devront donc implémenter l'interface :
module type JEUX = sig
  type position
  val initiale : unit -> position
(* eval donne la valeur d'une position du point de vue du «joueur» :
   plus le gain est grand et plus c'est bon pour le joueur, plus il
   est petit et meilleur c'est pour l'opposant *)
  val eval : position -> gain
(* accessibles est la liste des positions possibles à partir d'un position *)
  val accessibles : position -> position list
  val affiche : position -> unit
(* demande_un_coup doit être une interface avec un utilisateur humain qui
   devra choisir un coup possible. Peut renoyer l'exeption Position_finale *)
  val demande_un_coup : position -> position
(* est_joueur renvoie true si dans la position passée en argument, c'est
   au joueur de jouer, et false si c'est à l'opposant.
   Peut renvoyer l'exception Position_finale *)
  val est_joueur : position -> bool
end
À vous de définir le type gain.

Les stratégies

Étant donné un jeu, il est possible de définir différentes stratégies, qui donneront différents joueurs : le joueur MinMax, le joueur humain, le joueur alpha-beta, etc. La signature proposée pour les stratégies est :
module type STRATEGIE = functor (J : JEUX) -> sig
  type position = J.position
  val jouer : position -> position
end

Les parties

Pour définir une partie, il faut définir le jeux et les stratégies des deux joueurs. Le code pour une partie sera donc un foncteur prenant en argument une Strategie1, une Strategie2 et un Jeu. La pemière étape consiste à construire les modules
module Joueur = Strategie1(Jeu)
module Opposant = Strategie2(Jeu)
Ensuite, il faudra écrire l'algorithme générique qui fait jouer chaque joueur à son tour et afficher les positions jusqu'à la fin de la partie.

Travail en binôme, première étape

On propose donc de programmer ce TD en binôme, constitué d'un programmeur A et d'un programmeur B. Dans cette première étape, les tâches sont les suivantes :

  1. Définir le type gain et l'exception Position_finale dans un fichier jeux.ml qui contiendra aussi les signatures JEUX et STRATEGIE.

    Solution jeux.ml

  2. Le programmeur A implémente une STRATEGIE MinMax dans un fichier minmax.ml.

    Solution minmax.ml

  3. Le programmeur B implémente un module de jeu au choix entre le jeu des allumettes et le jeu de la reine dans un autre fichier.

    Solution allumettes.ml

    Solution reine.ml

  4. Le premier à avoir fini implémente le foncteur Partie dans un autre fichier.

    Solution partie.ml

  5. Tester.

  6. Implémenter la STRATEGIE humain qui se contente d'appeler demande_un_coup

    Solution humain.ml

  7. Écrire un module principal pour lancer le jeu.

    Solution pour le jeu de la reine : main.ml

  8. Jouer.

Deuxième étape, on change de rôle

  1. Modifiez les signatures pour que les algorithmes puissent prendre en paramètre un nombre maximal de nœuds à visiter (limitant ainsi le temps de calcul et donc la puissance des joueurs automatiques).
  2. Le programmeur A implémente un module de jeux puissance 4 en prenant bien soin de définir une valeur pour les positions non-terminales (cette valeur donne une estimation de la position pour le joueur).
  3. Le programmeur B implémente la stratégie alpha-beta.
  4. Jouez...

Annexe : les jeux

Le jeu des allumettes

Le jeu des allumettes est un jeu très simple : 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.

On suggère pour les positions d'utiliser simplement un couple indiquant d'une part le joueur dont c'est le tour et d'autre part le nombre d'allumettes restantes.
L'affichage pourra être purement textuel.

Tic-Tac-Toe

Sur une grille 3×3, chaque joueur coche à tour de rôle une case ; celui qui en aligne 3 a gagné.
NB : on peut remarquer que le test d'alignement de 3 valeurs identiques est plus facile si la case vide est codée par 0 et les cases cochées par +1 ou -1.

Jeu de la reine

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.

On propose une solution partielle pour l'implémentation du jeu de la reine.

Puissance 4

Sur une grille de 7 colonnes de 6 cases, chaque joueur met à tour de rôle un pion dans une colonne, et celui-ci descend en bas de la colonne. Celui qui en aligne 4 a gagné.