Corso di Fondamenti di informatica II 
	
PROGETTO 2 : " GIOCO DEL FILETTO IN SML "
a cura di Gianluca Di Tomassi

 

Questo e' stato uno dei due progetti da me curati per il corso di Fondamenti di Informatica 
II svolto nell'anno accademico 1995/96, di seguito viene riportato il codice :

 

(*  ---------------------------------------------------------   *)
(*  Progetto di gioco del filetto elaborato e realizzato da  :  *)
(*  DI TOMASSI GIANLUCA ingegneria informatica , matricola N.   *)
(*  080100021                                                   *)
(*  ---------------------------------------------------------   *)


signature SIGNATFILETTO =
 sig
   type segno
   type matrice
   val stampa : matrice -> unit
   val valutastra : matrice ->int
   val stati_succ : matrice -> segno -> (matrice list)
end;




structure  STRUCTFILETTO : SIGNATFILETTO =
 struct
   
datatype segno = X | O | v;

type matrice = segno list list; 

exception Error;

val dim = 3;


(* crearighe : int --> segno list. Funzione che consente la creazione di*)
(* una lista i cui elementi sono di tipo segno, in particolare sono di  *)
(* tipo v.Questa e' una funzione ausiliaria di creanuovo.               *)

fun  crearighe 0 = nil
    |crearighe n = v::(crearighe (n-1));



(* creanuovo : int --> int  --> matrice.         Funzione che crea ed *)
(* inizializza (con tutti v) la matrice n*n di gioco.                 *)

fun creanuovo 0 (m:int) = nil
   |creanuovo n m = ((crearighe n)::(creanuovo n (m-1)));
   
                 
 

(* contasegno : segno --> segno list --> int. Funzione che dato un    *)
(* segno (x,o,v) e una riga della matrice di gioco restituisce quante *)
(* volte tale segno occorre nella riga.                               *)

fun contasegno (tiposegno) nil = 0
   |contasegno (tiposegno) (a::L) =
             if (a=tiposegno)
                then (1+contasegno tiposegno L)
                   else (contasegno tiposegno L);



(* tresegno : segno list --> segno --> bool. Funzione che data in ingr*)
(* esso una riga e un segno (x,o) restituisce true se il segno occorre*)
(* tre volte nella riga, false altrimenti.                            *)

fun tresegno riga segno = ((contasegno segno riga)=3);


(* duesegno : segno list --> segno --> bool. Funzione che data in ingr*)
(* esso una riga e un segno (x,o) restituisce true se il segno occorre*)
(* due volte nella riga e il resto della riga e' v, false altrimenti. *)

fun duesegno riga segno = 
     ((contasegno segno riga)=2) andalso ((contasegno v riga)=1);


(* unosegno : segno list --> segno --> bool. Funzione che data in ingr*)
(* esso una riga e un segno (x,o) restituisce true se il segno occorre*)
(* una volta nella riga e il resto della riga e' v, false altrimenti. *)

fun  unosegno riga segno = 
     ((contasegno segno riga)=1) andalso ((contasegno v riga)=2);             


(* contaoccsegn : matrice --> (segno list --> segno --> bool) --> int *)
(* Funzione che data in ingresso la matrice di gioco e una funzione   *)
(* quantisegn, che sara' o tresegno o duesegno o uno segno,restituisce*)
(* il numero di occorrenze di un segno all' interno della matrice di  *)
(* gioco.                                                             *)  

fun contaoccsegn [nil] quantisegn segno = 0
   |contaoccsegn (r::L) quantisegn segno = 
               if (quantisegn r segno)
                  then (1 + (contaoccsegn L quantisegn segno)) 
                      else (contaoccsegn L quantisegn segno);
 

(* elemn : segno list --> int --> int. Funzione che data una riga *)
(* restituisce l'ennesimo elemento della riga.                    *)

fun elemn (a::L) 1 = a
    |elemn nil _ = raise Error
    |elemn (a::L) (q:int) = (elemn L (q-1));
    
    

(* diagonale : matrice --> segno list. Funzione che applicata alla*)
(* matrice di gioco, restituisce la diagonale principale.         *)

fun diagonale matr =
  let 
     fun aux nil _ = nil
        |aux (riga::rest) s = (elemn riga s)::(aux rest (s+1))
  in aux matr 1
end;

 
(* colonne : matrice --> matrice. Funzione che data la matrice di *)
(* di gioco, restituisce una lista i cui elementi sono liste di   *)
(* tipo segno e rappresentano le colonne della matrice di gioco.  *)

fun colonne matr =
  let 
     fun col nil _ = nil
        |col (riga::L) a = ((elemn riga a)::(col L a))

     fun aux 0 = nil
        |aux d = (col matr d)::(aux (d-1))
  in aux dim
end; 
 

(* totale : matrice --> matrice.  Funzione che data la matri      *)
(* ce di gioco, restituisce la lista di tutte le righe,diagonali  *)
(* e colonne.                                                     *)

fun totale matr = (diagonale matr) :: (diagonale (rev(matr))) :: ((matr)   
                  @ (colonne matr));


(* valutastra : matrice --> int. Funzione che valuta la strategia *)
(* ove A e' il numero di righe,colonne o diagonali che contengono *)
(* tre x , B e' il numero di righe,colonne o diagonali che conten *)
(* gono due x e i rimanenti posti sono v, C e' il numero di righe,*)
(* colonne o diagonali che contengono una x e i rimanenti posti   *)
(* sono v, D , E ed F sono valori analoghi per il segno o.        *) 

fun valutastra matr =
 let
    val tot = totale matr
    val A = (contaoccsegn tot tresegno (X))
    val B = (contaoccsegn tot duesegno (X))
    val C = (contaoccsegn tot unosegno (X))
    val D = (contaoccsegn tot tresegno (O))
    val E = (contaoccsegn tot duesegno (O))
    val F = (contaoccsegn tot unosegno (O))
 in
    100*A + 10*B + C - (100*D + 10*E + F)
end;



(* modstato : int --> int --> segno --> matrice --> matrice.      *)
(* Funzione che data la matrice di gioco, uno dei due segni di gio*)
(* co e le coordinate in cui si vuole andare ad inserire il segno,*)
(* restituisce la matrice di gioco aggiornata al nuovo stato.     *)

fun modstato a b segno matr =
let
   fun modriga _ 0 = nil
      |modriga (r::L) n =
          if ((n=1) andalso (r=v))
            then segno::L
               else r::(modriga L (n-1));

   fun trovarig (riga::resto) r s =
          if (r=1)
            then ((modriga riga s)::resto)
               else (riga::(trovarig resto (r-1) s))
in 
  trovarig matr a b
end;



(* statolibero : matrice --> int --> int --> bool.               *)
(* Funzione che data la matrice di gioco e le coordinate di una  *)
(* casella al suo interno, restituisce TRUE se la casella e' vuo *)
(* ta e FALSE se la casella e' occupata.                         *) 

fun statolibero matr coorx coory =
let
  
  (* cerca_ele : segno list -> int -> bool *)
  (* Funzione che data la riga permette di *)
  (* verificare se l' n-esimo posto e' vuo *)
  (* to oppure no.                         *)
    
  fun cerca_ele (a::rest) n =
        if n>1
           then (cerca_ele rest (n-1))
               else if a=v 
                      then true
		          else false;
	
  (* cerca_riga : matrice --> int * int --> bool *)

  fun cerca_riga (testa::rest) m n =
     if m>1 
        then (cerca_riga rest (m-1) n)
            else (cerca_ele testa n);

in cerca_riga matr coorx coory
end;




(* lista_stati_v : matrice --> (int * int) list.                 *)
(* Funzione che data in ingresso la matrice di gioco, restituisce*)
(* una lista di coppie, che rappresentano le coordinate delle    *)
(* caselle che sono libere.                                      *) 

fun lista_stati_v matr =

let 
   fun aux nil (m,n) = nil
      |aux (nil::rest) (m,n) = aux rest (m+1,n)
      |aux ((a::L)::rest) (m,n) =
           if (statolibero matr m n)
             then ((m,n)::(aux (L::rest) (m,n+1)))
                 else (aux (L::rest) (m,n+1))
in aux matr (1,1)

end;




(* stati_succ : matrice --> segno --> (matrice list)             *)
(* Funzione che data la matrice di gioco in ingresso (che si tro *)
(* vera' in un certo stato) e uno dei 2 segni (x,v), restituisce *)
(* in uscita la lista di tutte le possibili mosse che possono es *)
(* sere effettuate a partire dallo stato in cui si presentava la *)
(* la matrice data in input.                                     *)
  
fun stati_succ matr segno =

let 
   fun aux matr nil = nil
      |aux matr ((a,b)::rest)=
            (modstato a b segno matr)::(aux matr rest)
in
  aux matr (lista_stati_v matr)

end;


(* stampa : matrice --> unit                                     *)
(* stampasegni : segno --> unit                                  *)
(* stampariga : segno list --> unit                              *)
(* La funzione stampa e' una funzione che permette di stampare   *)
(* la griglia di gioco, essa al suo interno prevede due funzioni:*)
(* stampariga che stampa una riga e poi va accapo, e stampasegni *)
(* che permette di stampare data una riga i segni (X,O,v) che    *)
(* compaiono in essa.                                            *)

fun stampa nil = print("\n")
   |stampa (riga::rest) = 
    let 
       fun stampasegni (X) = print(" X")
          |stampasegni (O) = print(" O")
          |stampasegni (v) = print(" v")

       fun stampariga nil = print("\n")
          |stampariga ((x:segno)::rest) = 
                ( stampasegni (x) ; stampariga rest )

   in ( stampariga riga ; stampa rest )
end;



end;     (*   Stucture STRUCTFILETTO   *)




signature SIGMINIMAX = 
 sig

  structure PLAY : SIGNATFILETTO
  type albero
  val mossa : PLAY.matrice -> PLAY.segno -> PLAY.matrice

end;


 

functor MINIMAX (GAME:PLAY): SIGMINIMAX =
 struct
 
   structure PLAY = GAME;

   local 
        open PLAY
   in    

datatype albero = Alb of (matrice * Albero list)


(* opposto : segno --> segno.  Funzione che dato un segno in     *)
(* ingresso (x,o), restituisce il suo opposto (o,x).             *)

fun opposto (X) = (O)
   |opposto (O) = (X);
   
   
   

(* deriva : matrice --> segno --> int --> albero                 *)
(* derlista : matrice list --> segno --> int --> albero list     *)
(* Funzioni che si occupano di costruire l'albero delle deriva   *)
(* zioni fino ad una data profondita'(che indica il livello di   *)
(* difficolta')  data in input.                                  *)

fun derivamossa nil segno prof = raise Error
   |derivamossa matr segno prof = 
       Alb(matr,( derlista (stati_succ matr segno) opposto(segno) prof))

and derlista nil segno prof = nil
   |derlista (x::L) segno prof = 
        if prof=0 then nil else
	   (derivamossa x segno (prof-1))::(derlista L segno prof);
        
  

(* min : int --> int --> int.    Funzione che dati due interi mi *)
(* restituisce quello che tra i due risulta essere minore.       *)

fun min a (b:int) = a < b; 


(* max : int --> int --> int.    Funzione che dati due interi mi *)
(* restituisce quello che tra i due risulta essere maggiore.     *)
 
fun max a (b:int) = a > b; 



(* selezcoppie : (matrice*int) --> segno --> (matrice*int)       *)
(* Funzione che data in input una lista di coppie (matrice,valore*)
(* restituisce ,a seconda che debba muovere min (X) o max (O) ,  *)
(* quella che deve essere riportata a livello superiore nell' al *)
(* bero di derivazione.                                          *)

fun selezcoppie ((matr,valore)::(matr1,valore1)::xs) (segno) =

let

  fun minormax  f ((matr,valore)::nil) (segno) = (matr,valore)
     |minormax ((matr,valore:int)::(matr1,valore1)::xs) (segno) =        
           if ( f (valore) (valore1) )
              then minormax f ((matr,valore)::xs) (segno)
                   else minormax f ((matr1,valore1)::xs) (segno) 

in
   if (segno=X)
     then minormax min ((matr,valore)::(matr1,valore1)::xs) (segno)
       else minormax max ((matr,valore)::(matr1,valore1)::xs) (segno)
end;
             




(* minimax :  (albero*int) --> segno --> (matrice*int)           *)
(* minlist : (albero list) --> segno --> (matrice*int)           *)
(* Funzioni che si occupano dato in input l' albero delle deriva *)
(* zioni di valutare secondo la strategia del MINIMAX quale sia  *)
(* la mossa migliore che deve fare il giocatore attuale.         *)                

fun minimax (Alb(matr,nil)) (segno)   = ((matr),valutastra(matr))
  | minimax (Alb(matr,figli)) (segno) = 
          let 
             val (figlio,valore) = minlist (figli) (opposto(segno))
          in (matr,valore)
          end
	  

and minlist (figli) (segno) =
  let
    fun aux (nil) = nil
      | aux (x::L) = ((minimax (x) (segno))::aux (L))
  in selezcoppie (aux (figli)) (segno)
  end;


(* mossa : matrice --> segno --> matrice.         Funzione che data*)
(* in input la matrice di gioco attuale e il giocatore che deve muo*)
(* vere , restituisce la mossa piu' vantagiosa per tale giocatore  *)

fun mossa (matr) (segno) (profondita) =
    (#1( minimax (derivamossa (matr) (segno)) (segno) profondita);
     
        



end;       (*    Functor MINIMAX   *) 


 

Per qualsiasi chiarimento