Des modules et des jeux

Minmax et $\alpha -\beta$ sont des algorithmes classiquement utilisés dans la programmation des jeux à deux joueurs. Le principe de minmax est d'explorer tous les coups possibles et pour chacun toutes les réponses possibles jusqu'à une profondeur donnée. À chaque position est associée une valeur; le coup choisi est celui maximisant cette valeur en supposant que l'adversaire jouera toujours le meilleur coup. $\alpha -\beta$ est une optimisation de minmax consistant à élaguer les branches de l'arbre d'analyse partout où c'est possible.

Ces deux algorithmes sont plus ou moins indépendants du jeu que l'on veut programmer; il devient donc naturel de concevoir un module les implantant.

1.

Quels sont les éléments définissant un jeu à fournir pour réaliser une implantation des algorithmes minmax et $\alpha -\beta$.

2.

Définir la signature JEU à partir des informations receuillies à la question précédente.

3.

Donner la forme générale des modules MinMax et AlphaBeta implantant ces algorithmes.Un tel module a été implanté par R. COEFFIER et est (ou sera prochaînement) téléchargeable depuis le site WEB de P.O.D.

4.

Le jeu de Nim se joue à deux et un certain nombre d'allumettes réuni en un tas. Chaque joueur retire chacun à son tour une ou deux allumettes du tas. Celui qui ramasse la dernière allumette est perdant.
Définir le module Nim implantant ce jeu et respectant la signature JEU.

5.

On s'intéresse maintenant à l'interface des jeux. Définir la signature JEU_IO donnant une interface pour toutes les fonctions d'entrées-sorties nécessaires pour jouer.

6.

Écrire le foncteur Moteur qui á partir d'un JEU et d'une interface JEU_IO fournit une fonction play : unit -> unit qui lance le jeu.