Introduction à l’Intelligence Artificielle
Projet final : Graphe et apprentissage automatique
Esmia 2022
Rakotoarimalala Tsinjo
Indication
• Le projet est individuel, à rendre par mail tsinjofichiers@[Link] au plus tard le dimanche 13
mars 2022.
Objet du mail: projet ia
Nom du fichier: [Link] (XXXXXXX correspond à votre numéro d’étudiant)
• Ce qui est à envoyer : le projet java pour la partie une, et le notebook jupyter dont les cellules
ont été déjà toutes exécutées pour la partie deux.
• Le projet est composé de deux parties : une sur les graphes et la seconde sur la classification.
Vous devez faire les deux parties.
• Pour la partie graphe, vous pouvez choisir entre les deux sujets.
• Ce sujet est joint à un fichier nommé [Link].
1 Graphe sous Java/Python
1.1 Morpion graphique
Ce projet consiste à continuer le projet Morpion en ajoutant les deux fonctionnalités principales suiv-
antes:
1.1.1 MiniMax
L’IA doit utiliser l’algorithme Minimax (voir Wikipédia) pour le choix du coup qu’il va utiliser.
L’algorithme Minimax est un algorithme récursif optimal pour les jeux à somme nulle comme le
Morpion.
La tache principale consiste donc à modifier la méthode penser dans la classe Jeu de telle sorte
que l’IA choisit le prochain coût en utilisant l’algorithme Minimax.
1.1.2 Graphique
Vous devez ajouter une interface graphique au jeu de morpion tout en utilisant l’IA.
1
1.2 Taquin
Dans ce projet, le but est de faire une IA qui permet de résoudre le jeu de Taquin.
Ce jeu consiste à remettre dans l’ordre les 8 carreaux à partir d’une configuration initiale quelconque
en déplaçant le vide (Imaginer le jeu sous forme de jeu de plateforme en bois coulissants).
On modélise le problème en un problème de graphe. Un état sera représenté par un sommet ayant
un attribut label qui est la suite des nombres de cet état (de gauche vers la droite, de haut en bas).
Dans l’exemple l’état initial est étiqueté par "408632157" et l’état final par "123456780" (0
représente le vide).
Dans ce qui suit, les mots configuration, nœud et état seront interchangeables.
Les états voisins à un état i sont les états qu’on peut obtenir à un coup de l’état i avec les
déplacements possibles.
Par exemple la configuration "408632157" a comme voisins "480632157","048632157" et "438602157".
(faire les images si pas clair)
Partez du projet morpion.
1. En partant des exemples ci-dessus, écrire la fonction trouverVoisins de la classe Sommet qui
retourne la liste des sommets voisins du sommet récent.
Indication: le nombre de voisins varie selon la configuration, cela peut varier de 2 à 4. Les
labels de ces voisins s’obtiennent en déplaçant le zéro du label de l’état actuel à des places biens
précises.
2. Maintenant le problème est devenu un problème de recherche de chemin d’une configuration
initiale vers une configuration finale (nœud final "123456780"). En utilisant le parcours en
largeur, écrire la fonction pour résoudre le problème de taquin.
Indication: Utiliser (en modifiant un peu) et appliquer l’algorithme de parcours en largeur (la
méthode pl de la classe Graphe) en partant de l’état actuel. Pour ne pas trop utiliser de mémoire,
une fois l’état final ajouté dans la file et traité, arrêter le parcours en largeur.
Point clé: la difficulté dans cette question est savoir qui sont déjà passés dans la file.
3. Écrire une fonction qui permet de décrire le chemin suivi dans la résolution (suite de configurations
ou simplement l’historique des configurations faites pour arriver à l’état final) en utilisant la
fonction cheminDeSVersU de la classe Graphe.
2 Classification sous Python
Le projet consiste à la reconnaissance de chiffre à partir d’une image jpg en utilisant la classification
multiclasse.
2.1 Données et objectifs
L’objectif est la reconnaissance de l’écriture manuscrite de chiffre de 0 à 9. On a comme données des
images de 28 × 28 pixels.
Attention: Il y a plus de 42000 images, il faut essayer de pas souvent ouvrir les dossiers.
2
La première partie est le pré-traitement, il faut changer ses données images en données matricielles
réelles.
Pour se faire, vous devez changer les données de telle sorte qu’on obtienne un fichier csv avec une
entête comme suit:
pixel1,pixel2,...pixel784,classe
Donc une ligne représente les pixels des images (les 784 pixels de gauche à droite, de haut en bas,
et la classe ( ici la classe correspond à la valeur affichée sur l’image de 0 à 9 ).
Par exemple si les pixels sont :
0,0,0,...,0
1,1,1,...,1
...
28,28,...,28
et que l’image représente un 6 alors la ligne sera :
0,0,0,...,0, 1,1,1,...,1, ... 28,28,...,28,6
1. écrire un programme sous Python pouvant faire ce qui est expliqué ci haut.
Attention: faire attention avant de tester car ça prend pas mal de temps de faire les 40000
images. Prenez des petits exemple pour tester.
Indication: le nombre affiché dans l’image est le nom du dossier dans lequel il est.
2.2 Classification
1. Utiliser les 4 algorithmes en cours pour une classification multiclasse sur ces données.
Attention: faire une donnée de test de 20 pourcents.
Indication: Utiliser moins de données si vous n’y arrivez pas avec la totalité des données.
2. Lequel de ces algorithmes a le meilleur score
3. Documentez vous sur l’algorithme de type CNN, plus précisément de l’algorithme Multi-layer
Perceptron. Et appliquez le à nos données pour voir s’il est meilleur.
