> module GameTreeSearch where

> import List
> import Maybe

> alphaBeta :: (Real tVal)  => 
>               (tSide -> tSide) ->
>               (tSide -> tPos -> [(tMove, tPos)]) ->
>               (tSide -> tPos -> tVal) ->
>               tSide ->
>               tPos ->
>               tVal ->
>               tVal ->
>               Int ->
>               (tMove, tVal)
> alphaBeta otherSide
>           successors
>           evaluate
>           side
>           pos
>           alpha
>           beta
>           depth = let
>
>   alphaBeta'  side pos alpha beta depth   = let
>       succs   = successors side pos
>       side'   = otherSide side
>       (_, firstVal')  =
>               alphaBeta' side'((snd.head) succs)
>                       (-beta) (-alpha) (depth-1)
>       firstVal    = - firstVal'
>       firstMove   = (fst.head) succs
>
>       processSucc  (move, pos) v@(mBestMove, bestVal, alpha) = 
>          if bestVal >= beta 
>            then v
>            else let
>              alpha'  = if bestVal > alpha then bestVal else alpha
>              (_, bv') = alphaBeta' side' pos
>                               (-beta) (-alpha') (depth-1)
>              bv   = -bv'
>              in
>              if bv > bestVal
>                then (Just move, bv, alpha')
>                else (mBestMove, bestVal, alpha')
>
>       in
>       if depth == 0 || null succs 
>         then (Nothing, evaluate side pos)
>         else let
>              (bm, bv, _)  =
>                   foldr processSucc (Just firstMove, firstVal, alpha)
>                                     (tail succs)
>              in
>              (bm, bv)
>   in
>   if depth <= 0
>     then error "alphaBeta. depth must be greater than zero."
>     else if null (successors side pos)
>           then error "aplhaBeta. No move possible"
>           else let
>               (mmv, val) = alphaBeta' side pos alpha beta depth
>               in 
>               (fromJust mmv, val)