Sokoban

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Sokoban

Éditeur
Développeur
Concepteur	Hiroyuki Imabayashi
Début du projet	{{{début du projet}}}
Date de sortie	1980
Licence	{{{licence}}}
Version	{{{version}}}
Genre	puzzle
Mode de jeu	Un joueur
Plate-forme
Média
Langue	{{{langue}}}
Contrôles
Évaluation	{{{évaluation}}}
Moteur de jeu	{{{moteur de jeu}}}

Sokoban est un jeu vidéo de puzzle inventé au Japon. Ce nom que l'on écrit 倉庫番 en japonais, ou sokôban transcrit avec la méthode Kunrei, désigne un garde d'entrepôt.

Sommaire

1 Règles du jeu
2 Historique
3 Exemple (le niveau 1 de Sokoban)
4 Travaux scientifiques sur le jeu de Sokoban
5 Liens externes
6 Notes

[modifier] Règles du jeu

KSokoban, une implémentation du jeu de Sokoban pour GNU/Linux

Gardien d'entrepot (divisé en cases carrées), le joueur doit ranger des caisses sur des cases cibles. Il peut se déplacer dans les quatre directions, et pousser (mais pas tirer) une seule caisse à la fois. Une fois toutes les caisses rangées (c'est parfois un vrai casse-tête), le niveau est réussi et le joueur passe au niveau suivant, plus difficile en général. L'idéal est de réussir avec le moins de coups possibles (déplacements et poussées).

[modifier] Historique

Le jeu original a été écrit par Hiroyuki Imabayashi et comportait 50 niveaux. Il remporte 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 aujourd'hui les droits sur le jeu depuis 1982.

Aujourd'hui, il existe des tas de versions dérivées de ce jeu, comme par exemple Boxworld, une variante fonctionnannt sous Windows et incluant 100 niveaux. Comme les règles sont simples, le jeu est facile à programmer, même le Javascript suffit, il est ainsi possible de jouer en ligne avec un navigateur Web. On peut noter qu'il existe des logiciels proposant un affichage 3D (le principe du jeu reste en 2D, comme certains jeux d'échecs 3D).

[modifier] Exemple (le niveau 1 de Sokoban)

Ce texte est un niveau (le premier, de la première version), qui montre le format ".XSB", le format standard des niveaux Sokoban, et sa légende.


    #####                 # -> mur
    #   #                 $ -> caisse
    #$  #                 . -> destination
  ###  $##                * -> caisse sur une zone de rangement (pas dans ce niveau)
  #  $ $ #                @ -> personnage     
### # ## #   ######       + -> personnage sur une zone de rangement (pas dans ce niveau)
#   # ## #####  ..#
# $  $          ..#
##### ### #@##  ..#
    #     #########
    #######

[modifier] Travaux scientifiques sur le jeu de Sokoban

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^[1], 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 de Sokoban est également intéressant pour les chercheurs en intelligence artificielle, parce que la résolution de niveaux de Sokoban 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é que le Sokoban est PSPACE-complet^[2].

La difficulté du jeu de Sokoban provient de son facteur de branchement (qui est 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 1000 "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^[3]. C'est la méthode utilisée par Rolling Stone, un solveur de Sokoban développé par le groupe GAMES de l'Université d'Alberta, au Canada^[4]. Cependant, certains niveaux de Sokoban parmi les plus complexes semblent toujours hors de portée même des meilleurs solveurs automatiques.

[modifier] Liens externes

(en) La catégorie Sokoban (gratuiciels) de l'annuaire dmoz.
(jp) Sokoban (Site officiel japonais)
(fr)(de)(en) Sokoban project - informations
Sokoban Online - informations
SokoJS, jeu en ligne en Javascript sous licence GPL.
Krobizokoban, Un autre jeu de Sokoban en ligne écrit en PHP et Javascript dans le contexte du site krobiz.com.
Squirrel Sokoban, jeu en ligne
Sokoban, jeu en ligne avec éditeur de niveaux.
Pousse Caisse, solver de sokoban sous licence GPL.
(en) SokobanYASC (OpenSource) Jeu Libre Windows avec générateur automatique de niveaux : YASGen)
Sokoban pour Windows Version gratuite, en français, pour Windows 95, 98, Me, NT, 2000, XP, avec plus de 450 niveaux de difficultés variées, et de nombreuses solutions.
Sokostation Gratuiciels. La version 3, pour Windows, est en 3D.
(en) Yahoo! Sokoban Group (forum sur Yahoo!)
Triogical - Gratuiciel de type Sokoban amélioré (Sokoban-like)