data structures - breadth - Algoritmo y estructura de datos para resolver el juego "Globs"/flood fill/"FloodIt"

breadth first search pseudocode (7)

Si puedes, elimina un color.
¡Elige el color que más vecinos generen para ti!
goto paso 1.

Sugiere un algoritmo y una estructura de datos para resolver los Globos del juego ( http://www.deadwhale.com/play.php?game=131 ). Es bastante divertido de una manera geeky.

Indique la complejidad espacio-temporal (O grande) de su enfoque en términos de N , el tamaño de la cuadrícula (N> = 14). Se prefieren algoritmos eficientes suficientemente buenos con poca complejidad.

(MatrixFrog señala correctamente que este juego también se conoce como FloodIt, y Smashery dio una solución hace 3 meses en el enlace que cita a continuación. Todos ustedes sugieren sugerencias de poda / avaricia con solo 1 lookahead, que ofrece soluciones subóptimas).

El juego genera una cuadrícula al azar de nxn nodos, donde cada nodo tiene uno de seis colores (Grn = 1, Ylw = 2, Red = 3, Blu = 4, Pur = 5, Orn = 6). El nivel 1 tiene una cuadrícula de 9x9, luego n aumenta cada nivel, hasta 14. Cada nivel puedes tomar hasta 25 turnos o perderás. En cada turno, usted elige qué color cambiará el nodo superior izquierdo, por ejemplo, Grn-> Rojo, de modo que cualquier nodo adyacente conectado (horiz / vert) del nuevo color se asimile en una forma, y se AGREGA 1 pt por nodo asimilado a tu puntuación. El objetivo del puntaje es completar cada cuadrícula en el menor número de turnos posible, por ejemplo, si lo hace en 16 turnos, entonces sus 9 movimientos no utilizados => 2 * 9 MULTIPLICADOR multiplicarán su puntaje acumulado total.

Obviamente, hay un montón de maneras de descomponer esto, y la opción predeterminada de retroceso recursivo con una cuadrícula de 14x14 es un competidor viable; ¿A qué otros tipos de estructuras de datos se presta esto? UNA* ? No se obsesione con la optimalidad, me pregunto si hay un algoritmo "suficientemente bueno".

(Pensé que podría ser un proyecto divertido para codificar un robot y obtener puntajes muy altos. Aunque obtuve una puntuación de 3.5E + 12, todo por mi propio software físico).

Dado el estado de inicio fijo y el número limitado de movimientos, creo que puede explorar completamente un árbol de decisiones. Para cada ronda, solo hay 5 movimientos posibles y los movimientos desperdiciados (la elección de un color que no "pegará" a ningún vecino) puede eliminarse a medida que se construye el árbol. Una vez que se construya el árbol de decisiones, creo que podría explorar el valor en puntos de cada ruta, pero si necesita más optimización, un A * definitivamente lo acercará.

Para cada ronda, tendría el estado básico como una matriz de matrices de bits para el estado de las ubicaciones sin etiquetar (ya que el color ya no importa en las ubicaciones con globos, se puede ahorrar memoria en la estructura de datos de su estado al dejar de lado los bits de color) y un valor en puntos para cada decisión posible. Luego, su A *, o el primer algoritmo de amplitud, puede maximizar los valores de la ruta de forma normal. Guarde la ruta y, una vez que haya completado su análisis, realice todos los movimientos determinados.

Este juego realmente captó mi interés, por lo que pasé un par de días trabajando en él.

Lo primero que noté es que es fácil demostrar que después del primer tablero (quizás 2 en algunos casos), la forma más rápida de aumentar la puntuación es usar el multiplicador. Debido a esto, construí un sistema con el objetivo de resolver cada tablero en el menor número de pasos. Comencé a querer usar A * porque generalmente está diseñado solo para este tipo de problemas de búsqueda ... sin embargo, este problema aún resultó ser un problema.

Cuando se habla de A *, su efectividad realmente reduce su elección de estimación heurística. Cuanto más se acerque a adivinar la distancia real, menos nodos se deberán expandir para alcanzar la meta. Para este problema, pasé por una serie de ideas para la estimación, pero la mayoría de ellas rompió la regla A *, que es que NO se puede sobreestimar la distancia real, o bien se rompe la optimalidad de A *.

Hay algunos que funcionan sin embargo. Otros en este hilo han publicado acerca de simplemente tomar el número de colores restantes como la estimación, lo cual es admisible porque no puede sobreestimarse (debe cambiar los colores al menos una vez para cada color restante que no sea parte del área principal de "inundación". El problema con esta heurística es que estima muy poco la distancia real. Tomemos por ejemplo el primer movimiento, que generalmente tiene una estimación del número de colores, 6. A menudo se expande en 2 movimientos, cada uno de los cuales generalmente tiene una estimación de 7 , y así sucesivamente. Tome estos 5 niveles de profundidad y para un tamaño de tablero de 10x10, la mayoría de las hojas tienen una estimación de 11. Esta heurística es básicamente una implementación de una primera búsqueda de amplitud hasta que alcanza 4 o 5 movimientos desde su objetivo. Esto no es muy eficiente y, en mis propias pruebas, los exponentes son muy parecidos al tamaño de la placa 9, lo que a menudo requiere alrededor de 14 movimientos en la solución. Debe tenerse en cuenta que mi solución era de muy alto nivel y no se tuvo mucho cuidado. para adelgazar gs arriba

El problema es que A * solo es realmente bueno cuando cada paso hace un refinamiento significativo a la distancia real de la solución general. Mirando el problema directamente, es probable que no encuentre una buena heurística que pueda hacerlo mucho mejor sin sobreestimar el costo. Sin embargo, si transforma el problema en otro problema, las mejores heurísticas saltan sobre usted. El "número de colores restantes heurístico" responde a la pregunta, cuál es el número más pequeño de movimientos posibles. Para responder a esa pregunta, me pregunté "¿en qué lugar del tablero se requiere la cantidad máxima de pasos para llegar a"? Terminé decidiendo la respuesta a "cuántos pasos hay en la esquina inferior derecha" para mi heurística. Esto es bastante fácil de implementar ejecutando otra búsqueda A * que funciona más como encontrar direcciones de mapas y luego contar el número de pasos en la solución. Me doy cuenta de que este es un punto arbitrario en la placa para seleccionar, sin embargo, funcionó bastante bien en la prueba y ejecutar A * en cada punto restante tomó una buena cantidad de tiempo en mi máquina de prueba de procesador único.

Sin embargo, solo esta heurística tuvo una tendencia a colapsarse después de que la esquina inferior derecha se convirtiera en parte del área inundada, por lo que el resultado final fue MAX (pasos mínimos en la esquina inferior derecha, cantidad de colores que no forman parte de la inundación principal). Finalmente, esto fue capaz de lograr algunos tamaños de tableros muy grandes en menos de un segundo con mi implementación de alto nivel.

Voy a dejar el ajuste de registro para usted.

Otra optimización es que hay algunas manchas de color que no necesitan ser tomadas de inmediato. Puede haber hojas en el gráfico de distancia de la red donde una mancha de color no tiene otro vecino. Este blob de color no necesita tomarse hasta el blob más lejano del mismo color. Usando este enfoque, podemos ajustar el mapa de distancia para obtener el tiempo mínimo en el que se debe tomar una mancha de color.

Para algunas posiciones del tablero, podremos demostrar que no es necesario tomar un color elegible en el próximo turno. Podemos evitar ese color y reducir el factor de ramificación.

Otro enfoque es utilizar algoritmos genéticos. Dado que cualquier solución (parcial) consiste en una lista de colores, se traduce muy bien en un gen. Una función de aptitud podría ser algo así como 4 veces el componente conectado menos el número total de colores utilizados (longitud del gen).

Probé esto en tableros 10x10 en Mathematica, con un algoritmo no optimizado, y obtuve una solución corta bastante rápido. No afirmo que sea óptimo, pero si se toma el tiempo suficiente, la aleatoriedad en el proceso de mutación de los genes garantizará que finalmente termine con una solución óptima.

Una búsqueda recursiva de fuerza bruta encontrará la puntuación máxima. Tienes como máximo 5 ^ 25 estados finales para considerar. Muchos estados intermedios serán equivalentes; puede ser más rápido reconocerlos y eliminar el espacio de búsqueda de duplicados. Lleve un registro de la puntuación más alta encontrada en la búsqueda, junto con la ruta (secuencia de movimientos) que tomó para llegar allí.

Una buena heurística es generar el mapa de distancia conectado a color. Por ejemplo, la inundación actual es a distancia cero. Un grupo de colores conectados a un cuadrado en la distancia ''i'' está en la distancia ''i + 1''.

A continuación, observe cuántos colores están a la distancia máxima. Necesitamos movimientos de distancia máxima para eliminar un color a la distancia máxima, y necesitamos un movimiento adicional para eliminar cada color adicional a la distancia máxima. Si todos los colores no están a la distancia máxima, considere los colores de la distancia anterior que aún no se han eliminado. Podríamos eliminar uno de estos colores mientras hacemos movimientos de "máxima distancia", pero necesitaremos un movimiento para eliminar cada color adicional.

Esto proporciona una estimación bastante buena. En la posición inicial del tablero de 14x14, tiendo a obtener estimaciones de 17 a 18 mientras necesito de 20 a 22 movimientos para una solución óptima. Una tabla de 14x14 generalmente se puede resolver, con este límite inferior, mientras se observan alrededor de 10,000 posiciones de tabla. (Utilizando la optimización de hacer un movimiento que elimina un color si tal movimiento está disponible).