Encyclopédie Atypique Incomplète

Le Sokoban est un jeu de réflexion et de logique, d’origine japonaise, qui se joue sur ordinateur.
Les règles du jeu sont très simples, à la portée d’un enfant, et la difficulté varie d’un niveau à l’autre : il y a des niveaux très faciles, d’autres qui sont moyennement difficiles, et il y en a quelques uns qui sont très ardus. Bref, il y en a pour tous les goûts...

Un avantage du Sokoban, c’est que c’est un jeu dans lequel il n’y a pas du tout de violence, pas d’ennemis à tuer, que vous jouez uniquement avec votre intelligence et vos aptitudes de déduction, et qu’ainsi, il n’y a pas besoin de sauver la planète (ça, de toute façon, c’est le travail de Bruce Willis, pas le vôtre).

 Histoire

Le jeu original a été écrit par Hiroyuki Imabayashi et comportait 50 niveaux, qui lui ont permis de remporter en 1980 un concours de jeu vidéo pour ordinateur.

Plus tard Hiroyuki Imabayashi est devenu président de la compagnie japonaise Thinking Rabbit Inc. qui détient encore aujourd’hui les droits sur le jeu depuis 1982.

Comme les règles sont simples, qu’il n’y a pas d’effets sonores ni de visualisation en trois dimensions, le jeu est assez facile à programmer, et beaucoup de développeurs ont proposé leurs idées.

Comme les quelques 50 niveaux d’origine ont été assez vite résolus, des formats de fichier ont vu le jour pour permettre d’intégrer d’autres puzzles issus de la créativité diabolique de quelques énergumènes.

Il en existe ainsi trois que l’on peut rencontrer :

• le format “.xsb”, qui est, de loin, le plus utilisé.
• le format “.sok”, qui, bien qu’ayant été conçu pour remplacer le format “.xsb”, reste peu courant.
• le format “.stb”, peu courant, lui aussi.

Le texte suivant montre le contenu du fichier, au format .xsb, correspondant au premier niveau de la première version du jeu :

Avec comme légende :

• # : mur
• $ : objet à ranger
• . : destination zone de rangement
• * : objet sur une zone de rangement (pas dans ce niveau)
• @ : personnage (vous !)
• + : personnage sur une zone de rangement (pas dans ce niveau)

Ce qui correspond au niveau graphique à quelque chose comme :

 Règles

Le jeu consiste à ranger des objets à l’intérieur d’un entrepôt, en les poussant pour les amener sur des emplacements marqués au sol.
Pour cela, vous vous déplacez dans l’entrepôt avec les flèches du clavier ou en cliquant avec la souris.

Mais attention :

• on ne peut que pousser les objets.
• on ne peut pas les tirer.
• on ne peut pas passer par dessus.
• on ne peut en pousser qu’un seul à la fois.

Et pour simplifier le tout, l’entrepôt dans lequel il faut ranger ces objets a rarement la forme d’un simple rectangle. En fait, on dirait plutôt un labyrinthe, plus ou moins compliqué. Mais c’est justement ce qui fait l’intérêt de ce jeu...

L’idéal étant de réussir un puzzle avec le moins de coups possibles (déplacements et poussées) pour passer au niveau suivant, plus difficile en général.

 Complexité mathématique

Le jeu de Sokoban peut être étudié du point de vue de la théorie de la complexité. Il a été démontré que la résolution des niveaux de Sokoban est un problème de complexité NP-difficile, en ce sens que le jeu fait partie de la classe plus générale des problèmes de planification de déplacements, où le joueur est autorisé à pousser ou à tirer un ou plusieurs objets à la fois.

Le jeu est également intéressant pour les chercheurs en intelligence artificielle, car la résolution de niveaux peut être comparée à la conception d’un robot qui déplace des caisses dans un entrepôt. D’autres travaux ont par ailleurs montré qu’il est PSPACE-complet.

La difficulté du Sokoban provient de son facteur de branchement (comparable à celui des échecs, bien que très inférieur à celui du jeu de go), mais aussi de la très grande profondeur de son arbre de recherche.
Ainsi, certains niveaux nécessitent plusieurs milliers de déplacements et plus de 1 000 « poussées ». Les joueurs humains expérimentés se basent principalement sur des méthodes heuristiques. Ils sont généralement capables d’éliminer rapidement les tactiques de jeu inutiles ou redondantes, et ils identifient les dispositions du jeu et les sous-buts, ce qui leur permet d’élaguer sensiblement l’étendue des recherches.

Les problèmes de Sokoban peuvent être résolus automatiquement à l’aide d’un algorithme de recherche à agent unique, tel que IDA*, amélioré par plusieurs techniques qui font appel à des connaissances spécifiques de ce domaine. C’est la méthode utilisée par Rolling Stone, un solveur développé par le groupe GAMES de l’Université d’Alberta, au Canada.
Cependant, certains niveaux parmi les plus complexes semblent toujours hors de portée des meilleurs solveurs automatiques...

 Jouer en ligne

Le Sokoban qui vous est proposé...

• comporte quelques 88 puzzles différents à résoudre (les “officiels”),
• vous permet d’accéder à leurs solutions,
• vous donne un retour en arrière (undo) illimité de vos mouvements (cela permet de rattraper une erreur),
• et vous donne la possibilité de sauvegarder votre partie en cours pour revenir la finir plus tard.

Jouabilité

Avec les touches du clavier :

• Backspace/Retour Arrière : annule le dernier mouvement (illimité).
• Entrée/Return : recharge (redémarre à zéro) le puzzle courant.
• Les 4 flèches de direction vous permettent de déplacer votre personnage et de pousser les objets.

Avec la souris :

• Cliquez sur la case que vous souhaitez atteindre, votre personnage trouvera le plus court chemin pour y accéder.
• Cliquez sur un objet pour le pousser.

Bon amusement et bonnes réflexions !

Et si vous trouvez que ces quelques 88 « exercices » sont trop faciles, je vous propose de vous aiguiser les neurones sur “Sokoban II... Le Retour !”, où vous pourrez poursuivre l’investigation de 536 (!) puzzles diaboliques !