MSAMA Sokoban Solver
From Sokoban Wiki
This file is intended to help programmers who want to develop their own Sokoban Solver.
Our work is divided in 7 chapters in which we'll trying to explain how an A* based algorithm can solve Sokoban Levels. It's a perfect lecture for beginners and it's open to any modifications.
The investigation is written in spanish.
We'll appreciate to know any comment you give us about the work.
José Ramón García Alvarado
- Although I do not speak Spanish, I've tried to edit the format for the wiki. --Heiner 03:00, 21 November 2010 (UTC)
CAPÍTULO 1: SOLUCIONADOR DE SOKOBAN
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 produce software 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. El problema 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 por su 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 la heurí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 otras anteriores, 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 programas disponibles 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 es el 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 implementar una 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 búsqueda primero profundidad (Ver 2.1.2) limitada repetidamente, incrementando el límite de profundidad en cada iteración hasta que se llega a d, la profundidad del nodo más al fondo alcanzable.
En la búsqueda primero profundidad con inmersión iterativa el orden en que se visitan los nodos en el árbol de búsqueda (Ver Capítulo 2) es el mismo que en las búsquedas primero profundidad (Ver 2.1.2) pero el orden acumulativo de los primeros nodos visitados es primero amplitud. Esto representa una combinación entre la eficiencia en espacio de la búsqueda primero profundidad y la completitud de la búsqueda primero amplitud.
Los solucionadores de Sokoban generalmente no hablan de sus implementaciones o las técnicas que utilizan, sin embargo, son reconocidos por los problemas de Sokoban que son capaces de resolver.
Existen miles de niveles para resolver de Sokoban. Muchos de ellos están protegidos por derechos de autor y solo pueden ser usados con su consentimiento si deseamos agregarlo en un producto de software. Cada conjunto de problemas creado por un autor es registrado con un nombre para poder identificarlo más fácilmente o si este ésta incluido dentro de un solucionador lleva el mismo nombre. A una colección de problemas se le llama suite de prueba (test suite) y son las medidas que se toman para evaluar el rendimiento de un solucionador.
Collection Author Levels BSearch Tak YASS JSoko Aymeric Aymeric du Peloux 282 282 282 282 282 BoxWorld Various Authors 100 87 98 89 82 Grigr2001 Evgeny Grigoriev 100 93 94 92 91 Grigr2002 Evgeny Grigoriev 40 37 36 38 34 GrigrSpecial Evgeny Grigoriev 40 39 40 40 39 Holland David Holland 81 56 64 58 55 Kenyam Set A Kenya Maruyama 52 48 50 50 45 Microban David W. Skinner 155 155 155 155 155 Microban II David W. Skinner 135 134 134 135 135 Sasquatch David W. Skinner 50 22 35 23 28 Sasquatch II David W. Skinner 50 16 32 18 18 Sasquatch III David W. Skinner 50 14 20 9 12 Sasquatch IV David W. Skinner 50 27 36 27 25 Sasquatch V David W. Skinner 50 30 36 31 25 Sasquatch VI David W. Skinner 50 30 31 24 26 Sasquatch VII David W. Skinner 50 30 31 27 25 SokEvo Lee J Haywood 107 107 107 107 107 SokHard Lee J Haywood 163 163 163 163 131 Sven Sven Egevad 1623 1170 1363 1234 1147 XSokoban Thinking Rabbit, ... 90 42 86 75 65 Y.M. Auto Yoshio Murase 52 52 52 52 52 Y.M. Handmade Yoshio Murase 54 54 54 52 50 Total 3424 2688 2999 2781 2629
Fig. 1.1 Rendimientos de 4 diferentes solucionadores de Sokoban.
La tabla de la figura 1.1 obtenida de <http://sokobano.de/wiki/index.php?title=Solver_Statistics> pone a prueba el rendimiento de 4 de los mejores solucionadores de Sokoban automáticos en el mundo BoxSearch, Takaken, YASS (Yet Another Sokoban Solver) y JSoko.
La suite de XSokoban es nuestro objetivo principal, ya que es una colección de problemas creados o por el inventor de Sokoban. Planeamos resolver tantos niveles como sea posible para poner a prueba nuestro solucionador y además comparar contra diferentes solucionadores y en determinados niveles. Éste trabajo se pruebas se presenta en el capítulo 7.
CAPÍTULO 2: LA BÚSQUEDA
Imaginemos una posición de sokoban muy simple:
######## # Pared # . # @ Sokoban # @$ # $ Cajas #. $ # . Destinos # # ########
Fig. 2.1. Posición inicial de un nivel de Sokoban.
Llamaremos a la posición inicial la posición S0 mostrada en la figura 2.1. La forma más simple de analizar ésta posición es mover Sokoban a cualquier posición posible Si+1 y repetir el procedimiento para tales nuevas posiciones hasta llegar a una posición final Sf (donde las cajas han sido llevadas exitosamente a los destinos, mediante una serie de movidas legales) que es el objetivo del Sokoban. Esto genera un árbol de búsqueda, donde cada nodo representa una posición definida de Sokoban. Es obvio que ésta solución es completa, es decir, obtendrá una solución si ésta existe. Sin embargo, es fácil comprobar la no computabilidad de la solución.
######## ######## ######## # # # @ # # # # # # # # # # # # # # @ # #@ # # # # # ######## ######## ######## a) b) c)
Fig. 2.2. Diferentes posiciones del almacenista en laberintos vacíos.
a) Sokoban a la esquina, 2 posibles movimientos.
b) Sokoban sobre una sola pared, 3 posibles movimientos.
c) Sokoban en el centro, 4 posibles movimientos.
Observemos la figura 2.2. Si colocáramos a Sokoban en una de las esquinas solo tendría 2 movimientos posibles (a), un Sokoban al lado de una sola pared podría moverse en 3 direcciones (b) y un Sokoban al centro tendría libre acción hacia 4 puntos (c). Por tanto cuanto más tendremos 4 movimientos por cada nueva posición de Sokoban, éste será nuestro límite superior. Si por cada casilla dentro del laberinto consideramos el límite superior de movimientos posibles obtendremos 4n posiciones de búsqueda donde n es el número de espacios que Sokoban puede ocupar. Ésta consideración es un tanto descuidada, dado que el caso de que por cada casilla disponible haya 4 movimientos es imposible, pero no hay que olvidar que estamos aproximando el número de posiciones con un límite superior para calcular el peor de los casos.
Para una configuración con la de la Fig. 2.2a con 24 casillas posibles obtenemos 281474976710656 posibles posiciones de búsqueda, cantidad necesariamente incomputable, considerando que (de forma muy optimista) un computador promedio podría analizar 10’000,000 posiciones por segundo tal algoritmo tomaría poco menos de un año en encontrar la solución. Debemos entonces decidir entre otros métodos de búsqueda más eficientes. Las estrategias de búsquedas se dividen en dos corrientes principales, mencionaremos cada una de ellas y sus enfoques brevemente.
2.1 Estrategias de búsqueda no informadas
Las búsquedas no informadas (también llamadas búsquedas a ciegas) reciben tal nombre dado que no tienen información adicional sobre lo estados si no lo provisto en la definición del problema. Todo lo que pueden hacer es generar sucesores y distinguir un estado final ú objetivo de un estado que no lo es. Mencionaremos dos de éstas estrategias: búsqueda primero amplitud (Breadth-first search) y búsqueda primero profundidad (Depth-first search).
2.1.1 Búsqueda primero amplitud
La búsqueda primero amplitud es una simple estrategia en la cual el nodo raíz (posición inicial Si) es expandido primero, después todos los sucesores del raíz son expandidos, y los sucesores de éstos y así se hasta terminar. En general, todos los nodos son expandidos con una profundidad predefinida en el árbol de búsqueda antes de que algún otro nodo de otro nivel sea expandido. La BFS (por sus siglas en inglés) puede ser implementada mediante una cola regular o cola FIFO, en donde por cada expansión de un nodo se encolan sus sucesores y el siguiente nodo en expandir esta en el frente de la cola. El problema con éste tipo de expansión es la cantidad de de memoria que necesitará. Si para el nodo raíz tuviéramos b sucesores y para cada uno de estos otros b sucesores, considerando un árbol de profundidad máxima d la complejidad estaría dada con O(bd). Esta complejidad es equivalente a la memoria utilizada, dado que cuando hayamos expandido todos los nodos hasta llegar a las hojas, en cola habrá un máximo de bd nodos en la cola.
Esto nos lleva a aprender dos cosas: Primero, los requerimientos de memoria son un problema mayor en búsqueda primero amplitud que su tiempo de ejecución. Un problema con una solución en el nivel de profundidad 12 (d = 12) con b = 4 (como en el Sokoban) y suponiendo que un nodo en la cola ocupa 4 bytes (tamaño regular de un entero) necesitaría 64 gigabytes de memoria RAM para su ejecución. Segundo, en general las búsquedas de complejidad exponencial no pueden ser resueltas mediante métodos no informados.
2.1.2 Búsqueda primero profundidad
La DFS siempre expande el nodo de más al fondo en el estado actual del árbol de búsqueda. La búsqueda se mueve inmediatamente al nivel más profundo del árbol de búsqueda, donde los nodos no tienen sucesores. Ésta estrategia puede ser implementada con una cola LIFO o pila. Cada que se expande un nodo, sus sucesores son apilados y el siguiente nodo a expandir está al tope de la pila.
La búsqueda primero profundidad utiliza muy poca memoria. Solo necesita guardar un simple camino desde la raíz al nodo hoja, dado que una vez que todas las posibles combinaciones de sucesores se han buscado, el nodo puede ser retirado de la pila. Entonces el factor de ramaje b deja de repercutir en la memoria utilizada, guardando solo d nodos (profundidad máxima del árbol de búsqueda). Sin embargo la complejidad el algoritmo en el peor de los casos sigue siendo O(bd).
2.2 Estrategias de búsqueda informadas
En general las técnicas de búsqueda enumeradas anteriormente no son prácticas para la mayoría de los problemas, en específico Sokoban. Una alternativa mucho más eficiente son las búsquedas informadas: la búsqueda se realiza mediante información extra (heurística) que le permite desplazarse con un mayor conocimiento de su entorno y orientado a obtener una solución mas rápidamente.
El enfoque general que caracteriza a las búsquedas informadas es la búsqueda primero el mejor (best-first search). Esta búsqueda se realiza mediante un árbol de búsqueda ó grafo de búsqueda en la cual el nodo que se elije para la expansión es elegido basado en la evaluación de una función, f(n). Generalmente, el nodo con menor evaluación en n es el selecto para la expansión, dado que f(n) considera por lo común el costo de llegar al objetivo.
La búsqueda primero el mejor es implementada mediante una cola de prioridades, que mantendrá la lista ordenada en orden de acuerdo a los valores de f. Como se hace notar en Rusell et al(2003) el nombre que se adjudica a esta búsqueda es muy ambiguo, dado que lo que se hace no es expandir el “mejor” nodo si no el que a nuestra consideración aparenta ser el más “prometedor”.
Dada la cantidad tan grande de familias de heurísticas que existen, es imposible describirlas todas. Nosotros consideraremos los enfoques que utilizaremos para nuestro solucionador de Sokoban. Estos dos enfoques son: búsqueda glotona primero el mejor (Greedy best-first search) y búsqueda A*(A estrella).
2.2.1 Búsqueda glotona primero el mejor
La búsqueda glotona trata de expandir el nodo mas “cercano” al objetivo, esperando que esto lleve rápidamente a la solución, por tanto evalúa nodos usando solo una función heurística: f(n) = h(n). En nuestro problema de sokoban la implementación de una búsqueda glotona pudiera ser definiendo una heurística:
h(n) = número de cajas colocadas en los destinos
######## ######## # Pared # . # # . # @ Sokoban # @$ # # @ # $ Cajas #. $ # #$ $ # . Destinos # # # # ######## ######## a) b)
Fig. 2.3. Posiciones de sokoban con diferentes evaluaciones heurísticas. a) h(n) = 0, menor preferencia. b) h(n) = 1, mayor preferencia.
2.2.2 Búsqueda A*
Éste tipo de búsqueda evalúa los nodos combinando g(n), el costo de haber llegado al nodo, y h(n), el costo de llegar del nodo actual a el nodo objetivo. Entonces:
f(n) = g(n) + h(n)
Dado que g(n) nos da el costo del nodo inicial al nodo n, y h(n) es el costo estimado del trayecto mas barato de n a el objetivo, tenemos que:
f(n) = El costo estimado de la solución mas barata desde n.
Así que cuando tratamos de buscar la solución con menos costo, es razonable intentar primero por el nodo con la menor evaluación g(n) + h(n). Dadas algunas condiciones que h(n) debe satisfacer, A* es completa y optima. Una des éstas condiciones indica que h(n) debe ser una heurística admisible, es decir no debe sobre estimar el costo de alcanzar el objetivo.
Las búsquedas informadas como A* son una de las mejores opciones cuando se trata de resolver problemas de complejidad exponencial como Sokoban, por tanto nosotros hemos optado por usar las búsquedas informadas como estrategias de solución.
CAPÍTULO 3: FORMA GENERAL DEL SOLUCIONADOR DE SOKOBAN
Lo descrito a continuación es nuestra estrategia de solución de Sokoban. Se detallan los algoritmos utilizados y el porqué de tales enfoques. Dada la gran cantidad de soluciones propuestas para Sokoban, había que considerar un conjunto de casos que permitiera evaluar el rendimiento de cada solución. Esta test suite consiste en 90 problemas de Sokoban incluidos en el software de nombre XSokoban que son utilizados a nivel mundial.
Dentro de nuestra explicación se tomarán en cuenta algunos de éstos casos como apoyo para explicar el porqué de algún procedimiento u optimización. Los algoritmos se presentarán con pseudocódigo y esperamos sean perfectamente comprensibles, sin embargo (como nuestra intención es mostrar la implementación del solucionador de Sokoban) especificaremos las bondades que el lenguaje de programación tiene para nuestro intento de solución, el lenguaje de programación usado será C++. Se da por hecho que el lector está familiarizado con el lenguaje de programación C++ así como las platillas de la librería estándar como vector, map, set, etc.
3.1 Forma general del algoritmo para resolver Sokoban
ListaCerrada = VACIO ListaAbierta = VACIO nodo NodoActual, Sucesor AGREGAR ListaAbierta NodoInicial MEMORIZAR ListaCerrada NodoInicial MIENTRAS NO ListaCerrada.VACIA HACER | NodoActual = ListaAbierta.FRENTE | SACAR ListaAbierta | PARA cada sucesor de NodoActual HACER | | SI Sucesor NO en ListaCerrada HACER | | | SI Sucesor IGUAL NodoObjetivo HACER | | | | REGRESAR Solucion | | | FIN | | | AGREGAR ListaAbierta Sucesor | | | MEMORIZAR ListaCerrada Sucesor | | FIN | FIN FIN
Fig. 3.1. Pseudocódigo una búsqueda informada enfocada a Sokoban
Dos elementos destacan dentro del algoritmo: la lista cerrada y la lista abierta. La lista cerrada pretende memorizar que nodos dentro del árbol de búsqueda han sido ya visitados, de manera que no se visiten nodos repetidos. La segunda lista abierta es una cola de prioridades que mantiene los nodos ordenados de acuerdo la evaluación de la heurística. Estos elementos se detallarán posteriormente. Habiendo dejado claro el uso de las listas expliquemos como funciona el algoritmo: En la línea 1 y 2 se vacía las listas. En la línea 3 se declaran 2 elementos de tipo nodo que nos ayudarán durante el algoritmo. Posteriormente se agrega el estado inicial a la lista abierta y se memoriza en la lista cerrada que ésta posición ya ha sido visitada.
En la línea ocho comienza un ciclo MIENTRAS que no termina mientras haya elementos en la lista abierta, lo que nos asegura que sean expandidos todos los nodos formados en la cola mientras no se haya encontrado una solución. Para la línea 9 se hace nodo actual como el frente de la lista abierta (el nodo más prometedor) y en seguida se saca este elemento de la pila dado que su exploración está por hacerse y no lo necesitaremos más. La línea 11 tiene la intención de generar todos los posibles sucesores del nodo actual y en la línea 12 se verifica que no hayan sido ya visitados (que no estén en la lista cerrada).
En la línea 13 se compara el sucesor con el nodo objetivo (la posición donde todas las cajas han sido colocadas exitosamente) y si son iguales entonces se regresa la solución. Nótese que sería un error agregar a la cola el nodo y verificar si es igual a la solución posteriormente por que estaríamos continuando con la búsqueda cuando ya hemos encontrado una solución. Si llegamos a la línea 14 esto indicaría que el sucesor que generamos no es el nodo objetivo y aún no ha sido visitado, por lo que lo encolamos y memorizamos su visita.
La función de éste algoritmo es simplemente buscar nodos sucesores de uno nodo actual extraído de la cola, rechazar aquellos que ya han sido explorados y en caso de ser el nodo objetivo regresar la solución, si no, agregarlos a la cola por prioridad e indicar que ya han sido expandidos cortando así el árbol de búsqueda.
Es de notarse la función de la lista cerrada, dado que es una poda al árbol necesaria por que de lo contrario la búsqueda podía caer en ciclos que la arruinarían. La forma como se generan los sucesores, como se define un nodo y demás procedimientos son la siguiente parte del trabajo.
3.2 Nodos: situaciones de Sokoban
Quizá como lector le ha resultado un poco confuso el termino nodo refiriéndonos a Sokoban. Un nodo es una “situación” particular que es definida mediante valores que permitan distinguir de una situación a otra.
######## ######## # Pared #.. @ # #1 2 3 4 5 6 # @ Sokoban #$ # # #7 8 #9 1011# $ Cajas # ##$ # #1213##1415# . Destinos # $ .# #161718192021# ######## ########
Fig. 3.2. Nodo de sokoban con la configuración {7, 14, 18, 3}
Considérese la figura 3.2. La imagen de la izquierda muestra un nivel de Sokoban con tres cajas. La imagen de la derecha muestra la numeración de las casillas disponibles o alcanzables dentro del nivel (aquellas que están en blanco, con una caja ú ocupada por el Sokoban). Un nodo es una configuración de las cajas y el Sokoban, esto es lo único que necesitamos saber de la posición. Para el ejemplo de la figura 3.2 la configuración es {7, 14, 18, 3}, donde la posición de las cajas va a la inicio y la del Sokoban al final con el fin de ubicar siempre las cajas desde el índice 0 al n-1 y Sokoban en el índice n, donde n es la dimensión del vector que definimos como configuración.
Si por ejemplo dado un nivel de Sokoban cualquiera y una configuración {1, 3, 5} se llegara mediante una serie de movimientos válidos a la configuración {3, 1, 5}, ¿Existe alguna diferencia entre estas dos configuraciones? Quizá exista una diferencia entre el número de movimientos que se han realizado para llegar a tal posición, pero estas son esencialmente la misma, es decir, un nodo ya investigado. Por tanto las cajas han de mantenerse en orden (véase 3.3.1) de modo que sea notoria la repetición de una configuración (además de otra muy importante razón de carácter de implementación de la lista cerrada).
Implementación Una configuración será representada mediante un vector<short> donde para un nivel con n cajas desde el índice [0] hasta [n-1] son la ubicación de las cajas y el índice [n] la ubicación del Sokoban.
Debe observarse que en lugar de posiciones enumeradas con enteros pudimos haber utilizado coordenadas cartesianas para describir las posiciones de las cajas. La razón por la que no lo hicimos es un ahorro de memoria. Si describimos las posiciones mediante puntos cartesianos ocuparemos el doble de memoria dentro del vector, por ejemplo en la figura 3.2 la configuración con coordenadas sería {1, 3, 3, 1, 5, 2, 4, 4}.
Además utilizaremos un tipo de entero corto de 16 bits (short) que nos permite usar un rango de enteros desde el -32768 al 32767 suficiente para nuestro problema, ya que los casos de prueba no exceden mapas de 32x32 casillas y si pudiéramos numerarlas tendríamos como máximo 1024 posibles valores.
No obstante es posible definir una situación en un nivel de Sokoban mediante una configuración guardada en un vector<short>, esta no es la única información que conforma un nodo dentro de nuestra implementación. Así que definiremos una clase que contenga la configuración del nodo así como distintos valores cuya utilización será explicada posteriormente. Para referirnos a un nodo lo haremos mediante una instancia de la clase nodo, que dentro del código se ha definido en inglés como node.
class node {
short cost, h, placedbox;
int npath;
vector<short> config;
};
Fig. 3.3. Definición de la clase nodo
3.3 La lista cerrada
La intención de esta lista es memorizar qué nodos han sido previamente expandidos durante la ejecución del algoritmo. Esta tarea que suena muy simple, en realidad es una de las más “complejas” y que requiere extrema atención, debido a que la cantidad de nodos a explorar es exponencial y esto significa un gran uso de memoria. En adición, el método de búsqueda para encontrar nodos repetidos se complica por al misma razón. Así que tenemos dos problemas que involucran los dos recursos más importantes dentro de la computación: memoria y tiempo de ejecución.
Con nuestro problema de memoria iniciamos descartando almacenar cada configuración, considerando que si tuviéramos 256 MB de RAM disponibles y configuraciones de 7 cajas llenaríamos la memoria al llegar a los 2’000,000 de nodos aproximadamente, cantidad que es muy limitada.
Uno de los modelos más óptimos para resolver este tipo de problemas es: la tabla hash. Mediante una tabla hash se hace un mapeo de una estructura muy compleja a un valor mucho mas simple, así podemos lograr que una configuración de 16 cajas se convierta en un único valor entero corto. Por otra parte mediante la definición de una buena función hash se puede lograr que la búsqueda de elementos sea en tiempo constate. Dicho tiempo constante se ve alterado cuando la tabla se va llenando y se producen colisiones. Son necesarias varias pruebas para determinar que función hash es la más conveniente así como un muy buen método de resolución de colisiones.
Un segundo modelo, utiliza una función hash y almacenaje mediante árboles rojo-negro. La optimización en memoria es básicamente la misma, pero por otra parte se logra una búsqueda en tiempo O(log n). Así que no son necesarias otras pruebas.
Implementación Escoger entre una tabla hash y un árbol rojo-negro, es una decisión que necesita varias pruebas de implementación, las cuales no realizamos en nuestra investigación. Lo que si sabemos es que ambas son buenas opciones y afortunadamente una está disponible dentro de la librería estándar de plantillas mediante un contenedor asociativo conocido como map.
La definición de map< vector<short>, bool> asegura un mapeo uno a uno de una configuración de Sokoban (vector<short>) a un byte mediante una función hash y una estructura de árbol rojo-negro. Ésta implementación es buena, y a nuestra consideración suficiente dentro de nuestro enfoque. Es muy importante resaltar que map considera totalmente diferente la configuración {1, 2, 3} de la configuración {3, 2, 1}, por tanto es necesario un orden para las configuraciones.
3.4 La lista abierta
El objetivo de la lista abierta es mantener ordenados los nodos que faltan por expandir de acuerdo a su evaluación heurística, para simplemente, a cada iteración, tomar el nodo al frente de la lista ya que este es siempre el más prometedor. La estructura que simula tal procedimiento es una cola con prioridades. Una cola con prioridades permite realizar inserciones O(log n) evitando tener que insertar con recorridos O(n) o realizar ordenamientos de costo O(n log n).
Implementación También para esta lista utilizaremos un adaptador de contenedor conocido como priority_queue. La declaración de ésta cola de prioridad quedará como priority_queue< node >, que expresa que la cola contendrá instancias de la clase nodo. Dentro de los requisitos para la inserción en un adaptador de este tipo está la sobrecarga del operador < para elementos de tipo nodo y es precisamente esta sobrecarga la función heurística que nosotros utilizaremos. El siguiente capítulo está dedicado a ello.
CAPÍTULO 4: LA HEURÍSTICA
La heurística es una función f(n) que para un nodo n produce un valor que representa qué preferencia de expansión dar a ese nodo y permite ubicarlo dentro de la lista abierta. La preferencia de expansión para un nodo en Sokoban podría ser:
- El nodo que prometa una solución.
- El nodo que prometa una solución mínima.
Nuestra heurística esta pensada para la primera opción. Pero aún cuando estamos buscando simplemente una solución, de cierta manera interesa que sea si no la mínima, al menos una buena solución.
Diferentes heurísticas producen diversos resultados. Describiremos que alternativas podrían producir resultados como la solución mínima, cuales simplemente una solución y aquellos que conducen a una buena solución.
4.1 A*: la heurística admisible
Sea f(n) la función heurística conformada de:
g(n) = costo del recorrido hasta el nodo n
h(n) = costo aproximado de acomodar las cajas restantes
Entonces:
f(n) = g(n) + h(n)
g(n) es el numero de movimientos o empujes que ha hecho el almacenista. h(n) es un valor aproximado de cuantos movimientos costará llevar a los destinos las cajas que falta acomodar.
El uso de esta heurística promete encontrar una solución mínima, sin embargo, es muy lenta por sí sola, ya que puede perderse en posiciones que no tienen solución pero que aparentan ser mínimas.
4.2 La heurística voraz
Sea una función heurística f(n) donde:
f(n) = número de cajas acomodas
De entrada ésta parece una estrategia no muy buena, debido a la simplicidad y la cantidad de casos que pueden perjudicar su “correcto juicio de la posición”, es decir, existen infinidad de posiciones donde se ha logrado colocar una caja (están tendrán preferencia sobre aquellas que no tengan cajas acomodadas) y sin embargo no será posible colocar las demás, así que la búsqueda tendrá que analizar inútilmente todos los nodos en cuya configuración existe una caja acomodada para finalmente darse cuenta que esta era una posición muerta. Por otra parte, si hemos podido colocar una caja, probablemente hemos encontrado una ruta patrón que nos permita desplazar las demás cajas hacia los objetivos y además hacerlo rápidamente. Éste es el caso del nivel 1 de la suite de Sokoban.
,,,,#####,,,,,,,,,, # Pared
,,,,# #,,,,,,,,,, @ Sokoban
,,,,#$ #,,,,,,,,,, $ Cajas
,,### $##,,,,,,,,, . Destinos
,,# $ $ #,,,,,,,,, , Área externa
### # ## #,,,######
# # ## ##### ..#
# $ $ ..#
##### ### #@## ..#
,,,,# #########
,,,,#######,,,,,,,,
Fig. 4.1. Nivel 1 del test suite de Sokoban
Supongamos que después de una serie de movimientos legales sugeridos por nuestra heurística, llegamos a nodo con donde su configuración es la siguiente posición:
,,,,#####,,,,,,,,,, # Pared
,,,,# #,,,,,,,,,, @ Sokoban
,,,,#$ $#,,,,,,,,,, $ Cajas
,,### ##,,,,,,,,, . Destinos
,,# $ #,,,,,,,,, , Área externa
### #$## #,,,######
# # ## ##### ..#
# $ @$#
##### ### # ## ..#
,,,,# #########
,,,,#######,,,,,,,,
Fig. 4.2. Nivel 1 después de una serie de movimientos
Se ve claramente que una caja ha sido colocada correctamente y que las demás cajas tienen trayectos rápidos hacia la zona de destinos, por tanto hemos encontrado una ruta patrón que nos conducirá a una buena solución.
4.3 La heurística elegida
Nuestra implementación es una combinación de las heurísticas anteriores. Buscando obtener una solución buena en un tiempo relativamente rápido. Sea la función heurística f(n) compuesta por:
g(n) = costo del recorrido hasta el nodo n
h(n) = costo aproximado de acomodar las cajas restantes
i(n) = número de cajas colocadas en una casilla destino
Donde:
f(n) = i(n) | g(n) + h(n)
Nuestra heurística está definida o por el número de cajas colocadas correctamente (en un destino) ó la suma de movimientos hasta la configuración n más el costo aproximado de llevar a los destinos las cajas restantes. Éste significa que dentro de la lista abierta aparecerán primero los nodos con más cajas acomodadas correctamente y en caso de empates seguirán aquellos con menor costo acumulado de g(n) y h(n).
Los valores de i(n), g(n) y h(n) deben ser incluidos en un nodo y son correspondientes a las variables declaradas en la definición de la clase nodo de la figura 3.3.
cost = g(n)
h = h(n)
placedbox = i(n)
Implementación La implementación de la heurística es una sobrecarga del operador < para elementos de tipo nodo que permita insertar elementos en la cola de prioridad lista abierta.
La sobrecarga quedaría así:
bool operator < (const node &a, const node &b) {
if( a.placedbox == b.placedbox ) return a.h+a.cost > b.h+b.cost;
return a.placedbox < b.placedbox;
};
Fig. 4.3. Sobrecarga del operador < para instancias de tipo nodo en C++
Este código expresa más claramente la idea de la heurística elegida. Dados dos elementos a y b de tipo nodo uno tiene menor preferencia que el otro sí:
- a tiene menor número de cajas acomodadas en destinos que b
- b y a tienen el mismo número de cajas correctamente colocadas, pero a tiene un mayor costo suma de g(n) + h(n) que b.
Esta pequeña porción de código es muy práctica ya que cuando necesitamos cambiar la preferencia de un nodo simplemente tenemos que realizar pequeños cambios dentro de ésta función. Como calcular cada una de las funciones g(n), h(n) é i(n) se detalla a continuación.
4.3.1 Las funciones g(n), h(n) é i(n) g(n)
La función g(n) es el costo que hemos acumulado hasta el nodo actual, es decir, el número de movimientos que ha tomado llegar a dicha configuración. Para el nodo inicial n0 tenemos: n0.cost = 0
Posteriormente lo único que tenemos que hacer para cualquier nodo ni es igualar para cada uno de sus sucesores ni+1: ni+1.cost = ni.cost + 1
La manera como se calcula cada sucesor se verá en el capítulo 4, basta dejar en claro que cada sucesor de n es un único desplazamiento válido de una caja en alguna dirección.
h(n)
La función h(n) es el costo aproximado que nos tomará colocar las cajas que faltan por llevar a los destinos. Esta función está relacionada con las configuraciones definidas en el tema 3.2. Recordemos que una configuración c esta conformada por un conjunto de b de casillas que representan las cajas y una casilla s donde se encuentra el Sokoban.
######## ######## # Pared # $ .# #1 2 3 4 5 6 # @ Sokoban # $ # #7 8 9 101112# $ Cajas # # . @# #13#14151617# . Destinos # $. # #181920212223# ######## ########
Fig. 4.4. Configuración {3, 10, 21, 17} de un nivel de Sokoban
Tomemos como referencia el nivel mostrado en la figura 10. La pregunta es: Aproximadamente ¿Cuánto tomará colocar en un destino cada una de las cajas en el nivel?
Para calcular este problema utilizaremos lo que se conoce como distancia Manhattan entre dos puntos que es igual a |x1 - x2| + |y1 - y2|. El problema puede ser representado mediante un grafo bipartito completo entre las cajas y los destinos denotado como KB,D donde B son lo vértices que representan las cajas y D los vértices que representan los destinos, y como el grafo es bipartito completo B y D tienen la misma cardinalidad es decir |B| = |D|.
Fig. 4.5. Grafo bipartito para el problema de acarreo de cajas
Donde cada arco BiDi es la distancia Manhattan entre la caja Bi y el destino Di. El problema consiste en minimizar el costo del pareo entre cada vértice del conjunto B con un vértice del conjunto D. Debe notarse que éstos trayectos mínimos son considerando que no hay ningún obstáculo entre cada caja y destino, lo cual sabemos no se cumple en la mayoría de las veces, por eso solo estamos haciendo una aproximación del costo.
Sin embargo, resolver éste problema de optimización que nos garantiza obtener el costo mínimo, conlleva un algoritmo que en el mejor de lo casos es O(n2) y en el peor O(n4) donde n es el número de cajas, dado que puede ser reducido a un problema de flujo máximo costo mínimo Cormen et al (2001). Por eso nosotros hemos decido implementar una idea que se acerque al costo mínimo pero reduzca el complejidad de calcularlo.
La idea es la siguiente: Usaremos el nivel de la figura 4.4. 1.- Ordenamos la configuración de los destinos con respecto de su distancia Manhattan al origen y en caso de igualdad aquellos con la menor coordenada y. Así obtenemos D = {22, 15, 6} con las respectivas distancias MD = {6, 6, 10}.
2.- Para el nodo inicial n0 aplicamos el mismo orden que hicimos para los destinos. Para cada sucesor ni+1 basta con insertar mediante una búsqueda binaria con respecto de su distancia Manhattan y el criterio de desempate de la coordenada y con un costo O(log n). En nuestro ejemplo obtenemos B = {21, 10, 3} con las respectivas distancias MB = {5, 7, 7}.
3.- De los conjuntos obtenidos calculamos la sumatoria del valor absoluto de las diferencias entre los elementos en las distancias desde el índice 0 hasta b (número de cajas) y éste resultado es el costo aproximado de acarrear las cajas. Es decir:
h(n) = | MDi - MBi |
Entonces:
h(n) = n.h = |6-5| + |6-7| + |10-7| = 1 + 1 + 3 = 5
Para cada nodo dentro de nuestra búsqueda hay que ubicar la caja que deseamos eliminar dentro de la configuración lo que toma mediante búsqueda binaria O(log n), luego una inserción de la posición de la nueva caja con O(log n) también y finalmente calcular las diferencias que toma O(n), así que calcular la función h(n) tomará aprox. O(2log n + n).
Implementación La configuración dentro de un nodo está guardada en un vector<short> config. Para realizar las inserciones mediante búsqueda binaria utilizaremos un algoritmo de la librería estándar de plantillas llamado lower_bound.
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, StrictWeakOrdering comp);
Fig. 4.6. Forma del algoritmo de búsqueda binaria lower_bound
Ésta función recibe un iterador inicial (inicio del rango), un iterador final (fin del rango), un valor (el que deseamos ubicar) y una clase de comparación débil (una clase que contiene sobrecarga de operador < para instancias de tipo T) y regresa un iterador que apunta donde debería ser insertado el nuevo elemento para mantener el orden o en caso de que el elemento ya esté insertado nos diría donde está. La clase de comparación queda así:
class point_sort {
public:
bool operator () (const short& a, const short& b) {
// Donde a y b son las casillas ocupadas
// Si la distancia Manhattan de a es menor que la de b return 1
// Si la distancia Manhattan de a es mayor que la de b return 0
// Si la distancia Manhattan de a es igual que la de b y:
// Si el eje y de a es menor que el eje y de b return 1
// Si no return 0
};
};
Fig.4.7. Clase de comparación débil para casillas
En el ejemplo anterior con D = {22, 15, 6} y B = {21, 10, 3}, si deseáramos mover la caja en 21 a la casilla 22 (hacia la derecha), el procedimiento es el siguiente.
1.- Obtener el índice de la caja 21 y eliminarlo.
vector<short>::iterator ite = lower_bound( config.begin(),
--config.end(), 21, point_sort() );
config.erase(ite);
2.- Buscar la posición donde deberíamos insertar la nueva caja en la casilla 22 e insertarla.
vector<short>::iterator ite = lower_bound( config.begin(),
--config.end(), 22, point_sort() );
config.insert(ite,22);
Nótese que --config.end() está decrementado, ya que el final del rango no debe incluir la posición del Sokoban (la última) si no solamente el rango donde están las cajas.
La forma en como calcular la sumatoria para obtener h(n) es decisión del lector.
i(n)
La función i(n) es la cantidad de cajas que ocupan la mismas casilla que alguno de los destinos. La forma de obtener éste valor es decisión del lector. El valor i(n) esta guardado en n.placedbox.
CAPÍTULO 5: LOS SUCESORES Y LA SOLUCIÓN
En este capítulo pretendemos ahondar más dentro de la búsqueda informada enfocada a Sokoban presentada en el capítulo II (figura 3.1). En particular dos problemas quedan pendientes por analizar: Como se generan los sucesores de un nodo y como guardar la solución. Cada uno de estos problemas es de peculiar atención por que su construcción envuelve distintas formas de solución que deberemos considerar como parte de la optimalidad de nuestra implementación del solucionador.
5.1 Generando los sucesores
El sucesor ni+1 de un nodo ni, es un nuevo nodo en el cual la casilla de una caja ha sido modificada debido a un desplazamiento válido en alguna dirección (norte, sur, éste, oeste) y por ende con nuevos valores cost, h y placedbox.
Dos cosas hay que considerar para generar un nuevo sucesor: 1.- Existe un movimiento válido para alguna caja dentro del nodo actual ni y: 2.- Hay un camino posible del Sokoban a la casilla opuesta al movimiento que se pretende hacer de la caja, de modo que pueda empujarla.
Comenzaremos con los movimientos válidos de una caja.
5.1.1 Movimientos
Una caja puede desplazarse en cualquiera de los cuatro puntos cardinales. En general no hay ningún orden que seguir, es decir, pudiera probarse cualquier dirección primero. Sin embargo por métodos prácticos probaremos empezando por el norte y en sentido de las manecillas del reloj (norte, este, sur, oeste). Con los respectivos valores:
norte – 0 este – 1 sur – 2 oeste – 3
Implementación
Para todas las cajas dentro de una configuración ha de probarse si el movimiento de la caja bi con coordenadas x, y es válido. Para lograr esto es útil utilizar un vector de movimientos:
short moves[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
Donde para verificar si la casilla a donde deseamos mover la caja dentro un mapa[][] en la dirección i (desde 0 hasta 3) está vacía es suficiente hacer:
mapa[x+moves[i][0]][y+moves[i][1]] == vacía
Y para obtener la casilla contraría al movimiento deseado podemos hacer:
mapa[x+moves[(i+2)%4][0]][y+moves[(i+2)%4][1]]
Cualquier otro movimiento que se necesite puede ser fácilmente deducido por el lector.
5.1.2 Empujando las cajas
Para empujar una caja es necesario primero desplazar el Sokoban hasta la parte contraria de la caja con respecto al movimiento deseado. Éste camino puede ser fácilmente obtenido mediante un búsqueda en amplitud. Dentro de un mapa con dimensiones m, n la búsqueda puede hacerse en tiempo O(mn) como es descrito en Cormen et al(2001). Ya habíamos mencionado antes que las dimensiones máximas de un nivel de Sokoban son como máximo de 32x32, por tanto para m = 32 y n = 32 generaríamos un árbol de búsqueda de máximo 1024 nodos, lo cual es rápido de computar. Ésta búsqueda nos garantiza obtener una solución mínima si la hay, debido a esto y el bajo costo de calcularlo es que utilizaremos esta técnica en el sub problema de mover al almacenista.
Implementación Implementar esta búsqueda no requiere el uso alguna estructura de datos especial. Solamente se necesita una cola FIFO donde formar los nodos y seguir el pseudocódigo siguiente:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 FUNCION SokoCanPush LLENAR Mapa[MAXX][MAXY] -1 Cola = VACIO AGREGAR Cola DireccionInicialX AGREGAR Cola DireccionInicalY AGREGAR Cola 0 MIENTRAS NO Cola.VACIA HACER | entero X = Cola.FRENTE SACAR Cola | entero Y = Cola.FRENTE SACAR Cola | entero total = Cola.FRENTE SACAR Cola | SI X,Y IGUAL DireccionesDestino HACER | | REGRESAR total | FIN | SI Mapa[X][Y] DIFERENTE DE -1 HACER | | SALTAR A INICIO CICLO MIENTRAS | FIN | Mapa[X][Y] = total | PARA cada movimiento valido desde X,Y HACER | | AGREGAR Cola XNUEVA | | AGREGAR Cola YNUEVA | | AGREGAR Cola total+1 | FIN FIN REGRESAR -1
Fig. 5.1. Pseudocódigo de búsqueda en amplitud en un mapa[32][32]
Si se encuentra una solución, la función regresa la cantidad mínima de pasos desde la posición actual (coordenadas x, y del Sokoban) hasta la posición destino (coordenadas x, y del posterior de la caja), si no es posible encontrar un trayecto regresa -1.
Comprobadas la valides de un movimiento y la posibilidad de que el Sokoban lo realice, se obtiene un nuevo nodo que agregar a la lista abierta mediante el siguiente código:
node N; N.cost = CN.cost+1+findway; N.h = heur_fun(tcon); N.cpb = // nuevo total de cajas acomodadas en destinos N.state = // Descrito posteriormente sección 5.2 (implementación) N.config = tcon // nueva disposición de las cajas y sokoban OpenList.push( N );
Fig. 5.2. Porción de código para insertar un nuevo nodo a la lista abierta
Sea CN es el nodo que está siendo expandido, N el nuevo nodo, findway el costo que tomó llevar al Sokoban hasta la caja, tcon la nueva configuración (cajas y almacenista) y heur_fun() la función heurística para evaluar configuraciones. Entonces:
- El nuevo costo acumulado es igual a: el costo del nodo expandido + 1 + el costo de llevar el sokoban hasta la caja.
- La evaluación heurística del nuevo nodo es igual a: el resultado que regresa huer_fun() aplicada a la nueva configuración tcon.
De ésta manera se van agregando nodos sucesores a la lista abierta los cuales son priorizados respecto de su preferencia.
5.2 Cómo estructurar la solución
La línea 14 de la búsqueda informada enfocada a Sokoban REGRESAR Solucion es infinitamente simple a comparación de lo que representa. Dentro de una búsqueda informada expandimos los nodos que consideramos mejores, sin algún orden aparente. Tomemos como ejemplo el grafo de la figura 5.3 en la que los nodos son configuraciones de un nivel de sokoban y los arcos representan desplazamientos de las cajas.
Fig. 5.3. Grafo que representa los posibles estados de un nivel de Sokoban
Supongamos que nuestra heurística indica que se debe expandir primero el nodo B, luego el F y luego el nodo E como en la figura 5.4.
Fig. 5.4. Expansión de los nodos B, F y E en orden
Durante la búsqueda de una solución en el Sokoban, pasa exactamente lo mismo. Se busca una solución expandiendo un nodo (B) y en la siguiente expansión se considera uno totalmente ajeno (F), luego quizá regresemos a un mismo camino de búsqueda (E) y así. La pregunta es, ¿Cómo guardar el camino?
Si por ejemplo encontráramos la solución en el nodo G a través del trayecto A-D-E-G, lo único que necesitamos saber para poder reconstruir la solución es el movimiento que hicimos, es decir el arco por el cual nos desplazamos del nodo ni-1 al nodo ni. Esto es muy importante ya que pudiera creerse que es necesario saber cual fue el nodo anterior ni-1. Si fuese así sería necesario conservar todos los nodos en memoria por aparte de la lista abierta, ya que recordemos que después de ser expandidos estos son eliminados de la lista. Almacenar los nodos conlleva guardar sus configuraciones, heurísticas y demás información que para nuestro objetivo es innecesaria.
Por ésta razón construiremos una clase especial que contenga solamente la casilla hacia la que se desplazó la caja, la dirección en que se realizó el movimiento y el arco anterior, de forma que podamos ir recorriendo hacia atrás arco tras arco y poder reconstruir la solución. Así pues sabemos como es que fueron movidas las cajas, pero ¿Que trayecto ha seguido el almacenista para empujarlas?
Considérese el siguiente nivel de Sokoban.
######## ######## # Pared # @$# #1 2 3 4 5 6 # @ Sokoban # # #7 8 9 101112# $ Cajas #$# # #13#14151617# . Destinos # # #181920212223# ######## ########
Fig. 5.5. Configuración de Sokoban donde la caja en la casilla 5 ha sido movida a 6
Lo único que sabemos sobre la posición es que la última caja movida fue a la casilla 6 con coordenadas 6, 4 en dirección 1 (este) y además sabemos el arco antecesor a. Usando el vector de movimientos de la sección 4.1.2 podemos calcular las coordenadas antiguas de la caja:
xant = x-moves[1][0] yant = y-moves[1][1]
Donde xant, yant indican la casilla 5. Si el almacenista empujó las cajas hacia el este, él estaba situado en:
xsoko = x-2*moves[1][0] ysoko = y-2*moves[1][1]
xsoko, ysoko corresponde a la casilla 4. La posición que hemos reconstruido se vería así:
######## ######## # Pared # @$.# #1 2 3 4 5 6 # @ Sokoban # # #7 8 9 101112# $ Cajas #$# # #13#14151617# . Destinos # # #181920212223# ######## ########
Fig. 5.6. Nivel de la figura 5.5 reconstruido 1 movimiento de caja atrás
Ahora bien, el arco anterior a indica que la caja fue movida hacia la casilla 13 en dirección 2. Mediante el mismo procedimiento previo deduciríamos que en la posición anterior el almacenista estaba en 1 movió la caja en 7 y terminó ubicado en la casilla 7.
Entonces la transición entre las dos posiciones es la ruta de 7 - 4. Ésta puede ser calculada con el mismo algoritmo de búsqueda en amplitud descrito en la parte 4.1.2. Sin embargo en ésta ocasión deseamos conocer el camino mínimo que se siguió. Si aplicáramos el pseudocódigo de la figura 5.1 obtendríamos un mapa así:
- ######## # Pared
- 1 2 3 4$.# #1 2 3 4 5 6 # @ Sokoban
- 0 1 2 3 4-1# #7 8 9 101112# $ Cajas
- $# 3 4-1-1# #13#14151617# . Destinos
- -1-1 4-1-1-1# #181920212223#
- ########
a) b)
Fig. 5.7. a) Mapa con costos resultante de la búsqueda en amplitud con el pseudocódigo de la figura 5.1 b) Mapa con casillas disponibles numeradas
El costo mínimo de ir de la casilla 7 a la 4 es de 5 movimientos. Para ver el camino que siguió se debe obtener cualquier sucesión descendente en una unidad desde la casilla 4 hasta llegar a la casilla con costo 0. Ejemplos de estas trayectorias son 4-10-9-8-7 ó 4-3-2-8-7. Cuando hay varios caminos posibles no importa que camino se elija, ya que todos son mínimos y cumplen con el mismo objetivo.
Ahora ya podemos recuperar tanto la secuencia de desplazamientos de las cajas que conduce a la solución como los trayectos del sokoban para empujarlas. Recapitulando:
1. Necesitamos solo los arcos por los que hemos pasado para reestructurar la solución 2. Hemos presentado un método que permite ir hacia atrás calculando las antiguas posiciones de una caja y el Sokoban 3. Mediante búsqueda en amplitud podemos reconstruir el trayecto del Sokoban entre cada movimiento de cajas.
Ahora solo nos queda explicar como es que se guardan los arcos, éste tema se trata a continuación.
Implementación En la lista abierta se guardan nodos que representan una gran cantidad de memoria, pero éstos se eliminan cuando son expandidos. La lista cerrada guarda un boleano (8 bits en DEV C++) por cada nodo, lo cual no es una cantidad significativa dado que 1024 nodos serán apenas 1KB de memoria RAM. Pero ahora pretendemos guardar todos los arcos con al menos 3 variables diferentes (una casilla, una dirección y un arco anterior) así que necesitamos ser cuidadosos con ello.
La clase arco que nos permitirá guardar las tres variables anteriores se plantea a continuación:
class arco {
short xy;
short dir;
int back;
};
Fig. 5.8. Clase arco
xy: es la casilla donde terminó la caja desplazada
dir: la dirección en que se realizó el desplazamiento
back: el arco anterior
Cada vez que se crea un nuevo nodo, generaremos un arco correspondiente, el arco a través del cual se ha alcanzado el nuevo nodo. Como ya habíamos dicho, un nodo es explorado sin orden alguno. Por tanto agregaremos a la lista los arcos como vayan llegando enlazándolos mediante back. La estructura que nos permite hacer una lista de arcos es un vector:
vector< arco > path;
El último aspecto que resolver es realizar el enlazado, para esto finalmente describiremos la función de la variable npath de la clase nodo. Cada vez que se crea un nuevo nodo a este se le etiqueta mediante un valor entero comenzando con el 0 e incrementándose de 1 en 1, el nodo inicial no tiene un arco correspondiente por tanto es etiquetado con -1, pero cada nodo subsiguiente ha sido alcanzado mediante un movimiento válido (una arco) por tanto hay una correspondencia uno a uno entre el nodo y el arco. Esto indica que el arco que produjo el nodo etiquetado con el entero i puede ser encontrado en el vector path en el índice path[i].
Realizar el enlace entre los arcos se hace de la siguiente manera: Cada vez que se genera un nuevo nodo se agrega un arco correspondiente donde back (el arco anterior) es igual a la etiqueta del nodo que estamos expandiendo.
nodo CN; // Nodo siendo expandido arco A; A.xy = // Número de la casilla a la que se movió la caja A.dir = // Dirección en que se desplazó la caja A.back = CN.npath path.push( A );
Fig. 5.9. Porción de código que permite insertar un nuevo arco.
Ya enlazados los nodos simplemente tenemos que hacer un backtracking de la solución, una recapitulación de como fuimos desplazando las cajas y moviendo al Sokoban.
CAPÍTULO 6: CORTES EN EL ÁRBOL DE BÚSQUEDA
Las búsquedas informadas son guiadas a través del conocimiento que tienen sobre la posición. La información provista a nuestro algoritmo puede ser dividida en 2 tipos:
- Información sugerente. Ésta es la función heurística. Nos sugiere por donde ir, nos recomienda que nodo expandir, sin embargo no es una información absoluta ya que no puede garantizar nada.
- Información absoluta. La capacidad de diferenciar entre un nodo común y un nodo solución es información absoluta, o un nodo lo es o no lo es.
Un corte es un tipo de información absoluta. Cuando una configuración de un nodo tiene una disposición de las cajas tal que es imposible llegar a una solución, dicho nodo no debería seguir siendo expandido, es decir, deberíamos cortarlo.
Un corte no puede ser información sugerente, ya que debemos conocer fielmente que desde este nodo no se puede alcanzar alguna solución y no solo suponerlo.
Los cortes son una necesidad dentro del solucionador de Sokoban, estos son igual de importantes que la heurística implementada.
La razón es la siguiente: Supongamos que el nodo n al frente de la lista abierta es una posición muerta. Además supongamos que todos los hijos de dicho nodo serán insertados al frente de la lista abierta (tendrán máxima prioridad). La configuración del nodo n tiene b cajas y suponiendo que cada caja tiene 4 movimientos posibles, un nodo puede tener hasta 4b hijos, ésta cantidad de hijos se eleva aproximadamente de acuerdo al número de casillas disponibles dentro del nivel de sokoban d (profundidad máxima de la búsqueda), obteniendo un total de nodos sucesores igual a (4b)d.
Entonces, para un mapa de Sokoban relativamente pequeño, con 12 casillas disponibles y 3 cajas si hiciéramos un corte en éste nodo evitaríamos analizar 8’916’100’448,256 nodos, un ahorro increíblemente importante. Por ésta razón los cortes se hacen menester.
Dentro del juego de Sokoban existen muchas posiciones que pueden consideradas como muertas (aquellas que pueden ser cortadas), nosotros incluimos dentro de nuestra solución algunas de las más evidentes.
6.1 La esquinas
Observemos la siguiente figura correspondiente al nivel 1 de la suite de casos de prueba, en donde se ha marcado con una x cada esquina dentro del laberinto a excepción de aquellas que son también destinos.
##### # Pared
#x x# @ Sokoban
#$ # $ Cajas
### $## .Destinos
#x $ $x#
### # ## # ######
#x # ## #####x ..#
#x$ $ ..#
##### ### #@##x ..#
#x x#########
#######
Fig. 6.1. Nivel 1 de Sokoban con esquinas marcadas como x
No se debe llevar una caja a una esquina a menos que ésta esquina sea un destino.
Llevar una caja hacia una esquina producirá una posición muerta, mientras el algoritmo siga moviendo las cajas restantes la caja en la esquina permanecerá inamovible. La implementación de éste corte es trivial, simplemente hay que marcar la casillas que tienen en lados consecutivos (por ejemplo sur-este, norte-oeste, este-norte) paredes. La configuración de una caja en la esquina da las bases que nos conducen al siguiente corte.
6.2 Bloques
Cuando una caja es desplazada hacia una esquina se forma un bloque de 2x2 con la siguiente formación:
#$
##
Fig. 6.2. Bloque de 2x2 con una caja
Los bloques de 2x2 son imposibles de descomponer, dado que se bloquean mutuamente los lados por donde pudieran ser empujadas las cajas. Ejemplos de estos bloques son:
## $$ $# $$ $$
$# ## #$ #$ $$
Fig. 6.3. Bloques de 2x2 inamovibles
Todo bloque de 2x2 conformado por al menos 1 caja produce una posición muerta. Otro bloque que conduce a una posición muerta es el siguiente:
$$$
$ $
$$$
Fig. 6.4. Bloques de 3x3 con centro vacío inamovibles Una demostración fácil de que ésta es una posición muerta, es el hecho de que cada movimiento posible de una caja nos lleva a una posición con bloque de de 2x2. Con un poco de observación del bloque de 3x3 con centro vacío se revelan nuevas posiciones sin solución:
$$ $$
$ $ $ $
$$$ $$
Fig. 6.5. Bloques de 3x3 con centro y esquina vacías inamovibles
Así mismo este acomodo de las cajas es irresoluble. Por tanto la regla se puede describir como sigue:
Todo bloque de 3 x 3 con centro vacío con 1 ó 2 esquinas opuestas vacías produce una posición muerta
Por supuesto existen una gran cantidad de posibles bloques, por ejemplo:
#####
$ #
$$$$ #$$# $$$$$$ # $## $$$$
$ $ # # $ $ # $ # $ $
$$$$ $# $$$$$$ ## $# $$$$$
#
#
Fig. 6.6. Varias posiciones muertas
Los bloques de posiciones muertas son tan variados que deben ser tratados con inteligencia. Si deseamos incluir un tipo de bloque como parte del corte de nuestra solución debe tomarse en cuenta que tan probable es que este acomodo se encuentre en una posición y que tan costoso es hacer su búsqueda, entre otros.
Implementación
Encontrar dentro de una configuración de un nivel de Sokoban, un tipo de bloque es relativamente sencillo. Lo que hay que hacer es recorrer el mapa con tal configuración en búsqueda del bloque comparando casilla por casilla.
Se debe de ser cuidadoso al momento de establecer la búsqueda ya que pudieran cometerse errores como los siguientes:
######## ######## # Pared # # # # @ Sokoban # ... # # $$$# # $ Cajas # .. @ # # $. $@# . Destinos # ... # # $$$# # # # # # ######## ######## a) b)
Fig. 6.7.
a) Destinos dentro de el nivel de Sokoban b) Disposición de las cajas en el nivel de Sokoban
Pudiera considerarse el acomodo de las cajas en b) como posición muerta de acuerdo a los tipos de acomodos mostrados anteriormente, sin embargo, aún es posible conseguir llegar a la posición final desplazando la caja a la izquierda de Sokoban.
Éste tipo de condiciones deben preverse durante la construcción de la búsqueda, por lo demás es decisión del lector la implementación.
6.3 Paredes limitadas
Otra forma de colocar las cajas de manera que ya no puedan ser llevadas a los destinos es llevar las cajas a paredes limitadas.
,,,##########,,, # Pared
,,,#.. x#xxx#,,, @ Sokoban
,,,#.. x#,,, $ Cajas
,,,#.. x# ####, . Destinos
,,####### #xx##
,,#x x#
,,#x #x ##xx# x#
#### ##xx#### ##
#x $ x#####x# x#
#x# $ $ x#x$ x#
#x@$ $ x#xxx##
#### ## #######,
,,,#xxxx#,,,,,,,
,,,######,,,,,,,
Fig. 6.8. Nivel 17 de la suite de casos de prueba de Sokoban con las esquinas y paredes limitadas marcadas con x
Vamos a suponer que estamos ubicados en una esquina y estamos allí de modo que las paredes de la esquina nos quedan una a la espalda y otra al lado izquierdo. Avanzamos hacia adelante mientras tengamos del lado izquierdo una pared y no pasemos por un destino hasta topar de frente con otro muro. Esto es a lo que nos referimos cuando hablamos de pared limitada. Si este método es aplicado cada vez que se encuentra una esquina, obtendremos todas las paredes limitadas dentro de un nivel de Sokoban, como se muestra en la figura 6.8.
¿Por qué no es buena idea colocar una caja en una pared limitada? Cuando una caja es llevada hacia una de pared con tales características ya no podrá ser desplazada a otras casillas ajenas a las de la pared, debido a que su movimiento ha sido limitado a 2 direcciones entre ellas opuestas (sur-norte ó este-oeste).
Puede decirse que las paredes limitadas, son una expansión del corte de esquinas y quizá por este mismo camino, se puedan encontrar otro tipo de cortes aún más completos.
CAPÍTULO 7: PRUEBAS DE MSAMA (Nuestro programa solucionador de Sokoban)
Las pruebas fueron realizadas en una computadora con un procesador de 1.3 GHz y 224 MB de Memoria RAM. Los casos se consideran como no resueltos cuando han pasado más de 10 minutos y el programa no ha encontrado una solución.
Los resultados son los siguientes:
7.1 XSokoban (90 Niveles)
Nivel resuelto Tiempo de Ejecución (segundos) Número de Movimientos 1 0.578 258 2 68.484 497 38 504.109 350 77 3 begin_of_the_skype_highlighting 09 350 77 3 end_of_the_skype_highlighting begin_of_the_skype_highlighting 09 350 77 3 end_of_the_skype_highlighting begin_of_the_skype_highlighting 09 350 77 3 end_of_the_skype_highlighting begin_of_the_skype_highlighting 09 350 77 3 end_of_the_skype_highlighting.687 421 78 7.047 404 83 10.687 559
Fig. 7.1. 6 Niveles resueltos por nuestro solucionador del XSokoban test suite en http://stuff.mit.edu/afs/athena/contrib/games/lib/xsokoban/screens/
7.2 Mas Sasquatch (50 Niveles)
Nivel resuelto Tiempo de Ejecución (segundos) Número de Movimientos 1 0.484 200 2 190.718 291
Fig. 7.2. 2 Niveles resueltos por nuestro solucionador con Mas Sasquatch test suite en http://members.aol.com/SokobanMac/levels/masSasText.html
7.3 Microban (155 Niveles)
Nivel resuelto Tiempo de Ejecución (segundos) Número de Movimientos 1 0.000 33 2 0.000 16 3 0.000 41 4 0.000 31 5 0.015 31 6 0.031 107 7 0.031 50 8 0.015 97 9 0.000 30 10 0.015 91 11 0.015 80 12 0.000 49 13 0.015 55 14 0.015 51 15 0.015 43 16 0.093 104 17 0.015 26 18 0.015 73 19 0.015 44 20 0.000 56 21 0.015 19 22 0.015 47 23 0.000 58 24 0.000 35 25 0.015 33 26 0.015 41 27 0.000 52 28 0.000 33 29 0.015 104 30 0.015 23 31 0.015 17 32 0.000 35 33 0.015 51 34 0.015 41 35 0.000 41 36 4.187 172 37 0.015 73 38 0.015 39 39 0.015 85 40 0.016 25 41 0.000 56 42 0.031 70 43 0.093 54 44 0.000 1 45 0.000 53 46 0.000 47 47 0.015 83 48 0.031 73 49 0.046 84 50 0.015 80 51 0.000 46 52 0.015 29 53 0.000 53 54 0.421 84 55 0.015 64 56 0.000 23 57 0.015 62 58 0.015 46 59 0.796 183 60 0.156 251 61 0.046 132 62 0.046 74 63 0.031 101 64 0.092 95 65 0.281 164 66 0.031 93 67 0.015 53 68 0.062 98 69 0.703 104 70 0.031 78 71 0.015 120 72 0.125 115 73 0.062 102 74 0.921 123 75 0.140 98 76 0.765 187 77 1.375 201 78 2.281 167 79 0.000 54 80 0.562 131 81 0.000 56 82 0.015 52 83 2.468 210 84 1.062 241 85 1.578 163 86 0.093 143 87 0.640 155 88 1.421 205 89 2.375 153 90 0.125 74 91 0.000 48 92 0.203 144 93 80.968 155 94 0.031 83 95 0.000 36 96 0.203 98 97 4.078 172 98 80.64 311 99 122.953 349 100 0.593 169 101 0.109 79 102 2.562 160 103 0.031 35 104 0.062 95 105 0.062 77 106 4.453 257 107 0.031 42 108 33.781 252 109 37.875 221 110 0.093 55 111 37.250 216 112 30.968 276 113 14.218 174 114 27.171 273 115 1.328 159 116 0.093 74 117 36.453 274 118 0.906 184 119 0.078 133 120 0.421 219 121 0.578 161 122 136.609 247 123 38.375 340 124 0.234 297 125 2.265 142 126 1.203 113 127 0.171 158 128 0.140 94 129 0.484 114 130 0.890 124 131 0.453 80 132 0.296 177 133 7.453 157 134 3.265 274 135 0.703 151 136 0.890 174 137 12.328 219 138 49.484 230 139 * 140 18.312 294 141 1.093 149 142 1.453 120 143 21.312 252 144 * 145 * 146 * 147 1.076 172 148 0.956 236 149 0.156 94 150 17.296 189 151 7.453 137 152 1.593 293 153 * 154 0.031 429 155 0.046 282
Fig. 7.3. 150 Niveles resueltos por nuestro solucionador del Microban test suite en http://members.aol.com/SokobanMac/levels/microbanText.html
7.4 Análisis de los resultados
Para el análisis compararemos la cantidad de niveles resueltos en casa colección contra 3 de los mejores solucionadores del mundo.
XSokoban BoxSearch resolvió 42 de 90 niveles. Takaken resolvió 86 de 90 niveles. YASS resolvió 75 de 90 niveles. JSoko resolvió 65 de 90 niveles. MSAMA resolvió 6 de 90 niveles.
Desempeño de MSAMA: Muy malo
Mas Sasquatch BoxSearch resolvió 16 de 50 niveles. Takaken resolvió 32 de 50 niveles. YASS resolvió 18 de 50 niveles. JSoko resolvió 18 de 50 niveles. MSAMA resolvió 2 de 50 Niveles
Desempeño MSAMA: Muy malo
Microban BoxSearch resolvió 155 de 155 niveles. Takaken resolvió 155 de 155 niveles. YASS resolvió 155 de 155 niveles. JSoko resolvió 155 de 155 niveles. MSAMA resolvió 150 de 155 niveles.
Desempeño MSAMA: Muy bueno
XSokoban y Mas Sasquatch son unos de los conjuntos de problemas más complicados, MSAMA todavía no tiene nivel para competir. Sin embargo en suites no muy complicadas como Microban tiene un buen rendimiento y esta casi al nivel de cualquier otro solucionador.
Las carencias de nuestra implementación son aparentemente por falta de optimizaciones. En ocasiones se encuentra en posiciones que están perdidas y sigue buscando una solución. Éste tipo de problemas hace que tarde más analizando miles de posiciones que finalmente no le servirán de nada. En las conclusiones y trabajo futuro se amplía más sobre las optimizaciones pendientes.
VIII. REFERENCIAS BIBLIOGRAFÍCAS
Cormen Thomas H., Leiserson Charles E., and Rivest Ronald L. Introduction to algorithms. The MIT Press 2001.
Junghanns Andreas, Schaeffer Jonathan Sokoban: A Challenging Single-Agent Search Problem, Trabajo en Using Games as an Experimental Testbed for AI Research, Conferencia IJCAI-97, Nagoya, Japan, August 1997.
Russell Stuart, Norving Peter Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence. Englewood Cliffs, New Jersey 2003.
<http://sokobano.de/wiki/index.php?title=Solver_Statistics>. Fecha desconocida; última modificación en 21:47, 18 September 2007. Solver Statistics. México. [web en línea]. [con acceso el 10 de Junio de 2008]
APÉNDICE
CÓDIGO DEL SOLUCIONADOR DE SOKOBAN
/*
MSAMA 1.0 Sokoban Solver
IDE: Dev C++ 4.9.9.0
Autor: José Ramón García Alvarado
*/
#include <cstdio>
#include <fstream>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#include <string.h>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;
char mapa[32][32],bmapa[32][32];
short nummapa[32][32],amp[32][32],dirxy[1024][2];
ifstream in("mapa.txt");
vector<short> boxes,box_dest; vector<short>::iterator ite;
map<vector<short>,bool> ClosedList;
short sokop,Nbox=0,pcont=1,maxx=0,maxy=0;;
short moves[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
class node {
public:
node( short ccost, short ch, int cnp, short cpb,vector<short>& cbox ) {
cost=ccost; h= ch; npath=cnp; config=cbox; placedbox=cpb;
};
short cost,h,placedbox;
int npath;
vector<short> config;
};
class path_node {
public:
path_node(int cxy, short cdir, int cb) {
xy=cxy; dir=cdir; back=cb;
};
int xy;
short dir;
int back;
}; vector<path_node> path;
bool operator < (const node &a, const node &b) {
if(a.placedbox==b.placedbox) return a.h+a.cost>b.h+b.cost;
return a.placedbox<b.placedbox;
};
class point_sort {
public:
bool operator () (const short& a, const short& b) {
short da=dirxy[a][0]+dirxy[a][1], db=dirxy[b][0]+dirxy[b][1];
if(da==db) {
if(dirxy[a][0]==dirxy[b][0]) return dirxy[a][1]<dirxy[b][1];
return dirxy[a][0]<dirxy[b][0];
}
return da<db;
};
};
short heur_fun(vector<short> &sit) {
short fx=0;
for(int i=0;i<Nbox;i++)
fx+= ( abs( dirxy[sit[i]][0]-dirxy[box_dest[i]][0] )+
abs( dirxy[sit[i]][1]-dirxy[box_dest[i]][1] ));
return fx;
};
short SokoCanPush( short dx, short dy, short sx, short sy) {
queue<short> cola; memset(amp,-1,sizeof(amp));
cola.push(sx); cola.push(sy); cola.push(0);
while( !cola.empty() ) {
short x= cola.front(); cola.pop();
short y= cola.front(); cola.pop();
short cost= cola.front(); cola.pop();
if(x==dx && y==dy) { amp[x][y]=cost; return cost; }
if( amp[x][y]!=-1 ) continue;
amp[x][y]=cost;
for(int i=0;i<4;i++)
if( mapa[x+moves[i][0]][y+moves[i][1]]==' ' ) {
cola.push(x+moves[i][0]); cola.push(y+moves[i][1]);
cola.push(cost+1);
}
};
return -1;
};
void backtrack_sol( int fin ) {
stack<int> sol,minp;
while( path[fin].back!=-1 ) {
int finback= path[fin].back;
int d= path[fin].dir;
int od= path[finback].dir;
int x= dirxy[path[fin].xy][0]+2*moves[d][0];
int y= dirxy[path[fin].xy][1]+2*moves[d][1];
int bx= dirxy[path[finback].xy][0]+moves[od][0];
int by= dirxy[path[finback].xy][1]+moves[od][1];
int mox= dirxy[path[fin].xy][0];
int moy= dirxy[path[fin].xy][1];
int mx= dirxy[path[fin].xy][0]+moves[d][0];
int my= dirxy[path[fin].xy][1]+moves[d][1];
int mbx= dirxy[path[fin].xy][0]+2*moves[d][0];
int mby= dirxy[path[fin].xy][1]+2*moves[d][1];
mapa[mox][moy]=' '; mapa[mx][my]=' ';
mapa[mx][my]='$'; mapa[mbx][mby]='@';
mapa[mbx][mby]=' ';
SokoCanPush(bx,by,x,y);
int ix=bx,iy=by,nval=amp[bx][by];
while( nval>0 ) {
for(int i=0;i<4;i++)
if( amp[ix+moves[i][0]][iy+moves[i][1]]==nval-1 ) {
ix+=moves[i][0]; iy+=moves[i][1];
minp.push(i);
break;
}
nval--;
};
minp.push((d+2)%4);
while(!minp.empty()) { sol.push(minp.top()); minp.pop(); }
fin= path[fin].back;
};
int d= path[fin].dir;
int x= dirxy[path[fin].xy][0]+2*moves[d][0];
int y= dirxy[path[fin].xy][1]+2*moves[d][1];
int bx= dirxy[sokop][0];
int by= dirxy[sokop][1];
int mox= dirxy[path[fin].xy][0];
int moy= dirxy[path[fin].xy][1];
int mx= dirxy[path[fin].xy][0]+moves[d][0];
int my= dirxy[path[fin].xy][1]+moves[d][1];
int mbx= dirxy[path[fin].xy][0]+2*moves[d][0];
int mby= dirxy[path[fin].xy][1]+2*moves[d][1];
mapa[mox][moy]=' '; mapa[mx][my]=' ';
mapa[mx][my]='$'; mapa[mbx][mby]='@';
mapa[mbx][mby]=' ';
SokoCanPush(bx,by,x,y);
int ix=bx,iy=by,nval=amp[bx][by];
while( nval>0 ) {
for(int i=0;i<4;i++)
if( amp[ix+moves[i][0]][iy+moves[i][1]]==nval-1 ) {
ix+=moves[i][0]; iy+=moves[i][1];
minp.push(i);
break;
}
nval--;
};
minp.push((d+2)%4);
while(!minp.empty()) { sol.push(minp.top()); minp.pop(); }
fin= path[fin].back;
ofstream filesol("solution.txt");
while(!sol.empty()) { filesol<<sol.top()<<endl; sol.pop(); }
filesol.close();
};
bool deathlock() {
for(int i=1;i<pcont;i++) {
int x= dirxy[i][0];
int y= dirxy[i][1];
if( bmapa[x][y]!='.'&& mapa[x][y]!='@' ) {
if( ( (mapa[x][y]!=' '&& mapa[x][y]!='@') &&
(mapa[x+1][y]!=' '&& mapa[x+1][y]!='@') ) &&
( (mapa[x][y+1]!=' '&& mapa[x][y+1]!='@') &&
(mapa[x+1][y+1]!=' '&& mapa[x+1][y+1]!='@') ) ) {
return 1; }
if( ( (mapa[x][y]!=' '&& mapa[x][y]!='@') &&
(mapa[x+1][y]!=' '&& mapa[x+1][y]!='@') ) &&
( (mapa[x][y-1]!=' '&& mapa[x][y-1]!='@') &&
(mapa[x+1][y-1]!=' '&& mapa[x+1][y-1]!='@') ) ) {
return 1; }
if( ( (mapa[x][y]!=' '&& mapa[x][y]!='@') &&
(mapa[x-1][y]!=' '&& mapa[x-1][y]!='@') ) &&
( (mapa[x][y+1]!=' '&& mapa[x][y+1]!='@') &&
(mapa[x-1][y+1]!=' '&& mapa[x-1][y+1]!='@') ) ) {
return 1; }
if( ( (mapa[x][y]!=' '&& mapa[x][y]!='@') &&
(mapa[x-1][y]!=' '&& mapa[x-1][y]!='@') ) &&
( (mapa[x][y-1]!=' '&& mapa[x][y-1]!='@') &&
(mapa[x-1][y-1]!=' '&& mapa[x-1][y-1]!='@') ) ) {
return 1; }
/*if(x-2>=0 && y-2>=0) {
if( ( ( (mapa[x-1][y]!=' '&& mapa[x-1][y]!='@') &&
(mapa[x-1][y]!=' '&& mapa[x-1][y]!='@') ) &&
( (mapa[x][y-1]!=' '&& mapa[x][y-1]!='@') &&
(mapa[x-2][y]!=' '&& mapa[x-2][y]!='@') ) ) &&
( ( (mapa[x][y-2]!=' '&& mapa[x][y-2]!='@') &&
(mapa[x-2][y-1]!=' '&& mapa[x-2][y-1]!='@') ) &&
( (mapa[x-1][y-2]!=' '&& mapa[x-1][y-2]!='@') &&
(mapa[x-2][y-2]!=' '&& mapa[x-2][y-2]!='@') ) ) ) {
return 1; }
}*/
}
}
return 0;
};
void Astar() {
int nstate=0,spec=0;
boxes.push_back(sokop);
priority_queue< node > OpenList;
OpenList.push( node(0,heur_fun(boxes),-1,0,boxes) );
ClosedList[boxes]=1;
while( !OpenList.empty() ) {
node CN = OpenList.top(); OpenList.pop();
for(int i=0;i<Nbox;i++)
mapa[ dirxy[ CN.config[i] ][0] ][ dirxy[ CN.config[i] ][1] ]='$';
mapa[ dirxy[ CN.config[Nbox] ][0] ][ dirxy[ CN.config[Nbox] ][1] ]='@';
if(CN.placedbox==Nbox) { printf("solution\n");
printf("No estados: %d %d apilados: %d \n",path.size(),nstate,OpenList.size());
for(int i=0;i<maxx;i++) puts(mapa[i]);
while( !OpenList.empty() ) OpenList.pop();
backtrack_sol( CN.npath );
break; }
spec++;
if(spec==20000) {
printf("No estados: %d %d apilados: %d \n",path.size(),nstate,OpenList.size());
for(int i=0;i<maxx;i++) puts(mapa[i]); spec=0;
//getchar();
}
for(int i=0;i<Nbox;i++) {
int x=dirxy[ CN.config[i] ][0], y= dirxy[ CN.config[i] ][1];
for(int j=0;j<4;j++)
if( (mapa[ x+ moves[j][0] ][ y+ moves[j][1] ]==' ' ||
mapa[ x+ moves[j][0] ][ y+ moves[j][1] ]=='@')&&
bmapa[ x+ moves[j][0] ][ y+ moves[j][1] ]!='?' ) {
int findway = SokoCanPush( x+moves[(j+2)%4][0],y+moves[(j+2)%4][1],
dirxy[CN.config[Nbox]][0],dirxy[CN.config[Nbox]][1] );
if( findway==-1 ) continue;
vector<short> tcon= CN.config;
ite= lower_bound(tcon.begin(),--tcon.end(),
nummapa[ x ][ y ],point_sort());
tcon.erase(ite);
ite= lower_bound(tcon.begin(),--tcon.end(),
nummapa[ x+moves[j][0] ][ y+moves[j][1] ],point_sort());
tcon.insert(ite,nummapa[ x+moves[j][0] ][ y+moves[j][1] ]);
tcon[Nbox]=nummapa[ x ][ y ];
if(ClosedList[tcon]) continue;
ClosedList[tcon]=1;
for(int i=0;i<Nbox;i++) // Borrar
mapa[ dirxy[ CN.config[i] ][0] ][ dirxy[ CN.config[i] ][1] ]=' ';
mapa[ dirxy[ CN.config[Nbox] ][0] ][ dirxy[ CN.config[Nbox] ][1] ]=' ';
for(int i=0;i<Nbox;i++) // Grabar tcon
mapa[ dirxy[ tcon[i] ][0] ][ dirxy[ tcon[i] ][1] ]='$';
mapa[ dirxy[ tcon[Nbox] ][0] ][ dirxy[ tcon[Nbox] ][1] ]='@';
bool death= deathlock();
for(int i=0;i<Nbox;i++) // Borrar tcon
mapa[ dirxy[ tcon[i] ][0] ][ dirxy[ tcon[i] ][1] ]=' ';
mapa[ dirxy[ tcon[Nbox] ][0] ][ dirxy[ tcon[Nbox] ][1] ]=' ';
for(int i=0;i<Nbox;i++) // Restaurar
mapa[ dirxy[ CN.config[i] ][0] ][ dirxy[ CN.config[i] ][1] ]='$';
mapa[ dirxy[ CN.config[Nbox] ][0] ][ dirxy[ CN.config[Nbox] ][1] ]='@';
if(death) continue;
int cpb=0;
for(int i=0;i<Nbox;i++)
if( bmapa[ dirxy[tcon[i]][0] ][ dirxy[tcon[i]][1] ]=='.') cpb++;
OpenList.push( node(CN.cost+1+findway,heur_fun(tcon),nstate,cpb,tcon) );
path.push_back( path_node( nummapa[ x+moves[j][0] ][ y+moves[j][1] ],
(j+2)%4,CN.npath ) );
nstate++;
}
}
for(int i=0;i<Nbox;i++)
mapa[ dirxy[ CN.config[i] ][0] ][ dirxy[ CN.config[i] ][1] ]=' ';
mapa[ dirxy[ CN.config[Nbox] ][0] ][ dirxy[ CN.config[Nbox] ][1] ]=' ';
};
};
bool BlockedPath(short fx, short fy,short fwall, short fdir, short ite) {
//printf("ite: %d x: %d y: %d\n",ite,fx,fy);
if( mapa[fx][fy]=='#' ) return 1;
if( mapa[fx][fy]!=' ' || bmapa[fx][fy]=='.' ) return 0;
if( mapa[fx+moves[fwall][0]][fy+moves[fwall][1]]!='#' ) return 0;
if( BlockedPath( fx+moves[fdir][0],fy+moves[fdir][1],fwall,fdir,ite+1 ) ) {
bmapa[fx][fy]='?'; return 1;
}
return 0;
};
int main() {
clock_t start, end; start= clock();
string line;
memset(nummapa,-1,sizeof(nummapa));
while( getline(in,line) ) {
strcpy(mapa[maxx],line.c_str()); maxx++;
} maxy= line.size();
for(int i=0;i<maxx;i++)
for(int j=0;j<maxy;j++)
if(mapa[i][j]!='#' && mapa[i][j]!=',') {
if(mapa[i][j]=='$' || mapa[i][j]=='*') Nbox++;
nummapa[i][j]=pcont;
dirxy[pcont][0]=i; dirxy[pcont][1]=j;
pcont++;
}
boxes.reserve( Nbox+2 ); box_dest.reserve( Nbox+2 );
for(int i=0;i<maxx;i++)
for(int j=0;j<maxy;j++) {
if(mapa[i][j]=='$' || mapa[i][j]=='*') {
ite= lower_bound(boxes.begin(),boxes.end(),nummapa[i][j],point_sort());
boxes.insert(ite,nummapa[i][j]);
if(mapa[i][j]=='*') mapa[i][j]='.';
else mapa[i][j]=' ';
}
if(mapa[i][j]=='@' || mapa[i][j]=='+' ) {
sokop= nummapa[i][j];
if(mapa[i][j]=='+') mapa[i][j]='.';
else mapa[i][j]=' ';
}
if(mapa[i][j]=='.') {
ite= lower_bound(box_dest.begin(),box_dest.end(),nummapa[i][j],point_sort());
box_dest.insert(ite,nummapa[i][j]); mapa[i][j]=' '; bmapa[i][j]='.'; }
}
for(int i=0;i<maxx;i++)
for(int j=0;j<maxy;j++)
for(int k=0;k<4;k++)
if( (mapa[i][j]!='#' && mapa[i][j]!=',') && bmapa[i][j]!='.' )
if(mapa[i+moves[k][0]][j+moves[k][1]]=='#' &&
mapa[i+moves[(k+1)%4][0]][j+moves[(k+1)%4][1]]=='#') {
BlockedPath(i,j,k,(k+3)%4,0);
BlockedPath(i,j,(k+1)%4,(k+2)%4,0);
bmapa[i][j]='?';
}
for(int i=0;i<maxx;i++) {
printf("\n");
for(int j=0;j<maxy;j++) printf("%c", ((bmapa[i][j]=='?')? '?': mapa[i][j]) );
}
/*for(int i=0;i<maxx;i++) {
puts(mapa[i]);
} getchar(); getchar();*/
Astar(); end=clock();
double dif= end-start;
printf("\t EXECUTION TIME: %.5lf seg",(double)( dif/1000.0 ));
getchar();
}
