Is there a way to avoid unnecessary recursion?

Question

I posted this question over at CodeReview, but I came to realize that it's not so much a Haskell question as it is an algorithm question.

The Haskell code can be found on my github repo but I think the code isn't as important as the general concept.

Basically the program figures out the optimal first set of moves in a game of Kalaha (the Swedish variation). Only the first "turn" is considered, so we assume that you get to start and that anything from the point of the opponent getting to move is not computed.

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

The board starts off with empty stores and a equal amount of marbles in each pot.

You start your turn by choosing a non-empty pot on your side, pick all of the marbles up from that pot and then move around the board by dropping one marble when passing a pot. If your last marble lands in the store, you get another turn. If you land in a non-empty, non-store pot, you pick up all of the contents of that pot and continue. Finally, if you land in an empty pot, the turn is passed to the opponent.

So far I've solved this by picking all possible paths and then sorting them according to the amount of marbles in the store by the end. A path would mean to start from one of your pots, do all the necessary pick-up-and-move-around and see if you either land in a store or in an empty pot. If you land in the store you get to continue, and now there are as many new branches as there are non-empty pots on your side.

The problem lies in the fact that if you start with five marbles in the pots, it's already quite a few paths. Jump up to six and ghci runs out of memory.

The reason I can't figure out how to make this less expensive is because I think that each path is necessary during computation. While I'll only need at most three paths (the best ones) out of the thousands (or millions) generated, the rest need to be run through to see if they're actually better than the previous ones.
If one is longer (generally better) then that's good but costly. If it's shorter than any previous path, then program still had to compute that path to find that out.

Is there any way around this, or is computing all the paths necessary by definition?

Answer 1

Just try them all out in order, recording your sequences of moves as sequences of numbers 1 through 6 (representing the pot that you pick the marbles from), each time replaying the whole sequence from the start. Keep and update just the three winners, plus the very last sequence of moves so you'd know what to try next. If there's no next legal moves, go back one notch.

It's going to be prohibitively slow perhaps, but will use very little memory. You don't store resulting positions, only numbers of pots picked from, and replay the sequence anew each time from the starting position, altering the very last move (instead of 2, next try 3, 4 etc.; if no more legal moves, backtrack one level). Or maybe store positions just for the very last sequence of moves tried, for easier backtracking.

It's a typical space for speed trade-of then.

Answer 2

You could try parallellizing using this parallel version of map:

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

Then you will spark off a new thread for each choise in your branch.

if you use as parMap pathFunction kalahaPots as your recursion, it will spark a lot of threads, but it might be faster, you could chunk it but i'm not that good of a parallell haskeller.