Intelligence artificielle et l’étude des jeux

Cette partie permet d’introduire les concepts d’apprentissage, de stratégie et d’heuristique. Ce dernier est abordé par des exemples où l’heuristique est précisément définie mais sans en évaluer la performance. La connaissance des théories sous-jacentes aux algorithmes de cette section n’est pas un attendu du programme. Les étudiants acquièrent une familiarité avec les idées qu’ils peuvent réinvestir dans des situations où les modélisations et les recommandations d’implémentation sont guidées.

Notions	Commentaires
Apprentissage supervisé.	Algorithme des 𝑘 plus proches voisins avec distance euclidienne. Arbres 𝑘 dimensionnels. Apprentissage d’arbre de décision : algorithme ID3 restreint au cas d’arbres binaires. Matrice de confusion. On observe des situations de sur-apprentissage sur des exemples.
Apprentissage non-supervisé.	Algorithme de classification hiérarchique ascendante. Algorithme des 𝑘-moyennes. La démonstration de la convergence n’est pas au programme. On observe des convergences vers des minima locaux.
Jeux d’accessibilité à deux joueurs sur un graphe. Stratégie. Stratégie gagnante. Position gagnante. Détermination des positions gagnantes par le calcul des attracteurs. Construction de stratégies gagnantes.	On considère des jeux à deux joueurs (𝐽1 et 𝐽2 ) modélisés par des graphes bipartis (l’ensemble des états contrôlés par 𝐽1 et l’ensemble des états contrôlés par 𝐽2 ). Il y a trois types d’états finals : les états gagnants pour 𝐽1 , les états gagnants pour 𝐽2 et les états de match nul. On ne considère que les stratégies sans mémoire.
Notion d’heuristique. Algorithme minmax avec une heuristique. Élagage alpha-beta.
Graphe d’états. Recherche informée : algorithme A*.	On souligne l’importance de l’admissibilité de l’heuristique, ainsi que le cas où l’heuristique est également monotone.
Mesures de similarité pour l’apprentissage machine. Données d’entraînement et données de test, choix des descripteurs. Enjeux d’éthique (biais d’apprentissage, transparence).	COMPLÉMENTS AGREG