software.wikisort.org - Jeu_vidéo

Sokoban (倉庫番, Sōko-ban^?, litt. « garde d'entrepôt ») est un jeu vidéo de réflexion inventé au Japon.

Règles du jeu

Gardien d'entrepôt (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).

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 qui détient aujourd'hui les droits sur le jeu depuis 1982.

Aujourd'hui, il existe de multiples jeux dérivés de Sokoban, par exemple Boxworld, une variante fonctionnant sous Windows et incluant 100 niveaux. Microsoft proposait ce jeu sous le nom de « Pousse Bloc »[1]. Comme les règles sont simples, le jeu est facile à programmer. Plusieurs versions ont été écrites en JavaScript ; il est ainsi possible de jouer en ligne avec un navigateur web. Il existe des logiciels proposant un affichage 3D (le principe du jeu reste en 2D, comme certains jeux d'échecs 3D).

Certains jeux (par exemple Push Crate) mettent en place de nouveaux éléments de gameplay pour Sokoban tels que des trous, des téléportations, etc.

Formats des fichiers

Si, dans certaines versions du jeu, tous les niveaux jouables sont intégrés dans le jeu, sans permettre l'importation de niveaux, la majeure partie des versions permet de jouer des niveaux autres que ceux qui sont intégrés.

Pour cela, plusieurs formats existent, comme :

• le format .xsb, qui est, de loin, le plus courant ;
• 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.

Exemple (le niveau 1 de Sokoban)

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

    #####
    #   #
    #$  #
  ###  $##
  #  $ $ #
### # ## #   ######
#   # ## #####  ..#
# $  $          ..#
##### ### #@##  ..#
    #     #########
    #######

Légende :

# : mur

$ : caisse

. : destination

* : caisse sur une zone de rangement (pas présente dans ce niveau)

@ : personnage

+ : personnage sur une zone de rangement (pas présent dans ce niveau)

Étude du jeu

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[2], 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 pose des problèmes difficiles, pour lesquels il n'existe pas à ce jour d'algorithmes de résolution rapide. Des travaux ont par exemple montré que la version générale de Sokoban est incluse dans l'espace des problèmes PSPACE-complets[3]^,[4].

La difficulté du Sokoban provient de son facteur de branchement (en) (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[5]. 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[6]. Cependant, certains niveaux parmi les plus complexes semblent toujours hors de portée des meilleurs solveurs automatiques.

Voir aussi

• Kdegames, inclut le KSokoban, version KDE du sokoban

Liens externes

• Push Crate, un Sokoban amélioré gratuit, disponible en français
• (ja) Sokoban (Site officiel japonais)
• (en) Sokoban Wiki, wiki au sujet du jeu Sokoban
• (en) Cosmique Sokoban, un jeu de Sokoban en ligne
• (en) Sokoban, un jeu de Sokoban social et open source (GitHub)

Notes

• Portail du jeu vidéo

На других языках

---

[de] Sokoban

Sokoban (倉庫番 .mw-parser-output .Latn{font-family:"Akzidenz Grotesk","Arial","Avant Garde Gothic","Calibri","Futura","Geneva","Gill Sans","Helvetica","Lucida Grande","Lucida Sans Unicode","Lucida Grande","Stone Sans","Tahoma","Trebuchet","Univers","Verdana"}Sōkoban, japanisch „Lagerhausverwalter“) ist ein Computerspiel, das von Hiroyuki Imabayashi entwickelt und 1982 erstmals für verschiedene Computersysteme veröffentlicht wurde.

---

[en] Sokoban

Sokoban (倉庫番, Sōko-ban, lit. 'warehouse keeper'[1]) is a puzzle video game genre in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982.

---

[es] Sokoban

Sokoban es un clásico rompecabezas inventado en Japón, normalmente implementado como videojuego. El juego original fue creado por Hiroyuki Imabayashi, que en 1980 ganó con su juego una competición contra un ordenador. Hiroyuki Imabayashi es presidente de la empresa Thinking Rabbit Inc. en Japón. Con los años han aparecido muchas versiones del juego para todas las plataformas, y continuamente se crean nuevas colecciones de niveles.

---

- [fr] Sokoban

---

[ru] Sokoban

Sokoban (Soko-Ban, яп. 倉庫番, сокобан — кладовщик) — двухмерная компьютерная игра-головоломка, в которой игроку необходимо расставить ящики по обозначенным местам лабиринта. Кладовщик одновременно может двигать только один ящик, толкая вперёд.

---

---