Ensayo

1.1 Introducción
Sokoban es un juego rompecabezas de transporte en la cual el jugador empuja cajas a través de un laberinto, visto desde arriba, y trata de acomodarlas en lugares designados. Solo una caja puede ser empujada a la vez, y las cajas no pueden ser jaladas.
Sokoban fue creado en 1980 por Hiroyuki Imabayashi, y fue publicado en 1982 por Thinking Rabbit, una compañía que producesoftware en Takarazuka, Japón. Sokoban es una palabra con raíz japonesa que significa encargado del almacén ó almacenista.

El juego empezó a cobrar fama cuando en 1980 Hiroyuki Imabayashi ganó una competencia con su juego contra un ordenador.
Sokoban es de gran relevancia dentro del la investigación científica debido a que puede ser estudiado usando teoría de la complejidad computacional. Elproblema del almacenista se encuentra dentro de la clase de problemas NP-Hard (NP-Duros, la clase de problemas más complejos en las ciencias de la computación) y su resolución es también PSPACE-complete. Su interés aumenta desde el punto de vista de la inteligencia artificial dado que Sokoban puede ser comparado con un robot el cual mueve cajas en un laberinto.
La complejidad de Sokoban no es solo porsu factor de ramaje (el número de posibilidades que se presentan en una situación determinada) si no también debido al profundidad del árbol de búsqueda (que es comparable con el ajedrez, pero mucho menor que la existente para Go). Mientras que muchas de las partidas de ajedrez terminan en menos de 100 movimientos (sumando ambos jugadores) algunos niveles de Sokoban requieren hasta 1000 empujes.Al momento de tratar de resolver un nivel de Sokoban un humano se fía de sus heurísticas, descartando rápidamente líneas donde hay posiciones muertas además que pueden definir metas secundarias y patrones, lo cual es un corte drástico en el árbol de búsqueda. Sin embargo automatizar éstas técnicas no es nada fácil. Es aquí donde surgen las preguntas como ¿Qué técnica de búsqueda usar? ¿Cuál es laheurística de búsqueda? ¿Cómo se define una posición? e incluso ¿Qué estructuras de datos usar?
La solución que nosotros describimos a continuación es una gran respuesta para todas estas preguntas, pero no debe de considerarse como absoluta, es simplemente un enfoque que resulta de nuestra investigación.
Para tener un punto de referencia nuestra solución necesita ser comparada con otrasanteriores, y así determinar su efectividad y en lo posible recomendar una línea de trabajo futuro. Por tal motivo es que agregamos una descripción del estado de la investigación sobre solucionadores automáticos de Sokoban.
1.2 Antecedentes y estado de la investigación
Un solucionador de Sokoban es un programa que intenta resolver niveles de Sokoban. En Internet pueden encontrarse muchos programasdisponibles que son capaces de resolver ciertos niveles de Sokoban.
Algunos de los tipos más comunes son:
Solucionadores que solo tratan de obtener una solución.
Solucionadores que tratan de obtener una buena solución.
Solucionadores que tratan de obtener soluciones óptimas.
El tipo es determinado por la función heurística que el solucionador utiliza (Ver Capítulo 4) que hablando resumidamente esel conocimiento con el cual el solucionador decide por que camino buscar la solución.
Cualquier tipo de solucionador usa como enfoque de búsqueda alguno de los siguientes:
Enfoque con búsquedas informadas
Enfoque con agente individual de búsqueda
El primer enfoque es el descrito en nuestra solución y uno de los más conocidos. El segundo (que no trataremos muy a fondo) consiste en implementaruna técnica de búsquedas informadas en conjunto con una técnica de búsqueda no informada conocida como búsqueda primero profundidad con inmersión iterativa. Uno de los algoritmos más conocidos es el usado por el solucionador de Sokoban desarrollado en la Universidad de Alberta Canadá descrito en Junghanns et al(1997). Este algoritmo trabaja haciendo una búsqueda en la cual se implementa una...