%
% alfabeta.pl
%


%
% PARTE DIPENDENTE DAL GIOCO (TRIS)
%


% iniziale(POS)
%
% POS e` la posizione iniziale per il giocatore max.

iniziale([0,0,0,0,0,0,0,0,0]).



% applicabile(MOSSA,GIOC,POS)
%
% Nella posizione POS il giocatore GIOC puo` effettuare la mossa MOSSA.

applicabile(_,_,POS) :- vincente(POS,_), !, fail.
applicabile(1,_,[0,_,_,_,_,_,_,_,_]).
applicabile(2,_,[_,0,_,_,_,_,_,_,_]).
applicabile(3,_,[_,_,0,_,_,_,_,_,_]).
applicabile(4,_,[_,_,_,0,_,_,_,_,_]).
applicabile(5,_,[_,_,_,_,0,_,_,_,_]).
applicabile(6,_,[_,_,_,_,_,0,_,_,_]).
applicabile(7,_,[_,_,_,_,_,_,0,_,_]).
applicabile(8,_,[_,_,_,_,_,_,_,0,_]).
applicabile(9,_,[_,_,_,_,_,_,_,_,0]).



% trasforma(MOSSA,GIOC,POS,NUOVA_POS)
%
% NUOVA_POS e` la posizione che si ottiene a partire dalla posizione POS se il
% giocatore GIOC effettua la mossa MOSSA.

trasforma(1,max,[0|REST],[1|REST]) :- !, retract(count(N)), N1 is N+1, assert(count(N1)).
trasforma(1,min,[0|REST],[-1|REST]) :- !, retract(count(N)), N1 is N+1, assert(count(N1)).
trasforma(MOS,GIOC,[H|REST],[H|NEW_REST]) :- MOS1 is MOS-1,
                                             trasforma(MOS1,GIOC,REST,NEW_REST).



% vincente(POS,GIOC)
%
% POS e` una posizione vincente per il giocatore GIOC.

vincente([1,1,1,_,_,_,_,_,_],max).
vincente([_,_,_,1,1,1,_,_,_],max).
vincente([_,_,_,_,_,_,1,1,1],max).
vincente([1,_,_,1,_,_,1,_,_],max).
vincente([_,1,_,_,1,_,_,1,_],max).
vincente([_,_,1,_,_,1,_,_,1],max).
vincente([1,_,_,_,1,_,_,_,1],max).
vincente([_,_,1,_,1,_,1,_,_],max).
vincente([-1,-1,-1,_,_,_,_,_,_],min).
vincente([_,_,_,-1,-1,-1,_,_,_],min).
vincente([_,_,_,_,_,_,-1,-1,-1],min).
vincente([-1,_,_,-1,_,_,-1,_,_],min).
vincente([_,-1,_,_,-1,_,_,-1,_],min).
vincente([_,_,-1,_,_,-1,_,_,-1],min).
vincente([-1,_,_,_,-1,_,_,_,-1],min).
vincente([_,_,-1,_,-1,_,-1,_,_],min).



% valuta(POS,STIMA)
%
% STIMA e` una stima euristica della posizione POS.

valuta(POS,menoinf) :- vincente(POS,min), !.
valuta(POS,piuinf) :- vincente(POS,max), !.
valuta(POS,VAL) :- conteggia(16,POS,0,VAL).

conteggia(1,POS,ACC,VAL) :- verifica(1,POS,CONTRIB), VAL is ACC+CONTRIB.
conteggia(N,POS,ACC,VAL) :- verifica(N,POS,CONTRIB), ACC1 is ACC+CONTRIB,
                            N1 is N-1, conteggia(N1,POS,ACC1,VAL).

verifica(1,[X,_,_,_,X,_,_,_,_],X) :- !.
verifica(1,_,0).
verifica(2,[_,_,_,_,X,_,_,_,X],X) :- !.
verifica(2,_,0).
verifica(3,[_,_,X,_,X,_,_,_,_],X) :- !.
verifica(3,_,0).
verifica(4,[_,_,_,_,X,_,X,_,_],X) :- !.
verifica(4,_,0).
verifica(5,[X,X,_,_,_,_,_,_,_],X) :- !.
verifica(5,_,0).
verifica(6,[_,_,_,X,X,_,_,_,_],X) :- !.
verifica(6,_,0).
verifica(7,[_,_,_,_,_,_,X,X,_],X) :- !.
verifica(7,_,0).
verifica(8,[_,X,X,_,_,_,_,_,_],X) :- !.
verifica(8,_,0).
verifica(9,[_,_,_,_,X,X,_,_,_],X) :- !.
verifica(9,_,0).
verifica(10,[_,_,_,_,_,_,_,X,X],X) :- !.
verifica(10,_,0).
verifica(11,[X,_,_,X,_,_,_,_,_],X) :- !.
verifica(11,_,0).
verifica(12,[_,X,_,_,X,_,_,_,_],X) :- !.
verifica(12,_,0).
verifica(13,[_,_,X,_,_,X,_,_,_],X) :- !.
verifica(13,_,0).
verifica(14,[_,_,_,X,_,_,X,_,_],X) :- !.
verifica(14,_,0).
verifica(15,[_,_,_,_,X,_,_,X,_],X) :- !.
verifica(15,_,0).
verifica(16,[_,_,_,_,_,X,_,_,X],X) :- !.
verifica(16,_,0).



%
% PARTE INDIPENDENTE DAL GIOCO
%


% insieme_applicabili(POS,GIOC,L_MOSSE)
%
% L_MOSSE e` la lista delle mosse possibili per il giocatore GIOC nella
% posizione POS.

insieme_applicabili(POS,_,[]) :- vincente(POS,min),!.
insieme_applicabili(POS,_,[]) :- vincente(POS,max),!.
insieme_applicabili(POS,GIOC,L_MOSSE) :-
                             findall(MOSSA,applicabile(MOSSA,GIOC,POS),L_MOSSE).



% espandi(POS,GIOC,N,VAL,BEST_MOSSA)
%
% Data un'espansione a N livelli dell'albero a partire dalla posizione POS,
% VAL e` la stima euristica di POS e BEST_MOSSA e` la mossa migliore per il
% giocatore GIOC in POS.

espandi(POS,GIOC,N,VAL,BEST_MOSSA) :- espandi(POS,GIOC,N,[menoinf,piuinf],VAL,BEST_MOSSA).

espandi(POS,_,0,_,VAL,_) :- !, valuta(POS,VAL).
espandi(POS,GIOC,N,SOGLIA,VAL,BEST_MOSSA) :-
                         insieme_applicabili(POS,GIOC,L_MOSSE),
                         espandi1(POS,GIOC,N,L_MOSSE,SOGLIA,VAL,BEST_MOSSA).



% espandi1(POS,GIOC,N,L_MOSSE,SOGLIA,VAL,BEST_MOSSA).
%
% Relazione ausiliaria per espandi, con medesimo significato di POS, GIOC, N,
% VAL, BEST_MOSSA. L_MOSSE e` la lista delle mosse ammissibili. SOGLIA e` la
% lista [S_MIN,S_MAX], in cui S_MIN ed S_MAX rappresentano i valori oltre i
% quali avviene un taglio; per un nodo min si ha un taglio se esiste un nodo
% figlio con stima =< S_MIN; per un nodo max si ha un taglio se esiste un nodo
% figlio con stima >= S_MAX.

espandi1(POS,_,_,[],_,VAL,_) :- !, valuta(POS,VAL).
espandi1(POS,GIOC,N,[MOSSA|L_MOSSE],SOGLIA,VAL,BEST_MOSSA) :-
             trasforma(MOSSA,GIOC,POS,NEWPOS),
             N1 is N-1,
             inverti_gioc(GIOC,GIOC1),
             espandi(NEWPOS,GIOC1,N1,SOGLIA,VAL1,_),
             check_taglio(POS,GIOC,N,L_MOSSE,VAL1,MOSSA,SOGLIA,VAL1,MOSSA,VAL,BEST_MOSSA).



% check_taglio(POS,GIOC,N,L_MOSSE,VAL1,MOSSA1,SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA).
%
% Relazione ausiliaria per espandi1, con medesimo significato di POS, GIOC, N,
% L_MOSSE, SOGLIA, VAL, BEST_MOSSA. MOSSA1 e` la mossa che si sta considerando,
% caratterizzata dalla stima VAL1. TMP_MOSSA e` la miglior mossa fino ad ora
% individuata, caratterizzata dalla stima TMP_VAL.
% Questa relazione verifica se esiste la possibilita` di operare un taglio;
% all'occorrenza prosegue nell'espansione, aggiornando SOGLIA, TMP_VAL,
% TMP_MOSSA.

check_taglio(_,max,_,_,VAL,BEST_MOSSA,[_,S_MAX],_,_,VAL,BEST_MOSSA) :- mineq(S_MAX,VAL), !.
check_taglio(_,min,_,_,VAL,BEST_MOSSA,[S_MIN,_],_,_,VAL,BEST_MOSSA) :- mineq(VAL,S_MIN), !.
check_taglio(POS,max,N,L_MOSSE,VAL1,MOSSA1,[_,S_MAX],TMP_VAL,_,VAL,BEST_MOSSA) :-
                     min(TMP_VAL,VAL1), !,
                     espandi2(POS,max,N,L_MOSSE,[VAL1,S_MAX],VAL1,MOSSA1,VAL,BEST_MOSSA).
check_taglio(POS,min,N,L_MOSSE,VAL1,MOSSA1,[S_MIN,_],TMP_VAL,_,VAL,BEST_MOSSA) :-
                     min(VAL1,TMP_VAL), !,
                     espandi2(POS,min,N,L_MOSSE,[S_MIN,VAL1],VAL1,MOSSA1,VAL,BEST_MOSSA).
check_taglio(POS,GIOC,N,L_MOSSE,_,_,SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA) :-
                     espandi2(POS,GIOC,N,L_MOSSE,SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA).



% espandi2(POS,GIOC,N,L_MOSSE,SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA.
%
% Relazione ausiliaria per check_taglio, con medesimo significato di tutte le
% variabili.
% Questa relazione prosegue nell'espansione dell'albero.

espandi2(_,_,_,[],_,VAL,BEST_MOSSA,VAL,BEST_MOSSA) :- !.
espandi2(POS,GIOC,N,[MOSSA|L_MOSSE],SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA) :-
     trasforma(MOSSA,GIOC,POS,NEWPOS),
     N1 is N-1,
     inverti_gioc(GIOC,GIOC1),
     espandi(NEWPOS,GIOC1,N1,SOGLIA,VAL1,_),
     check_taglio(POS,GIOC,N,L_MOSSE,VAL1,MOSSA,SOGLIA,TMP_VAL,TMP_MOSSA,VAL,BEST_MOSSA).



% inverti_gioc(GIOC1,GIOC2)
%
% GIOC1 e GIOC2 sono due giocatori diversi.

inverti_gioc(max,min).
inverti_gioc(min,max).



% min(X,Y)
%
% X e' minore di Y, con piuinf e menoinf ad indicare rispettivamente piu` e
% meno infinito.

min(_,menoinf) :- !, fail.
min(piuinf,_) :- !, fail.
min(_,piuinf) :- !.
min(menoinf,_) :- !.
min(X,Y) :- X < Y.



% mineq(X,Y)
%
% X e' minore o uguale a Y, con piuinf e menoinf ad indicare rispettivamente
% piu` e meno infinito.

mineq(X,X) :- !.
mineq(X,Y) :- min(X,Y).



% alfabeta(POS,N,MOSSA,STIMA,NODI)
%
% MOSSA e` la mossa migliore (con stima STIMA) per il giocatore max nella
% posizione POS secondo la strategia min-max con tagli alfa-beta in cui
% l'albero del problema viene espanso fino al livello N; NODI indica il
% numero di nodi espansi nell'albero.

alfabeta(POS,N,MOSSA,STIMA,NODI) :- assert(count(0)),
                                    espandi(POS,max,N,STIMA,MOSSA),
                                    retract(count(NODI)).