Résolution de problèmes en Intelligence Artificielle

Feuilles d'exercices

• TD sur la formalisation de problèmes et les opérateurs de changement d'état.
• TD sur les méthodes de recherche dans les graphes d'états.

Codage des problèmes en Python

1. Coder un état et un opérateur de manière générique.
2. Instancier avec les problèmes vus en TD (flèches, cruches, taquin, etc.) : liste des opérateurs disponibles, état initial, caractérisation des états finaux, etc.

Codage de la recherche en profondeur d'abord

1. Programmer, de manière générique, l'algorithme de recherche en profondeur d'abord.
2. Programmer une variante avec la mémorisation des états visités.
3. Programmer une variante qui limite la profondeur de recherche (attention alors à la mémorisation des états déjà vus).
4. Tester sur les problèmes définis en TD et précédemment codés en Python.

Codage de la recherche en largeur

1. Programmer, de manière générique, l'algorithme de recherche en largeur.
2. Tester sur les problèmes définis en TD et précédemment codés en Python. Faire varier le choix du nœud à sortir des Ouverts.

Comparaisons des méthodes de recherche

1. Mesurer, pour chaque méthode et pour chaque problème, le nombre d'états visités et le temps d'exécution.
2. Comparer les méthodes sur les nouveaux problèmes suivants :
   • les flèches : passer de l'état initial ↓↑↑↑↑↓ à l'état final ↑↑↑↑↑↑,
   • les cruches : obtenir 6 litres à partir de la configuration initiale (0,0),
   • le taquin : partir de l'état de jeu

     	5	7
     6	2	8
     3	4	1

Algorithmes de jeux : Min-Max et Alpha-Beta

Feuille d'exercices

• TD sur les algorithmes de jeu (MinMax et Alpha-Bêta).

Codage de la méthode Min-Max

1. Programmer, de manière générique et en Python, l'algorithme qui développe complètement un arbre de jeu à partir d'une situation donnée et qui fait remonter les évaluations selon la méthode Min-Max.
2. Coder le jeu de Nim et le jeu du morpion en instanciant les méthodes génériques vues en cours.
3. Ajouter le code Python pour mener des parties de Nim et de Morpion entre un joueur humain et Min-Max.

Min-Max avec profondeur limitée, heuristiques et coupes Alpha-Bêta

Application à des jeux comme Puissance 4, Othello, awalé, dames, échecs, go, breakthrough, Havannah, Hex, etc.

Apprentissage automatique

arbres de décision avec C5.0

1. installation de la version de démonstration ;
2. parcours du tutoriel ;
3. premières expérimentations avec le problème golf : fichiers de description et de données ;
4. expérimentations sur les problèmes breast cancer et housing (fichiers fournis avec C5.0) ;
5. test du problème cardio (fichiers de description et de données), puis enrichissement par la valeur de l'index pondéral de chaque patient (Poids / Taille²) ;
6. réflexion sur le problème mystere : fichiers de description, d'apprentissage et de test.

Techniques de Boosting

1. An applet demonstrating adaboost par Yoav Freund.

Algorithmes de type EM

1. EM algorithm for Mixture models par Shotaro Akaho.

Réseaux de neurones

1. démonstration de Perceptron ;
2. reconnaissance de chiffres ;
3. page de SNNS.

algorithmes génétiques

1. The famous video of Karl Sims' evolved virtual creatures (zipped mpeg) ;
2. Aspects of Evolutionary Design by Computers ;
3. Computer Evolution of Buildable Objects ;
4. Mondriaan Art by Evolution.