MSAMA Sokoban Solver

From Sokoban Wiki

Revision as of 11:06, 3 January 2011 by Briandamgaard (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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)

Contents

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:

  1. Solucionadores que solo tratan de obtener una solución.
  2. Solucionadores que tratan de obtener una buena solución.
  3. 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í:

  1. a tiene menor número de cajas acomodadas en destinos que b
  2. 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í:

                1. ######## # Pared
  1. 1 2 3 4$.# #1 2 3 4 5 6 # @ Sokoban
  2. 0 1 2 3 4-1# #7 8 9 101112# $ Cajas
  3. $# 3 4-1-1# #13#14151617# . Destinos
  4. -1-1 4-1-1-1# #181920212223#
                1. ########
                                 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:

  1. 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.
  2. 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 14:43, November 28, 2010. 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();
 }
Personal tools