(* val minimize : ('a -> 'a -> bool) -> ('b -> 'a) -> 'b list -> 'b * 'a = <fun> *)
let  minimize cmp eval l =
  let rec  trouve ((m, v) as c) =  function
      []    -> c 
    | x'::l -> let  v' = eval x' in 
      if cmp v' v  then
        trouve (x', v') l               
      else  
        trouve c l 
  in match l  with
    []   -> failwith "minimize: empty list "
  | x::l -> trouve (x, eval x) l
;; 

(* val min : ('a -> 'b) -> 'a list -> 'a * 'b = <fun> *)
let  min eval l = minimize (fun a b -> a < b) eval l;;
(* val max : ('a -> 'b) -> 'a list -> 'a * 'b = <fun> *)
let  max eval l = minimize (fun a b -> a > b) eval l;;

(* val minmax : ('a -> float) -> ('a -> 'a list) -> 'a -> 'a * float = <fun> *)
let  minmax eval suiv dep =
  let eval1 p = match  eval p with
    0.0 -> 1.0    (* plus que 1 coup à jouer - perdu pour adversaire *)
  | 1.0 -> 0.0    (* plus que 1 coup à jouer - perdu pour courant *)
  | _   -> snd (min eval (suiv p)) (* au moins deux - l'aversaire va minimiser notre score *)
  in
  max eval1 (suiv dep)
;;

(* val minmax_n : ('a -> float) -> ('a -> 'a list) -> int -> 'a -> 'a * float = <fun> *)
let  minmax_n eval suiv n dep =
  let rec  eval1 n p = match  eval p with
    0.0 -> 1.0    
  | 1.0 -> 0.0   
  | _   -> 
      if n = 0 then
	snd (min eval (suiv p))        
      else
	snd (min (fun  p -> snd (minmax_rec (n - 1) p)) (suiv p))
  and  minmax_rec n p = match eval p with
    (0.0 | 1.0) as e -> p, e
  | _                -> max (eval1 n) (suiv p)
  in  minmax_rec n dep
;;

(****** jeu des allumettes *******)
type  configuration = bool * int;;

let  configuration_initiale = true, 20;;

(* configurations suivantes *)
(* val suiv : bool * int -> (bool * int) list = <fun> *)
let  suiv (b, n) =
  match  n  with
    0 -> []  
  | 1 -> [not b, 0]  
  | 2 -> [not b, 0 ; not b, 1]  
  | n -> [not b, n-3 ; not b, n-2 ; not b, n-1]
;;

(* val eval : 'a * int -> float = <fun> *)
let eval (b,n) = 
  match  n  with
    0 -> 1.0  
  | _ -> 0.5
;;

(* ordi - ordi *)
(* val joue : bool * int -> bool * int = <fun> *)
let joue       ((b, n) as c) = fst (minmax_n eval suiv (n / 2 + 1) c);;

(* humain - ordi *)
let jouejoueur1 ((b, n) as c) = 
  if b then 
    begin
      print_string "Joueur 1 : ";
      not b, n - read_int()
    end
  else
    fst (minmax_n eval suiv (n / 2 + 1) c)
;;

(* ordi - humain *)
let jouejoueur2 ((b, n) as c) = 
  if not b then 
    begin
      print_string "Joueur 2 : ";
      not b, n - read_int()
    end
  else
    fst (minmax_n eval suiv (n / 2 + 1) c)
;;

(* humain - humain *)
let jouejoueurs ((b, n) as c) = 
  if b then 
    print_string "Joueur 1 : "
  else
    print_string "Joueur 2 : ";
  not b, n - read_int()
;;

(* val affiche_configuration : bool * int -> unit = <fun> *)
let affiche_configuration (b,n) =
  if b then 
    print_string "au joueur 1 : "
  else
    print_string "au joueur 2 : ";
  for  i = 1 to n  do
    print_string " |"
  done;
  print_newline ()
;;

(* val boucle : (bool * int -> bool * int) -> bool * int -> unit = <fun> *)
let boucle coup ci =
  let rec  boucle_rec ((b,n) as c) =
    if n = 0 then
      begin
	if b then
	  print_string "le joueur 1 gagne !"
	else
	  print_string "le joueur 2 gagne !";
	print_newline ()    
      end
    else
      begin
	affiche_configuration c;
	boucle_rec (coup c)    
      end
  in
  boucle_rec ci
;;

boucle joue configuration_initiale;;