Cours Algo Recherche

Christophe DENIS
• Maitre de Conférences (HDR) – Sorbonne Université

• [email protected]
§ Contexte
§ Conjecture : la résolution de jeux de stratégie par l’ordinateur pourrait montrer que celui-
ci dispose d’une certaine intelligence
§ Une partie importante de la recherche en IA a été consacré à la résolution de jeux de
stratégie (Tic-Toe, jeux de dames, jeu d’échec, jeu de Go)
§ Modélisation du jeu sous la forme d’un arbre ou d’un graphe (l’effort de modélisation
n’est pas négligeable pour certains jeux)
§ Besoin de développer des algorithmes de recherche performant pour casser la
complexité de d’une recherche exhaustive qui ne pourrait pas s ’exécuter sur un
ordinateur classique
§ Déterminer un plus court circuit qui passe une et une seule fois par toutes les villes
(ici 15 villes).
§ Complexité O(n-1)!/2 soit O(n!)

N=20 à n! ≃ 2.43e18 chemins possibles à évaluer
§ Problème NP-complet, c’est à dire qu’il n’existe pas actuellement d’algorithme qui
permettre une résolution exacte en un temps fini.
§ Au delà d’une dizaine de points, les algorithmes exhaustifs sont incapables
d’apporter une solution exacte en un temps raisonnable.
« La machine à échecs est idéale pour commencer, puisque : (1) le problème est
clairement défini à la fois dans les opérations autorisées (les coups) et dans le but
ultime (échec et mat) ; (2) il n'est ni simple au point d'être trivial ni trop difficile à
résoudre de manière satisfaisante ; (3) on considère généralement que les échecs
exigent une "réflexion" pour un jeu habile ; la solution de ce problème nous obligera
soit à admettre la possibilité d'une réflexion mécanisée, soit à restreindre davantage
notre concept de "réflexion" ; (4) la structure discrète des échecs s'intègre bien dans la
nature numérique des ordinateurs modernes. …. Nous aimerions jouer une partie
habile, peut-être comparable à celle d'un bon joueur humain »
Claude Shannon, 1949

§ Algorithme minimax basée sur le théorème du même nom de John Von Neumann .
§ Hypothèse et principe :
§ Les joueurs prendront en compte tous les mouvement futures du jeu et joueront de manière
optimale.
§ En d'autres termes, un joueur choisit un coup de telle sorte que, même si l'adversaire choisit
la meilleure réponse à ce coup et à chacun de ses futurs coups, ce joueur obtient toujours le
meilleur score possible à la fin de la partie.
§ Modélisation sur un ordinateur :
§ Données : représentation des positions (appelées états) et des règles du jeu (pour faire passer
un état à un autre)
§ Le programme génère tous les états possibles de la prochaine étape à partir de l'état actuel et
les états possibles pour ces états, et ainsi de suite.
§ On obtient un arbre de chemins possibles du début vers la fin du jeu
§ Un algorithme dite de coupes va être nécessaire pour réduire les évaluations des états
§ Turochamp programme d'échecs et le premier jeu développé pour un ordinateur, développé en
1948 par Alan Turing et D. G. Champernowne, sans implémentation d’un ordinateur
§ Le programme n’est pas basée sur une recherche exhaustive mais sur des heuristiques sur une
orientation de type heuristique.
§ En 1952, un ami de Turing joue contre Turochamp et gagne la partie, alors que Turing simule à la
main les calculs normalement pris en charge par l'ordinateur.
§ Pour le centenaire de la naissance d'Alan Turing,(2012)

§ Implémentation de l’algorithme Turochamp
§ Garry Kasparov joue une partie contre Turochamp qu'il gagne facilement … tout en reconnaissant le
contexte historique et la qualité de Turochamp.
§ Turochamp reste le premier programme d'échecs, conçu avant même les premiers ordinateurs.
§ Le jeu de dames possède une combinatoire plus réduire que le jeu d’échec tout en
restant suffisament compliqué
§ Utilisation de technique d’apprentissage machine (on l’examinera plus tard)
§ Un agent est une entité qui :
§ observe un environnement à travers des senseurs
§ agit dans l’environnement grâce à des effecteurs
§ Les agents peuvent être des humains, des robots, des logiciels, des thermostats...
§ En vacances en Roumanie, actuellement dans la ville d’Arad mon vol de retour part
demain de Bucharest. Comment rejoindre Bucharest ?
§ But
§ être à Bucharest
§ Formulation du problème
§ états : les villes de Roumanie
§ actions : déplacement de ville en ville
§ Solution du problème
§ séquence de villes me permettant d’arriver à Bucharest, par exemple Arad, Zerind, Sibiu,
Fagaras et Bucharest.
§ Déterministe, complètement observable à problème à un seul état
§ L’agent sait exactement dans quel état il est et dans quel état il sera
§ La solution est une séquence d’actions
§ Non-observable à problème sans possibilité de percevoir l’environnement

§ L’agent n’a aucune idée d’où de son état
§ La solution est une séquence d’actions
§ Non-déterministe ou partiellement observable à problème dans lesquels il faut g

gérer des éventualités
§ Les perceptions fournissent de nouvelles informations sur l’état courant
§ Souvent les phases de recherche et d’exécution sont entrelacées
§ L’espace d’états est inconnu à problème d’exploration

§ Agent
§ aspirateur
§ Perceptions
§ Exemple [A, pas propre]
§ Actions
§ Déplacement à gauche
§ Déplacement à droite
§ Aspiration
§ Pas d’action
§ Etat #5
§ aspirateur
§ Solution
§ Droite, aspire
§ Un problème non-déterministe et complètement observable est défini par
§ un état initial
§ « à Arad »
§ un ensemble d’actions ou une fonction de transition, succ(x)

§ succ(Arad) = {Zerind,Timisoara}
§ un test de terminaison pour savoir si le but est atteint

§ Expliciteà « à Arad »
§ Implicite à vérifier mat au échec
§ un coût (additif)
§ somme des distances, le nombre d’actions ex ́ecut ́ees, etc.
§ c(x, a, y) est le coût d’une transition, c(x, a, y) ≥ 0
§ Une solution est une séquence d’actions partant de l’état initial et menant au but.
§ Le monde réel est trop complexe pour être modélisé
§ L’espace de recherche modélise une vue abstraite et simplifiée du monde réel
§ Un état abstrait représente un ensemble d’états réels

§ Une action abstraite représente une combinaison complexe d’actions réelles
§ « Arad → Zerind » représente un ensemble de routes possibles, de détours, d’arrêts, etc.
§ Une action abstraite doit être une simplification par rapport à une action réelle
§ Solution abstraite correspond à un ensemble de chemins qui sont solutions dans le

monde réel.
§ Etats : état de propreté du sol et position de l’aspirateur
§ Actions : droite, gauche, aspire
§ Test du but : toutes les positions doivent être propres
§ Coût du chemin : 1 par action
§ Etats : ?
§ Actions : ?
§ Test du but : ?
§ Coût du chemin : ?
§ Etats : les positions des pièces
§ Actions : déplacement à droite, à gauche, en haut, en bas
§ Test du but : état but donné
§ Coût du chemin : 1 par déplacement
§ Etats : coordonnées du robot, angles, position de l’objet à assembler
§ Actions : déplacements continus
§ Test du but : objet complètement assemblé
§ Coût du chemin : le temps d’assemblage
§ Principe
§ exploration de l’espace d’états en générant des successeurs d’états déjà explorés
§ génération d’un arbre de recherche
§ arrêt lorsque un état exploré correspond à un état final
§ On définit une structure de donnée nœuds qui contient état, parent, enfant,
profondeur, coût du chemin noté g(x)
§ Expand crée des nouveaux nœuds
§ Insert-Fn insère des nœuds dans la liste des nœuds à traiter
§ Un état est une représentation d’une configuration physique du monde
§ Un nœud est une structure de données partie intégrante de l’arbre de recherche
incluant :
§ l’état
§ le parent, i.e., le nœud père
§ L’action réalisée pour obtenir l’état contenu dans le nœud
§ le coût g (x ) pour atteindre l’état contenu dans le nœud
§ la profondeur du nœud, i.e., la distance entre le nœud et la racine de l’arbre
§ Les différents attributs des nœuds sont initialisés par la fonction Expand
§ Une stratégie de recherche est définie par l’ordre dans lequel les nœuds sont développés
par l’intermédiaire de la fonction Insert-Fn
§ Une stratégie est évaluée en fonction des paramètres suivants :
§ la complétude : trouve-t-elle toujours une solution, si une solution existe ?

§ la complexité en temps : le nombre de nœuds crées
§ la complexité en mémoire : le nombre maximum de nœuds en mémoire
§ l’optimalité : les solutions trouvées sont-elles toujours les moins coûteuses ?
§ La complexité en temps et en mémoire se mesure en termes de :
§ b : le facteur maximum de branchement de l’arbre de recherche, i.e., le nombre maximum de fils

des nœuds de l’arbre de recherche
§ d : la profondeur de la solution la moins coûteuse
§ m : la profondeur maximum de l’arbre de recherche qui peut être ∞
§ Les stratégies de recherche non-informées utilisent seulement les
informations disponibles dans le problème
§ Il existe plusieurs stratégies :
§ Recherche en largeur d’abord

§ Recherche en coût uniforme
§ Recherche en profondeur d’abord
§ Recherche en profondeur limitée
§ Recherche itérative en profondeur
§ Peter E. Hart, Nils John Nilsson et Bertram Raphael , « A Formal Basis for the Heuristic
Determination of Minimum Cost Paths », IEEE Transactions on Systems Science and
Cybernetics, (1968)
§ Nils Nilsson essayait d'améliorer la planification de Shakey le robot, un robot
prototype qui se déplace dans une pièce avec des obstacles.
§ Algorithme de Dijkstra ( trouver des plus courts chemins dans un graphe)
§ stratégie efficace si on ne sait pas où se trouve notre destination
§ Peu efficace des d'informations sont connues sur sur la destination
§ Algorithme A* : est un algorithme de recherche de chemin dans un graphe entre un

nœud initial et un nœud final.
§ basé sur une évaluation une évaluation heuristique sur chaque nœud pour estimer le
meilleur chemin y passant, et visite ensuite les nœuds par ordre de cette évaluation
heuristique.
à Nous détaillerons ce cas dans le cadre du TD et du TP de la semaine prochaine
§ L’enseignement des jeux en IA nécessiterait tout le monde
§ Dans le cadre de ce module, introductif nous allons présenter les grandes
différences entre un algorithme de recherche et de jeux.
§ Contrairement aux algorithmes de recherche, il existe au moins deux joueurs

pouvant être coopératifs ou compétitifs
§ Jeux à somme nulle / à somme non-nulle
§ Jeux à information complète / à information non-complète
§ Jeux à deux joueurs / jeux à n joueurs
§ Arbre de recherche
Deux joueurs
• Maxime (X) : 1 si Maxime gagne

• Minda (O) : -1 si Minda gagne
• à 0 si égalité
Elaguer des branches inutiles de l’arbre (algorithme 𝛼𝛽)
Nous le verrons dans un le cours de la semaine prochaine

Cours Algo Recherche

Transféré par

Droits d'auteur :

Formats disponibles

Cours Algo Recherche

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours Algo Recherche

Transféré par

Droits d'auteur :

Formats disponibles

Christophe DENIS

• Maitre de Conférences (HDR) – Sorbonne Université

§ Complexité O(n-1)!/2 soit O(n!)

Claude Shannon, 1949

§ Pour le centenaire de la naissance d'Alan Turing,(2012)

§ Non-observable à problème sans possibilité de percevoir l’environnement

§ Non-déterministe ou partiellement observable à problème dans lesquels il faut g

§ L’espace d’états est inconnu à problème d’exploration

§ un ensemble d’actions ou une fonction de transition, succ(x)

§ un test de terminaison pour savoir si le but est atteint

§ Un état abstrait représente un ensemble d’états réels

§ Solution abstraite correspond à un ensemble de chemins qui sont solutions dans le

§ la complétude : trouve-t-elle toujours une solution, si une solution existe ?

§ La complexité en temps et en mémoire se mesure en termes de :

§ b : le facteur maximum de branchement de l’arbre de recherche, i.e., le nombre maximum de fils

§ Recherche en largeur d’abord

§ Algorithme A* : est un algorithme de recherche de chemin dans un graphe entre un

§ Contrairement aux algorithmes de recherche, il existe au moins deux joueurs

• Maxime (X) : 1 si Maxime gagne

Vous aimerez peut-être aussi