Kalaha Solver: finding the marbles

Question

As with my other question this is regarding my Kalaha solver.

Currently the way I find out the optimal progression of moves is with a command like this:

snd $ head $ reverse $ sortByMostInStore $ pickAllPaths $ generatePotList 4

The snd is there to just get the list of moves from the ([Pot], [Int]) pair and the reverse is there because the sorting is ascending. My main problem is that pickAllPaths is really taking every possible path. This results in manageable execution time for generatePotList 5 with 17352 paths, but bring it up to 6 marbles in each pot and that results in 7657399 paths, which takes a significantly longer time to compute.

-- The [Int] is the list of starting positions you picked up marbles from.
pickAllPaths :: [Pot] -> [([Pot], [Int])]
pickAllPaths startingListOfPots = resultingPotsAndPaths where
    resultingPotsAndPaths = branchLoop startingListOfPots []

    branchLoop :: [Pot] -> [Int] -> [([Pot], [Int])]
    branchLoop listOfPots pathTaken
        | null validStartingPositions = [(listOfPots, pathTaken)]
        | otherwise = loopHelper validStartingPositions listOfPots pathTaken []
        where
            validStartingPositions = map position $ filter (not . isPotEmpty) potsOwnedByPlayer
            potsOwnedByPlayer = take 6 listOfPots

    loopHelper :: [Int] -> [Pot] -> [Int] -> [([Pot], [Int])] -> [([Pot], [Int])]
    loopHelper [] _ _ returnList = returnList
    loopHelper (x:xs) listOfPots pathTaken returnList
        | not $ landsInStore = loopHelper xs listOfPots pathTaken combinedList
        | otherwise = branchLoop resultingPots (pathTaken ++ [x]) ++ loopHelper xs listOfPots pathTaken returnList
        where
            (resultingPots, landsInStore) = makeStartingMove listOfPots x
            combinedList = ((resultingPots, (pathTaken ++ [x])) : returnList)

Since I'll generally only be interested in the three best (and maybe worst) paths, which is less than 1% of all the calculated paths, I'm sure there must be a better way of doing this.

Is there a way to avoid unnecessary recursion?

Answer 1

The standard trick is to skip portions of the search space that cannot bring a better solution than the ones found so far. For this you need to:

• Remember the best solution found so far (or several best solutions, if you want).
• Estimate an upper bound on possible scores that can be achieved from a given game state.

Then, given a partial game state, you compare the estimated upper bound to the current best solution, and if it's lower, there is no need to process the game state. The better the estimate, the more unnecessary processing is skipped.

Depending on the game it's might or it might not be possible to make a precise estimate. If it's not possible, you can use approximate examples. But there is a trade-off: The less precise estimate the higher chance you'll miss the best solution (but most likely the returned solution would be good enough).