FAQ sobre DCColorSort

[dfloreaa]

¿Qué encontrarán aquí? 📄

Aquí podrán encontrar preguntas frecuentes sobre la actividad de la tarea DCColorSort 🧪 y un par de explicaciones que les ayudarán a comprender mejor el flujo del programa y a desarrollar su tarea ✨.

Para mantener este espacio ordenado les pido hacer consultas sobre la tarea en las issues del repositorio del curso y no en los comentarios de esta issue. (Consultas sobre el contenido del FAQ si son aceptadas :) )

Sobre el flujo del programa 🛣️

El juego de BallSort es completamente manejado por la clase BallSortGame() del archivo BallSortBack.py. Una vez generada una instancia del juego, podemos cargar un mapa en formato JSON utilizando su método load_map().

Ball Sort se encuentra modelado según "estados". Cada estado corresponde a una distribución de las bolas dentro de los tubos de ensayo y las transiciones entre ellas vienen dadas por los movimientos válidos que podemos jugar desde un determinado estado.

Podemos obtener una tupla con información sobre posibles estados futuros según el método del juego get_valid_moves(). Este método retorna una lista de tuplas que contienen tres elementos: [new_state, [from_idx, to_idx], cost]:

• new_state: Corresponde al nuevo estado que se obtendría si ejecutamos la acción asociada.
• [from_idx, to_idx]: Corresponde a la acción asociada a la tupla, indica desde qué tubo vamos a sacar una bola (from_idx) y en cuál vamos a colocarla (to_idx).
• cost: Indica el costo de llevar a cabo la determinada acción, en este caso, todos los movimientos válidos tienen costo 1, pero lo indicamos ya que hay otros problemas en donde este no es el caso.

Suponiendo que nuestro juego (instanciado bajo game) se encuentra en un estado $s$, podemos obtener todas las acciones válidas posibles desde este estado mediante la línea valid_moves = game.get_valid_moves(). Luego, si deseamos ejecutar alguna de estas acciones (por ejemplo, la primera) y pasar a un nuevo estado, podemos hacerlo mediante el método make_move(from_idx, to_idx).

action = valid_moves[0][1] (extraemos la acción del primer elemento de valid_moves) game.make_move(action[0], action[1])

Alternativamente, podemos actualizar directamente el estado del juego (se recomienda hacer esto en el algoritmo A*): new_state = valid_moves[0][0] (extraemos el estado al que llegaríamos del primer elemento de valid_moves) game.current_state = new_state

De este modo, nuestro juego ha ejecutado la acción action y ha pasado a un nuevo estado.

La premisa del problema de búsqueda es ir probando todas las acciones posibles hasta llegar a un estado final (ganar el juego). El algoritmo de A* nos permite además priorizar estudiar soluciones de menor costo (número de movimientos totales) antes que aquellas que podrían tener un mayor costo.

En líneas generales, nuestro algoritmo de búsqueda buscará todos los movimientos posibles desde un estado inicial $s_0$, luego, desde cada estado al que se podría llegar buscaremos nuevamente todos los movimientos posibles, ordenándolos desde aquel que nos acerque más a la solución hasta aquel que menos lo hace. Así hasta que el estado alcanzado sea la solución.

Objetivos de la tarea 🎯

Para trabajar en su tarea deberán editar dos archivos, BallSortSolver.py y heuristics.py. El primero se encarga de llevar a cabo la búsqueda de A* sobre el juego, mientras que el segundo se encarga de la implementación de las heurísticas que este algoritmo utiliza.

BallSortSolver.py

En este archivo se contiene a la clase AStarSolver(), que ejecuta la búsqueda sobre una instancia del juego en la clase BallSortGame().

A) Uso de la clase Node 📦:

Cada estado dentro del juego deberá tener un nodo asociado en el problema de búsqueda, estos pueden ser instanciados según la clase Node del archivo node.py. Un nuevo nodo deberá ser instanciado de la siguiente forma:

Node(child_state, parent_node, action) con:

• child_state: El estado representado por el nodo.
• parent_node: El nodo desde el que se provino para llegar al nodo actual (el nodo asociado al estado anterior).
• action: La acción tomada para poder llegar de parent_state a child_state (una lista con primer elemento el índice del tubo al que se le saca una bola y segundo elemento el índice del tubo al que se movió esta bola).

Es importante notar que cada vez que deseemos expandir un nodo deberemos actualizar el estado actual del juego para coincidir con el estado del nodo expandido. Por lo que si obtenemos un nodo desde nuestro open utilizando node = self.open.extract(), deberemos actualizar el estado actual del juego mediante la línea self.game.current_state = node.state.

Podremos obtener todos los estados hijos del actual mediante el método .get_valid_moves() del objeto BallSortGame() contenido en self.game e iterar sobre todos sus valores (listas de 3 valores del tipo [child_state, action, cost]). Un nuevo nodo podrá ser instanciado como Node(child_state, node, action) y deberá actualizar su h según el valor de la heurística utilizada sobre él.

Recuerden que cada vez que visitamos un nodo (ya sea por primera vez o lo visitamos nuevamente por un camino de menor costo), deberemos actualizar el valor de la acción asociada al nodo, su valor de g y su valor F, que será almacenado bajo su atributo .key.

Por último, cada nodo de la clase Node posee un método llamado .trace(), este método se encarga de devolver una tupla (s, actions), donde s corresponde a un string que representa los pasos llevados a cabo para encontrar una solución, mientras que actions corresponde a una lista con estos movimientos (en orden, desde primero a último).

Al encontrar una solución, la búsqueda deberá retornar el output al aplicar .trace() sobre el nodo objetivo. Además del número de expansiones llevadas a cabo y el tiempo total de búsqueda.

return node.trace(), self.expansions, self.end_time - self.start_time

(O bien return None, self.expansions, self.end_time - self.start_time si no encontró una solución)

B) Uso de la clase BinaryHeap 🌳:

BinaryHeap es una estructura de datos que permite ordenar los nodos encontrados según su valor F (contenido en node.key).

Dentro del código es instanciado bajo self.open y contendrá todos los nodos por expandir dentro del algoritmo. Para su uso es importante que conozcan los siguientes métodos:

• .clear(): Permite vaciar la estructura completa.
• .is_empty(): Retorna un booleano indicando si la estructura está vacía o no (no quedan nodos por expandir).
• .extract(): Permite extraer el elemento Node con menor valor asociado a su key.
• .insert(node): Permite insertar el nodo node al heap, reordenándolo en el proceso.

C) Información miscelánea ℹ️:

• Podemos medir el tiempo desde el comienzo hasta el fin de nuestra implementación (en segundos) utilizando el método time.process_time() (debemos importar la librería time), almacenando el tiempo del comienzo de nuestra búsqueda en un atributo (por ejemplo, self.start_time) y el tiempo de término en otro (por ejemplo, self.end_time). En este caso, el tiempo total de ejecución está dado por self.end_time - self.start_time.

• El número de expansiones llevadas a cabo corresponde a un entero instanciado al comienzo de nuestra clase como cero, bajo el atributo self.expansions. Cada vez que expandamos un nodo (extraigamos un nodo desde self.open), deberemos sumarle uno a este contador.

• La disposición de cada estado puede ser representado según un string utilizando el método __str__() de la clase State. Ahora bien, si deseo tener alguna forma de identificar a este estado en particular (por ejemplo, para revisar si ya fue visitado anteriormente, wink, wink ;) ), para una búsqueda no óptima (como la que es guiada por una heurística no admisible) también se deberá considerar el estado desde el que se proviene para llegar a este. Entonces, una representación para el estado puede ser state.from_state.__str__() + state.__str__().

heuristics.py

En este archivo se definen las distintas heurísticas con las que se puede ejecutar la búsqueda de A*.

Sin importar de qué heurística se trate, cada una de ellas recibirá un único input; el estado actual del juego, una instancia de la clase State, y deberá retornar una heurística estimando el costo para llegar a una solución del juego.

A) El estado del juego State 🎮:

Cada vez que accedamos al estado actual del juego nos encontraremos con una instancia de la clase State, definida en el archivo BallSortBack.py.

Si bien esta clase contiene múltiples atributos, aquel con que deberás trabajar será su atributo .tubes, el cual se trata de una lista que contiene a otras listas, cada una de ellas representando a un distinto tubo del juego.

Por ejemplo, el siguiente layout:

Sería descrito por state.tubes = [[1,1,0], [0,0,1], [0,1]] (el último elemento de una lista es la bola de más arriba)

Mientras que cada lista corresponde a un tubo distinto, cada número corresponderá a un color de bola distinto.

Recomendaciones 😉

1. Les recomiendo FUERTEMENTE implementar el algoritmo A* utilizando la heurística heuristics.no_heuristic para comenzar la tarea.

2. Si les quedan dudas respecto a la tarea, el flujo, por donde partir o el algoritmo de A*, revisen el FAQ y si su problema no ha sido respondido antes, creen una issue al respecto.

3. Para debuggear, generen sus propios tests utilizando el archivo entregado puzzle_generator.py y usen puzzles simples donde pueden identificar la solución óptima de forma intuitiva.

4. Implementen ambas heurísticas, no debería tomarles mucho tiempo y es una manera sencilla de sumar puntaje aún cuando su algoritmo no funcione correctamente.

FAQ (Preguntas frecuentes) ❓:

Esta sección será actualizada periódicamente con las consultas más frecuentes o relevantes sobre DCColorSort, por favor, revísenla constantemente al trabajar en su tarea, ya que puede ser de gran ayuda.

1. ¿Qué debe retornar el método AStarSolver.search()? (#32)

La idea es que este método retorne una tupla de tres elementos: return node.trace(), self.expansions, self.end_time - self.start_time
Donde el único elemento realmente necesario para la solución (y poder visualizarla) es el output del método .trace() sobre el nodo final al resolver el puzzle, esto corresponde a una lista con todos los movimientos realizados para llegar a este estado desde el estado inicial.
self.expansions corresponde al número total de expansiones llevadas a cabo para completar la búsqueda (se le suma uno cada vez que expandimos un nodo), mientras que la última variable corresponde al tiempo demorado en encontrar una solución. Ambos sirven para mantener rastro del desempeño del algoritmo y poder contrastar entre distintas heurísticas.

2. Sobre repeated_color_heuristic (#33)

• ¿Cómo debería funcionar esta heurística en caso de que en un tubo todas las bolas sean distintas?

  Intuitivamente, la heurística retorna el mínimo número de movimientos necesarios para poder remover todas las bolas de un tubo hasta que sean todas de un mismo color (sin considerar su orden). Tomando esto en cuenta, la salida deberá ser len(tubo) - 1.

• ¿Qué ocurre cuando hay más de un color con la misma cantidad? (Ej. [4, 4, 3, 6, 3])

  Similar al caso anterior, deberemos retornar el mínimo número de movimientos hasta que solo queden bolas de un color, en el caso particular de [4, 4, 3, 6, 3] este sería 3.

3. ¿A qué se refieren con demostrar la admisibilidad de una heurística? (#33)

Tal como fue visto en la Ayudantía 6, una heurística será considerada admisible si la estimación que provee la heurística h entre dos estados no sea nunca superior al costo óptimo para llegar desde uno a otro. Es decir, $$h(s, s') \leq h^*(s, s')$$

4. ¿Cómo funciona la Wagdy heuristic? (#37)

La intuición detrás de ella es que para cada par de bolas consecutivas que tengan distinto color, tomará al menos 2 pasos para poder hacer que la bola de arriba sea idéntica a la de abajo (uno para sacarla y uno para colocarla de vuelta). Por ejemplo, para un tubo de forma [1,1,2,2,3,4] la heurística retornaría el valor 6, dado que existen 3 pares distintos de pelotas consecutivas distintas ((1,2), (2,3), (3,4)).

5. ¿Por qué mi búsqueda se demora tanto? (#43)

Primero, revisa que tus algoritmos y heurísticas se encuentren bien implementados, comienza con ejemplos pequeños que puedes generar usando el archivo puzzle_generator.py y revisando cómo se estan expandiendo y almacenando los estados. Notamos que usar la heurística repeated_color_heuristic() puede tomar mucho tiempo en llegar a una solución, por lo que si tu búsqueda es mayor a 2 minutos, simplemente repórtala como 2 minutos en el punto 1.5 (comparación de heurísticas) (entenderemos que esto significa TIMEOUT).

6. ¿Cuántas ejecuciones debo hacer? (#43)

En la actividad del item 1.5 se les pide "tomar una muestra de al menos 5 ejecuciones en cada caso". Esto se refiere a tomar una muestra para cada uno de los 5 mapas de la carpeta /maps para cada combinación algorimto-heurística (A y Lazy A, wagdy_heuristic y repeated_color_heuristic). Por lo que en total tendrías 20 ejecuciones en mapas distintos.

7. Mi BinaryHeap arroja error por quedarse sin memoria (IndexError) (#40)

Esto se debe a que la búsqueda expande más estados de los que se pueden almacenar dentro de self.open, esto puede ser debido a la naturaleza del mapa o bien por que el tiempo que la búsqueda ha tomado es mucho y ha expandido muchos estados. En cualquiera de los casos, la manera a proseguir es la siguiente:

1. Incrementa el tamaño de tu open al instanciarla, BinaryHeap(max_size = 20000000) por ejemplo.
2. Si la ejecución ya fue mayor a 2 minutos, simplemente interrúmpela y considerala un TIMEOUT en tu informe.

8. ¿Debo usar el parámetro HEURISTIC_PONDERATOR? (#48)

No, o bien debe permanecer igual a 1. El parámetro HEURISTIC_PONDERATOR permite otorgarle mayor relevancia a la heurística dentro del problema de búsqueda a costa de sacrificar la optimalidad de la solución encontrada. A esto se le conoce como Weighted A* y se trata de otro algoritmo que encuentra soluciones subóptimas en menor tiempo.
Dentro de la tarea les pedimos implementar A* y Lazy A*, no Weighted A*.

9. ¿Qué pasa con repeated_color_heuristic cuando no hay un máximo de bolas de un color? (#49)

Se deberá asumir un color de bolitas como el máximo (de aquellas que tengan mayor cardinalidad) y proseguir normalmente. Por ejemplo, para el tubo [0, 0, 1, 1, 2] la heurística deberá retornar 3. La intuición es que retorna el mínimo número de bolas que deberé sacar del tubo para poder tenerlo con un solo color.

[ExRage2000]

mientras que la última variable corresponde al tiempo demorado en encontrar una solución

¿Para implementar el tiempo debemos buscar en internet? No hay un método para obtener el tiempo en el código

Tampoco existen los atributos self.start_time y self.end_time en la clase AStarSolver, así que supongo que podemos modificar esa parte para agregarlos

[dfloreaa]

@ExRage2000 más abajo en la issue comento al respecto, te invito a leerlo

Podemos medir el tiempo desde el comienzo hasta el fin de nuestra implementación (en segundos) utilizando el método time.process_time() (debemos importar la librería time), almacenando el tiempo del comienzo de nuestra búsqueda en un atributo (por ejemplo, self.start_time) y el tiempo de término en otro (por ejemplo, self.end_time). En este caso, el tiempo total de ejecución está dado por self.end_time - self.start_time.