Résultats du grand concours de chasse au Wumpus
Posted: 17 Nov 2013, 22:26En juin 2013, nous vous lancions un grand concours de programmation TI-Nspire. Le sujet mélangeait l'intelligence artificielle, thème qui semble revenir à la mode ces derniers mois à nombre d'examens ou concours, avec un objet mathématique particulier dont l'enseignement en lycée est réservé aux Terminales ES spécialité mathématique, les graphes.
Il fallait résoudre le célèbre problème dit "monde du Wumpus" dans un labyrinthe généralisé sous la forme d'un graphe circulaire. Le labyrinthe ainsi représenté pouvait selon les cas aussi bien découler d'un univers en deux dimensions qu'en trois dimensions, quatre ou même plus encore! Et oui, sans le savoir, vous avez peut-être déjà dépassé les frontières de l'Univers connu !
Nous avons reçu 10 intelligences artificielles de votre part. En y rajoutant la mienne développée à des fins de test, ainsi que TI-Bot qui a souhaité concourir malgré tout avec l'IA aléatoire fournie par défaut avec l'interface, nous en sommes donc à 12:
Vos IA ont été évaluées de façon automatisée grâce à la technologie TI-Nspire Navigator par un cluster de calculatrices TI-Nspire qui au plus fort de son activité a compté jusqu'à 42 unités équipées de leur module WiFi, et toutes munies des OS 3.2.3 ou 3.2.4.
Nous tenons d'ailleurs à remercier Texas Instruments France pour le prêt de cette technologie, sans laquelle nous aurions eu besoin de beaucoup plus de temps.
Vos IA ont été testées sur 7 types de labygraphes différents, des plus petits et simples aux plus gros et compliqués:
Mais comment savoir si votre IA est meilleure ou pas que celles des autres? Nous avons utilisé le principe statistique de la loi des grands nombres, en lui faisant répéter pour chaque type de labygraphe plusieurs dizaines à plusieurs centaines de milliers de parties. En effet, pour un échantillon suffisamment grand, la moyenne obtenue finit par converger vers les valeurs théoriques caractéristiques de vos performances.
Restait encore un dernier petit point à résoudre: quand s'arrêter, la convergence ayant mathématiquement lieu pour une taille infinie. Et bien pour chaque type de graphe, chaque IA a en fait été testée deux fois, sur deux machines différentes. Les performances n'étaient relevées que lorsque les deux machinent finissaient enfin par produire des valeurs identiques ou similaires.
Certaines des IA reçues n'étaient au départ pas directement évaluables sur le cluster à cause de divers problèmes. Lorsque ces problèmes pouvaient être corrigés de façon générique sans rien changer au fonctionnement ou aux performances de l'IA, nous l'avons fait.
Les fichiers éventuellement corrigés et tels qu'utilisés pour l'évaluation sont téléchargeables ci-dessous.
D'autres IA hélas, ont des problèmes d'optimisation dus au fonctionnement interne de l'IA et ne rentrent donc pas dans la catégorie ci-dessus:
Voici donc ce soir enfin venue l'heure des résultats!
Avant d'aller plus loin, je tiens à féliciter tous les participants, et particulièrement le public lycéen. Vous avez su vous approprier un problème complexe de niveau universitaire, faisant l'objet de nombreuses recherches et thèses, et je suis fier de vous tous!
Je citerai à ce sujet notre regretté Albert Barillé:
« Donner à nos enfants le désir de savoir, éveiller leur curiosité. Les traiter aussi en personnes à part entière, qui comprennent bien plus que ne le croient les adultes. Vous les fortifierez ainsi et ils vous en sauront gré. »
Voici donc l'ensemble des résultats fournis par notre cluster de TI-Nspire:
Encore merci à tous pour cette superbe aventure, et à très bientôt pour un nouveau concours!
Téléchargements :
Il fallait résoudre le célèbre problème dit "monde du Wumpus" dans un labyrinthe généralisé sous la forme d'un graphe circulaire. Le labyrinthe ainsi représenté pouvait selon les cas aussi bien découler d'un univers en deux dimensions qu'en trois dimensions, quatre ou même plus encore! Et oui, sans le savoir, vous avez peut-être déjà dépassé les frontières de l'Univers connu !
Nous avons reçu 10 intelligences artificielles de votre part. En y rajoutant la mienne développée à des fins de test, ainsi que TI-Bot qui a souhaité concourir malgré tout avec l'IA aléatoire fournie par défaut avec l'interface, nous en sommes donc à 12:
- AnToX98
- compu
- critor
- David E.
- Extra44
- fortytwo
- le solutionneur
- Max G.
- mdr1
- oakwood
- TI-Bot
- zero44
Vos IA ont été évaluées de façon automatisée grâce à la technologie TI-Nspire Navigator par un cluster de calculatrices TI-Nspire qui au plus fort de son activité a compté jusqu'à 42 unités équipées de leur module WiFi, et toutes munies des OS 3.2.3 ou 3.2.4.Nous tenons d'ailleurs à remercier Texas Instruments France pour le prêt de cette technologie, sans laquelle nous aurions eu besoin de beaucoup plus de temps.
Vos IA ont été testées sur 7 types de labygraphes différents, des plus petits et simples aux plus gros et compliqués:
- n=10, d=10, p=10
- n=10, d=20, p=10
- n=10, d=20, p=20
- n=20, d=20, p=20
- n=20, d=30, p=20
- n=20, d=30, p=30
- n=30, d=30, p=30
Mais comment savoir si votre IA est meilleure ou pas que celles des autres? Nous avons utilisé le principe statistique de la loi des grands nombres, en lui faisant répéter pour chaque type de labygraphe plusieurs dizaines à plusieurs centaines de milliers de parties. En effet, pour un échantillon suffisamment grand, la moyenne obtenue finit par converger vers les valeurs théoriques caractéristiques de vos performances.
Restait encore un dernier petit point à résoudre: quand s'arrêter, la convergence ayant mathématiquement lieu pour une taille infinie. Et bien pour chaque type de graphe, chaque IA a en fait été testée deux fois, sur deux machines différentes. Les performances n'étaient relevées que lorsque les deux machinent finissaient enfin par produire des valeurs identiques ou similaires.
Certaines des IA reçues n'étaient au départ pas directement évaluables sur le cluster à cause de divers problèmes. Lorsque ces problèmes pouvaient être corrigés de façon générique sans rien changer au fonctionnement ou aux performances de l'IA, nous l'avons fait.
- désactivation du mode automatique en cas d'impossibilité de résoudre un graphe (instruction de debug)
- instructions d'affichage dans la console (debug encore) qui en comptant l'évaluation de leurs paramètres ralentissaient énormément la machine, et pouvaient même parfois épuiser la mémoire
- boucles infinies 'while' ou 'repeat' sur certains graphes
Les fichiers éventuellement corrigés et tels qu'utilisés pour l'évaluation sont téléchargeables ci-dessous.
D'autres IA hélas, ont des problèmes d'optimisation dus au fonctionnement interne de l'IA et ne rentrent donc pas dans la catégorie ci-dessus:
- épuisement de la mémoire disponible qui fait redémarrer la calulatrice TI-Nspire (ou planter le logiciel TI-Nspire), la taille des données à stocker en mémoire augmentant beaucoup trop vite à chaque coup
- ralentissement de l'exécution, par la croissance exponentielle de la taille de l'univers de réflexion (salles voisines, puis voisines des voisines, et etc...)
Voici donc ce soir enfin venue l'heure des résultats!
Avant d'aller plus loin, je tiens à féliciter tous les participants, et particulièrement le public lycéen. Vous avez su vous approprier un problème complexe de niveau universitaire, faisant l'objet de nombreuses recherches et thèses, et je suis fier de vous tous!
Je citerai à ce sujet notre regretté Albert Barillé:
« Donner à nos enfants le désir de savoir, éveiller leur curiosité. Les traiter aussi en personnes à part entière, qui comprennent bien plus que ne le croient les adultes. Vous les fortifierez ainsi et ils vous en sauront gré. »
Voici donc l'ensemble des résultats fournis par notre cluster de TI-Nspire:
- En 12ème position, nous avons donc la participation honorifique de TI-Bot avec l'IA aléatoire par défaut. On l'applaudit tous bien fort!
- A la 11ème place, nous félicitons donc David E., qui arriver à doubler voir même tripler les performances de TI-Bot!
- En 10ème position, compu arrive à faire encore mieux. Bravo!
- En 9ème position, voici donc mon IA de test. Bien qu'étant parmi les meilleures sur de petits graphes, l'algorithme de recherche du plus court chemin (Dijkstra) nécessite rapidement beaucoup trop de mémoire, et la rend hélas inévaluable à partir de n=20, d'où la perte de points.
- En 8ème, le solutionneur est notre premier gagnant qui recevra 4 stickers TI-Planet. Bien joué!
- A la 7ème place, zero44 était bizarrement mal parti sur de petits graphes faciles mais s'est vite rattrapé. Il remporte un bloc notes Texas Instruments ainsi que 2 stickers TI-Planet. Bravo!
- En 6ème position, mdr1 a une IA qui comme la mienne est excellente sur de petits graphes, mais devient rapidement inutilisable sur des situations plus complexes. Il recevra un stylo USB Texas Instruments accompagné de 2 stickers TI-Planet.
- 5ème, AnToX98 pourra choisir parmi son lot parmi nos posters Texas Instruments, et recevra également deux stickers TI-Planet.
- Max G. nous ouvre la tête de peloton en 4ème place. Notons que son IA était la meilleure sur les deux premiers types de labygraphes, mais se laisse hélas ensuite progressivement dépasser et dispenser. Il recevra une calculatrice TI-82 Stats.fr ainsi que deux stickers TI-Planet.
- Et voici maintenant le trio de tête très serré avec tout d'abord fortytwo qui arrache la médaille de bronze. Il gagne une calculatrice TI-83 Plus.fr USB accompagnée de deux stickers TI-Planet.
- Médaille d'argent pour oakwood qui recevra une calculatrice TI-84 Plus C Silver Edition couleur avec deux stickers TI-Planet.
- Notre grand médaillé d'or ce soir dont l'IA avait bizarrement mal commencé mais dépasse finalement tous les autres, Extra44, remporte la calculatrice TI-Nspire CX CAS couleur compatible Ndless, ainsi que deux stickers TI-Planet.
Encore merci à tous pour cette superbe aventure, et à très bientôt pour un nouveau concours!
Téléchargements :
