Jflesch.kwain.net

Description

IA41 est une des UVs (Unité de Valeur) proposée par l'UTBM. Il s'agit d'une UV d'initiation à l'intelligence artificielle (ainsi qu'au Sli^W Lisp / Prolog). Comme pour les deux tiers des UVs d'informatique de l'UTBM, il nous a été demandé de réaliser, en binôme, un projet.

Sujet du projet:
Ecrire un programme en Lisp (Elisp) capable de résoudre le jeu de hanoï. Minimum demandé: Il doit être capable de résoudre un jeu où deux types de disques sont donnés.

Binôme:
Anderson David.

Réalisation:
Commencé un samedi midi, fini le lundi juste après, à 4h du mat (et avec une soirée frites le samedi soir, s'il vous plaît ;). Bon, je dois aussi préciser que David a continué à fignoler un peu le travail (notamment l'heuristique) après coup.
L'algorithme utilisé fût A*.

Résultat

Gère, en théorie, autant de tours qu'on veut. Dans les faits, au delà de 4~5 tours, ca devient ... euh ... tendu.
Gère autant de types de disques que l'on veut.
Est capable de partir de n'importe-quel état de jeu pour arriver à n'importe-quel autre état (s'il y a une solution, bien entendu ... ;).

Une des seules limitations se situe au niveau de l'affichage: La fonction d'affichage ne prend pas en charge des tours de plus de 8 disques (la théorie voudrait cependant que le programme n'explose pas si on en a plus, c'est juste que ca ne s'affichera pas bien :p).

Un autre détail est, que, normalement programmer en Lisp implique de faire pratiquement tout de manière récursive, sauf que pour des questions d'optimisations (ou plutôt pour éviter que emacs ne crève avant d'avoir trouvé une solution), un des morceau de l'algo a été implémenté de manière itérative.

Téléchargement

Projet et rapport

Conclusion

Il semblerait qu'un certain nombre d'autres groupes aient réussi à coder des programmes similaires au notre (quoique je n'en suis même pas sûr), donc du coup, pour satisfaire notre égo, on est obligé de se rattraper sur le fait qu'on l'a codé en ~3 jours là où les autres ont dû passer une bonne semaine (en sachant que ni eux ni nous ne connaissions le Lisp avant IA41).