Des Astuces pour Jouer à Sokoban

Notation

Ce guide utilisera les termes suivants :

• coup: un pas du robot, que ce soit une poussée ou un simple déplacement.
• chemin: une séquence de coups.
• position: le puzzle entier décrivant l’emplacement du robot et des boîtes.
• solution: une position où chaque boîte est sur un point rouge
• chemin de solution:la séquence de coups permettant de passer de la position initiale à la solution.
• position morte: une position à partir de laquelle la solution est inatteignable .

Stratégie générale

La solution la plus rapide peut contenir 100, 300, voire 1 000 coups (il faut déjà 73 coups pour compléter notre puzzle le plus simple, dans le 8^ème puzzle il faut 126 coups). S’il y a en moyenne deux possibilités pour chaque coup et la solution nécessite 100 coups alors il faudrait chercher 2 ¹⁰⁰ chemins pour retrouver la solution si on les vérifier un par un. Alors il faut :

1. reconnaître les positions mortes au plus tôt,
2. diviser l'objectif global en sous-tâches. La complexité du problème est considérablement réduite quand on peut diviser un chemin de solution de 100 coups en 10 sous-tâches par exemple. En plus, il pourrait être possible de déterminer l’ordre dans lequel il faut réaliser les sous-tâches pour faciliter la résolution du problème,
3. trouver des restrictions sur le chemin de la solution,
4. penser à d'autres heuristiques.

1) 1) Reconnaître les positions mortes au plus tôt

1.1) Parfois il est facile à déterminer qu’une position est morte, il suffit de regarder la région entourant une seule boîte. Une inspection « locale » est suffisante. Si une boîte n’est pas sur un point rouge et ne peut se déplacer horizontalement ni verticalement, la position est morte. La boîte est peut-être bloquée par le mur ou d’autres boîtes qui ne peuvent pas être déplacées non plus.

1.2) Il est un peu plus difficile de voir qu'une position est morte quand la boîte se trouve sur un mur et on peut la pousser mais uniquement le long du même mur où aucune des cases qu’elle peut atteindre n’est un point.

1.3) Dans cette généralisation, la boîte se trouve sur un mur et on peut la déplacer dans une case où elle n’aura pas le mur de côté (la case A ci-dessous), mais le robot ne pourra pas atteindre cette case A car elle sera bloquée par la boîte.

On peut reconnaître ces trois cas localement sans déplacer le robot. Alors on peut les retrouver dès la position initiale pour ensuite les marquer comme « interdits » avec un symbole tel que ! pour éviter de pousser une boîte dans une telle case.

1.4) Prenant cette généralisation plus loin, le robot pourra atteindre la case A mais uniquement s’il condamne une autre boîte.

Cette explication est récursive.^[1], c.-à-d. qu’elle définit une position morte en utilisant les mots « position morte ». Il est plus difficile de reconnaître de telles positions mortes car on ne peut pas les détecter localement et il est peut-être nécessaire d’effectuer des coups d’essai.

2) Formuler des sous-tâches

Exemples des sous-tâches:

1. Déplacer le robot de A à B,
2. Déplacer une boîte de A à B

Où chaque tâche doit être réalisée sans créer de position morte.

Exemple pour (a) : Comment contourner une boîte pour rejoindre la case A:

Tout l’espace vide est nécessaire pour que le robot puisse faire le tour de la boîte. Sans cet espace vide le robot ne pourra contourner la boîte sans faire de position morte.

Si on connaît déjà le nombre de sous-tâches ainsi que le plan du labyrinthe, on peut résoudre le problème plus rapidement, dans ce cas-ci le chemin à 9 coups. Encore plus important, on sera plus motivé à compléter la sous-tâche sachant qu’elle n’est pas impossible.

Une question liée à des sous-tâches, c’est comment les identifier, ce qui peut se faire, par exemple, en essayant de résoudre le problème à rebours. Supposons qu’on ne peut atteindre un certain point rouge qu’avec une certaine boîte poussée d’une seule direction. Pour ce faire, le robot doit se mettre dans la case derrière pour pousser la boîte. Une sous-tâche peut consister à mettre la boîte et le robot dans les bonnes cases.

Ce qui suit est une autre manière typique de déterminer des sous-tâches. Il est raisonnable de supposer que tout l’espace intérieur dans une position est nécessaire pour la solution. Ceci veut dire que si la position initiale a plein de gros espaces vides, comme la zone 2×3 vide dans l’exemple ci-dessus, on doit déterminer à quoi sert cet espace. Peut-être est-il est nécessaire pour permettre au robot de contourner une boîte ou pour poser une boîte le temps de libérer de la place ailleurs. Dans ce deuxième cas on se demande ensuite quelle boîte? Et comment mettre la boîte dans cet espace?

3) Formuler des Restrictions sur le Chemin de Solution

Dès la position initiale, sans essayer de coups, on peut identifier plein de restrictions sur la solution. Voici quelques exemples :

3.1) Il existe un couloir qu’une boîte ne peut pas traverser mais dans lequel elle peut pourtant entrer, alors l’espace au bout du couloir sera bloqué.

3.2) On ne peut atteindre un certain point rouge que par un côté même s’il y a de l’espace sur d’autres côtés.

3.3) On ne peut pas déplacer une certain boîte dans une certaine direction et donc on ne peut la placer que sur un seul point rouge.

3.4) Puisque certains point rouges ne sont accessibles que par certains côtés, l’ordre dans lequel les points seront occupés est déjà déterminé.

3.5) Il est évident dès le départ quel point il faudra couvrir en dernier car l’espace doit d’abord servir à déplacer d’autres boîtes.

4) D’autres Heuristiques

4.1) Il faut essayer toute séquence de poussées réversible, même si le robot doit effectuer beaucoup de déplacements pour défaire ces poussées. Cet exercice a l’air inutile mais la nouvelle position résultante peut révéler la façon de procéder.

4.2) S’il y a une ligne droite séparant tous les points d’au moins une boîte, alors cette boîte doit traverser cette ligne. Si ceci est impossible alors la position est morte. S’il n’existe qu’une seule façon pour faire traverser la boîte alors on identifie ainsi une forte restriction sur le chemin de solution.

Exemple d’une Solution Complète (Jeu 8)

On assigne des coordonnées pour pouvoir décrire les cases. Par exemple, le robot commence dans la case G1.

Au début le robot n’a que 2 options : a) entrer dans le trou G3, ou b) entrer dans le trou E3. Entrer dans le trou G3 ne lui permettra que de pousser la boîte dans B3 dans B1 → position morte. Alors le robot entrer dans le trou E3 et se met sur B2 :

Les seules poussées possibles sont a) la boîte B3 à B4 (pas B5, ce sera la mort) ou la boîte C2 à la droite.

On se rend compte qu’on ne pourra pas pousser les boîtes sur un chemin qui passe par G3 car il sera impossible de les pousser à gauche après. (voir 1.2)

Cependant, pour les déplacer à travers le trou B3,C3 il faut y faire de la place, donc il va falloir mettre une ou deux boîtes sur la droite pour revenir les chercher après.

On se rend compte que la boîte B3 ne peut se déplacer que sur la ligne B alors elle finira certainement sur le point B4.

Pour pouvoir mettre des boîtes sur C4 et les pousser à droite, le robot doit pouvoir se mettre sur A4, mais pour y accéder de dessous, il faut poser la boîte B3 sur B2 et les cases B3, C3, C2 doivent être vides, alors il faut dégager deux boîtes et les mettre en bas à droite.

o

Mais on ne peut pas pousser les boîtes A3 et B3 en bas. La seule option restante dans la position (2) est de pousser d’abord la boîte de B3 à B4 et ensuite d’effectuer les coups pour atteindre la position (3). On obtient

Maintenant on peut avancer en poussant la boîte C3 à C2 et puis en déplaçant le robot pour pousser la boîte F2 à G2 et ensuite à G3 :

Comme mentionné ci-dessus, il faut libérer les cases B3, C3, C2 pour pousser la boîte B4 à B2 donc il faut poser la boîte C2 temporairement sur G2. On obtient :

Ensuite on peut poursuivre notre programme est pousser la boîte G2 à C4 pour ensuite la pousser à droite :

Attendez : on doit pousser la boîte C4 à droite, mais de combien de cases? Il faut toujours pousser la boîte G3 le long du même chemin nécessaire pour que le robot atteigne G4. Pour ce faire il faut pousser la boîte C4 à F4, déplacer le robot à G4, et pousser la boîte G4 à G3 :

Pour pousser la boîte G2 à gauche le robot doit refaire tout le chemin dans le sens antihoraire jusqu’à H2.

Il ne reste que des coups simples : pousser la boîte G2 à C2, C4, D4.

Ensuite on pousse la boîte B2 à B4 et le robot se met sur G4 pour pousser la boîte F4 sur le point E4.

TERMINÉ.