Sokoban (倉庫 番, Sōko-ban ) es ungénero de videojuego de rompecabezas en el que el jugador empuja cajas o cajas en un almacén , tratando de llevarlas a lugares de almacenamiento.
Sokoban fue creado en 1981 por Hiroyuki Imabayashi. El primer juego comercial fue publicado en diciembre de 1982 por Thinking Rabbit , una empresa de software con sede en Takarazuka , Japón .
Como se Juega
El juego se juega en un tablero de cuadrados , donde cada cuadrado es un piso o una pared. Algunos cuadrados del piso contienen cajas y algunos cuadrados del piso están marcados como ubicaciones de almacenamiento.
El jugador está confinado al tablero y puede moverse horizontal o verticalmente sobre casillas vacías (nunca a través de paredes o cajas). El jugador puede mover una caja caminando hacia ella y empujándola hacia la casilla más allá. Las cajas no se pueden tirar y no se pueden empujar a cuadrados con paredes u otras cajas. El número de cajas es igual al número de ubicaciones de almacenamiento. El rompecabezas se resuelve cuando todas las cajas se colocan en lugares de almacenamiento.
Lanzamientos seleccionados
Año | Título | País | Plataforma | Editor | Medios de comunicación |
---|---|---|---|---|---|
mil novecientos ochenta y dos | Sokoban (倉庫 番) | Japón | NEC PC-8801 | Pensando en conejo | Cinta |
1983 | Sokoban [Edición extra] (倉庫 番 [番外 編] [1] [2] ) | Japón | NEC PC-8801 | PC マ ガ ジ ン | Código fuente |
1984 | Sokoban 2 (倉庫 番 2 ) | Japón | NEC PC-8801 | Pensando en conejo | Cinta |
1988 | Soko-Ban | nosotros | IBM-PC y compatibles | Espectro HoloByte | Flexible |
1989 | Soko-ban perfecto (倉庫 番 perfecto ) | Japón | NEC PC-9801 | Pensando en conejo | Flexible |
1990 | Boxyboy | Japón, EE. UU. | Turbografx-16 y motor de PC | Comité ejecutivo nacional | HuCard |
1991 | Venganza Soko-ban (倉庫 番 Venganza ) | Japón | NEC PC-9801 | Pensando en conejo | Flexible |
2016 | Toque Sokoban (番 番 Toque ) | Japón, EE. UU. | Android y Apple iOS | Pensando en conejo | Distribución digital |
Desarrollo
En 1988, Sokoban fue publicado en EE. UU. Por Spectrum HoloByte para las series Commodore 64 , IBM-PC y Apple II como Soko-Ban . Sokoban fue un éxito en Japón y había vendido más de 400.000 unidades en ese país cuando Spectrum HoloByte lo importó a los Estados Unidos. [3]
Implementaciones
Se han escrito implementaciones de Sokoban para numerosas plataformas informáticas , incluidos casi todos los sistemas informáticos domésticos y personales . También existen diferentes versiones para consolas de videojuegos , teléfonos móviles , calculadoras gráficas , cámaras digitales y organizadores electrónicos .
Investigación científica
Sokoban se puede estudiar utilizando la teoría de la complejidad computacional . Primero se demostró que el problema de resolver los acertijos de Sokoban era NP-difícil . [4] [5] El trabajo posterior mostró que era significativamente más difícil que los problemas de NP ; es PSPACE-completo . [6] Esto es de interés para la investigación de inteligencia artificial (IA) porque la resolución de Sokoban se puede comparar con la planificación automatizada requerida por algunos robots autónomos .
Sokoban es difícil no solo por su gran factor de ramificación , sino también por la gran profundidad de su árbol de búsqueda . Algunos tipos de niveles pueden incluso extenderse indefinidamente, y cada iteración requiere un número de movimientos y empujes que crece exponencialmente . [7] Los jugadores humanos expertos se basan principalmente en la heurística y generalmente son capaces de descartar rápidamente una gran cantidad de líneas de juego inútiles o redundantes al reconocer patrones y subobjetivos, reduciendo así drásticamente la cantidad de búsqueda.
Algunos acertijos de Sokoban se pueden resolver automáticamente mediante el uso de un algoritmo de búsqueda de un solo agente , como IDA * ; mejorado por varias técnicas que hacen uso del conocimiento específico del dominio. [8] Este es el método utilizado por Rolling Stone , [9] un solucionador de Sokoban desarrollado por el Grupo GAMES de la Universidad de Alberta . Festival [10] fue el primer solucionador automático que resolvió los 90 niveles en el conjunto de pruebas estándar de referencia. Sin embargo, los niveles más complejos de Sokoban están fuera del alcance incluso para los mejores solucionadores automatizados. [11]
Variantes
Varios rompecabezas pueden considerarse variantes del juego original de Sokoban 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 colocan en una cuadrícula . Varias variantes aplican las reglas de Sokoban a laberintos dispuestos en otros mosaicos. Hexoban usa hexágonos regulares y Trioban usa triángulos equiláteros .
- Múltiples empujadores : en las variantes Multiban e Interlock , el jugador puede controlar múltiples personajes.
- Objetivos alternativos : Varias variantes ajustan los requisitos para completar un nivel. Por ejemplo, en Block-o-Mania las cajas tienen diferentes colores y el objetivo es colocarlas en cuadrados con colores iguales. Sokomind Plus implementa una idea similar, con recuadros y cuadrados de destino numerados de forma única. En Interlock y Sokolor , las cajas también tienen diferentes colores, pero el objetivo es moverlas para 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. En una variante llamada Beanstalk , los elementos del nivel deben insertarse en un cuadrado 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. Los ejemplos incluyen agujeros, teletransportes, bloques móviles y pasajes de un solo sentido. El juego de 1982 Sokoban ( NEC PC-8801 ) presentaba niveles con paredes destructibles . [12]
- Acciones de los personajes : en Pukoban , el personaje puede tirar de cajas además de empujarlas.
- Modo inverso : el jugador resuelve el rompecabezas al revés, desde el final hasta la posición inicial, tirando de las cajas en lugar de empujarlas. Los acertijos estándar de Sokoban se pueden jugar en modo inverso, y las soluciones de modo inverso se pueden convertir en soluciones para los acertijos del modo estándar. Por lo tanto, el modo de juego inverso también puede ser fundamental para resolver los acertijos estándar de Sokoban .
Ver también
- Rompecabezas de lógica
- Rompecabezas deslizante
- Rompecabezas de transporte
- Planificación de movimiento
Referencias
- ^ "今 回 は こ の ゲ ー ム を 開 発 し た THINKING RABBIT さ ん に お 願 い し て, 市 販 品 と は 別 に 10 の 倉庫 を つ く っ て も ら い ま く っ て も ら い ま le preguntamos a た. almacenes separados 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.
- ^ Low, Lafe (noviembre de 1988). "News Line; Made in Japan". en Sidra (43). 14, 15.
- ^ M. Fryers; MT Greene (1995). "Sokoban". Eureka (54).
- ^ Dor, Dorit; Zwick, Uri (1999). "SOKOBAN y otros problemas de planificación de movimiento" . Geometría computacional . 13 (4): 215-228. doi : 10.1016 / S0925-7721 (99) 00017-6 . ISSN 0925-7721 .
- ^ Joseph C. Culberson, Sokoban es PSPACE-completo ( PS ). Informe técnico TR 97-02, Departamento de Ciencias de la Computación, Universidad de Alberta, 1997.
- ^ David Holland y Yaron Shoham, "Análisis teórico sobre Picokosmos 17" .
- ^ Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: Mejora de los métodos generales de búsqueda de un solo agente mediante el conocimiento del dominio , Inteligencia artificial 129 (1–2): 219–251 (Número especial sobre búsqueda heurística en inteligencia artificial).
- ^ Junghanns, Andreas; Schaeffer, Jonathan (1997). "Sokoban: un desafiante problema de búsqueda de un solo agente" (PDF) . En el taller de IJCAI sobre el uso de juegos como banco de pruebas experimental para la investigación de IA . Universidad de Alberta . págs. 27–36.
- ^ Yaron Shoham, Jonathan Shaeffer (2020) El algoritmo FESS: un enfoque basado en funciones para la búsqueda de un solo agente . Publicado en: 2020 IEEE Conference on Games (CoG)
- ^ "Estadísticas del solucionador - Wiki Sokoban" . Consultado el 8 de febrero de 2013 .
- ^ THE 倉庫 番(en japonés). 1987. p. 113. ISBN 4-88239-606-8.
enlaces externos
- Sitio oficial de Sokoban (en japonés)
- La página de la Universidad de Alberta Sokoban
- Virkkala, Timo (2011). Resolver Sokoban (PDF) ( Trabajo Fin de Máster). Universidad de Helsinki . Consultado el 24 de septiembre de 2014 .