Programmation fonctionnelle, projet 2014

Dates et principe

Cette page peut être mise à jour, avec informations complémentaires, précisions, questions bonus, etc. Pensez à y revenir souvent.

---

Projet à rendre pour le vendredi 16/01 à 23h59, aucun retard ne sera toléré.
Des soutenances pourront être organisées ensuite.

Lire tout le sujet (tout ? tout).

Un rendu de projet comprend :

• Un rapport précisant et justifiant vos choix (de structures, etc.), les problèmes techniques qui se posent et les solutions trouvées ; il donne en conclusion les limites de votre programme. Le rapport sera de préférence composé avec LaTeX. Le soin apporté à la grammaire et à l'orthographe est largement pris en compte.
• Un manuel d'utilisation, même minimal.
• Un code abondamment commenté ; la première partie des commentaires comportera systématiquement les lignes :
  
1. @ requires décrivant les préconditions : c'est-à-dire conditions sur les paramètres pour une bonne utilisation (pas de typage ici),
2. @ ensures décrivant la propriété vraie à la sortie de la fonction lorsque les préconditions sont respectées, le cas échéant avec mention des comportements en cas de succès et en cas d'échec,
3. @ raises énumérant les exceptions éventuellement levées (et précisant dans quel(s) cas elles le sont).
On pourra préciser des informations additionnelles si des techniques particulières méritent d'être mentionnées.

Le code doit enfin compiler sans erreur (évidemment) et sans warning.

Avez-vous lu tout le sujet ?

---

Protocole de dépôt

Vous devez rendre

• Votre rapport (en pdf) et
• Vos fichiers de code

rassemblés dans une archive tar gzippée identifiée comme votre_prénom_votre_nom.tgz.
La commande devrait ressembler à :
tar cvfz randolph_carter.tgz rapport.pdf fichiers.ml autres_truc_éventuels…
Lisez le man ! et testez le contenu de votre archive (une commande comme par exemple :
tar tvf randolph_carter.tgz doit lister les fichiers et donner leur taille). Une archive qui ne contient pas les fichiers demandés ne sera pas excusable. Une archive qui n'est pas au bon format ne sera pas considérée.

Procédure de dépôt
Vous devez enregistrer votre archive tar dans le dépôt dédié au cours IPF (ipf-2014) en vous connectant à http://exam.ensiie.fr. Ce dépôt sera ouvert jusqu'au 16 janvier inclus.

---

Contexte

Le but de ce projet est d'uiliser des techniques de programmation génétique pour obtenir un programme qui joue à Pierre-Papier-Ciseaux, qui plus est qui joue bien contre un humain. En effet un humain a bien du mal à jouer au hasard et il est possible d'anticiper ses choix avec de bonnes chances de succès. On devra donc produire :

1. Une plateforme qui fait s'affronter deux joueurs/programmes,
2. Des fonctions de croisement et de sélection de programmes.

Lire le sujet en entier est une bonne idée.

Vous devez au moins réaliser la première époque.

Pierre-Papier-Ciseaux (PPC)

Deux joueurs s'affrontent à PPC.

Une partie de PPC se déroule en une ou plusieurs manches.

Une manche consiste en un choix simultané par les joueurs d'un objet parmi :

• Pierre,
• Papier et
• Ciseaux (dont, au passage, on remarquera le pluriel).

Le gain d'une manche est obtenu par le joueur qui a choisi :

• Pierre contre Ciseaux ou bien
• Ciseaux contre Papier ou bien
• Papier contre Pierre ;

toutes les autres possibilités donnent lieu à une manche nulle.

Un score peut être obtenu pour un programme en comptant un point pour une victoire, 0 pour une manche nulle et -1 pour une défaite.

Un programme pour PPC

On peut représenter un programme jouant à PPC comme associant à une séquence de manches le prochain choix. Par exemple, on peut décrire que si, au cours de la partie, les deux dernières manches sont Pierre Pierre (manche nulle) et Pierre Ciseaux (gain pour le joueur) alors le prochain sera Papier, ce qu'on écrira dans cet énoncé : Pierre,Pierre Pierre,Ciseaux → Papier
Une règle avec la séquence vide à gauche représente le coup par défaut, toujours présent.

Un ensemble non vide de telles règles constituera un programme ; notez que les longueurs des séquences à gauche de la flèche ne sont pas nécessairement égales dans un même programme.

N.B. Si plusieurs règles peuvent s'appliquer on convient de prendre au hasard une de celles dont la séquence est maximale.

Un chouia de génétique

Une population est un ensemble de programmes.

On peut générer un nouveau programme par mutation d'un programme ou par croisement de deux programmes.

• La mutation est la modification aléatoire (changement d'objets, effacements dans une séquence, etc.) d'une certaine proportion des éléments d'un programme.
• Le croisement consiste à réaliser l'union des ensembles de règles de deux programmes. Ce croisement peut être contraint par un nombre maximal de règles. Si le cardinal de l'union dépasse ce nombre, on élimine aléatoirement le nombre adéquat de règles.

On peut enfin sélectionner des programmes pouvant participer à une prochaine génération.

• La sélection consiste à ne retenir que les programmes ayant obtenu les meilleurs scores (par exemple les progammes ayant obtenu parmi les meilleurs 10% des scores) lorsqu'on les a tous confrontés deux à deux sur un grand nombre de parties.

On obtient les générations successives de programmes en alternant mutations, croisements et sélection.

Mimer des humains

Pour obtenir un programme imitant la stratégie d'un humain, on fait jouer un humain contre un des programme et on enregistre les coups joués durant la partie.

De cette séquence on obtient un certain nombre de règles comportant à gauche les sous-séquences d'une longueur n donnée et à droite le choix suivant cette sous-séquence dans la partie. On complète par les n règles données par les sous-séquences initiales de longueur inférieure à n.

Exemple.De la séquence Pierre,Pierre Ciseaux,Pierre Ciseaux,Ciseaux Papier,Papier où le choix humain est à gauche, on peut extraire le programme constitué des deux règles de longueur 2 :

• Pierre,Pierre Ciseaux,Pierre → Ciseaux
• Ciseaux,Pierre Ciseaux,Ciseaux → Papier

complétées par

• Pierre,Pierre → Ciseaux et
• → Pierre

Remarquez que dans cette séquence, la dernière manche Papier,Papier doit être la première accessible, la représentation concrète pourrait être (mais est-ce vraiment la meilleure façon ?) :
(Papier,Papier) :: (Ciseaux,Ciseaux) :: (Ciseaux,Pierre) :: (Pierre,Pierre) :: [ ]

Le programme est alors ajouté à la population. Plus il y a de tels programmes, plus c'est intéressant au niveau de la sélection d'individus efficaces contre des humains. On récoltera de nouvelles informations en faisant jouer des humains contre cette nouvelle population, etc.

Première époque

On pourra utiliser les fonctions Random.int, Random.float de la bibliothèque standard d'OCaml.

0. Proposer une structure d'association pertinente pour représenter un programme.
1. Proposer une fonction joue qui sur la donnée d'un programme, d'un bool et d'une séquence de manches (dont la dernière jouée est la première accessible) retourne le choix de ce programme pour la prochaine manche.
   La valeur true en paramètre indique que le programme fournit le coup de gauche, la valeur false indique que le programme fournit le coup de droite dans chaque manche de la séquence.
2. On appelle joueur une fonction de type : bool → manche list → objet.
   Un joueur peut être humain ou obtenu à partir d'un programme.
   Proposer une fonction qui sur la donnée de deux joueurs J₁ et J₂ munis de scores et d'un nombre n de manches maximal retourne les nouveaux scores respectifs après une partie de n manches entre J₁ et J₂.
3. Proposer une fonction darwin qui sur la donnée d'un ensemble de programmes, d'un nombre n de parties, d'un nombre de manches par parties et d'un pourcentage p retourne l'ensemble des p pourcents des meilleurs programmes sur un tournoi où chacun des programmes a joué n parties contre chacun des autres.
4. Proposer une fonction qui sur la donnée d'un programme, retourne un programme comportant les mêmes règles sauf une retirée aléatoirement.
5. Proposer une fonction croisement qui sur la donnée d'un nombre maximal de règles et de deux programmes retourne un de leurs croisements possibles.
6. Proposer une fonction mutation qui sur la donnée d'une proportion de modifications et d'un programme retourne une mutation possible de ce programme.
7. Proposer une fonction extrait qui sur la donnée d'un nombre de règles maximal, d'une taille de sous-séquence et d'une séquence de manches retourne un programme (comportant au moins les règles initiales) dont les règles imitent la stratégie du joueur 1 dans ces manches. On sélectionnera aléatoirement les règles à éliminer pour respecter le nombre de maximal de règles.

Deuxième époque

On ajoute bien sûr les objets Lezard et Spock tels que :

• Lezard bat Spock et Papier
• Spock bat Ciseaux et Pierre
• Pierre bat Lezard et Ciseaux
• Papier bat Spock et Pierre
• Ciseaux bat Lezard et Papier

Interface

Afin de permettre les entrées des choix d'un joueur humain nous fournissons ICI un .ml et un .mli réalisant l'interface.

Exemples de valeurs

On obtient déjà des résultats intéressants avec :

• 9 manches par partie,
• 20 règles par programme,
• Construction des règles par sous-séquences de longueur 3,
• 10% proba de modification dans une mutation,
• 1000 parties par paires de programmes.

Trouvez-vous de meilleures valeurs ?

Vous devez avoir lu jusqu'ici avant de commencer.

---

Merci à J.-C. Filliâtre pour l'idée de sujet.