Practica Tgr 3 Sokoban PDF

Preview

Summary

TGR basado en el videojuego de sokoban...

Description

Paradigmas de Programaci´ on – TGR 3 SOKOBAN (Warehouse Keeper) Resumen Sokoban (s¯ oko − ban, warehouse keeper, depositario) es un videojuego rompecabezas, en el cual el jugador representa a un empleado de almacen que empuja cajas para tratar de colocarlas en unas determinadas ubicaciones de almacenamiento. Sokoban fue creado en 1981 por Hiroyuki Imabayashi, y publicado en 1982 por Thinking Rabbit, una compa˜ n´ıa de software con base en Takarazuka, Jap´on. El objetivo de este TGR es escribir un programa que resuelva de modo autom´atico tableros sencillos del juego Sokoban.

1

Reglas del juego

El juego se desarrolla en un tablero de casillas, donde cada casilla es suelo o es pared. Algunas casillas suelo contienen cajas, y algunas est´an marcadas como ubicaciones de almacenamiento o destinos. El jugador est´a confinado en el tablero, y puede moverse horizontal o verticalmente hacia las casillas suelo vac´ıas (pero nunca a trav´es de paredes o cajas). El jugador se puede mover tambi´en a una casilla ocupada por una caja, en cuyo caso la empuja hacia la casilla siguiente. Las cajas no pueden empujar a otras cajas o a paredes. Tampoco se puede tirar de las cajas, solo est´a permitido empujarlas. El n´umero de cajas es igual al n´ umero de destinos. El rompecabezas queda resuelto cuando todas las cajas est´ an en los destinos.

Figura 1: Interfaz en modo Game, lista para jugar el tablero level-08.brd

2

Interfaz gr´ afica

Junto con el presente enunciado, se proporciona una interfaz gr´afica escrita en OCaml (sokoban.ml), que permite jugar partidas de Sokoban. Dicha interfaz est´a implementada usando 1

u ´nicamente las primitivas gr´aficas de OCaml, de tal forma que para poder usarla es suficiente con tener instalada la librer´ıa graphics.cma y compilarla con esta orden: ocamlc -o sokoban graphics.cma sokoban.ml Si el comando sokoban es lanzado sin argumentos, escribir´a en pantalla todas las opciones de manejo de la interfaz (las cuales se muestran tambi´en en el ap´endice A). Si el comando es lanzado contra un fichero de texto que contenga una descripci´ on adecuada de un tablero (por ejemplo, sokoban level-08.brd), la interfaz arrancar´a en modo Game y permitir´ a al usuario jugar su partida, es decir, intentar resolver dicho tablero. La figura 1 muestra el aspecto de la interfaz y la descripci´on textual del tablero que est´ a en juego. Las casillas naranjas son paredes, las verdes son suelo, los puntos azules marcan los destinos, los bloques marrones son las cajas pendientes de colocar, los bloques azules son las cajas ya colocadas, y la cruz es el jugador. Y si el comando es lanzado contra un tablero y contra otro fichero de texto adicional que contenga un plan de acciones (por ejemplo, sokoban level-08.brd level-08.sol), la interfaz arrancar´a en modo Solver y permitir´ a al usuario efectuar una comprobaci´on visual de si dicho plan de acciones constituye o no una soluci´ on de la partida. En este caso, el jugador no podr´a ser movido libremente, sino de acuerdo con las acciones marcadas en el plan. Si el plan no constituye una soluci´on, la simulaci´on quedar´a bloqueda y no podr´ a avanzar. La figura 2 muestra la resoluci´ on del tablero level-08.brd, tras finalizar correctamente la ejecuci´ on de las 55 acciones contenidas en el fichero de plan level-08.sol.

Figura 2: Interfaz en modo Solver, tras ejecutar el plan level-08.sol

3

Objetivo

Precisamente, el objetivo de este TGR es escribir un programa que resuelva de modo autom´atico tableros del juego Sokoban. O dicho coloquialmente, escribir un programa que reciba como entrada un fichero de texto .brd (board, tablero), y genere como salida otro fichero de texto .sol (solution, soluci´on), cuyo contenido sea una secuencia de acciones que resuelva el tablero de entrada. Las 2

posibles acciones deben corresponderse con los posibles movimientos del jugador (Up, Down, Left, Right), y cada una de ellas debe ir escrita en una l´ınea independiente. V´ease el ap´endice A para obtener m´as detalle sobre el formato de los ficheros de entrada y de salida. Junto con el presente enunciado, se proporcionan tambi´en 15 tableros de prueba (ficheros level-01.brd a level-15.brd). Estos tableros corresponden a los 15 niveles de una de las versiones m´as populares del juego en sus comienzos, y presentan diferentes grados de dificultad a la hora de intentar solucionarlos, ya sea manualmente jugando partidas, o bien autom´aticamente ejecutando nuestro programa objetivo. El ap´endice B muestra todos estos tableros, indicando el n´ umero de pasos necesarios para resolver cada uno de ellos de forma o´ptima, es decir, el n´ umero de pasos de la soluci´on m´as corta de entre todas las posibles, as´ı como una estimaci´on del grado de dificultad para obtener dicha soluci´ on de forma autom´ atica.

4

Complejidad del problema

Sokoban ha sido estudiado con detalle desde el punto de vista de su complejidad computacional, y se ha demostrado que el problema de resolver los acertijos de Sokoban es NP-hard y PSPACEcomplete (v´ease este enlace para m´as informaci´ on). Este hecho hace que el problema sea muy interesante para los investigadores en inteligencia artificial, ya que la resoluci´on de Sokoban se puede comparar con la planificaci´on automatizada que debe realizar un robot que mueva cajas en un almac´en. Sokoban es dif´ıcil no solo por su factor de ramificaci´on (que es comparable al del ajedrez), sino tambi´en por la gran profundidad de su a´rbol de b´ usqueda. Algunos niveles pueden extenderse enormemente, y cada iteraci´on puede requerir un n´ umero exponencialmente creciente de movimientos y empujes. Los jugadores humanos expertos utilizan principalmente la heur´ıstica. Por lo general, son capaces de descartar r´apidamente l´ıneas de juego in´ utiles o redundantes, y reconocer patrones y submetas, reduciendo dr´asticamente la cantidad de b´ usquedas. Algunos acertijos de Sokoban se pueden resolver autom´aticamente mediante el uso de complejos algoritmos de b´ usqueda, generalmente mejorados mediante t´ecnicas que integran conocimiento espec´ıfico del dominio. Sin embargo, los niveles m´ as complejos de Sokoban est´ an fuera de alcance incluso para los mejores solucionadores automatizados. En cualquier caso, los juegos de pruebas Sokoban para algoritmos de inteligencia artificial est´an formados por decenas de tableros de dimensiones que alcanzan las 20 columnas y/o las 20 filas, mientras que en este TGR utilizaremos tableros de dimensiones bastante m´ as reducidas. De esta forma, estaremos considerando una versi´on m´as manejable del problema, la cual es abordable incluso con sencillos algoritmos de b´ usqueda basados principalmente en la fuerza bruta, si acaso apoyados por un peque˜ no n´ umero de sencillas heur´ısticas. Se trata, pues, de un ejercicio de introducci´on a los algoritmos b´ asicos de b´ usqueda. Eso s´ı, a´ un con todo, si bien una buena implementaci´ on de estos algoritmos b´asicos puede resolver cada uno de nuestros 15 tableros de prueba en cuesti´on de segundos, una mala implementaci´ on podr´ıa tardar horas. Es importante, por tanto, reflexionar sobre las ideas que se comentan a continuaci´on.

5

Sugerencias de implementaci´ on

Tal y como se comentaba anteriormente, se presentan a continuaci´ on algunas ideas que podr´ıan orientar al estudiante durante la implementaci´ on de su programa objetivo. Debe quedar claro que, si bien estas ideas no son de obligado cumplimiento, s´ı es conveniente considerarlas y comprenderlas, as´ı como saber valorar las posibles ventajas y desventajas, tanto de su aplicaci´ on directa, como de la aplicaci´on de cualquiera de sus alternativas.

3

5.1

Representaci´ on de los estados

Puede resultar muy conveniente definir un tipo de dato, llam´emosle state, capaz de representar cualquier posible configuraci´on del tablero en juego. En este punto, seguramente estaremos tentados de utilizar una matriz que albergue en cada celda el contenido de cada casilla del tablero. Sin embargo, es muy posible que de esta forma estemos almacenando mucha informaci´ on redundante. Y adem´ as, a medida que la resoluci´ on del problema avance desde el estudio del estado inicial, ser´a necesario ir almacenando otros muchos estados: los estados pendientes de procesar, y los estados que ya han sido generados en alg´ un paso anterior, y que por tanto no deben ser procesados de nuevo, ya que estar´ıamos repitiendo c´alculos y/o corriendo el riesgo de que el proceso de b´ usqueda entre en un lazo sin fin. Ocurre entonces que una estructura imperativa, como puede ser la matriz, exigir´a la creaci´on de nuevos valores y la copia expl´ıcita de datos de unos valores a otros, a la hora de ir manteniendo esas colecciones de estados pendientes y de estados ya visitados. Todo esto podr´ıa resultar enormemente costoso. As´ı pues, se anima al estudiante a que reflexione sobre la posibilidad de utilizar una estructura alternativa que sea funcional, y que adem´as almacene solo las partes m´ oviles del problema (es decir, la posici´on del jugador y la lista de las posiciones de las cajas). Todos los dem´ as elementos (casillas suelo, paredes y destinos) son elementos fijos, no variar´an a lo largo de la ejecuci´ on del programa, y podr´ıan por tanto mantenerse en valores constantes de cualquier tipo.

5.2

Representaci´ on de las acciones y de los planes

Puede resultar muy conveniente tambi´en definir otro tipo de dato, llam´emosle action, que represente todas las operaciones que pueden producir variaciones en el tablero, o lo que es lo mismo, todas las acciones que permiten pasar de un estado a otro durante el proceso de b´ usqueda de una soluci´on. As´ı mismo, resultar´ a u ´til tambi´en la definici´on de un tipo de dato plan, que simplemente ofrezca la posibilidad de agrupar varias acciones en un u ´nico valor. Por simplicidad, la recomendaci´on en este punto es considerar como acciones los cuatro movimientos que puede efectuar el jugador: arriba, abajo, izquierda y derecha. No obstante, es importante hacer notar que ´este no es el u ´nico planteamiento posible. La alternativa m´as obvia ser´ıa considerar directamente los posibles movimientos de todas aquellas cajas que sean alcanzables desde la posici´ on del jugador (aunque habr´ıa que a˜ nadir a los planes de acciones los movimientos necesarios para que el jugador alcance cada caja en cuesti´ on). Este planteamiento se basa en el hecho de que las diferencias notables entre los diversos estados por los que puede pasar el problema vienen producidas esencialmente por los movimientos de las cajas, y en menor medida por los movimientos del jugador. La elecci´on entre una u otra alternativa se deja al criterio del estudiante, si bien se advierte de que este segundo planteamiento ser´ıa bastante m´as complicado de programar.

5.3

Ejecuci´ on de las acciones

Puede ser interesante definir una funci´on, llam´emosla new state, que dada una acci´on y una configuraci´on actual del tablero, devuelva la nueva configuraci´ on resultante de aplicar dicha acci´on sobre el tablero. Es decir, dado un valor de tipo action y otro valor de tipo state, esta funci´on devuelve otro nuevo valor tambi´en de tipo state. Si la acci´on no es aplicable al estado actual, el comportamiento de la funci´on queda al criterio del programador. Una opci´on puede ser que la funci´on active una excepci´on, la cual entonces debe ser interceptada y tratada adecuadamente por el proceso de b´ usqueda, para que el programa no aborte descontroladamente, y siga probando otras acciones y otras configuraciones. Una alternativa puede ser que la funci´ on no devuelva un valor de tipo state, sino un valor de tipo state option. Es decir, Some st, cuando la aplicaci´ on de la acci´on produzca el nuevo 4

estado st; o bien None, cuando la aplicaci´ on de la acci´on no sea posible. Otra alternativa ser´ıa que la funci´on recibiera una lista de acciones, por ejemplo, el conjunto completo de las cuatro acciones antes mencionadas (arriba, abajo, izquierda y derecha), y devuelva una lista de nuevos estados. Si ninguna acci´on fuera aplicable, la funci´on devolver´ıa la lista vac´ıa.

5.4

Algoritmos de b´ usqueda

Como dec´ıamos anteriormente, este TGR constituye un ejercicio introductorio a los algoritmos b´asicos de b´ usqueda. En este contexto, denominaremos espacio de soluciones al esquema que marca la evoluci´on de los diferentes estados por los que va pasando nuestro problema al ejecutar todas las posibles acciones. Asumiendo entonces que nuestro espacio de soluciones pueda tener una representaci´on arborescente, las dos principales estrategias simples de b´ usqueda son la b´ usqueda en anchura (breadth-first search) y la b´ usqueda en profundidad (depth-first search). La b´ usqueda en anchura explora el espacio de soluciones agotando los niveles del a´rbol. Es decir, procesa todos los nodos de profundidad n antes de pasar a procesar los nodos de profundidad n + 1. O dicho de otro modo, tras procesar un nodo, pasamos a procesar sus hermanos antes que sus hijos. En t´erminos de estructuras de programaci´on habituales, este m´etodo de b´ usqueda podr´ıa resolverse utilizando una cola de espera (que en OCaml podr´ıa impementarse mediante dos listas). Su principal desventaja viene dada por su complejidad temporal y espacial, ya que ambas son exponenciales con respecto a la profundidad del nivel que estamos explorando. Sin embargo, este algoritmo es completo, es decir, si existe soluci´ on, la encuentra. Y adem´as es o´ptimo, es decir, encuentra soluciones a distancia m´ınima de la ra´ız, lo que se corresponde con los planes de acciones m´as cortos de entre todos los posibles. En la b´ usqueda en profundidad, tras procesar un nodo, se procesan sus hijos antes que sus hermanos. Es decir, este algoritmo tiende a explorar el espacio de soluciones agotando ramas completas del a´rbol. Haciendo referencia nuevamente a las estructuras de datos cl´asicas, este algoritmo podr´ıa programarse utilizando una pila (lo cual en OCaml puede ser equivalente al uso de una lista o del propio stack recursivo de la m´ aquina). Su complejidad temporal tambi´en es exponencial, ya que en el peor de los casos podr´ıa ser necesario procesar todos los nodos del a´rbol. Sin embargo, su complejidad espacial es lineal con respecto a la longitud de la rama m´as larga, ya que en todo momento almacena u ´nicamente los nodos de la rama que est´ a siendo explorada. En principio, la busqueda en profundidad no es o´ptima ni completa. No es o´ptima porque nada garantiza que la primera soluci´ on encontrada sea de longitud m´ınima. Y no es completa porque, en determinadas circunstancias, el proceso de b´ usqueda podr´ıa quedarse explorando indefinidamente una misma rama. No obstante, se puede eliminar este problema imponiendo un l´ımite m´ aximo a la profundidad de b´ usqueda, o evitando el estudio de nodos que ya han sido procesados previamente. El presente TGR se centra en la obtenci´ on de planes o´ptimos. Por lo tanto, la recomendaci´ on es utilizar un algoritmo de b´ usqueda en anchura. No obstante, evitaremos tambi´en el procesado de nodos o estados que ya hayan sido visitados anteriormente. El motivo es que el tratamiento de estados repetidos no aporta nada a la obtenci´on de planes o´ptimos, porque: si el estado ya apareci´ o en niveles superiores, su distancia a la ra´ız desde el nivel actual ser´ a mayor; y si ya apareci´ o en el nivel actual, su distancia a la ra´ız ser´a la misma. Y adem´as, a medida que avanza el proceso de b´ usqueda, evitar el procesamiento de estados ya visitados aten´ ua el crecimiento exponencial del n´ umero de nodos en cada nivel. En resumen, una buena gesti´ on de la colecci´ on de estados ya visitados puede ser clave para el rendimiento de nuestro algoritmo de b´ usqueda. Es por ello que se recomienda leer atentamente la secci´ on 5.7, dedicada principalmente a esta problem´atica. Por u ´ltimo, cabe decir que las b´ usquedas en anchura y en profundidad que hemos descrito se basan en la enumeraci´ on sistem´atica de las posibles configuraciones del problema. Por lo tanto, podr´ıan catalogarse dentro de los m´etodos de fuerza bruta, o tambi´en dentro de los denominados algoritmos de b´ usqueda ciega o no informada. Sin embargo, tal y como ya esbozamos anteriormente, y aunque se sale del a´mbito del presente trabajo, es importante aclarar que existen 5

algoritmos de b´ usqueda mucho m´ as complejos y sofisticados, basados en estrategias iterativas y/o bidireccionales, en la asignaci´ on de pesos o costes a las diferentes ramas del a´rbol, en la integraci´ on de informaci´on espec´ıfica del dominio, etc. (v´ease este enlace para m´as informaci´ on). En cualquier caso, todo lo expuesto anteriormente debe ser tenido en cuenta a la hora de implementar una funci´ on, llam´emosla build plan, que dado un estado inicial del problema (jugador y cajas en las posiciones indicadas por el tablero proporcionado en la entrada) y un estado final (cajas en los destinos), devuelva un plan de acciones que permita llegar de uno a otro de la forma m´as eficiente posible. Si no existiera un plan capaz de hacer esto, el comportamiento de la funci´on queda al criterio del programador.

5.5

Escritura de las acciones y de los planes

Resultar´a u ´til definir una funci´on, llam´emosla print action, que, dada una acci´ on, escriba su nombre en un fichero de salida. Los nombres que debe escribir esta funci´ on para cada una de las acciones son: Up, Down, Left y Right. Convendr´ a entonces definir otra funci´on, llam´emosla print plan, que dado un plan de acciones y utilizando la funci´on anterior, escriba en un fichero los nombres de todas las acciones que forman el plan, cada una de ellas en una l´ınea independiente. Es admisible tambi´en que todas estas escrituras sean realizadas sobre la salida est´andar. Si se desea registrarlas en un fichero, siempre podr´ a hacerse redireccionando la salida est´ andar hacia ese fichero.

5.6

Heur´ısticas

En este contexto, el t´ermino heur´ısticas hace referencia al conjunto de reglas emp´ıricas que pueden ayudar a encontrar la soluci´ on a nuestro problema. Se trata, por tanto, de m´etodos menos rigurosos, pero igualmente efectivos, que pueden acelerar los procesos de b´ usqueda. M´as concretamente, en los tableros Sokoban, debe evitarse, por ejemplo, la colocaci´on de una caja en una esquina que no coincida con un destino. Aunque se puedan efectuar acciones sobre el resto de cajas, y por lo tanto se puedan generar nuevas configuraciones, el tablero ya no podr´ a ser resuelto, porque es imposible sacar la caja de la esquina y llevarla a un destino. Esta simple regla reduce enormemente el n´ umero de estados generados (del orden de un 75%). Se anima al estudiante a que integre esta regla en su programa, y a que investigue la existencia de otras reglas similares que sean capaces tambi´en de simplificar las b´ usquedas.

5.7

Almacenamiento eficiente de los estados y de las acciones

Tal y como se ha esbozado anteriormente, la b´ usqueda en anchura puede implementarse con una cola de espera, o bien con dos listas: una que almacenar´ıa los estados pendientes de procesar en el nivel actual del espacio de b´ usqueda; y otra que almacenar´ıa los nuevos estados que van siendo generados a partir de los de la primera lista, y que por tanto pertenecen al nivel siguiente. Una vez procesados todos los estados de la primera lista, dicha lista es descartada, la segunda lista pasa a ser el nuevo nivel actual, y el nuevo nivel siguiente se inicializa a la lista vac´ıa. Comienza entonces una nueva iteraci´on del algoritmo de b´ usqueda, que procesa los estados de la primera lista y almacena en la segunda lista los nuevos estados obtenidos. Este proceso se repite hasta que se encuentra una soluci´on, o hasta que se alcanza una situaci´ on en la que que no se pueden generar nuevos estados, quedando vac´ıas ambas listas. Esta si...