Algoritmo y estructura de datos para resolver el "juego de Bolas"/llenar/"FloodIt"

Question

Sugieren un algoritmo y estructura de datos para resolver el juego Globs (http://www.deadwhale.com/play.php?game=131).Es bastante divertido en un geek tipo de camino.

Estado del tiempo-espacio de la complejidad (big-O) de su enfoque en términos de N, el tamaño de la cuadrícula (N>=14). Suficientes algoritmos eficientes con baja complejidad, que son los preferidos.

(MatrixFrog señala correctamente este juego también es conocido como FloodIt, y Smashery dio una solución de 3 meses en el enlace que se cita a continuación.Todo lo que dudes de lo que sugiere la poda/codicioso con sólo 1 oteo, que da soluciones subóptimas.)

El juego genera un azar retícula cuadrada de nxn nodos, donde cada nodo es de color de uno de los seis colores (Grn=1, Ylw=2, Rojo=3, Blu=4, Pur=5, Orn=6).El nivel 1 tiene cuadrícula de 9x9, entonces n se incrementa cada nivel, hasta el día 14.Cada nivel puede tomar hasta 25 vueltas o bien se pierde.En cada turno puedes elegir el color que va a cambiar la parte superior izquierda del nodo a, por ejemplo,Grn->Rojo, de tal manera que cualquier conectados adyacentes (horiz/vert) nodos de el nuevo color se asimilan en forma de a, y 1 pt en cada nodo asimilados se AÑADE a su puntuación.La puntuación objetivo es completar cada cuadrícula en unas pocas vueltas como sea posible, por ejemplo,si lo hace en 16 vueltas, después de su 9 no utilizado se mueve => 2*9 MULTIPLICADOR veces el total acumulado de puntuación.

Obviamente, hay un montón de maneras de descomponer este, y la elección por defecto de recursivas retroceso con un 14x14 red es un candidato viable;¿Qué otros tipos de estructuras de datos hace esto se presta a?Un* ?No se colgó en la optimalidad, me pregunto si hay un "suficientes" algoritmo.

(Pensé que podría ser un divertido proyecto de código hasta un robot y obtener tonto de puntuaciones más altas.Aunque me marcó 3.5 E+12 todo por mi fleshware auto.)

Answer 1

Este juego realmente agarró de mi interés, así que me pasé un par de días trabajando en ello.

La primera cosa que he notado, es que es fácil demostrar que después de la primera tabla (tal vez 2 en algunos casos), la forma más rápida para aumentar la puntuación es mediante el multiplicador.Debido a esto, he construido un sistema con el objetivo de resolver cada tablero en el menor número de pasos.Empecé a querer usar Un* debido a que generalmente es construido precisamente para este tipo de problemas de búsqueda de...sin embargo, este problema todavía resultó ser un desafío.

Cuando se habla de Un*, la eficacia de lo que realmente se reduce a su elección de la heurística de la estimación.Más cerca de llegar a adivinar la distancia real, el menor número de nodos que tendrá que ser ampliado con el fin de llegar a la meta.Para este problema, me fui a través de una serie de ideas para la estimación, pero la mayoría de ellos rompió el* regla, que es que usted NO puede sobre estimar la distancia real, o de lo contrario se rompe la optimalidad de Un*.

Son pocos los que trabajar, sin embargo.Otros en este hilo se han publicado acerca de tomar sólo el número de los restantes colores como el cálculo, la cual es admisible porque no se puede sobreestimar (puedes cambiar los colores, al menos, una vez por cada uno de los restantes de color de la parte de la "inundación" de la zona.El problema con esta heurística es que es muy poco estimaciones de la distancia real.Tomemos por ejemplo el primer movimiento, que generalmente tiene una estimación de la cantidad de colores, 6.A menudo se expande en 2 movimientos, cada uno de los cuales por lo general tiene una estimación de 7, y así sucesivamente y así sucesivamente.Tome este 5 niveles de profundidad y de un tamaño del tablero de 10x10, la mayoría de las hojas con una estimación de 11.Esta heurística es básicamente una aplicación de una primera extensión de la búsqueda hasta llegar dentro de 4 o 5 movimientos de su objetivo.Esto no es muy eficiente y en mis propias pruebas, los exponentes de ejecutar un mucho alrededor de la junta de tamaño 9, que a menudo requiere alrededor de 14 movimientos en la solución.Cabe señalar que mi solución era muy alto nivel, sin embargo, y no mucho cuidado, para acelerar las cosas.

El problema es que Un* sólo es realmente bueno cuando cada paso hace un refinamiento a la distancia real de la solución en general.Mirando el problema directamente, usted probablemente no encontrarán una buena heurística que puede hacerlo mucho mejor que este sin más de la estimación del costo.Sin embargo, si usted transformar el problema en otro problema, mejor heurística saltan a la vista.La heurística "número de colores restantes" es responder a la pregunta, ¿cuál es el menor número de movimientos posibles restantes.La respuesta a esa pregunta, me pregunté a mí mismo ", que lugar en el consejo requiere que el número máximo de pasos para llegar a"?Me terminaron asentándose en la respuesta a "¿cuántos pasos es la esquina inferior derecha" para mi heurística.Esto es bastante fácil de implementar mediante la ejecución de otro* búsqueda que funciona más como encontrar las direcciones en el mapa y, a continuación, contando el número de pasos en la solución.Me doy cuenta de que este es un punto arbitrario en la junta directiva seleccione, sin embargo, que funcionó bastante bien en las pruebas y la ejecución de Un* en cada punto se tomó una buena cantidad de tiempo en mi procesador de la máquina de prueba.

Esta heurística solo había una tendencia al colapso después de la esquina inferior derecha se convirtió en parte de la zona inundada sin embargo, por lo que el resultado final fue MAX(esquina inferior derecha min pasos, el número de colores restantes no forma parte de los principales de la inundación).Este fue finalmente capaz de lograr algún tablero de grandes tamaños en menos de un segundo con mi alto nivel de la aplicación.

Voy a dejar el registro de configuración para usted.

Answer 2

Otro enfoque es el uso de algoritmos genéticos.Desde cualquier (parcial) de la solución consta de una lista de colores, traduce muy bien a un gen.Una función de adaptación podría ser algo como 4 veces el componente conectado, menos el número de colores utilizados total (longitud de los genes).

He probado esto en 10x10 tablas en Mathematica, con una no muy algoritmo optimizado, y tuvo un breve solución más rápidamente.No voy a decir que es la óptima, pero dado el tiempo suficiente, la aleatoriedad en el proceso de la mutación de los genes se asegurará de que usted finalmente termina con una solución óptima.

Answer 3

Dado el fijo estado inicial y el número limitado de movimientos creo que se puede explorar un árbol de decisión.Para cada ronda, sólo hay 5 posibles movimientos y los movimientos inútiles (la elección de un color que no se 'pegote' para los vecinos lo) puede ser eliminado, ya que el árbol es construido.Una vez que el árbol de decisión se construye creo que se podría explorar el valor en puntos de cada ruta, pero si usted necesita más de optimización de de un Un* definitivamente se le acercan.

Para cada ronda, me gustaría tener la básica del estado como una matriz de matrices de bits para el estado de la unglobbed lugares (ya que el color no importa en el global lugares que usted podría ahorrar memoria en el estado de la estructura de datos dejando fuera de los bits de color) y un valor de puntos para cada decisión posible.Entonces su A*, o amplitud primer algoritmo sólo puede maximizar el camino de los valores normales.Guardar la ruta, y una vez que su análisis está completa, todos los determinados movimientos.

Answer 4

Un ataque de fuerza bruta búsqueda recursiva encontrará la máxima puntuación.Usted tiene a más de 5^25 de poner fin a los estados a considerar.Muchos estados intermedios será equivalente;puede ser más rápido para reconocer estos y podar el espacio de búsqueda de duplicados.Mantener un seguimiento de la puntuación más alta que se encuentran tan lejos como usted busca, junto con el camino (secuencia de movimientos) que tomó para llegar allí.

Answer 5

1. si usted puede, eliminar un color.
2. elegí el color que generan más nuevos vecinos para usted !
3. vaya al paso 1.

Answer 6

Una buena heurística es generar el color conectados a la distancia de mapa.E. g.la actual inundación está a una distancia de cero.Un grupo de colores conectado a una plaza en la distancia 'i' en la distancia 'i+1'.

Siguiente, observar cómo muchos colores están en la distancia máxima.Necesitamos la máxima distancia que se mueve para eliminar un color a la distancia máxima, y necesitamos un adicional de medidas para eliminar cada color adicional a la máxima distancia.Si todos los colores no están en la distancia, considere la posibilidad de los colores en la anterior distancia, que no han sido eliminados.Podemos eliminar uno de estos colores, mientras que la máxima distancia' se mueve, pero vamos a necesitar un movimiento para eliminar cada color adicional.

Esto proporciona una buena estimación.En la inicial 14x14 posición de la junta directiva, que tienden a obtener las estimaciones de los 17 a los 18 años, mientras que necesitan de 20 a 22 se mueve a una solución óptima.Un 14x14 de la junta general puede ser resuelto, con este límite inferior, mientras miraba alrededor de 10.000 puestos de la junta.(El uso de la optimización de hacer un movimiento que elimina un color si tal movimiento está disponible.)

Answer 7

Otro de optimización es que hay algo de color a los blobs que no necesitan ser tomadas de inmediato.No puede ser de hojas en la distancia de red gráfico donde un color blob no es otra que la del vecino.Este color blob no necesita ser llevado hasta el extremo de blobs del mismo color.Con este enfoque, se puede ajustar la distancia de mapa para obtener el mínimo de tiempo en el que un color blob debe ser tomado.

Para algunos puestos de la junta, vamos a ser capaces de demostrar que cumple los requisitos, el color no necesitan ser tomadas en el siguiente turno.Podemos evitar que el color y reducir el factor de ramificación.