Jeux de Taquin: Théorie des Jeux (Tech 3)

But du projet: se familiariser avec les algorithmes de théorie des jeux et en particulier la représentation des connaissances et la notion d’heuristique et l’algorithme A*.

Description du projet:

Avant tout, rappelons le but du jeu de taquin. Une image est décomposée en petits carrés. Ces derniers ont été mélangés. Le but du jeu est de reconstituer l’image originelle.

Le jeu de tacquin part d’une configuration aléatoire de début et doit finalement atteindre une configuration de ce type :

 1 2 3 8 4 7 6 5 

La version du programme que devront réaliser les étudiants de troisième année devra fonctionner avec des grilles de taille différentes fixées en paramètres comme par exemple: (3 × 3, 4 × 4, …).

Le programme devra comporter les fonctions suivantes :

• Fonction de filtrage initiale (élimination des déplacements impossibles ne permettant pas ainsi de jouer).
• Génération des possibilités.
• Evaluation et exploration de l’arbre des possibilités.
• Le principe d’exploration est d’appliquer l’algorithme A avec l’heuristiques.

Pour rappel, l’heuristique est une technique consistant à apprendre petit à petit, en tenant compte de ce que l’on a fait précédemment pour tendre vers la solution d’un problème. L’heuristique ne garantit pas du tout qu’on arrive à une solution quelconque en un temps fini contrairement à l’algorithmique.

Le jeu ne se déroule donc, réellement, qu’à la fin du processus d’exploration, c’est à dire qu’un chemin aura été trouvé entre la configuration initiale et la configuration finale.

Contraintes techniques:

Il faudra proposer plusieurs heuristiques d’évaluations (2 au minimum).
Il faudra aussi comparer ses heuristiques à l’heuristique dite, Distance de Manathan. Un paramètre permettra donc de lancer le programme en appliquant l’une ou l’autre des heuristiques.

L’utilisation des algorithmes de recherche d’exploration de graphe et d’élagage est obligatoire. L’algorithme et l’heuristique (fonction d’évaluation) sont libres de choix. Aussi il n’y a pas de contrainte concernant les structures de données et la formalisation du jeu. Ce projet est à réaliser par groupes de deux.