Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1. Introduction Le but de ce projet est l’implémentation d’un logiciel pour la

1. Introduction Le but de ce projet est l’implémentation d’un logiciel pour la résolution automatique des puzzles du type Sokoban – un jeu de réflexion inventé par le japonais Hiroyuki Imabayashi dans les années ’80 du siècle dernier. Le jeu se déroule dans un labyrinthe divisé en cases carrées, dans lequel se trouvent des pierres et dont certaines cases sont marquées comme cases-cibles. Le joueur contrôle un personnage qui peut se déplacer à l’intérieur du labyrinthe et qui peut pousser les pierres ; le but du jeu est de ramener toutes les pierres sur les cases-cibles. Comme restrictions, les pierres peuvent être seulement poussées et une seule pierre peut être deplacée à un moment donné. (Le personnage ne peut donc ni remorquer les pierres, ni en déplacer deux à la fois). Fig. 1 : Puzzle du Sokoban. Le but est de ramener toutes les pierres sur les cibles ; Les pierres sont déplacées en les poussant, une seule pierre à la fois. Ce jeu est intéressant car, malgré la grande simplicité des règles, les problèmes qu’il pose sont souvent des vrais casse-têtes. Pour bien de niveaux du jeu la solution implique des centaines de mouvements ; cette grande profondeur de l’arbre de recherche s’ajoute à un grand degré de ramification – le nombre d’alternatives disponibles à chaque mouvement rend le jeu comparable au jeu d’échecs. Dans ce qui suit, les cases du labyrinthe seront nommées cellules ; les cases-cible seront appelées simplement cibles. Le personnage est nommé pousseur. 1 2. Etat du domaine de l’intelligence artificielle. 2 3. Présentation de l’application Le logiciel présenté a un caractère didactique : c’est une application Java contenant une collection d’une vingtaine de puzzles Sokoban, de plus simples jusqu'à des puzzles de complexité moyenne. L’utilisateur peut choisir parmi les labyrinthes proposés et peut essayer de les résoudre lui-même ou bien il peut démarrer une analyse automatique de n’importe quel puzzle de la collection. Si l’analyse automatique mène à une solution, l’utilisateur pourra ensuite visualiser la solution trouvée (qui pourra être parcourue automatiquement ou pas à pas, arrêtée ou parcourue en sens inverse). Apres toute analyse automatique, l’utilisateur aura aussi l’option d’examiner la ‘pensée’ du programme : il aura l’option d’examiner les états parcourus par l’analyseur automatique, afin d’en évaluer la performance. L’application se présente comme une collection d’une soixantaine de fichiers binaires (classes Java) (Le grand nombre de fichiers s’explique par la multitude des composantes de l’interface graphique, chacune ayant une classe Java correspondante). La classe principale de l’application est PusherMain ; pour exécuter l’application on va donc lancer la commande : java PusherMain qui va faire apparaître l’écran principal du programme. Dans ce qui suit, on va présenter un à un les écrans du programme et on va détailler leur fonctionnement. 3 3. 1. Ecran principal Dans l’image suivante on présente un instantané de la fenêtre principale de l’application (en l’occurrence, celle correspondant à un des puzzles les plus simples). On y retrouve le dessin du labyrinthe avec les pierres et le pousseur ; le nombre du labyrinthe dans la collection (6, dans notre cas) ; et des indications sur les commandes disponibles. Fig. 2 : La fenêtre principale de l’application Dans cet écran, l’utilisateur peut essayer de résoudre lui-même le puzzle ; pour cela, il se sert des flèches pour déplacer le pousseur dans le labyrinthe. Pour la commodité, et comme une extension au jeu original, l’utilisateur a aussi la possibilité de revenir en arrière sur ses pas, en utilisant la touche <backspace>, s’il se rend compte qu’il a fait une erreur. es autres commandes disponibles dans cet écran sont les suivantes (toute 4 commande peut être exécutée en cliquant sur le bouton de la commande ou par appui de la touche correspondante): - la touche <Entrée> peut être appuyée à tout moment pour démarrer une analyse automatique du puzzle dans l’état où il se trouve (par exemple, si l’utilisateur essaye de résoudre lui-même le puzzle et se retrouve dans un impasse, il a l’option de demander une analyse automatique de la situation) ; - les touches <Page Up> / <Page Down> servent à passer au labyrinthe précédent ou au labyrinthe suivant de la collection ; - pour sortir du programme, on utilise les touches <Echapper> ou <Q>. 5 3. 2. Ecran d’analyse en cours Lorsque l’utilisateur demande une analyse automatique de la situation (en appuyant sur <Entrée> dans l’écran principal), le programme va afficher la fenêtre ‘analyse en cours’. Dans ce mode, le labyrinthe reste affiché mais l’utilisateur ne peut plus déplacer le pousseur ; le programme va afficher continuellement le nombre d’états analysés jusqu'à présent. A tout moment, l’utilisateur peut cliquer sur ‘stop analysis’ (ou appuyer sur <Echapper> ou sur <Q>) pour arrêter l’analyse, ce qui conduit à l’écran des résultats de l’analyse. Fig. 3 : Ecran d’analyse en cours 6 3. 3. Ecran de résultats de l’analyse Quand l’analyse d’un puzzle s’achève – après l’atteinte d’une solution, après avoir épuisé tous les mouvements possibles sans trouver de solution ou après l’arrêt de l’analyse par l’utilisateur – le programme va afficher une fenêtre avec les résultats de l’analyse. Cette fenêtre contiendra, outre le labyrinthe lui-même, le nombre du labyrinthe analysé dans la collection, le nombre total d’états parcourus, le nombre de blocages trouvés (voir section sur l’architecture de l’application pour des explications sur les blocages). Si l’analyse a mené à une solution, cette fenêtre va contenir l’indication ‘found solution’ (‘solution trouvée’). Fig. 4 : L’écran des résultats de l’analyse du labyrinthe 6 (notez la mention ‘found solution’, qui indique que l’on a trouvé une solution) 7 Les commandes disponibles dans cette fenêtre sont les suivantes : - Défilage automatique de la solution, en appuyant sur <Entrée>. Cette commande va conduire à la fenêtre de défilage automatique de la solution (voir plus bas) ; - Exécution pas-à-pas de la solution, en appuyant sur <Espace> pour avancer et sur <Backspace> pour aller en arrière. De cette manière l’utilisateur peut exécuter pas à pas la solution trouvée par le programme, en insistant s’il le désire sur certaines successions de mouvements ; - Reprise de la solution à partir de l’état initial, en appuyant sur <Home>. Cela va remettre le labyrinthe dans son état initial, et l’utilisateur pourra faire défiler la solution encore une fois ; - Visualisation des états parcourus dans l’analyse, en appuyant sur <S>. Cette commande va ouvrir la fenêtre de visualisation des états, dans laquelle l’utilisateur peut examiner, un à un, les états parcourus par le programme pendant l’analyse; - Visualisation des blocages, en appuyant sur <D>. Cette commande va ouvrir la fenêtre de visualisation des blocages, où l’utilisateur peut examiner, un à un, les blocages découverts par le programme ; - En appuyant sur <Q> ou <Echapper>, l’utilisateur peut rentrer à l’écran principal du programme. 8 3. 4. Ecran de défilage automatique de la solution Cette fenêtre (présentée dans la figure 5) va afficher, de façon animée, la succession de mouvements qui conduit à la solution du puzzle. On y trouve aussi un pourcentage indiquant la proportion de la solution qui a été déjà parcourue. Pour arrêter l’animation on appuie sur <Q> ou sur <Echapper>, ce qui nous retourne conduit à l’écran des résultats de l’analyse. La vitesse de l’animation est fixe, choisie afin d’assurer une visualisation commode de la solution. Selon la complexité du puzzle analysé, le défilage complet de la solution peut durer plusieurs minutes. Fig. 5 : Ecran de défilage automatique de la solution pour le labyrinthe 6 9 3. 5. Ecran de visualisation des états Cet écran permet à l’utilisateur de visualiser un à un les états du labyrinthe examinés par le programme pendant l’analyse. Cette fenêtre va afficher le nombre total d’états examinés, le numéro de l’état affiché à présent, et le labyrinthe avec les positions des pierres et du pousseur dans l’état considéré. En cliquant avec le bouton de droite de la souris sur une pierre, l’utilisateur va visualiser le domaine admissible de la pierre en question (voir section sur l’architecture de l’application pour une définition du domaine admissible). Fig. 6 : La fenêtre de visualisation des états parcourus. On examine un état rencontré pendant l’analyse du labyrinthe 6. 10 Fig. 7 : Fenêtre de visualisation des états parcourus avec affichage du domaine admissible d’une pierre (en bleu) Les autres commandes accessibles dans cette fenêtre sont les suivantes : - les touches <Page Up> / <Page Down> réalisent l’affichage de l’état précédent ou de l’état suivant (notons qu’il ne s’agit pas de l’état précédent ou suivant au sens de l’évolution du labyrinthe, mais de l’état précédent ou suivant dans la collection globale des états examinés) ; - la touche <F> va créer un fichier sur le disque contenant tous les états examinés par le programme ; c’est une fonction utile surtout pour le dépannage du programme ou pour l’évaluation de ses performances ; - pour rentrer a l’écran précédent on appuie sur <Echapper> ou sur <Q>. 11 3. 6. Ecran de visualisation des blocages Cet écran permet à l’utilisateur de visualiser un à uploads/Management/ sokoban.pdf