%
% minmax.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.
% Se una posizione e` vincente, allora nessuna mossa e` applicabile

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



% insieme_trasformati(POS,GIOC,L_MOSSE,L_TRASF)
%
% L_TRASF e` la lista di coppie [MOSSA,NUOVA_POS] per ogni mossa MOSSA in
% L_MOSSE e tale per cui NUOVA_POS e` la posizione risultante dall'esecuzione
% della mossa MOSSA nella posizione POS da parte del giocatore GIOC.

insieme_trasformati(_,_,[],[]).
insieme_trasformati(POS,GIOC,[MOSSA|L_MOSSE],[[MOSSA,NUOVA_POS]|L_TRASF]) :-
                                trasforma(MOSSA,GIOC,POS,NUOVA_POS),
                                insieme_trasformati(POS,GIOC,L_MOSSE,L_TRASF).



% 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,_,0,VAL,_) :- !, valuta(POS,VAL).
espandi(POS,GIOC,N,VAL,BEST_MOSSA) :-
                                  insieme_applicabili(POS,GIOC,L_MOSSE),
                                  insieme_trasformati(POS,GIOC,L_MOSSE,L_TRASF),
                                  espandi1(POS,GIOC,N,L_TRASF,VAL,BEST_MOSSA).

espandi1(POS,_,_,[],VAL,_) :- !, valuta(POS,VAL).
espandi1(_,GIOC,N,L_TRASF,VAL,BEST_MOSSA) :-
                                   espandi_tutti(L_TRASF,GIOC,N,VAL,BEST_MOSSA).



% espandi_tutti(L_TRASF,GIOC,N,VAL,BEST_MOSSA)
%
% Data la lista L_TRASF di coppie [MOSSA,NUOVA_POS] e data una espansione
% dell'albero di N livelli a partire da POS, BEST_MOSSA e` la mossa ottimale
% (con valutazione VAL) per il giocatore GIOC nella posizione POS.

espandi_tutti([[MOSSA,NUOVA_POS]],GIOC,N,VAL,MOSSA) :-
                                              N1 is N-1,
                                              inverti_gioc(GIOC,GIOC1),
                                              espandi(NUOVA_POS,GIOC1,N1,VAL,_).
espandi_tutti([[MOSSA,NUOVA_POS]|REST],GIOC,N,VAL,BEST_MOSSA) :-
                              N1 is N-1,
                              inverti_gioc(GIOC,GIOC1),
                              espandi(NUOVA_POS,GIOC1,N1,VAL1,_),
                              espandi_tutti(REST,GIOC,N,VAL2,BEST2),
                              scegli(GIOC,VAL1,MOSSA,VAL2,BEST2,VAL,BEST_MOSSA).



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

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



% scegli(GIOC,VAL1,MOSSA1,VAL2,MOSSA2,VAL,BEST_MOSSA)
%
% Date le due mosse MOSSA1 e MOSSA2 che portano a posizioni con stima
% euristica VAL1 e VAL2 rispettivamente, BEST_MOSSA con stima VAL e` la
% migliore tra le due mosse per il giocatore GIOC.

scegli(max,VAL1,MOSSA1,VAL2,_,VAL1,MOSSA1) :- mineq(VAL2,VAL1).
scegli(max,VAL1,_,VAL2,MOSSA2,VAL2,MOSSA2) :- min(VAL1,VAL2).
scegli(min,VAL1,MOSSA1,VAL2,_,VAL1,MOSSA1) :- mineq(VAL1,VAL2).
scegli(min,VAL1,_,VAL2,MOSSA2,VAL2,MOSSA2) :- min(VAL2,VAL1).



% 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).



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

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