algo de recherche en profondeur

Bonjour,

Je dois programmer une "IA" permettant de donner les solutions à un petit jeu avec un personnage qui part de la case en haut à gauche de la grille pour aller en bas à droite de cette dernière en se déplaçant entre les éventuels blocs que le personnage peut pousser lors de son déplacement.

Comme état pour ce problème j'ai considéré la configuration de la grille à un instant donné. Ainsi, j'ai commencé par implémenter l'algorithme de recherche en profondeur d'abord pour résoudre ce problème. Tout marche bien et j'obtiens bien une solution.

J'utilise une matrice à 2 dimensions pour stocker la grille . Compte tenu de la place importante prise en mémoire par ce stockage je me demande quelle est la meilleure solution pour ressortir la solution au problème.

J'hésite entre construire le graphe d'état correspondant durant la recherche en profondeur d'abord ( en liant le père au fils et le fils au père pour pouvoir en partant du père afficher facilement les différentes configurations possibles)
ET entre stocker les déplacements possibles dans une liste que je mets à jour au fur et à mesure de la recherche en profondeur d'abord.

Bien sur, je n'aurais pas le même résultat dans les deux cas puisque d'un côté je pourrais afficher les différents configurations de la grille avec les déplacements et dans l'autre solution juste la liste des déplacements ayant conduits à la grille solution.
Mais ce n'est pas un problème, mon problème ça serait de savoir ce qui serait le mieux au niveau de la place occupée en mémoire notamment.

Qu'en pensez vous ? et si vous avez une idée d'une meilleure solution, n'hésitez pas.

merci d'avance.

Citation:

---

Envoyé par sylsau

Bien sur, je n'aurais pas le même résultat dans les deux cas puisque d'un côté je pourrais afficher les différents configurations de la grille avec les déplacements et dans l'autre solution juste la liste des déplacements ayant conduits à la grille solution.
Mais ce n'est pas un problème, mon problème ça serait de savoir ce qui serait le mieux au niveau de la place occupée en mémoire notamment.

Qu'en pensez vous ? et si vous avez une idée d'une meilleure solution, n'hésitez pas.

merci d'avance.

---

Heu.. Pourquoi tu pourrait pas afficher la grille ? Je veux dire, ça se calcule... Et dans tous les cas, tu doit calculer l'état suivant pour vérifier si la solution est trouvée ou non.
Donc le soucis qui implique tout le compromis temps/espace, c'est au moment du backtrack. Si tu stocke les déplacements dans une liste, il te suffit de supprimer le dernier déplacement (très rapide et pas besoin d'empiler les états succéssifs de cette dernière, si j'ai bien compris c'est ça ton idée).
Par contre tu aura une grille courante qui te permet d'évaluer la situation. Que tu sera obligé de retransformer à l'inverse (et celà est-il toujours possible ?) ce qui est coûteux en temps de calcul. Si le temps n'est pas un soucis, alors tu peux faire comme ça.
Sinon, il faut se poser les questions : quelle est la profondeur maximale d'une branche de l'arbre ? Multipliée par la taille max de la grille, ça donne quoi ? De quelle mémoire je dispose ?

Moi en fait ce qui me turlupine, c'est que tu utilise une méthode de résolution exacte sur un problème NP-complet. C'est plus de l'IA :roll: (stricto-sensus, ça l'est, mais à mon goût...).
Si tu n'as pas besoin de TOUTES les solutions possibles, à ta place j'aurais plutôt opté pour une heuristique, utilisant une "perception locale" de l'environnement par l'agent (le p'tit bonhomme qui pousse).

PS : Trap D aura sûrement une solution, mais il est spécialisé dans le poussage de boules de pierres, exclusivement :wink:

En fait, ça s'est la première partie du projet. A mon gout aussi c'est pas vraiment de l'IA c'est juste un test en force de toutes les possibilités dans le pire des cas mais bon c'est la première questiion du projet donc faut bien la faire :D.

Après dans les autres parties , faudra utiliser une heuristique effectivement puis appliquer l'A*,etc... . Là ça sera déjà plus intelligent comme démarche.

J'ai choisi la solution avec la liste qui permet de gagner de la place en mémoire et de ressortir plus facilement la solution (soit en affichant simplement le contenu de la liste soit en effectuant tous les déplacements et en affichant les différentes configurations de grilles possibles comme tu as dit en effectuant au fur et à mesure les déplacements).

Maintenant que j'ai implémenté l'algorithme, je vais le modifier en rajoutant une heuristique et en choisissant le meilleur état possible selon cette heuristique.

Cependant, pour l'algorithme j'ai pas trouvé grand chose sur le net à part la distance de Manhattan (distance du point courant au point final) et la distance euclidienne.

Mais étant donné que dans ce jeu les obstacles peuvent se déplacer faudrait surement en tenir compte dans l'heuristique mais je vois pas trop comment prendre en compte ce fait là.

Auriez vous l'idée d'une autre heuristique incluant ce fait là ou même d'une autre heuristique tout court ?

Merci d'avance de votre aide.

Bien sûr puisque j'en ai parlé !!
Les processus de décisions Markovien. (Autrement nommé "apprentissage par renforcement").
Vite fait : L'agent perçoit son environement. A chaque état, il peut effectuer plusieurs actions (pour simplifier, toujours les mêmes, Nord, Sud, Est Ouest), en fonction de la récompense espérée (qui ressemble à un "coéficient de préférence" pour telle action dans tel état).
Ceci dis c'est assez dangeureux si ça n'est pas maitrisé...
Le problème est que si l'environnement est non-markovien (c'est à dire si du même état, pour la même action, on peut arriver dans des états différents) le truc va se gauffrer méchamment (l'apprentissage ne va pas converger).

L'idée est néanmoins de ne récompenser l'agent que quand il a atteint son but, il finira par comprendre tout seul le chemin optimal. Il faut aussi qu'il reçoive une récompense négative s'il fait vraiment nawak (genre pousser une pierre qui est bloqué).

Je pense qu'il n'a pas besoin de percevoir toute la carte (ça le fera gagner en généricité) par contre il est impératif qu'il connaisse sa position en (X,Y) (car il devrait finir par comprendre quelle évolution de ces valeur l'ammène au but). L'apprentissage est assez long. Il peut être raccourcis en rajoutant des récompenses intermédiaires (pas trop, sinon tu lui explique tout), en utilisant des maps progressives en difficulté (à vu de nez, je sais pas s'il est necessaire que la taille soit constante ou non), ou encore le doter de "préférences" pour les directions intuitivement justes à l'init des coefs.
Pour diminuer la place mémoire, peut-être que le fait de percevoir des blocs de 3x3 comme un même (X,Y) ne le pertubera pas.

Après, y'a pleins de variantes (epsilon-greedy, SARSA, etc...) pour le modèle de décision lui même, mais il faut toujours garder à l'esprit cette notion de perception markovienne de l'environnement.

Si j'ai d'autres idées je te fait signe !!