Studio-Dev.fr - Julien Lafont

Accédez au projet Google Code et téléchargez le code source : Jade-IA

Présentation

L’objectif du projet est de développer un système expert capable de deviner des entités en posant à l’utilisateur une série de questions. Ce concept est inspiré de l’application Akinator ou 20Q.

Réalisé sous forme de jeu, le logiciel devra sélectionner les questions pertinentes qui permettront au moteur d’intelligence artificielle de deviner le plus rapidement possible ce à quoi pense l’utilisateur. Pour cela, il s’appuiera sur une base de connaissance composée au démarrage de 100 entités, et d’en moyenne 200 questions, lesquelles seront au fur et à mesure des parties complétées et affinées.

Notre moteur Jade (pour Julien, Alexandre, Djeneba, Epsi) sera capable de découvrir le sport auquel vous pensez, ou une série télévisée. A chaque étape, des données statistiques seront enregistrées pour améliorer le système, et à la fin de la partie, en cas d’erreur, le logiciel proposera à l’utilisateur de saisir sa réponse et une question discriminative pour ne plus réitérer cette erreur dans les prochaines parties.Outils

Outils de développement

Le choix du langage de programmation s’est naturellement orienté sur le langage libre et open-source Java.

Dans un premier temps, une étude technique a été réalisée sur le moteur d’inférence Jess (http://www.jessrules.com) afin de déterminer s’il était ou non adapté à notre cahier des charges.

Jess est un moteur de règle maintenu par le laboratoire Sandia (http://www.sandia.gov), offrant une implémentation en JAVA du langage Clips. Jess offre un système de programmation par règle permettant de développer des systèmes experts et des moteurs d’inférence. De ce fait, il répond à notre besoin sur la partie technique.

Cependant, plusieurs points nous ont amenés à choisir une solution alternative : développer notre propre moteur d’inférence.

Tout d’abord, Jess est un langage propriétaire, dont les sources sont verrouillées et qui n’offre qu’une documentation très partielle. Bien que le système soit lui-même très complet, le développeur ne peut que très difficilement exploiter tout le potentiel de ce moteur. De surcroît, il nous a semblé très intéressant de coder nous-même notre moteur afin d’en comprendre le fonctionnement interne, et de pouvoir l’adapter plus finement à notre besoin.

Concernant la base de connaissance, celle-ci est actuellement stockée dans une Système de gestion de base de données relationnel (SGBRD) dit « embarquée » : DerbySQL. Cette caractéristique nous permet de déployer facilement notre application, la base de données est directement incluse et ne demande pas l’installation ou la configuration d’un service extérieur.

De plus, nous avons utilisé la librairie JDBC de Java qui permet d’utiliser de manière transparente n’importe quel SGBDR. Il est alors tout à fait possible de transférer la base de connaissance sur une base de données hébergée en ligne, permettant ainsi à plusieurs utilisateurs de se connecter, de partager et d’enrichir une unique base de données.

Algorithme principal

Objectif : Trouver l’entité à laquelle pense l’utilisateur en lui posant un minimum de questions fermée.
Stratégie : Parcours avant de l’arbre de recherche préparé par l’expert et amélioré par les précédentes parties du jeu.

Nœud <- récupérer question racine
 Proposition <- Nul
 Tant que Proposition est nul faire
             Poser question à l’utilisateur
             Réponse <- Récupérer réponse de l’utilisateur
             Nœud <- Avancer dans l’arbre à partir du nœud courant en fonction de la réponse1
             Si nœud est de type question alors           
                         question <- Nœud
             Sinon
                         Proposition <- Nœud
             Fin si
 Fin boucle

 Afficher Proposition
 Résultat <- Demander à l’utilisateur si la proposition est correcte

Si Résultat est Vrai alors
             Fin de partie gagnante
Sinon
             Réponse <- Demander réponse à l’utilisateur
             Si réponse existe déjà alors
                         Rechercher source de l’erreur
                         Afficher à l’utilisateur la question où il s’est trompé
             Sinon
                         Demander à l’utilisateur la question discriminative
                         Insérer dans la base de connaissance la nouvelle réponse
             Fin si
 Fin si

Conclusion et perspectives

Au final, l’application Jade fournit un système de recherche parfaitement fonctionnel.
La base de connaissance initiale comporte environ 100 sports et séries, avec en moyenne 500 questions par arbre de recherche, et une longueur moyenne des branches de 10-15 questions.

Plusieurs améliorations peuvent être apportées au système pour le rendre plus performant, et le code du moteur et des contrôleurs ont été pensés pour qu’elles soient possibles et facilement intégrables.

 La première amélioration serait de transformer l’arbre de recherche en un graphe, où plusieurs branches peuvent se rejoindre dans des cas où la réponse à une question n’est pas formelle. Cela permettrait ainsi de rattraper des erreurs récurrentes des utilisateurs.

Une autre idée est de stocker les questions auxquelles le joueur a répondu « Je ne sais pas », et en cas d’erreur à la fin de la recherche, le moteur pourrait repartir sur ces questions en prenant l’autre réponse. Cela permettrait d’avoir un comportement proche de celui d’Akinator où le moteur a plusieurs chances de trouver la solution.