Sokoban

A Sokoban rompecabezas siendo resuelto.

Sokoban ( 倉庫番, Sōko-ban, lit. 'encargado del almacén') es un videojuego de rompecabezas en el que el jugador empuja cajas en un almacén, tratando de llevarlas a los lugares de almacenamiento. El juego fue diseñado en 1981 por Hiroyuki Imabayashi y publicado por primera vez en diciembre de 1982.

Jugabilidad

El juego se desarrolla en un tablero de cuadrados, donde cada cuadrado es un suelo o una pared. Algunos cuadrados de piso contienen cajas y algunos cuadrados de piso están marcados como ubicaciones de almacenamiento.

El jugador está confinado al tablero y puede moverse horizontal o verticalmente hacia 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 que está más allá. Las cajas no se pueden tirar y no se pueden empujar hacia casillas 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 los lugares de almacenamiento.

Lanzamientos oficiales seleccionados

Desarrollo

Sokoban fue creado en 1981 por Hiroyuki Imabayashi. El primer juego comercial fue publicado en diciembre de 1982 por Thinking Rabbit, una casa 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, Unix, Commodore Amiga y Apple II como Soko-Ban. Sokoban fue un éxito en Japón, donde había vendido más de 400 000 copias 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 videoconsolas, teléfonos móviles, calculadoras gráficas, cámaras digitales y agendas electrónicas.

Investigación científica

Sokoban se puede estudiar utilizando la teoría de la complejidad computacional. El problema de resolver acertijos Sokoban primero demostró ser NP-difícil. El trabajo posterior mostró que era significativamente más difícil que los problemas 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 exponencialmente creciente de movimientos y empujones. Los jugadores humanos expertos se basan principalmente en la heurística y, por lo general, pueden descartar rápidamente muchas líneas de juego inútiles o redundantes al reconocer patrones y subobjetivos, lo que reduce drásticamente el esfuerzo 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 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 de los mejores solucionadores automáticos.

Variantes

Varios rompecabezas pueden considerarse variantes del juego Sokoban original en el sentido de que todos utilizan un personaje controlable que empuja cajas en un laberinto.

• Tilings alternativos: En el juego estándar, los laberintos se establecen en una cuadrícula cuadrada. Varias variantes aplican las reglas de Sokoban a los laberintos establecidos en otros azulejos. Hexoban usa hexágonos regulares, y Trioban usa triángulos equiláteros.
• Múltiples impulsores: En las variantes Multiban y Interlock, el jugador puede controlar múltiples caracteres.
• 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 empujarlos a cuadrados con colores iguales. Sokomind Plus implementa una idea similar, con cajas y plazas de destino numeradas únicamente. In 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. In CyberBox, cada nivel tiene un cuadrado de salida designado, y el objetivo es alcanzar esa salida. En una variante llamada Beanstalk, los elementos del nivel deben ser empujados a un cuadrado objetivo en una secuencia fija.
• Elementos adicionales del juego: Empuje Crate, Sokonex, Xsok, Cyberbox y Block-o-Mania todos añaden nuevos elementos al rompecabezas básico. Ejemplos incluyen agujeros, telepuertos, bloques móviles y pasajes de un solo sentido.
• Medidas de carácter: En Pukoban, el personaje puede tirar cajas además de empujarlos.
• Modo inverso: El jugador resuelve el rompecabezas hacia atrás, desde el final hasta la posición inicial tirando en lugar de empujar cajas. Estándar Sokoban los rompecabezas se pueden jugar en modo inverso, y las soluciones de movimiento inverso se pueden convertir en soluciones para los rompecabezas de movimiento estándar. Por lo tanto, el juego de movimiento inverso también puede ser instrumental en la solución de estándar Sokoban rompecabezas.