module Alphabeta
where

import Data.Tree
import Data.List
import Data.Char

class Ord a => Searchable a where
  static :: a -> Int
  dynamic :: a -> Bool
  dynamic = const False
  children :: a -> [a]

reptree :: (a -> [a]) -> a -> Tree a
reptree f a = Node a (map (reptree f) (f a))

gametree :: (Searchable s) => s -> Tree s
gametree pos = reptree children pos

maximize, minimize :: (Ord a) => Tree a -> a
maximize (Node n []) = n
maximize n = maximum (maximize' n)
minimize (Node n []) = n
minimize n = minimum (minimize' n)

maximize' :: Ord a => Tree a -> [a]
maximize' (Node n []) = [n]
maximize' (Node n children) = mapmin (map minimize' children)

minimize' :: Ord a => Tree a -> [a]
minimize' (Node n []) = [n]
minimize' (Node n children) = mapmax (map maximize' children)

mapmin (x:xs) = (minimum x) : (omit (minimum x) xs)
mapmax (x:xs) = (maximum x) : (omit (maximum x) xs)

omit pot [] = []
omit pot (nums:rest) | minleq nums pot = omit pot rest
omit pot (nums:rest) | otherwise = (minimum nums) : (omit (minimum nums) rest)

minleq [] pot = False
minleq (x:xs) pot = x <= pot

prune :: (Searchable s) => Int -> Tree s -> Tree s
prune 0 (Node a x) | dynamic a = Node a (map (prune 0) x)
prune 0 (Node a x) | otherwise = Node a []
prune n (Node a x) = Node a (map (prune (n-1)) x)

highfirst (Node n children) = Node n (sort (map lowfirst children))
lowfirst  (Node n children) = Node n (sortBy (flip compare) (map highfirst children))

evaluate :: (Searchable s) => Int -> s -> Int
evaluate n = static . maximum . maximize' . prune n . gametree