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?