Je ne connaissait pas ASP, mais après une rapide recherche, c'est purement déclaratif, et donc c'est « l'interpréteur » qui s'occupe de faire la véritable exploration si j'ai bien compris, alors que mon objectif était de faire un parcours en largeur à gros coup de concat . map.
C'est à peu près ça, même si on va dire que la définition française proposée par Wikipédia est très limitée. La version anglaise est mieux.
L'idée ici était surtout de te proposer une autre manière de rechercher des solutions à ricochet robots (essentiellement à des fin de comparaison, mais aussi parce ricochet robots c'est cool et qu'il n'y a pas beaucoup d'IA pour ce jeu)
ASP est un formalisme qui permet de faire de la programmation par contrainte et de l'optimisation au travers de la programmation logique. Généralement, on s'en sert pour résoudre de problème NP-complet. Ton programme ASP est une description de ton problème sous forme logique. Ensuite cherche des solutions à ton problème en utilisant un solveur auquel tu donneras la définition du problème, les données, et éventuellement une stratégie de recherche (comme un parcours en largeur ou en profondeur de l'espace de recherche par exemple).
Si le sujet t'intéresse davantage, tu pourras consulter les cours disponibles ici quand sourceforge tombera en marche.
Du coup, quel est l'avantage d'ASP par rapport à une bibliothèque de résolution en python par exemple ? Parce qu'il y a quand même des désavantages :
ASP est prévu pour faire de la programmation logique, comme python est prévu pour faire de la programmation impérative. En fonction de ce que tu cherches à faire, l'un est plus adapté que l'autre, mais rien ne t'empêche de faire un solveur en python (ou haskell), c'est un bon exercice. D'ailleurs je trouve ta démarche super bien.
Pas d'interaction utilisateur possible en restant déclaratif
Alors, ça c'est hors de la partie résolution du problème. Généralement, tu branches le solveur à autre chose. Par exemple tu peux utiliser ASP (gringo et clasp) avec python. Après, en fonction de ton solveur, tu as des fonctions de contrôle pour interagir avec le solveur lui-même (par exemple interrompre le calcul ou obtenir un résultat intermédiaire suboptimal)
Le debug du programme se fait via les options fournies pas l'interpréteur
Normalement, ton programme est un ensemble de définitions mathématiques. Pour vérifier que tout fonctionne bien, tu fais des preuves. Au pire tu utilises des exemples représentatifs de tes différents cas de figure. Si tu as un soucis avec les résultats, c'est soit que qu'il y a un problème dans tes définitions, soit que le solveur contient une erreur. Il arrive aussi que tu te plantes dans le résultat attendu d'un de tes exemples.
Quid de l'intégration dans un véritable programme (par exemple en tant qu'IA dans un jeu interactif) ?
Là encore, ça ne dépend que de comment tu modélises ton IA. Le solveur est juste une brique à laquelle tu te branches à l'aide de bibliothèques ou de wrappers et à laquelle tu va faire des "requêtes". En fonction de tes contraintes, tu choisiras un solveur plutôt qu'un autre. Dans le cas de ricochet robots,tu peux visez un solveur qui, pour chaque cible, te donnes une réponse (1) optimale quand il a parcouru tout l'espace de recherche ou (2) une réponse suboptimale (et peut-être optimale) quand tu lui demandes (comme au bout des 50 secondes après la réponse du premier joueur).
Tu peux aussi envisager que ton solveur ne parcours pas tout l'espace de recherche, mais parcours juste ton espace de recherche de façon aléatoire. Dans ce cas, tu ne pourras jamais dire qu'il n'a pas de solution, mais dans le cas de ricochet robots, il me semble qu'il existe toujours une solution.
[^] # Re: Version ASP (Answer Set Programming)
Posté par eingrossfilou . En réponse au journal Résolution naïve d'un jeu de société. Évalué à 4.
C'est à peu près ça, même si on va dire que la définition française proposée par Wikipédia est très limitée. La version anglaise est mieux.
L'idée ici était surtout de te proposer une autre manière de rechercher des solutions à ricochet robots (essentiellement à des fin de comparaison, mais aussi parce ricochet robots c'est cool et qu'il n'y a pas beaucoup d'IA pour ce jeu)
ASP est un formalisme qui permet de faire de la programmation par contrainte et de l'optimisation au travers de la programmation logique. Généralement, on s'en sert pour résoudre de problème NP-complet. Ton programme ASP est une description de ton problème sous forme logique. Ensuite cherche des solutions à ton problème en utilisant un solveur auquel tu donneras la définition du problème, les données, et éventuellement une stratégie de recherche (comme un parcours en largeur ou en profondeur de l'espace de recherche par exemple).
Si le sujet t'intéresse davantage, tu pourras consulter les cours disponibles ici quand sourceforge tombera en marche.
ASP est prévu pour faire de la programmation logique, comme python est prévu pour faire de la programmation impérative. En fonction de ce que tu cherches à faire, l'un est plus adapté que l'autre, mais rien ne t'empêche de faire un solveur en python (ou haskell), c'est un bon exercice. D'ailleurs je trouve ta démarche super bien.
Alors, ça c'est hors de la partie résolution du problème. Généralement, tu branches le solveur à autre chose. Par exemple tu peux utiliser ASP (gringo et clasp) avec python. Après, en fonction de ton solveur, tu as des fonctions de contrôle pour interagir avec le solveur lui-même (par exemple interrompre le calcul ou obtenir un résultat intermédiaire suboptimal)
Normalement, ton programme est un ensemble de définitions mathématiques. Pour vérifier que tout fonctionne bien, tu fais des preuves. Au pire tu utilises des exemples représentatifs de tes différents cas de figure. Si tu as un soucis avec les résultats, c'est soit que qu'il y a un problème dans tes définitions, soit que le solveur contient une erreur. Il arrive aussi que tu te plantes dans le résultat attendu d'un de tes exemples.
Là encore, ça ne dépend que de comment tu modélises ton IA. Le solveur est juste une brique à laquelle tu te branches à l'aide de bibliothèques ou de wrappers et à laquelle tu va faire des "requêtes". En fonction de tes contraintes, tu choisiras un solveur plutôt qu'un autre. Dans le cas de ricochet robots,tu peux visez un solveur qui, pour chaque cible, te donnes une réponse (1) optimale quand il a parcouru tout l'espace de recherche ou (2) une réponse suboptimale (et peut-être optimale) quand tu lui demandes (comme au bout des 50 secondes après la réponse du premier joueur).
Tu peux aussi envisager que ton solveur ne parcours pas tout l'espace de recherche, mais parcours juste ton espace de recherche de façon aléatoire. Dans ce cas, tu ne pourras jamais dire qu'il n'a pas de solution, mais dans le cas de ricochet robots, il me semble qu'il existe toujours une solution.
J'espère que c'est assez clair.