Un rompecabezas de Sokoban en proceso de resolución
Sokoban (倉庫番, Sōko-ban , lit. ' guardián del almacén ' [1] ) es un videojuego de rompecabezas en el que el jugador empuja cajas por un almacén , intentando llevarlas a lugares de almacenamiento. El juego fue diseñado en 1981 por Hiroyuki Imabayashi y publicado por primera vez en diciembre de 1982.
Jugabilidad
El almacén se representa como una cuadrícula de cuadrados , cada uno de los cuales representa una sección de piso o una sección de pared. Algunos cuadrados de piso contienen cajas y otros están marcados como lugares de almacenamiento. El jugador, a menudo representado como un personaje trabajador, puede moverse un cuadrado a la vez horizontal o verticalmente sobre cuadrados de piso vacíos, pero no puede atravesar paredes o cajas.
Para mover una caja, el jugador se acerca a ella y la empuja hacia un cuadrado vacío que se encuentra justo detrás de la caja. Las cajas no se pueden empujar hacia cuadrados con paredes u otras cajas, y no se pueden jalar. La cantidad de cajas coincide con la cantidad de ubicaciones de almacenamiento. El rompecabezas se resuelve cuando todas las cajas ocupan las ubicaciones de almacenamiento.
Desafíos y estrategia
Para avanzar en el juego es necesario planificar cuidadosamente y realizar maniobras precisas. Un solo error, como empujar una caja hacia una esquina u obstruir el camino de otros, puede hacer que el rompecabezas sea irresoluble y obligue al jugador a retroceder o reiniciar. Anticipar las consecuencias de cada empujón y considerar el diseño general del rompecabezas es crucial para evitar puntos muertos y completar el rompecabezas con éxito. [2]
Desarrollo
Sokoban fue creado en 1981 por Hiroyuki Imabayashi. [3] [4] El primer juego comercial fue publicado en diciembre de 1982 por su compañía, Thinking Rabbit , con sede en Takarazuka , Japón . Sokoban fue un éxito en Japón, vendiendo más de 400.000 copias antes de ser lanzado en los Estados Unidos. [5] En 1988, Spectrum HoloByte publicó Sokoban en los EE. UU. para IBM PC , Commodore 64 y Apple II como Soko-Ban . [6] En 2001, la empresa de software japonesa Falcon adquirió las marcas comerciales de Sokoban y Thinking Rabbit. Desde entonces, Falcon ha seguido desarrollando y licenciando juegos oficiales de Sokoban.
Sokoban se ha estudiado utilizando la teoría de la complejidad computacional . Se demostró por primera vez que el problema computacional de resolver los rompecabezas de Sokoban era NP-hard . [9] [10] Trabajos posteriores demostraron que también es PSPACE-completo . [11] [12]
Resolver rompecabezas Sokoban no triviales es difícil para las computadoras debido al alto factor de ramificación (muchos empujes legales en cada turno) y la gran profundidad de búsqueda (muchos empujes necesarios para llegar a una solución). [13] [14] Incluso los rompecabezas pequeños pueden requerir soluciones largas. [15]
El juego Sokoban proporciona un banco de pruebas desafiante para desarrollar y evaluar técnicas de planificación . [16] El primer solucionador automático documentado fue Rolling Stone , [17] desarrollado en la Universidad de Alberta . Sus principios básicos sentaron las bases para muchos solucionadores más nuevos. Empleaba un algoritmo de búsqueda convencional mejorado con conocimiento específico del dominio. [18] Festival , utilizando su algoritmo FESS, fue el primer solucionador automático en completar los 90 acertijos en el conjunto de pruebas XSokoban ampliamente utilizado. [19] [20] Sin embargo, incluso los mejores solucionadores automáticos no pueden resolver muchos de los acertijos más desafiantes que los humanos pueden resolver con tiempo y esfuerzo. [21] [22]
Variantes
Varios rompecabezas pueden considerarse variantes del juego Sokoban original en el sentido de que todos hacen uso de un personaje controlable que empuja cajas en un laberinto .
Mosaicos alternativos : en el juego estándar, los laberintos se disponen en una cuadrícula cuadrada . Existen varias variantes que aplican las reglas de Sokoban a laberintos dispuestos en otros mosaicos. Hexoban utiliza hexágonos regulares y Trioban utiliza triángulos equiláteros .
Varios empujadores : en la variante Multiban , el rompecabezas contiene más de un empujador. En el juego Sokoboxes Duo , estrictamente dos empujadores colaboran para resolver el rompecabezas.
Ubicaciones de almacenamiento designadas : en Sokomind Plus , algunas cajas y cuadrados objetivo tienen un número único. En Block-o-Mania , las cajas tienen diferentes colores y el objetivo es empujarlas hacia cuadrados con colores iguales.
Objetivos alternativos del juego : Varias variantes presentan objetivos diferentes a los del juego tradicional de Sokoban. Por ejemplo, en Interlock y Sokolor , las cajas tienen colores diferentes, pero el objetivo es moverlas de manera que las cajas de colores similares estén adyacentes. En CyberBox , cada nivel tiene una casilla de salida designada y el objetivo es llegar a esa salida empujando cajas, potencialmente más de una simultáneamente. En una variante llamada Beanstalk , el objetivo es empujar los elementos del nivel hacia una casilla objetivo en una secuencia fija.
Elementos adicionales del juego : Push Crate , Sokonex , Xsok , Cyberbox y Block-o-Mania añaden nuevos elementos al rompecabezas básico. Algunos ejemplos son los agujeros, los teletransportadores, los bloques móviles y los pasajes de un solo sentido.
Acciones del personaje : En Pukoban , el personaje puede tirar cajas además de empujarlas.
Modo inverso : en esta variante, el jugador resuelve el rompecabezas estándar al revés, comenzando con todas las casillas en las casillas objetivo. Luego, el jugador tira de las casillas para alcanzar la posición inicial. Las soluciones obtenidas en el modo inverso se pueden aplicar directamente para resolver el rompecabezas estándar invirtiendo el orden de los movimientos. Esto hace que el modo inverso sea una herramienta útil para los jugadores, ya que les permite desarrollar estrategias para resolver rompecabezas en el juego estándar. [23]
Comunicados oficiales seleccionados
En esta tabla se enumeran algunos lanzamientos oficiales destacados de Sokoban que marcan hitos, como la expansión a nuevas plataformas o la consecución de una gran popularidad. Están organizados por fecha de lanzamiento.
^ Yoshio Murase; Hitoshi Matsubara; Yuzuru Hiraga (1996). Norman Foo; Randy Goebel (eds.). Elaboración automática de problemas de Sokoban. Medios de ciencia y negocios de Springer. pag. 592.ISBN 978-3-540-61532-3.
^ Jean-Noël Demaret; François Van Lishout; Pascal Gribomont (2008). Planificación jerárquica y aprendizaje para la resolución automática de problemas de Sokoban (PDF) . págs.1, 2.
^ "Thinking Rabbit - Entrevista al desarrollador de 1983".
^ "Mi conversación con el señor Hiroyuki Imabayashi".
^ Lafe Low (noviembre de 1988). "News Line; Made in Japan". inCider . pág. 14.
^ Austin Barr; Calvin Chung; Aaron Williams (2021). Los rompecabezas Block Dude son NP-Hard (y las alfombras realmente unen las reducciones) (PDF) . CCCG (2021). pág. 1.
^ "Reseño el juego integrado en mi nuevo CRT (Boxman)". YouTube . 22 de noviembre de 2020.
^ "Manual del usuario de CHDK 1.5". Wiki de CHDK . Consultado el 13 de julio de 2023 .
^ Michael freidoras; Michael Greene (1995). "Sokoban" (PDF) . Eureka (54): 25-32.
^ Dorit Dor ; Uri Zwick (1999). "SOKOBAN y otros problemas de planificación del movimiento". Geometría computacional . 13 (4): 215–228. doi : 10.1016/S0925-7721(99)00017-6 .
^ Joseph C. Culberson (1997). "Sokoban es PSPACE-completo" (PDF) . Informe técnico TR 97-02, Departamento de Ciencias Informáticas, Universidad de Alberta .
^ Robert Aubrey Hearn (2006). Juegos, rompecabezas y computación (PDF) (tesis doctoral). Instituto Tecnológico de Massachusetts. pp. 98–100.
^ Andreas Junghanns; Jonathan Schaeffer (2001). "Sokoban: Mejorando la búsqueda con cortes de relevancia" (PDF) . Ciencias Informáticas Teóricas . 252 (1–2): 5. doi : 10.1016/S0304-3975(00)00080-3 .
^ David Holland; Yaron Shoham. "Análisis teórico sobre Picokosmos 17". Archivado desde el original el 7 de junio de 2016.
^ Timo Virkkala (2011). Resolver Sokoban (PDF) (tesis de maestría). Universidad de Helsinki. pag. 1.
^ Andreas Junghanns (1999). Ampliando los límites: nuevos desarrollos en búsquedas de un solo agente (tesis doctoral). Universidad de Alberta. doi : 10.7939/R3W95103S .
^ Andreas Junghanns; Jonathan Schaeffer (2001). "Sokoban: Mejora de los métodos generales de búsqueda de un solo agente utilizando el conocimiento del dominio". Inteligencia artificial . 129 (1–2): 219–251. doi : 10.1016/S0004-3702(01)00109-6 .
^ Yaron Shoham; Jonathan Shaeffer (2020). El algoritmo FESS: un enfoque basado en características para la búsqueda de un solo agente (PDF) . Conferencia IEEE sobre juegos de 2020 (CoG). Osaka, Japón: IEEE. doi :10.1109/CoG47356.2020.9231929.
^ Yaron Shoham (2020). "Presentación de FESS en la conferencia CoG (17,5 minutos)" (video) . archive.org .
^ "Estadísticas de Let's Logic Bots" (PDF) . Consultado el 6 de octubre de 2024 .
^ "Estadísticas del solucionador Sokoban: conjunto de pruebas de gran tamaño" . Consultado el 14 de abril de 2024 .
^ Frank Takes (2008). "Sokoban: resolución inversa" (PDF) .
^ "今回はこのゲームを開発した CONEJO PENSANTE さんにお願いして, 市販品とは別に10の倉庫をつくってもらいましたので" [Esta vez, le pedimos a THINKING RABBIT, quien desarrolló este juego, que construyera 10 almacenes por separado de los productos comerciales]. PC マ ガ ジ ン(en japonés). Agosto de 1983. págs. 52–56.
^ "題して『倉庫番』PCマガジン番外編 (このプログラムは, PC-8801/9801 で使えます)" [Titulado "Sokoban" PC Magazine Extra Edition (este programa se puede utilizar con PC-8801/9801)] . PC マ ガ ジ ン(en japonés). Agosto de 1983. págs. 52–56.
