Cette page permet de tester différents algorithmes de
parcours afin de résoudre un Sokoban. Ces algorithmes,
leurs enjeux d'optimalité, de complexité temporelle et
d'utilisation de la mémoire, sont largement
détaillés sur cette page.
Un Sokoban est un jeu se déroulant sur une grille
régulière telle que celle présentée ci-dessous.
Le point vert représente un personnage, qui peut se déplacer d'une case vers le haut, le bas, la gauche ou la droite.
Les cases marron représentent des caisses, qui peuvent être poussées par le personnage (une seule à la fois).
Enfin, les cases noires correspondent à des murs, infranchissables par le personnage ou les caisses.
Le but du jeu est d'amener ces caisses aux emplacements cibles marqués d'une croix, en un nombre minimal de déplacement. Résoudre un niveau de Sokoban est un problème NP-difficile
On considérera dans toute la suite le nombre de
déplacement de caisses - les déplacements de personnage
qui ne poussent pas de caisse étant considérés de coût
nul. Peu importe donc la position précise du personnage
parmi l'ensemble des cases auxquelles il peut accéder sans
déplacer de caisse.
Le problème peut donc se formuler comme un parcours dans
le graphe des positions accessibles : chaque sommet
est une position (décrite par la position des caisses et
la zone où se trouve le personnage), et un arc relie deux
sommets si et seulement si on peut passer du premier au
second en poussant une caisse. On cherche alors dans ce
graphe un chemin reliant la position initiale à la
position cible, où chaque caisse est sur un emplacement
cible.
L'application permet de tester différents niveaux, et différents algorithmes de parcours. Vous trouverez en dessous des précisions
supplémentaires sur les algorithmes, et notamment sur les heuristiques utilisées pour les algorithmes d'exploration guidée.
Nouvelle position :
Résoudre :
Positions possibles pour les caisses :
Algorithme : Itérations : Temps : Mémoire utilisée : Longueur du chemin trouvé :
Algorithme
Itérations
Temps
Mémoire
Longueur du chemin
Tout coup «vaut» 1 : dans le
graphe des configurations, les arêtes sont toutes de poids 1. L'algorithme de Dijkstra n'apparait donc pas, puisqu'il revient à un parcours en largeur.
Le nombre de positions accessibles est difficile à évaluer. Le nombre de positions possibles pour les caisses est majoré par $\binom{n}{p}$, où $p$ est le nombre de caisses, et $n$ le nombre de cases différentes d'un mur. Toutes ces combinaisons ne sont pas accessibles, et cela ne prend pas en compte les positionnements du personnage. Cela donne néanmoins un ordre de grandeur de l'espace des états. Si l'on prend en compte les placements du personnage, le nombre de positions accessibles est majoré (très grossièrement) par $(n-p)\binom{n}{p}$. À noter que la combinatoire du problème augmente fortement avec le nombre de caisses.
Il y a un gain important à précalculer
(comment ?) des cases dont une caisse ne pourra
plus sortir pour atteindre une cible. Cela diminue
environ d'un facteur quatre l'espace des configurations sur les exemples ci-dessus.
L'heuristique «distances 1» est la somme des distances
de chaque caisse à la cible la plus proche - distance désignant le nombre de coups nécessaires pour atteindre la cible la plus proche si la caisse pouvait se déplacer de façon autonome. L'image ci-dessous montre le nombre de mouvements nécessaire pour atteindre la plus proche cible depuis chaque case.
Dans l'heuristique «distances 2», on prend désormais en compte le fait qu'une caisse doit être poussée, ce qui donne les distances suivantes :
Aucune de ces heuristiques ne prend en compte les «interactions» entre les caisses.
Le niveau 5 a une combinatoire importante, et est
très long à résoudre avec un parcours en largeur. Il
devient trivial avec une heuristique.
L'implémentation propre des parcours en profondeur
ou largeur est un excellent exercice de
programmation. Pour atteindre des performances
raisonnables, on peut utiliser une table de hachage pour
retrouver rapidement les
positions déjà rencontrées.
Éditeur de niveau
Cliquer plusieurs fois sur une case pour changer son contenu.
Références
Algorithmique, de Cormen et al.
Intelligence artificielle 3e édition : Avec plus de 500 exercices, chapitre 3, de Russel et Norvig
A Formal Basis for the Heuristic Determination of Mimimum Cost Paths (pour A*), de Hart, Nilsson et Raphael