Marien Fressinaud Le blog

Puzzle solver et intelligence artificielle

Le 09 novembre 2013.

Une semaine après avoir publié le code de mon jeu de Quarto, il est temps que je vous parle de mon résolveur de puzzles.

Ce "puzzle solver" a aussi été écrit dans le cadre de mon cours de programmation d’IA et c’est donc mon deuxième projet. Je l’ai écrit pendant le mois d’octobre cette fois-ci. Le code est publié sous licence MIT et est disponible sur Github.

Le principe de ce projet est assez simple : le but est juste de proposer un algorithme permettant de résoudre des jeux (aussi appelés "problèmes") de façon modulaire. Ainsi, l’algo en lui-même doit être capable de résoudre un maximum de jeux avec un minimum d’adaptations.

Deux jeux étaient imposés à la base : le problème des huit dames et le problème de coloration de graphe. Le troisième jeu était libre et j’ai choisi le carré magique qui me semblait bien adapté au sujet (après coup, ce n’était pas forcément le plus simple :p).

Il y avait encore une autre contrainte, et c’est d’ailleurs là le cœur du projet. En fait il s’agissait d’implémenter non pas un seul algorithme, mais deux. Mais avant d'aller plus loin il me faut expliquer comment sont représentés les jeux. Comme je le disais plus haut, un jeu est aussi appelé "problème". Un problème peut donc être défini par :

Au début d’un jeu, on assigne à chaque variable une valeur aléatoire issue de son domaine. Aussi il y a de fortes chances que certaines variables "violent" des contraintes. Le jeu n'est donc pas dans son état optimal et il va falloir appliquer un algorithme pour faire en sorte de réduire le nombre de violations de contrainte.

L’algorithme du recuit simulé est beaucoup trop compliqué pour arriver à en faire une bonne explication en quelques lignes, je vous invite donc à lire sa page Wikipédia si vous voulez plus d’information dessus :p

Pour y voir plus clair dans l’architecture de mon programme, j’ai fait un diagramme de classes assez global. Il y a pas mal de classes reliées entre elles du coup ce n’était pas super simple de faire un beau diagramme. Sachez juste que la partie "implémentation" (qui représente la phase d’adaptation à un jeu en particulier) ne représente pour chacun des jeux que quelques lignes de code, consistant à assigner les domaines aux variables et à définir les contraintes.

Je m’arrêterai là pour les explications. Sachez juste que je me suis bien éclaté sur ce projet. Au départ j’étais un peu affolé par l’algorithme du recuit simulé sur lequel on avait pas mal bloqué l’année dernière (les explications étaient assez confuses). Finalement je me suis rendu compte qu’il est plutôt simple à implémenter :) (reste le choix de certaines valeurs qui est assez compliqué et c’est là où je n’ai pas été très bon). Au final le projet m’a valu un 100/100, je suppose donc que mon boulot n’est pas mauvais :D

Le dernier projet parlera de particules et d’oiseaux et sera encore plus rigolo :)

Retourner au blog