IA et jeux vidéos

Petite histoire de l'Intelligence Artificielle.

Depuis les temps anciens jusqu'à aujourd'hui est en cours une fusion du système de pensée humain dans un modéle rationnel, dont la recherche se poursuit aujourd'hui.    En 1642, le philosophe et mathématicien Pascal construit la première mise en oeuvre de ces techniques : une machine à calculer. Un siécle plus tard, le philosophe Leibniz apporte des améliorations à la machine de Pascal et propose une modélisation mathématique de la pensée.

Nombre de penseurs du XVIIIe et XIXème siècles étaient convaincus qu'un système de raisonnement formel, basé sur une maniére de mathématique, pourrait modéliser l'intégralité de la pensée humaine, afin d'être utilisé pour résoudre toutes sortes de problèmes. Thomas Jefferson, par exemple, était persuadé qu'un tel système existait déjà, et qu'il suffisait seulement de le découvrir.

Au XIXe siècle, George Boole proposa un système des "lois de la pensée", dont les concepts relatifs de base, "ET", "OU" et "NON" suffisaient à établir la maniére dont les idées et les objets se lient entre eux. L'encodage de la logique selon Boole s'appliquait à toute la pensée humaine, et à n'importe lequel de ses objets.

Au début du XXe siècle, B. Russell et A. N. Whitehead ont publié Principia Mathematica, qui marqua le début de l'intérêt de la philosophie de l'époque pour la formalisation de la rationalité en vue d'analyser mathématiquement la connaissance : la logique formelle. A cette époque, les scientifiques commencèrent à visualiser les connexions synaptiques du cerveau, et le mot "cybernétique", décrivant l'étude du contrôle et de la communication dans les systèmes biomécaniques, commençait à se faire connaître. Claude Shannon écrivait sa théorie de l'information.

Vinrent les ordinateurs. La mémoire informatique étant un paysage purement symbolique, elle apparut comme l'endroit idéal pour syncrétiser le résultat des travaux des 2000 années passées. En 1936, Alan Turing exposa sa théorie sur la machine ultime : un espace mémoire illimité, peuplé de symboles, avec un programme minimal écrit lui aussi sous forme de symboles, servant à scanner, lire et interpréter ces symboles. Le "programme" et les "données" étant confondus dans le même espace mémoire, elle acquerrait ainsi la capacité de se modifier elle-même. La "machine de Turing" devait ainsi pouvoir résoudre toutes sortes de problèmes et simuler, selon Alan Turing, l'intelligence humaine (quoique cette interprétation de l'intelligence soit encore soumise à débat).

 

  • En 1957, Allen Newell et Herbert Simon inventérent le Résolveur Général de Problèmes.

  • En 1958, McCarthy inventa le langage LISP, un langage interprété de symboles donnant à la machine la possibilité de modifier son propre programme.

  • En 1966, Joseph Weizenbaum créait Eliza, le premier robot de discussion.

  • En 1970, Terry Winograd créait SHRDLU, le premier programme capable de PENSEE COGNITIVE.

 barre-1.jpg

Organisation hétérarchique de SHRDLU

Depuis, plus rien. L'informatique ayant choisi l'aspect commercial au détriment de l'application scientifique, les travaux sur l'IA se sont arrêtés. Seuls quelques laboratoires spécialisés continuent encore les recherches. Les travaux de Winograd ont été oubliés, son programme désormais ne tourne plus sur aucune machine et personne n'est capable de le comprendre afin de le porter sur une architecture moderne. On se sert toujours d'Eliza en de plus ou moins bonnes implémentations, dans les salons IRC, comme robot de discussion pour amuser les internautes.

Eliza était un robot de discussion capable de conversations assez intéressantes et ayant même une certaine tendance à la psychanalyse, mais dont la lacune de taille était qu'elle ne comprenait pas ce qu'elle disait. Sa technologie s'est pourtant déclinée en de nombreuses variantes (Parry, le robot paranoiaque, et Alice, qui furent ses successeurs), puis Jason Hutchens utilisa les travaux de Markov, mathématicien statisticien dont la théorie du langage voulait que la construction syntaxique du message ne soit qu'une affaire de probabilités de placer tel mot devant tel autre, en fonction des mots précédents et de ceux censés suivre. Sa théorie des modèes de langage stochastiques a conduit à une révision majeure des théories sur les canaux d'expression humains. La grammaire et la syntaxe, règles nécessaires au décodage de l'information dans le langage naturel, seraient uniquement des produits de l'expression, et non l'inverse. Jason Hutchens créa alors MegaHAL, un robot de discussion capable initialement de ne rien dire, mais d'apprendre n'importe quel langage pour peu que l'on veuille bien le lui enseigner. Le robot révéla une capacité d'apprentissage assez spectaculaire, mais n'avait toujours pas la compréhension de ce qu'il disait. Bien que grammaticalement correctes, certaines de ses phrases pouvaient faire penser au discours que l'on pourrait avoir avec une personne qui parle inconsciemment dans son sommeil.

SHRDLU fut la première machine capable de comprendre réellement le monde. Le système se constituait d'un bras articulé et d'une caméra (un "oeil") virtuels, et son monde se limitait à un certain nombre de blocs de couleur empilables, posés sur une table. Il se révéla capable d'exécuter des manipulations assez complexes avec ces blocs, ainsi que, selon la demande de l'utilisateur, d'expliquer ce qu'il faisait et pourquoi il le faisait, de demander la signification des choses qu'il ne comprenait pas et d'en tirer les leçons. Ce fut la première intelligence artificielle.

 

Personne n'a été capable de faire mieux depuis lors. Ce programme était bel et bien un être vivant, non dans notre monde réel, mais un être vivant dans son monde virtuel de cubes et de blocs empilables, heureusement incapable de le transcender, tout comme nous-mêmes sommes incapables de transcender les quatre dimensions perceptibles de notre Univers (x, y, z, t) pour en percevoir d'autres. 


barre-1.jpg

Qu'est-ce qu'un bot ?

Bot signifie robot. Dans ce cas précis, un bot est un adversaire contrôlé par ordinateur, avec lequel ceux qui ne sont pas connectés à Internet ou ceux qui ont manqué la dernière LAN peuvent s'entraîner un peu, en attendant la suivante. Un bot a l'apparence d'un joueur humain, et son IA acquiert par apprentissage la faculté de reproduire plus ou moins bien le comportement normal d'un joueur en cours de partie : vous tirer dessus quand il vous voit, escalader les échelles, se cacher sous un escalier en attendant votre passage, collecter des objets, se moquer de vous quand vous êtes mort, en somme toutes les fourberies possibles et imaginables comme dans un véritable jeu en réseau. Si le bot est bon, le joueur peut avoir l'impression de jouer contre un adversaire humain.

IL S'AGIT DU TEST DE TURING.

barre-1.jpg

Logique floue.

La logique floue ou « fuzzy logic » est une technique issue des milieux académiques dans les années 60 et basée sur la théorie des ensembles flous. Elle a depuis été utilisée dans de nombreuses applications industrielles : en automatisme (freins ABS), dans le contrôle aérien, dans le diagnostic médical, etc … et dans les jeux vidéos. L’idée sous-jacente est de permettre à une condition d’être dans un autre état que vrai ou faux. Autrement dit, la nécessité de trouver une formalisation mathématique pour exprimer des notions vagues et approximatives.

Dans un jeu vidéo, cela permet d’utiliser des opérations logiques sur des valeurs imprécises (« assez loin », « plutôt dangereux ») et de déclencher simultanément plusieurs états, à des niveaux d’importance différents (« faché », mais davantage « peur »), ce qui permet au final d’obtenir des comportements moins tranchés. Le jeu Sims utilise notamment ce genre de technique en complément aux smart terrains
Les règles de fonctionnement d’un joueur de football peuvent, par exemple, s’exprimer de la façon suivante :

  • SI goal proche ET adversaire NON proche : Tirer au but
  • SI adversaire proche ET coéquipier NON loin : Passer le ballon
  • SI adversaire proche ET coéquipier loin : Dribbler

 

Figure ci-dessus : Représentation graphique de fonctions d’appartenance


Les notions proche, avoisinant ou loin sont déterminée par un « degré d’appartenance » à un ensemble. Cette valeur comprise entre 1 et 0 est calculée au moyen de fonctions d’appartenance. Le système d’inférence peut produire ensuite, sur base de ces règles et des  évènements et stimuli perçus dans l’environnement, une cotation des activités qui peut être la suivante :

  • Tirer au but avec une valeur de 0.1
  • Passer le ballon avec une valeur de 0.2
  • Dribbler avec une valeur de 0.7

L’action à effectuer est simplement celle ayant la meilleure cote. Des extensions de ce système permettent d’utiliser des filtres pour choisir l’action gagnante.

barre-1.jpg

Modèles inspirés par la biologie.

Dans leur quête pour reproduire une imitation de l’intelligence humaine, les chercheurs en intelligence artificielle se sont inspirés de différents mécanismes biologiques pour concevoir des modèles informatiques de décision. Dans le domaine du jeu vidéo, deux de ces méthodes ont été utilisées avec succès : les réseaux de neurones artificiels et les algorithmes génétiques. Les neurones artificiels tentent de reproduire un réseau artificiel de neurones, interconnectés par des synapses. Techniquement, ces neurones sont organisés en couches successives, chaque neurone d’une couche prenant ses entrées dans des neurones de la couche précédente. Des stimuli externes excitent la première couche et par propagation, l’excitation se propage de couche en couche pour aboutir au final à des valeurs de sortie, sur base desquelles sera prise la décision finale. Cette technique permet de prendre des décisions s’appuyant davantage sur la perception que sur le raisonnement.

A chaque synapse est associé un poids qui amplifie le signal perçu. Les signaux d’entrée sont combinés en tenant compte des poids des synapses, et le tout est fourni à une fonction d’activation qui est non linéaire et détermine la valeur d’activation du neurone. Celle-ci est
ensuite utilisée comme stimulus d’entrée pour les neurones de la couche suivante. Figure 8 : Neurone artificiel : combinaison du signal perçu (valeurs x d’entrée) et activation non linéaire du neurone.

En fonction des types de réseau, différentes fonctions de combinaison peuvent être utilisées :
fonction de combinaison sous forme de produit scalaire entre les entrées et les poids synaptiques, fonction de combinaison basée sur la distance euclidienne entre les entrées, …


Figure ci-dessus : Neurone artificiel : combinaison du signal perçu (valeurs x d’entrée) et activation non linéaire du neurone.


En fonction des types de réseau, différentes fonctions de combinaison peuvent être utilisées :
fonction de combinaison sous forme de produit scalaire entre les entrées et les poids synaptiques, fonction de combinaison basée sur la distance euclidienne entre les entrées, …

En ce qui concerne la fonction d’activation, l’idée est utiliser un seuil en dessous duquel, le neurone est inactif (0 ou – 1) et au-dessus duquel, le neurone est actif (1). Aux alentours du seuil, on a une phase de transition. Les fonctions mathématiques de type sigmoïde ou de type hyperbolique offrent ces propriétés. D’autres fonctions non linéaires présentant un seuil sont également possibles. Toute la finesse dans l’utilisation des réseaux de neurones, réside dans le nombre de couches et de neurones à utiliser, mais surtout dans la technique utilisée pour l’apprentissage ou ajustement des différents paramètres (coefficients des synapses) de façon à corriger les erreurs commises. L’apprentissage peut être supervisé (on force le réseau à converger vers un état final précis quand on lui présente des stimuli) ou être non-supervisé (on le laisse converger librement vers n’importe quel état lorsqu’on lui présente des stimuli).

L’apprentissage supervisé a notamment été utilisé dans différents jeux, notamment les jeux de voitures (Colin McRae Rally13) ou les jeux de combats (Tekken14). L’apprentissage consiste ici à faire des parcours de circuit ou des séances de combat manuellement, et de corriger
ensuite les coefficients des synapses, en utilisant la technique de rétro-propagation. C’est-àdire en rétro-propageant l’erreur commise par un neurone à ses synapses et aux neurones qui y sont reliés (les poids synaptiques qui contribuent à engendrer une erreur importante sont
modifiés de façon plus significative que ceux qui ont engendrés une erreur plus faible). D’autres jeux ont également utilisé ces techniques de réseaux neuronaux pour des simulations de vie artificielle comme Creatures15 et Black & White16.

Les algorithmes génétiques sont utilisés quant à eux dans différents problèmes d’optimisation, afin de déterminer des solutions qui sont satisfaisantes sans être pour autant optimales. Les chercheurs en intelligence artificielle se sont ici inspirés des mécanismes de sélection naturelle dans la théorie de l’évolution. Dans un jeu vidéo, cela revient, par exemple, à ramener les caractéristiques d’un opposant sous la forme d’une chaîne d’ADN artificielle, et d’effectuer une sélection parmi les meilleurs opposants, pour ensuite les croiser et obtenir le meilleur des caractéristiques d’origine. De temps à autre, des mutations sont effectuées sur cette chaîne d’ADN pour obtenir de nouvelles variantes.
La difficulté est donc ici de modéliser les caractéristiques sous forme de chaîne d’ADN artificielle représentées par des bits ou des réels, de déterminer une fonction adéquate pour sélectionner les meilleurs candidats et de développer ces méthodes de mutation et de croisement. Plusieurs techniques de sélection sont utilisées : sélection par rang (choisir les individus possédant les meilleurs scores d’adaptation), sélection proportionnelle à l’adaptation (principe de la roue de la fortune biaisée ou chaque individu est représenté par une portion proportionnelle à son adaptation), sélection par tournoi (choisir la sélection proportionnelle sur des paires d’individus, et choisir ensuite parmi ces paires, l’individu qui a le meilleur score d’adaptation), sélection uniforme (choix aléatoire sans tenir compte de la valeur d’adaptation).

La technique, dite des systèmes à classeurs (ou classifier systems), a été expérimentée dans une version modifiée du jeu Half Life17. Dans sa version simple, cette technique consiste à modéliser des règles de déclenchement d’actions sous forme de patterns de 0, 1 et * (0 ou 1). Une action se déclenche si son pattern coïncide avec les stimuli présentés en entrée. Ici, des algorithmes génétiques ont été utilisés pour sélectionner les meilleurs patterns (en cotant les actions effectuées).

Figure ci-dessus : Organisation des systèmes à classeurs


Cette expérience a permis d’optimiser automatiquement le comportement d’une équipe de quatre bots. Leurs performances se sont avérées être au final comparable ou supérieure à celle des meilleurs bots disponibles sur Internet (scriptés manuellement).

Figure ci-contre : Half Life modifié pour tester les systèmes à classeurs

 

Modèles inspirés par l’éthologie

Certains chercheurs en intelligence artificielle se sont inspirés de l’éthologie, c’est-à-dire des études comportementales effectuées sur les animaux, afin de reproduire des êtres artificiels. L’accent est plutôt mis sur l’émotion et le réalisme plutôt que sur le comportement réfléchi.

Figure ci-contre : Structure d'un modèle basé sur le comportement

En général, le comportement de l’animal est modélisé comme une hiérarchie de comportements plus spécifiques. A chaque niveau, a lieu une compétition entre les comportements pour prendre le contrôle de l’animal et ainsi imposer son action.

Au niveau des stratégies de compétition, deux principaux modèles ont été utilisés : inhibition et fatigue (les comportements tentent de s’inhiber mutuellement, et lorsqu’un comportement a le contrôle, il perd progressivement de sa pertinence dû à un phénomène de fatigue), et free-flow (on fait propager une quantité d’énergie au sommet de la hiérarchie, et les comportements ayant absorbés le plus d’énergie seront les vainqueurs).

Figure ci-dessus : Inhibition-Fatigue vs Free-Flow


Ces types de modèles ont été utilisés dans le projet de chien robotique AIBO18 de Sony et le jeu Nintendogs de Nintendo pour sa console à écran tactile Nintendo DS.

Lire l'article complet format pdf Games_dossier_FR.pdf

Article sur l'intelligence artificielle, format pdf livret-IA.pdf

Date de dernière mise à jour : 16/06/2013

Créer un site gratuit avec e-monsite - Signaler un contenu illicite sur ce site