Bonjour !

Dans le cadre de mon projet info je suis en train de programmer un jeu de taquin 3x3 et une des fonctions que j'aimerais y integrer est la résolution du jeu.

Apres avoir trouvé la case a bougé un message du style suivant sur apparaiterait



Et ainsi de suite.

J'ai trouvé ça mais je vois pas comment je vais le coder

Citation : Algorithme de resolution

Soit C le chemin (liste d'états) menant d'un état E à l'état initial. Une fonction heuristique possible est : h(C) = longueur(C) + d(E).

Soit I l'état initial. F une file d'attente de chemins avec priorité h, et D un dictionnaire des états déjà visités. On suppose que I est différent de l'état final.

Rentrer le chemin réduit à I dans F (avec h(I)) et dans D
Fini := faux
Tant que (non Fini) et (F non vide) faire
Sortir un chemin C de F de priorité minimale; soit E le premier élément de C
Pour tous les successeurs S de E et tant que (non Fini) faire
Si S est l'état final alors Fini := Vrai et Solution := inverse(S.C)
Sinon, si S n'est pas dans D alors rentrer S.C dans F (avec h(S)) et S dans D

Cet algorithme se termine toujours et garantit l'obtention d'une solution si elle existe. La file ne peut pas être vide si l'état initial est soluble. La solution obtenue n'est pas nécessairement de longueur minimale : tout dé de la distance d.

On dit que d est "optimiste" si pour tout état E, d(E) est inférieur ou égal à la longueur d'un chemin optimal permettant de passer de E à l'état final. On montre que si d est optimiste, le chemin est au pire de longueur minimale plus 1.

Le choix de la distance a une influence sur le coût de l'algorithme. On notera par exemple que si d(E) = 0 pour tout état E, l'algorithme effectue un parcours en largeur, et donc trouve un chemin optimal. Malheureusement, le coût est prohibitif.

Quelqu'un aurait une source ou une idée ?

pourais-tu m'expliquer rapidement le but du jeu.
(parce-que ton texte est assez lourd a comprendre )

Le jeu du taquin c'est ça:



Et il me semble que l'algorithme c'est A*
C'est très utilisé pour ce genre de probleme.

Un tour sur wikipedia te donnera quelques liens interressants et un pseudo code:
http://fr.wikipedia.org/wiki/Algorithme_A%2A

L'algo est pas très compliqué en fait, mais le texte que tu cites est pas des plus intuitif
Prend de temps de bien te renseigner pour comprendre l'algo, ça va te simplifier enormement la tache.


En gros c'est un parcours dans un graph. On part du taquin mélangé, et on doit arriver au taquin résolu. Chaque arc du graph représente un déplacement, et chaque noeud du graph un état du taquin.
L'algo va parcourir ce graph, et trouver le chemin qui a le cout minimal(ou presque).
Le cout dans ton cas c'est le nombre de deplacements.
Pour que cela fonctionne, il faut que pour chaque noeud (chaque état du jeu), tu puisses estimer le cout entre ce noeud et le noeud final (la solution). En d'autres termes, combien de deplacements il te reste pour terminer le puzzle à partir de ce noeud? (c'est la fonction d(E) dans ton texte, E étant un noeud)

Ton texte te dit que si tu estimes toujours ton cout à 0, tu vas trouver la bonne solution (comme c'est optimiste), mais tu vas parcourir ton graph en integralité->perfs minables.
Faut avoir l'évaluation du cout la plus fine possible (mais qu'elle reste optimiste) pour avoir les meilleurs perfs possibles.


Il faut aussi que tu saches pour chaque noeud le cout necessaire pour y arriver: Combien de deplacements on étés effectués pour arriver à cet état du jeu? ( longueur(C) dans ton texte)


Et enfin tu as ton heuristique. Celle donnée parton texte convient très bien. C'est la somme des deux fonctions que je viens d'expliquer. Cela sera donc une estimation optimiste du cout du chemin partant de l'état inital et arrivant à l'état final, tout en passant par le noeud ou tu te trouves
Autrement dit: si je passe par ce noeud, je vais trouver la solution en x déplacements en partant du taquin initial.




Après il te restes à parcourir le graph, en prenant à chaque fois le noeud dont ta fonction heuristique rendra la valeur la plus faible, jusqu'à atteindre la solution.
Un petit schéma tout moche montrant les trois premieres étapes:



En rouge, le noeud ou tu te trouve.
En noir les noeuds deja parcourus.
En verts les noeuds "candidats" pour le meilleur chemin, ce sont ceux que tu compare pour savoir vers lequel aller.
Les valeurs indiquées sont celles que te renvoie ton heuristique.


Voilà, mes explications sont peut etre confuses, mais il est tard
Quoi qu'il en soit après avoir fouillé le lien wikipedia et les quelques sites ou ils renvoie ça devrait etre bon.

Merci pour les explications ... c'est pas sur que j'arrive a l'intégrer, mais si je le comprend c'est deja bien

"Pour que cela fonctionne, il faut que pour chaque noeud (chaque état du jeu), tu puisses estimer le cout entre ce noeud et le noeud final (la solution). En d'autres termes, combien de deplacements il te reste pour terminer le puzzle à partir de ce noeud? (c'est la fonction d(E) dans ton texte, E étant un noeud) "

J'ai tenté sans d(E) comme si ça valait zero (donc je parcours tout le graph) et effectivement les perf sont plus que minable (sauf quand y'a que 2-3 trucs à bouger)
Le probleme c'est que je voit pas comment estimer le cout entre un noeud et l'etat final.

Pour trouver un d(E) le meilleur possible, une des astuces qui existe est de simplifier le probleme (en s'affranchissant de certaines contraintes).
En gros tu te fais des nouvelles regles du jeu, très simplifiées, et tu compte combien de coups il faudrait dans ces conditions. Comme tu enleve certaines contraintes par rapport au vraies regles, mais que tu n'en ajoute pas de supplémentaires, cela reste une estimation optimiste.

Par exemple, on peut imaginer que l'on puisse bouger les pieces sans contrainte aucune: il suffirait alors de prendre une piece mal placée, et de la poser au bon endroit (meme si il y en a deja une à cette place). Ca peu paraitre idiot, mais ça fonctionne! Tu regarde quel srait le coup pour finir le jeu avec ces regles, et ça te donne une estimation du coup réel!

Cela revient à regarder le nombre de pieces qui ne sont pas en place. C'est loin d'etre bon, mais c'est deja mieux que d(E) = 0

Pas excellent, car cela ne tient pas compte de la position des pieces. Or une piece juste à coté de la bonne case, ça se regle en un coup, alors que si elle est à l'opposé du plateau, il va falloir plusieurs coups. (mais l'estimation renvoyée par d(E) sera la meme).


On peut affiner ça de cette façon, avec ces "nouvelles regles":
Tu peux desplacer les pieces comme precedement, mais tu dois tenir compte de la distance de deplacement. Plus lapiece est loin, plus le cout sera élevé. Il suffit de calculer la distance "à vol d'oiseau" entre la case ou se trouve une piece, et la case ou elle devrait etre. Il On fait la somme de toutes les distances de chaque piece pour avoir une estimation. (il suffit de voir le plateau comme un repere mathematique, chaque case à des coordonnées à partir desquelles on peut calculer une distance entre deux cases).


On doit pouvoir faire mieux que ça, mais deja avec ça tu vas parcourir ton arbre bien plus vite. (tu peux compter les noeuds parcourus pour comparer plusieurs fontions d'estimation )

Je sais pas si ça peut fonctionner parce que justement rapprocher les piece de leur position finale rapproche rarement le taquin de son etat resolu , souvent c'est même le contraire.
En fait la meilleur solution ça reste de prendre un taquin resolu et de le melanger en sauvegardant le chemin.
Mais bon c'est moins marrant.
Enfin avec 362 880 noeuds possible je comprend que ça prenne du temps , et encore c'est seulement pour un taquin 3*3.

Je suis sur que cela fonctionne, après j'ai pas dit que c'était la meilleure méthode hein

Mais compare deja le nombre de noeuds parcourus avec d(E) = 0 et avec une des deux (voir les deux) solutions que je te propose (en partant du meme taquin mélangé). Tu vas economiser un bon paquet de noeuds, c'est certain

Si ça te suffit pas, une recherche google avec taquin et heuristique devrait te donner des methodes un peu plus avancées (mais probablement plus dure/longues à mettre en place).