Discussion :

[Aspic]

Bonjour,

Je cherche à appliquer un A* au problème du Sokoban
http://fr.wikipedia.org/wiki/Sokoban

Le principe est très simple : soit un puzzle (représenté par une matrice) comportant un personnage (le pousseur), des caisses et des goals. Le but est de pousser toutes les caisses dans les goals sachant qu'on ne peut pousser qu'une seule caisse à la fois. Il est interdit de tirer une caisse. Un goal ne peut avoir qu'une caisse dessus.

J'ai lu sur internet que l'algorithme A* est optimal, c'est à dire retourne toujours la solution la plus courte si la fonction heuristique utilisée est admissible, c'est à dire si elle ne sur-estime jamais le coût entre le noeud considéré et l'objectif final.

J'essaye d'appliquer cela au Sokoban. Soit l'état initial qui représente la position des caisses au début du niveau et la position du personnage. L'état final correspond à l'état où toutes les caisses sont dans un goal.
Soit f(n) le coût total de l'état n (un noeud = un état = positions des caisses + personnage)
Soit g(n) le coût pour aller de l'état initial à l'état n
Soit h(n) le coût pour aller de l'état n à l'état final (fonction heuristique)
On a ainsi d'après A*: f(n) = g(n) + h(n) pour tout n.

J'ai volontairement choisis une heuristique mauvaise pour ce jeu : la distance de Manhattan entra chaque caisse et son goal le plus proche.
Etant donné que je ne sur-estime jamais, A* devrait me retourner la solution optimale (c'est à dire la solution qui nécessite le moins de poussée de caisse, sachant qu'on ne se préoccupe pas du déplacement du personnage = coût nul)

Pourtant parfois, mon algo ne me retourne pas la solution la plus courte. Est ce que mon raisonnement est juste ? ou alors peut être que mon heuristique n'est pas correcte et sur-estime dans certains cas ?

Merci d'avance

[Flodelarab]

Bonjour,

on ne se préoccupe pas du déplacement du personnage = coût nul

Pourtant, c'est ce qu'on compte dans le sokoban. Il faut atteindre le minimum de déplacements.

[Aspic]

Bonjour,

Pourtant, c'est ce qu'on compte dans le sokoban. Il faut atteindre le minimum de déplacements.

Bonjour,

Non pas du tout, la plupart des solveurs de nos jours ne se préoccupe que des déplacements des caisses et ne cherche pas l'optimalité dans les déplacements du personnage. C'est le cas de solveurs comme Rolling Stone ou Taking Stone voire même de YASS Solver.