¿Hay alguna manera de evitar recursiones innecesarias?

Question

Publiqué esta pregunta over at CodeReview, pero me di cuenta de que no es tanto una pregunta de Haskell como una cuestión de algoritmo.

El código de Haskell se puede encontrar on my github repo pero creo que el código no es tan importante como el concepto general.

Básicamente, el programa descubre el primer conjunto óptimo de movimientos en un juego de Kalaha (la variación sueca). Solo se considera el primer "giro", por lo que suponemos que puede comenzar y que no se computa nada desde el punto en que el oponente se mueve.

Kalaha board http://www.graf-web.at/mwm/kalaha.jpg

La junta comienza con tiendas vacías y una cantidad igual de canicas en cada maceta.

Comience su turno eligiendo una olla no vacía de su lado, recoja todas las canicas de esa olla y luego mueva alrededor de la tabla dejando caer una canica al pasar una olla. Si tus últimas tierras de mármol en la tienda, obtienes otro turno. Si aterrizas en un bote que no esté vacío, no guardas, recoges todo el contenido de ese bote y continúas. Finalmente, si aterrizas en una olla vacía, el turno pasa al oponente.

Hasta ahora he resuelto esto seleccionando todos los caminos posibles y luego ordenándolos según la cantidad de canicas en la tienda al final. Un camino significaría comenzar desde una de tus ollas, hacer todo lo necesario para moverte y ver si aterrizas en una tienda o en una olla vacía. Si aterrizas en la tienda, puedes continuar, y ahora hay tantas ramas nuevas como ollas no vacías a tu lado.

El problema radica en el hecho de que si comienzas con cinco canicas en las macetas, ya hay bastantes caminos. Saltar hasta seis y ghci se queda sin memoria.

La razón por la que no puedo entender cómo hacer que esto sea menos costoso es porque creo que cada ruta es necesaria durante el cálculo. Aunque solo necesitaré como máximo tres rutas (las mejores) de las miles (o millones) generadas, el resto debe revisarse para ver si en realidad son mejores que las anteriores.
Si uno es más largo (generalmente mejor), entonces eso es bueno, pero costoso. Si es más corto que cualquier ruta anterior, entonces el programa aún tenía que calcular esa ruta para descubrirlo.

¿Hay alguna forma de evitar esto o está computando todas las rutas necesarias por definición?

Answer 1

Sólo probarlas todas con el fin, grabar sus secuencias de movimientos como secuencias de números del 1 al 6 (en representación de la olla que selecciona los mármoles de), cada vez que repitiendo toda la secuencia desde el principio. Mantenga y actualice solo a los tres ganadores, además de la última secuencia de movimientos para que sepa qué probar a continuación. Si no hay próximos movimientos legales, regrese una muesca.

Va a ser extremadamente lento quizás, pero utilizará muy poca memoria. No almacena las posiciones resultantes, solo el número de potes elegidos, y repite la secuencia nuevamente desde la posición inicial, alterando el último movimiento (en lugar de 2, luego prueba 3, 4, etc., si no hay más movimientos legales) , retrocede un nivel). O tal vez almacene posiciones solo para la última secuencia de movimientos probados, para un retroceso más fácil.

Es un espacio típico para el comercio de velocidad de entonces.

Answer 2

usted podría intentar parallellizing usando esta versión paralela del mapa:

parMap :: (a -> b) -> [a] -> Eval [b] 
parMap f xs = map f xs `using` parList rseq 

Entonces te desencadenar un nuevo hilo para cada elección en su rama.

si usa como recursión parMap pathFunction kalahaPots, provocará muchos hilos, pero podría ser más rápido, podría romperlo pero no soy tan bueno como un haskeller en paralelo.