Discussion :

[GuiomNantes]

Bonjour
Je dois realiser un Casse tete le jeu du taquin, j'ai quelque questions:
Je dois utiliser une fonction heuristique

J'ai donc choisit d'utiliser "Manhattan" a savoir calculer la distance entre l'emplacement actuel de la piéce du puzzle et l'objectif.

Le problème qui se pose c'est que je dispose de prédicat pour me déplacer à droite , à gauche, ne bas , en haut comme par exemple:

down ( A/B/C/D/E/0/H/I/J , A/B/C/D/E/J/H/I/0 ).

Ces prédicats sont appelés dans des fonctions du type :
move(P,C,up) :- down(P,C).

Et ma fonction heuristique est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Heuristique(A/B/C/D/E/F/G/H/I, P) :-
     a(A,Pa), b(B,Pb), c(C,Pc),
     d(D,Pd), e(E,Pe), f(F,Pf),
     g(G,Pg), h(H,Ph), i(I,Pi),
     P is Pa+Pb+Pc+Pd+Pe+Pf+Pg+Ph+Pg+Pi. 
 
 
is_goal(1/2/3/8/0/4/7/6/5).

Donc P contient la distance totale, je cherche donc la distance la plus petite


Donc pour lancer
solver(A,Z):-is_goal(Z). // cas de base


// je n'arrive pas à faire le cas général, car il faut bien que je stock le type de mouvement, deplus je pense que ma fonction heuristique n'est pas suffisante car elle donne juste le chemin le plus court, mais elle ne se préoccupe pas des cases voisines .. Donc les chemins ne sont pas forcement bon.
Mais bon je voudrais d'abord pouvoir faire fonctionner mon algo avec une fonction heuristique.
solver(A,Z):-

Merci d'avance

[luckyvae]

Comment représentes-tu tes différentes pièces? Via ces lettres?
Si oui, pourquoi ne pas les représenter par deux points: le premier t'indique où se situe la pièce et le second t'indique où elle devra se situer. Ainsi, calculer la distance de Manhattan sera un jeu d'enfant. De plus, si tu veux passer à un jeu possédant plus de pièces, ce sera assez facile.

Ensuite, concernant ton choix de fonction heuristique, elle ne me semble pas particulièrement mauvaise. J'ai déjà vu des implémentations dans lequels la fonction heuristique était bêtement le nombre de pièce mal placée.

Quel algorithme de recherche vas-tu utiliser?

[GuiomNantes]

Comment représentes-tu tes différentes pièces? Via ces lettres?
Si oui, pourquoi ne pas les représenter par deux points: le premier t'indique où se situe la pièce et le second t'indique où elle devra se situer. Ainsi, calculer la distance de Manhattan sera un jeu d'enfant. De plus, si tu veux passer à un jeu possédant plus de pièces, ce sera assez facile.

Ensuite, concernant ton choix de fonction heuristique, elle ne me semble pas particulièrement mauvaise. J'ai déjà vu des implémentations dans lequels la fonction heuristique était bêtement le nombre de pièce mal placée.

Quel algorithme de recherche vas-tu utiliser?

En fait le jeu est un gros cube à l'intérieur c'est comme un Sudoku des petites cases representés par des chiffres, il y a une case vide permettant de déplacer les autres.

Pour le choix de la fonction heuristique elle ne me semble pas assez suffisante car , dans ce puzzle nous ne pouvons pas déplacer les pièces comme nous voulons, tous les changements sont dépendants des autres, je ne sais pas si je me fais bien comprendre.

En pieces jointes une image du jeu

[luckyvae]

Les propriétés nécessaires relatives à la fonction heuristique dépendent de ta méthode de recherche. Certaines demandent plus de propriétés que d'autres mais en général la propriété demandée est la suivante: il faut que dans tout les cas possible, la valeur de la fonction heuristique soit inférieure au coût de l'optimum réel. Donc, comme fonction heuristique tu pourrais très bien prendre la fonction constante 1. Mais si tu prend cette fonction constante, la recherche ne sera pas très efficace car trop d'états seront explorés.
Au plus la valeur de l'heuristique sera proche de l'optimum, au moins d'états seront explorés.
Je suppose donc que tu cherches une meilleure heuristique dans le but d'améliorer tes résultats. Mais il faut garder deux choses en tête. Tout d'abord la propriété d'infériorité. Ensuite, que cette heuristique doit être facile à calculer. En effet, si celle-ci devient plus difficile à calculer que d'effectuer une recherche, alors l'efficacité diminuera.

En pratique, dans le cadre du jeu de taquin, on utilise quasi toujours l'heuristique que tu proposes car son calcul est immédiat, il n'y a aucun mal à prouver la propriété et la différence entre le coût réel et le coût calculé n'est pas trop grand.

[GuiomNantes]

Les propriétés nécessaires relatives à la fonction heuristique dépendent de ta méthode de recherche. Certaines demandent plus de propriétés que d'autres mais en général la propriété demandée est la suivante: il faut que dans tout les cas possible, la valeur de la fonction heuristique soit inférieure au coût de l'optimum réel. Donc, comme fonction heuristique tu pourrais très bien prendre la fonction constante 1. Mais si tu prend cette fonction constante, la recherche ne sera pas très efficace car trop d'états seront explorés.
Au plus la valeur de l'heuristique sera proche de l'optimum, au moins d'états seront explorés.
Je suppose donc que tu cherches une meilleure heuristique dans le but d'améliorer tes résultats. Mais il faut garder deux choses en tête. Tout d'abord la propriété d'infériorité. Ensuite, que cette heuristique doit être facile à calculer. En effet, si celle-ci devient plus difficile à calculer que d'effectuer une recherche, alors l'efficacité diminuera.

En pratique, dans le cadre du jeu de taquin, on utilise quasi toujours l'heuristique que tu proposes car son calcul est immédiat, il n'y a aucun mal à prouver la propriété et la différence entre le coût réel et le coût calculé n'est pas trop grand.

D'accord mais je ne vois pas trop comment je peux limplementer car en utilisant cette méthode , je ne vais pas pouvoir utiliser mes prédicats de déplacements, je m'explique ma fonction heuristique va me donner par exemple 30 en résultat , le poids minimun.
mais comment je vais pouvoir obtenir mes chemin, par exemple il faut aller à droite, à gauche.. je suis un peu bloqué.
En fait je n'arrive pas à faire la relation entre la formule de "manhattan" et mes prédicats de déplacements.
Auriez vous une idee?

[luckyvae]

Lorsque l'on est dans un état donné, le système (ou le joueur) peut choisir entre différentes options: le trou se déplace vers le haut, le bas, la gauche ou la droite. Il faut donc déterminer laquelle de ces options est celle qui nous amèneras à la solution. Il faut donc utiliser un algorithme de recherche dans un espace d'état . L'algorithme A* par exemple. Pour connaitre un chemin gagnant, il faudra donc retenir les différents états par lesquels A* est passé pour arriver à la solution.

La structure du programme sera donc la suivante:

• un prédicat vous permettant de donner l'ensemble des états que l'on peut atteindre à partir de l'état courant
• calculer la valeur de l'heuristique pour chacun de ces états atteignable
• utiliser un algorithme de recherche pour connaitre l'état suivant à explorer (celui-ci peut ne pas être un des états atteignables à partir de la position courante, mais plutôt un état précédant qui pourrait se révéler plus intéressant)
• changer l'état du jeu pour atteindre l'état désigné par l'algorithme. Et lors de ce changement, modifier en conséquence l'historique des déplacements.

J'espère que cela vous aidera et que ce sera plus clair pour vous.
Ces deux trois petits trucs que je connais, je les ais appris dans le livre Intelligence artificielle dans lequel ils parlent du problème de recherche dans un espace d'état, et ils prennent justement le jeu de taquin pour exemple d'application d'un des algorithme décrit.