Programmation génétique pour le jeu Tetris
Cadre
Ce projet a été réalisé dans le cadre du Module d'Initiation à la Recherche Méthodes Evolutionnistes de la filière Vie Artificielle du DEA Intelligence Artificielle, Reconnaissance des Formes et Applications, Université Pierre-et-Marie-Curie (Paris 6), encadré par Norbert Cot (Paris 5).
Il consiste en une étude critique du travail proposé par Michael Yurovitsky dans Playing Tetris Using Genetic Programming et un approfondissement de son travail.
La programmation génétique est une méthode de recherche de programmes optimaux dans un espace de programmes représentés par des arbres.
Les noeuds de ces arbres sont des fonctions, et les feuilles sont des arguments de ces fonctions.
La méthode de recherche consiste à définir une fonction fitness qui évalue la performance d'un arbre-programme en fonction du problème à resoudre, et à générer de nouveaux programmes par sélection génétique des programmes précédents, en fonction de leurs performances.
Les techniques génétiques mises en oeuvre sont les traditionnelles reproduction, mutation et croisement, qui s'effectuent dans ce cadre au niveau des noeuds des arbres.
La conception pour résoudre un problème par programmation génétique s'effectue en 3 phases :
- Définition du problème à résoudre et de la fonction fitness
- Définition des terminaux (feuilles) et fonctions (noeuds) utilisables pour construire les arbres
- Définition des paramètres d'évolution génétique : profondeur maximale des arbres, taille de la population, nombre de générations, taux de mutation et de croisement, mode de sélection directe d'une génération à l'autre, etc.
Ensuite, il suffit de laisser evoluer le moteur de programmation génétique et d'attendre que celui-ci propose des programmes quasi-optimaux.
Remarque importante : la phase la plus essentielle de cette conception est le choix des terminaux et des fonctions.
En effet, ils constituent les briques de base qui vont former les programmes, tels que les opérateurs structurels ou numériques d'un langage de programmation.
Plus les fonctions proposées sont de haut niveau et plus la marge de manoeuvre laissée à l'évolution est faible, tout en permettant des résultats conséquents assez rapidement.
A l'inverse, en réduisant ces ensembles aux expressions les plus élémentaires (par exemple, portes logiques d'un processeur) on peut virtuellement obtenir tous les programmes existant dans le monde, au prix d'une recherche probablement longue, fastidieuse et pas sûre d'aboutir.
Ressources
Si ce projet vous intéresse, je vous invite vivement à consulter le rapport de projet disponible ici : mir_methevo_rapport.pdf
Les sources du projet sont disponibles sur demande, car non-utilisables en l'état, pour le moment.
Résultats
Le travail accompli porte pour une part importante sur l'abolition des simplifications introduites par M. Yurovitsky, particulièrement sur le nombre de pièces et la formes de celles-ci.
L'autre part significative du projet porte sur des modifications dans les ensembles de fonctions et terminaux, ainsi que sur l'introduction de contraintes de typage sur les données manipulées.
Les résultats obtenus ne sont pas à la hauteur des espérances, en comparaison de ceux de l'article étudié.
Ceci s'explique principalement par le fait que la qualité des résultats obtenus dans l'article est dûe pour une part majoritaire aux simplifications introduites dans le problème.
Il semble ainsi que l'ajout de fonctions et les contraintes de typages ont introduit une plus grande complexité dans l'espace de recherche sans y apporter un bénéfice suffisant.
Des expériences sur de plus grandes populations ou un plus grand nombre de générations peuvent cependant ouvrir la voie à de meilleures performances.
Les résultats n'étant pas visuels, je vous invite à consulter le rapport de projet qui présente les modalités des expériences de manière plus précise.