Sokoban - Sokoban

Se está resolviendo un rompecabezas de Sokoban .

Sokoban (倉庫 番, Sōko-ban ) es ungénero de videojuegos de rompecabezas en el que el jugador empuja cajas o cajas en un almacén , tratando de llevarlas a lugares de almacenamiento.

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 el cuadrado 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

Desarrollo

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 .

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.

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 . El trabajo posterior mostró que era significativamente más difícil que los problemas de NP ; es PSPACE-completo . 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 . Los jugadores humanos expertos se basan principalmente en la heurística y, por lo general, pueden descartar rápidamente una gran cantidad de líneas de juego inútiles o redundantes al reconocer patrones y subobjetivos, lo que reduce 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. Este es el método utilizado por Rolling Stone , un solucionador de Sokoban desarrollado por el Grupo GAMES de la Universidad de Alberta . Festival fue el primer solucionador automático en resolver los 90 niveles en el conjunto de pruebas de referencia estándar. Sin embargo, los niveles más complejos de Sokoban están fuera del alcance incluso para los mejores solucionadores automatizados.

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 .

• Azulejos alternativos : en el juego estándar, los laberintos se colocan en una cuadrícula cuadrada . 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 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. 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 .
• 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

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 .

Referencias