Puzzle solver et intelligence artificielle

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 :

• Des variables. Une variable est la donnée qu’on manipule et est définie par un domaine. Typiquement dans le problème des 8 dames, une variable représente une reine. On va donc avoir 8 dames, chacune positionnée sur une ligne différente des autres. Ainsi, le domaine de ces variables va être représenté par les indices des colonnes (une reine étant assignée à une ligne, elle ne peut se déplacer que de colonne en colonne)
• Des contraintes. C’est ce qui va déterminer les règles du jeu. Dans le jeu des 8 dames, le but est qu’aucune des dames ne puisse en "manger" une autre, ni en ligne, ni en colonne, ni en diagonale. Ainsi on va assigner à chacune des dames la contrainte qu’elle ne doit pas se trouver dans la ligne de mir d’une autre dame. Il s’agit simplement d’une petite fonction qui va vérifier l’emplacement des différentes reines.

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.

• Min conflicts (minimisation de conflits [il n’y a pas de page Wikipédia en français ! :o]) : ce premier algorithme est assez simple et aussi, la plupart du temps, plus efficace. Il va choisir une variable aléatoirement pourvu qu’elle viole au moins une contrainte. Elle va chercher dans le domaine la valeur qui minimise le nombre de violations et va l’assigner à la variable. Et on continue ainsi jusqu’à ce que plus aucune variable ne viole de contrainte.
• Simulated annealing (recuit simulé) : un peu plus compliqué que le premier algorithme, mais ingénieux ! Le principe est d’évaluer le jeu à chacune de ses étapes et de faire en sorte de faire évoluer le jeu de façon à maximiser cette évaluation. Pour faire évoluer le jeu on va simuler des états voisins (un changement de valeurs pour certaines variables). On va ensuite choisir soit d’assigner aléatoirement un de ces états pour la prochaine étape du jeu, soit d’assigner l’état qui possède la meilleure évaluation. Plus on va faire tourner l’algorithme, plus on va choisir l’état maximisant l’évaluation. Pour cela on a à notre disposition une "température" que l’on va réduire au fur et à mesure (d’où l’idée de recuit simulé). Plus la température est basse, plus on va se diriger vers l’état maximal.

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 :)