Hallo zusammen, im Rahmen meiner Bachelorarbeit habe ich ein Haskell-Programm geschrieben, welches alle möglichen Zustände berechnet, in den sich das Mühle-Brett befindet, nachdem alle neun weißen und neun schwarzen Steine gesetzt wurden. Der Inhalt des Programms sei nun weniger wichtig, ich habe vor allem das Problem, dass bei der Ausführung der Arbeitsspeicher meines Laptops (4GB) voll ist. Allerdings scheint der Haskell Interpreter auch nur 1,6 GB zu nutzen und dann mit der Meldung \"out of memory\" zu terminieren. Zumindest arbeitet ab da die CPU nicht mehr für den Prozess. hat nun jemand eine Idee, wie ich den Interpreter (GHCi) dazu bewegen kann, die Auslagerungsdatei auf der Festplatte mit zu nutzen? Ich hänge mal das Programm hier an, dann könnt ihr das Problem nachvollziehen (für Verbesserungsvorschläge bin ich dankbar):
-- Haskell-Program for calculation of all possible states after setting of stones
-- possible occupations for the positions data Stone = E | W | B deriving (Show,Eq)
-- positions on the Nine Men\'s Morris Board type Position = (Int,Int,Int) -- a whole Nine Men\'s Morris Board type Board = [(Position, Stone)] -- a whole State of Nine Men\'s Morris including a board and the last position W placed a stone on and the last position B placed a stone on type State = (Board,(Position,Position)) -- the set of states that is operated on type States = [State]
-- possible coordinates for the positions coordinates = [0,1,2] -- the set of positions that a Nine Men\'s Morris board consists of positions = [(r,x,y) | r <- coordinates,x <- coordinates,y <- coordinates, (x,y) /= (1,1)]
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The Main Programm
-- compute all states that occur after setting of stones computeStates :: States computeStates = rekComputeStates 0 initState
-- compute recursively all States with 9 Stones being set by each player rekComputeStates :: Int -> States -> States rekComputeStates 9 a = a rekComputeStates n a = rekComputeStates (n+1) (removeDuplicates (concat (map checkMillBTakeW (concat (map setBStone (concat (map checkMillWTakeB (concat (map setWStone a)))))))))
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The atomic formulas
occupiedW :: Position -> State -> Bool occupiedW (r,x,y) s = if elem ((r,x,y),W) (fst s) then True else False
occupiedB :: Position -> State -> Bool occupiedB (r,x,y) s = if elem ((r,x,y),B) (fst s) then True else False
playedW :: Position -> State -> Bool playedW (r,x,y) s = if (r,x,y) == fst(snd(s)) then True else False
playedB :: Position -> State -> Bool playedB (r,x,y) s = if (r,x,y) == snd(snd(s)) then True else False
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The more complex formulas millClosedW :: State -> Bool millClosedW s = or [ and [occupiedW (i,j,k) s | k<-[0,1,2]] && or [playedW (i,j,k) s| k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] || or [ and [occupiedW (k,1,j) s | k<-[0,1,2]] && or [playedW (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] || (and [occupiedW (k,0,1) s | k<-[0,1,2]] && or [playedW (k,0,1) s | k<-[0,1,2]]) || (and [occupiedW (k,2,1) s | k<-[0,1,2]] && or [playedW (k,2,1) s | k<-[0,1,2]])
millClosedB :: State -> Bool millClosedB s = or [ and [occupiedB (i,j,k) s | k<-[0,1,2]] && or [playedB (i,j,k) s| k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] || or [ and [occupiedB (k,1,j) s | k<-[0,1,2]] && or [playedB (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] || (and [occupiedB (k,0,1) s | k<-[0,1,2]] && or [playedB (k,0,1) s | k<-[0,1,2]]) || (and [occupiedB (k,2,1) s | k<-[0,1,2]] && or [playedB (k,2,1) s | k<-[0,1,2]])
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- initialize a States set with one empty Nine Men\'s Morris board initState :: States initState = [([(a,E) | a <- positions],((-1,-1,-1),(-1,-1,-1)))]
-- compute a set of States starting from one state placing a white stone on an empty position of the board setWStone :: State -> States setWStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),W)],((r,x,y),snd (snd s))) | ((r,x,y),t) <- fst s, t == E]
-- compute a set of States starting from one state placing a black stone on an empty position of the board setBStone :: State -> States setBStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),B)],(fst (snd s), (r,x,y))) | ((r,x,y),t) <- fst s, t == E]
-- compute a set of States starting from one state taking a black stone from the board takeBStone :: State -> States takeBStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),E)],snd s) | ((r,x,y),t) <- fst s, t == B]
-- compute a set of States starting from one state taking a white stone from the board takeWStone :: State -> States takeWStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),E)],snd s) | ((r,x,y),t) <- fst s, t == W]
-- Check if there is a White Mill, if there is one, take a black stone checkMillWTakeB :: State -> States checkMillWTakeB s = if millClosedW s then takeBStone s else [s]
-- Check if there is a Black Mill, if there is one, take a white stone checkMillBTakeW :: State -> States checkMillBTakeW s = if millClosedB s then takeWStone s else [s]
-- delete a position from a given board deletePosition :: Position -> Board -> Board deletePosition (r,x,y) [] = [] deletePosition (r,x,y) (b:bs) = if fst b == (r,x,y) then deletePosition (r,x,y) bs else b:deletePosition (r,x,y) bs
--removes duplicate entries from a list removeDuplicates :: (Eq a) => [a] -> [a] removeDuplicates [] = [] removeDuplicates (x:xs) = if elem x xs then removeDuplicates xs else x:removeDuplicates xs |
Mal ein Anfang:
import Data.List
-- Haskell-Program for calculation of all possible states after setting of stones
-- opponents data Player = Black | White deriving (Show, Eq) -- possible occupations for the positions data Stone = E | W | B deriving (Show,Eq)
-- positions on the Nine Men\'s Morris Board type Position = (Int,Int,Int) -- a whole Nine Men\'s Morris Board type Board = [(Position, Stone)] -- a whole State of Nine Men\'s Morris including a board and the last position W placed a stone on and the last position B placed a stone on type State = (Board,(Position,Position)) -- the set of states that is operated on type States = [State]
-- possible coordinates for the positions
-- the set of positions that a Nine Men\\\'s Morris board consists of positions = [(r,x,y) | r <- coordinates, x <- coordinates, y <- coordinates, (x,y) /= (1,1)] where coordinates = [0,1,2] --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The Main Programm
-- compute all states that occur after setting of stones computeStates :: States computeStates = rekComputeStates 0 initState
-- compute recursively all States with 9 Stones being set by each player rekComputeStates :: Int -> States -> States rekComputeStates 9 a = a rekComputeStates n a = rekComputeStates (n+1) $ nub $ concatMap (checkMillTake Black) $ concatMap (setStone Black) $ concatMap (checkMillTake White) $ concatMap (setStone White) a
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The atomic formulas
stone White = W stone Black = B
occupied :: Player -> Position -> State -> Bool occupied player pos s = elem (pos, stone player) (fst s)
played :: Player -> Position -> State -> Bool played White pos s = pos == fst (snd s) played Black pos s = pos == snd (snd s)
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- The more complex formulas millClosed :: Player -> State -> Bool millClosed p s = or [ and [occupied p (i,j,k) s | k<-[0,1,2]] && or [played p (i,j,k) s | k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] || or [ and [occupied p (k,1,j) s | k<-[0,1,2]] && or [played p (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] || (and [occupied p (k,0,1) s | k<-[0,1,2]] && or [played p (k,0,1) s | k<-[0,1,2]]) || (and [occupied p (k,2,1) s | k<-[0,1,2]] && or [played p (k,2,1) s | k<-[0,1,2]])
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- initialize a States set with one empty Nine Men\\\'s Morris board initState :: States initState = [([(a,E) | a <- positions],((-1,-1,-1),(-1,-1,-1)))]
-- compute a set of States starting from one state placing a white stone on an empty position of the board setStone :: Player -> State -> States setStone p s = [ (deletePosition pos (fst s) ++ [(pos, stone p)], f pos p) | (pos ,t) <- fst s, t == E] where f pos White = (pos, snd (snd s)) f pos Black = (fst (snd s), pos)
-- compute a set of States starting from one state taking a black stone from the board takeStone :: Player -> State -> States takeStone p s = [ (deletePosition pos (fst s) ++ [(pos, E)],snd s) | (pos,t) <- fst s, t == stone p]
-- Check if there is a White Mill, if there is one, take a black stone checkMillTake :: Player -> State -> States checkMillTake p s = if millClosed p s then takeStone (opp p) s else [s] where opp Black = White opp White = Black
-- delete a position from a given board deletePosition :: Position -> Board -> Board deletePosition pos = filter ((== pos).fst)
Ich hoffe, dass ich nichts zerschossen habe. rekComputeStates und millClosed sehen noch furchtbar aus. |