Discussion:Sokoban
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Jeu vidéo.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Faible |  | Jeu vidéo (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Image niveau 1 modifier
Bonjour, j'ai fait cette image pour remplacer la portion de text, puis-je la placer sur l'article ?
~ þayo ♫♪♫♪ 20 octobre 2005 à 23:26 (CEST)
Bonjour. Veuillez plutôt ajouter votre image, au lieu de remplacer le texte. Le texte est en effet indispensable pour montrer le format ".XSB". PS : une image du premier niveau existe déjà, mais la volonté de marquer différents thèmes est indispensable. guffman 27 octobre 2005 à 04:12 (CEST)
- Ma question été en fait entèrieur aux placement de ces images. Maintenant qu'il y en a, je n'en vois plus vraiment d'utilité de la placer. Pour la carte en text, il serai alors bien de la commenter, c'est bien de dire que c'est un format normalisé en page de discussion, c'est mieux de l'écrire dans l'article non ? ~ þayo ♫♪♫♪ 27 octobre 2005 à 13:40 (CEST)
Classe de complexité modifier
Bonjour, il est dit dans la partie Travaux scientifiques d'une part que la résolution des niveaux de sokoban est un problème NP-complet, et un peu plus loin qu'il est P-complet. Etant donné qu'on n'a pas encore démontré P=NP, au moins l'une des deux affirmations doit être pour le moment infondée. Je vais étudier les liens donnés pour voir ce qui est dit précisément, mais en attendant, je mets un désaccord de pertinance sur la partie concernée. Jamian 18 decembre 2005, 14:53 CET
Trouvé ! Il fallait lire PSPACE à la place de P, ce qui n'est pas la même chose :)Jamian 18 decembre 2005, 15:00 CET
Ah ben en fait, j'avais introduit une autre erreur. A la place de NP-complet, il fallait aussi lire NP-difficile (la résolution du sokoban n'est pas NP) Jamian 22 decembre 2005, 11:47 CET
"la résolution du sokoban n'est pas NP" Ça personnes ne le sait pour l'instant... (NP=PSpace est un problème ouvert.) --Pparent (d) 9 avril 2012 à 20:36 (CEST)
Facteur de branchement modifier
Dans la partie "Etude du jeu" de l'article, il est dit: "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."
Si l'on compte comme coup (pour l'étude de l'arbre de recherche) les déplacements aussi bien que les poussées, alors la moyenne du facteur de branchement est très proche de 4 car le pousseur peut, à chaque coup, se déplacer dans (au maximum) 4 directions.
Aux échecs, le facteur de branchement est généralement (relativement) bien plus grand. Ainsi, dans la position de départ, il est déjà égal à 20 et, lorsque l'échiquier est plus clairsemé, les possibilités de déplacement des pièces à longue portée peuvent l'augmenter (mais il peut aussi diminuer, voire passer à 0, dans le cas du pat ou du mat).
Je ne connais pas du tout le go, mais j'imagine que poser une pierre sur un goban 19x19 conduit plus ou moins à un branching factor d'environ 361, qui est donc très supérieur à celui du jeu d'échecs et donc, a fortiori, à celui du sokoban.
Du point de vue de la théorie des jeux, un facteur de branchement de l'ordre de 20 est généralement considéré comme "très supérieur" à 4 (et très inférieur à 361).
En conséquence, est-il rigoureux de dire que le facteur de branchement du sokoban est "comparable" à celui du jeu d'échecs?
La profondeur de l'arbre de recherche aux échecs est généralement bien inférieure à celle du sokoban (au moins pour les niveaux "difficiles").
En tant que joueur de sokoban, créateur de tableaux et concepteur d'un programme qui génère automatiquement des tableaux de sokoban, il me semble que le difficulté de résolution provient d'abord de la profondeur de l'arbre avant de provenir du facteur de branchement.
Peut-être faudrait-il des sources plus précises?
Jack-cnv (d) 21 juin 2010 à 15:51 (CEST)
- Bonjour,
- Etant le créateur de Sokolution, le solveur le plus efficace connu à ce jour pour résoudre des problèmes de Sokoban, je peux vous confirmer que le facteur de branchement est tout autant un problème que la profondeur de l'arbre de recherche. En effet, vous avez raison le facteur de branchement est proche de 4 si on ne compte que les déplacements du joueur à chaque étape (et non les poussées). La plupart des solveurs de nos jours ne prennent pas en compte le déplacement du joueur et cherchent des solutions en termes de nombre de poussées (et quand elles sont optimales, on obtient le nombre de poussées minimal).
- Quand on décrit une transition d'un état à un autre en termes de poussée, le facteur de branchement peut devenir conséquent pour les niveaux difficiles et peut être proche de 100. Certaines thèses le montre rapidement comme ici :
- Advances in Artificial Intelligence
- Je ne sais pas si ce fil de discussion est toujours actif mais je voulais ajouter ma pierre à l'édifice sur ce sujet que j'ai étudié pendant 5 ans :)
- --Sokolution (discuter) 4 mars 2019 à 23:08 (CET)