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 *)