module Minimax( Player, machine, player, opponent, Position(..), -- makeMove, -- makeMove :: Position pos => Int -> pos -> pos -- leiab parima käigu analüüsides mängupuud -- argumendina antud sügavuseni -- makePerfectMove, -- makePerfectMove :: Position pos => pos -> pos -- leiab parima käigu analüüsides kogu puud; -- kasutatav ainult lõplike puude korral ) where import List(sortBy) class Position pos where moves :: pos -> [pos] static :: pos -> Int dynamic :: pos -> Bool win :: Player -> pos -> Bool type Player = Bool machine, player :: Player machine = True player = False opponent :: Player -> Player opponent = not data Gtree a = Node a [Gtree a] deriving Show genGtree :: (a -> [a]) -> a -> Gtree a genGtree f x = Node x [genGtree f t | t <- f x] mapGtree :: (a -> b) -> Gtree a -> Gtree b mapGtree f (Node x ts) = Node (f x) [mapGtree f t | t <- ts] gametree :: Position pos => pos -> Gtree pos gametree p = genGtree moves p minimax :: Gtree Int -> Int minimax t = - minimum(mmx(bestfirst t)) bestfirst (Node x ts) = Node x (sortBy cmp (map bestfirst ts)) where cmp (Node x _) (Node y _) = compare x y mmx (Node x []) = [-x] mmx (Node x ts) = mapmin (map mmx ts) mapmin (xs:xss) = -n : omit n xss where n = minimum xs omit n [] = [] omit n (xs:xss) | minleq n xs = omit n xss | otherwise = -v : omit v xss where v = minimum xs minleq n [] = False minleq n (x:xs) = x <= n || minleq n xs prune 0 (Node x ts) | dynamic x = Node x [prune 0 t | t <- ts] | otherwise = Node x [] prune (n+1) (Node x ts) = Node x [prune n t | t <- ts] evaluate :: Position pos => Int -> pos -> Int evaluate n = minimax . mapGtree static . prune n . gametree perfectEval :: Position pos => pos -> Int perfectEval = minimax . mapGtree static . gametree --makeMove :: Position pos => Int -> pos -> pos --makeMove n p = chooseMin (head ps) (tail ps) -- where ps = [(p',evaluate n p') | p' <- moves p] makeMove :: Position pos => Int -> pos -> pos makeMove n p = chooseMin (head ps) (tail ps) where pss = [(p', map (evaluate n) . sortedMoves \$ p') | p' <- sortedMoves p] ps = mapmin2 pss mapmin2 ((p,xs):xss) = (p,-n) : omit n xss where n = if null xs then -(static p) else minimum xs omit n [] = [] omit n ((p,xs):xss) | minleq n xs = omit n xss | otherwise = (p,-v) : omit v xss where v = if null xs then -(static p) else minimum xs minleq n [] = False minleq n (x:xs) = x <= n || minleq n xs sortedMoves p = map fst . sortBy cmp \$ [(p', static p') | p' <- moves p] where cmp (_,i) (_,j) = compare i j makePerfectMove :: Position pos => pos -> pos makePerfectMove p = chooseMin (head ps) (tail ps) where ps = [(p',perfectEval p') | p' <- moves p] chooseMin (p,w) [] = p chooseMin (p,w) ((p',w'):xs) | w < w' = chooseMin (p,w) xs | otherwise = chooseMin (p',w') xs