Partiel d'Intelligence Artificielle : Jeux et Recherche

Introduction à l'évaluation d'Intelligence Artificielle

Ce document propose un sujet de partiel d'Intelligence Artificielle destiné aux étudiants en Master 1 Informatique. L'évaluation s'intéresse à des notions fondamentales de la discipline à travers plusieurs exercices pratiques portant sur la théorie des jeux, les arbres de décision et les algorithmes de recherche heuristique. Les étudiants y trouveront des applications concrètes d'algorithmes classiques ainsi que des corrections manuscrites détaillées qui permettent de comprendre la résolution pas à pas.

Présentation générale du document

Le sujet a été proposé à l'Université Paris 7 le 22 novembre 2006 dans le cadre du cursus de Master 1 Informatique, spécialité Intelligence Artificielle. D'une durée prévue d'une heure et demie, il couvre plusieurs thèmes majeurs abordés dans les enseignements de premier cycle universitaire en IA. Les documents étaient autorisés lors de cette épreuve, ce qui reflète l'accent mis sur la compréhension et l'application des méthodes plutôt que sur la simple restitution de cours.

Thèmes et exercices abordés

Le document s'articule autour de quatre exercices principaux qui testent différentes compétences en résolution de problèmes et en exploration d'espaces d'états :

Exercice 1 : Étude d'un arbre de jeu comportant des nœuds min et max. Les étudiants doivent appliquer l'algorithme minimax ainsi que l'élagage alpha-bêta avec un parcours de gauche à droite, en partant des valeurs initiales habituelles.
Exercice 2 : Problème de manipulation de pions sous contraintes de déplacement. Cet exercice introduit un graphe d'états avec des actions spécifiques d'échange, suivi d'une recherche guidée par heuristique (recherche gloutonne et algorithme A*).
Exercice 3 : Analyse approfondie de l'algorithme alpha-bêta sur un arbre de jeu spécifique, demandant de déterminer des valeurs de feuilles pour éviter toute coupe lors du parcours.
Exercice 4 : Exploration de l'algorithme de recherche à faisceau (beam search) dérivé de A*, avec l'analyse de cas où l'algorithme peut manquer la solution ou omettre la solution optimale.

Méthodes et concepts clés

L'examen met en œuvre des notions théoriques et pratiques incontournables en intelligence artificielle :

La recherche antagoniste avec les algorithmes Minimax et Alpha-Bêta pour l'optimisation des décisions dans les jeux.
La modélisation d'espaces d'états et la formalisation d'actions avec des coûts unitaires.
La conception et l'utilisation d'heuristiques admissibles pour guider les algorithmes de recherche.
L'évaluation de la performance d'algorithmes dérivés d'A*, tels que la recherche gloutonne et la recherche à faisceau.

Utilisation du document pour les révisions

Ce partiel corrigé constitue un outil de travail précieux pour les étudiants souhaitant s'entraîner aux examens d'intelligence artificielle. Il est conseillé de chercher à résoudre chaque exercice de manière autonome avant de consulter les solutions manuscrites fournies dans les pages du document. Cette démarche permet de confronter ses propres méthodes de calcul et de raisonnement aux corrections officielles, en particulier pour le suivi des valeurs des bornes alpha et bêta ou le développement des nœuds dans les graphes de recherche.

Questions fréquentes

À quel niveau d'études s'adresse ce sujet de partiel ?

Ce sujet est destiné aux étudiants en première année de Master (Master 1) en Informatique, dans le parcours ou la spécialité d'Intelligence Artificielle.

Quels sont les principaux algorithmes étudiés dans ce document ?

Le document aborde principalement l'algorithme minimax, l'élagage alpha-bêta, la recherche gloutonne, l'algorithme A* et la recherche à faisceau (beam search).

Quelle est l'origine institutionnelle de ce document ?

Ce partiel provient de l'Université Paris 7 et a été évalué le 22 novembre 2006 pour une durée d'une heure et demie.

Testez vos connaissances

Question 1

Quel est le rôle principal de l'élagage alpha-bêta dans un arbre de jeu ?

Trouver systématiquement toutes les feuilles de l'arbre sans exception.
Éviter d'évaluer des branches entières qui ne peuvent pas influencer la décision finale.
Modifier la structure de l'arbre en cours de partie.
Remplacer complètement les nœuds max par des nœuds min.

Réponse correcte : Éviter d'évaluer des branches entières qui ne peuvent pas influencer la décision finale.

Explication : L'élagage alpha-bêta permet d'optimiser l'algorithme minimax en coupant l'exploration des sous-arbres dont on sait qu'ils n'affecteront pas le résultat de la racine.

Question 2

Dans le cadre de l'exercice 2, comment est définie la fonction d'évaluation heuristique h ?

Par le nombre total de déplacements possibles depuis l'état initial.
Par le coût cumulé des actions déjà réalisées.
Par le nombre de pions mal placés par rapport à l'état final désiré.
Par une valeur constante égale à zéro pour tous les nœuds.

Réponse correcte : Par le nombre de pions mal placés par rapport à l'état final désiré.

Explication : L'heuristique utilisée dans le corrigé évalue la distance à la solution en comptant les pions qui ne sont pas à leur position finale (par exemple par rapport à l'état CBAD).

Question 3

Quelle est la particularité de la recherche à faisceau (beam search) présentée dans l'exercice 4 ?

Elle conserve tous les nœuds générés sans aucune limitation mémoire.
Elle ne garde à chaque étape que les k meilleurs enfants selon la valeur f = g + h.
Elle n'utilise aucune fonction heuristique.
Elle garantit toujours de trouver la solution optimale.

Réponse correcte : Elle ne garde à chaque étape que les k meilleurs enfants selon la valeur f = g + h.

Explication : Contrairement à A*, la recherche à faisceau limite le nombre de nœuds conservés à chaque niveau en ne sélectionnant que les k meilleures options, ce qui peut parfois mener à rater la solution optimale.

Télécharger Partiel d'Intelligence Artificielle : Jeux et Recherche pdf