Encyclopédie Atypique Incomplète
Incomplète, car toujours en construction au gré des jours, avec sérieux, curiosité et humour.
Atypique, car toujours dans l'esprit de la connaissance par l'observation et la pratique.
Incomplète, car toujours en construction au gré des jours, avec sérieux, curiosité et humour.
Atypique, car toujours dans l'esprit de la connaissance par l'observation et la pratique.
mardi 19 janvier 2010
Sokoban est un jeu vidéo de puzzle inventé au Japon.
Ce nom que l’on écrit 倉庫番 en japonais (ou sôkoban transcrit avec la méthode Kunrei), désigne un garde d’entrepôt.
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).
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 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 :
Ce qui correspond au niveau graphique à quelque chose comme :
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 :
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.
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...
Le Sokoban qui vous est proposé...
Jouabilité
Avec les touches du clavier :
Avec la souris :
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 !
Les images de cette interprétation du jeu de Sokoban viennent de Philippe Galmel.