(* Minimax search, alpha beta and alpha beta with pruning for the NIM game *) 
(* Author: Carsten Schuermann *)

signature MINIMAX = 
  sig
    val minimax : int * int -> int
    val maximin : int * int -> int
    val next : int * int -> (int * int) list
  end

structure  MinimaxNoPrune :  MINIMAX = 
  struct
    type config = int * int
      (* Representation invariant:  (n, m) : config iff n <m *)
    
    fun orient (nil) = nil
      | orient ((n,m) :: L) = 
        if n<m then (n,m) :: orient L
	else (m, n) :: orient L

    fun next' (0, m) = nil
      | next' (n, m) =  (n-1, m) :: next' (n-1, m) 

    fun next (n, m) = 
        if n=m then next' (n, m)
	else orient (next' (n, m) @ next' (m, n))


    fun max l = foldr (fn (a, b) => if a > b then a else b) ~1 l
    fun min l = foldr (fn (a, b) => if a < b then a else b) 1 l
      
    fun minimax (0, 0) = 1 
      | minimax c = 
        let 
	  val l = map maximin (next c)
        in
  	  max l
        end
    
    and maximin (0, 0) = ~1 
      | maximin c = 
      let 
	val l = map minimax (next c)
      in
	min l
      end
end


structure  Alphabeta :  MINIMAX = 
  struct
    type config = int * int
      (* Representation invariant:  (n, m) : config iff n <m *)

    local
      fun orient (nil) = nil
	| orient ((n,m) :: L) = 
            if n<m then (n,m) :: orient L
	    else (m, n) :: orient L

      fun next' (0, m) = nil
	| next' (n, m) =  (n-1, m) :: next' (n-1, m) 
	
      fun next (n, m) = 
            if n=m then next' (n, m)
	    else orient (next' (n, m) @ next' (m, n))


      fun max (a, b) = if a > b then a else b
      fun min (a, b) = if a < b then a else b

      fun mapMax f (a, b) nil = a
	| mapMax f (a, b) (h::l) =
          let 
	    val a' = max (a, f (a, b) h)
	  in
	    mapMax f (a', b) l
	  end
      fun mapMin f (a, b) nil = b
	| mapMin f (a, b) (h::l) =
          let 
	    val b' = min (f (a, b) h, b)
	  in
	    mapMin f (a, b') l
	  end

      fun minimax (a, b) (0, 0) = 1 
	| minimax (a, b) c = 
	    mapMax maximin (a, b) (next c)    
      and maximin (a, b) (0, 0) = ~1 
	| maximin (a, b) c = 
            mapMin minimax (a, b) (next c)
    in
      val minimax = fn c => minimax (~100, 100) c
      val maximin = fn c => maximin (~100, 100) c
      val next = next 	      
    end
end



structure  AlphabetaPruning :  MINIMAX = 
  struct
    type config = int * int
      (* Representation invariant:  (n, m) : config iff n <m *)

    local
      fun orient (nil) = nil
	| orient ((n,m) :: L) = 
            if n<m then (n,m) :: orient L
	    else (m, n) :: orient L

      fun next' (0, m) = nil
	| next' (n, m) =  (n-1, m) :: next' (n-1, m) 
	
      fun next (n, m) = 
            if n=m then next' (n, m)
	    else orient (next' (n, m) @ next' (m, n))


      fun max (a, b) = if a > b then a else b
      fun min (a, b) = if a < b then a else b

      fun mapMax f (a, b) nil = a
	| mapMax f (a, b) (c::l) =
          let 
	    val a' = max (a, f (a, b) c)
	  in
	    if a' < b then mapMax f (a', b) l
	    else a'
	  end
      fun mapMin f (a, b) nil = b
	| mapMin f (a, b) (h::l) =
          let 
	    val b' = min (f (a, b) h, b)
	  in
	    if b' > a then mapMin f (a, b') l
	    else b'
	  end

      fun minimax (a, b) (0, 0) = 1 
	| minimax (a, b) c = 
	    mapMax maximin (a, b) (next c)    
      and maximin (a, b) (0, 0) = ~1 
	| maximin (a, b) c = 
            mapMin minimax (a, b) (next c)
    in
      val minimax = fn c => minimax (~100, 100) c
      val maximin = fn c => maximin (~100, 100) c
      val next = next 
    end
end