:- include('tictactoe.pl'). 

% Algorithme MinMax avec convention Negamax. Retourne pour un joueur J donné, devant jouer dans une situation donnée Etat, de profondeur donnée P, le meilleur couple [Coup, Valeur] apres une analyse pouvant aller jusqu'à la profondeur Pmax.

% Cas 1 : Profondeur max atteinte -> éval par heuristique
negamax(J, Etat, P, Pmax, [rien, Val]) :-
    P >= Pmax, 
    !,
    heuristique(J, Etat, Val).

% Cas 2 : Aucun coup possible -> éval par heuristique
negamax(J, Etat, _, _, [rien, Val]) :-
    successeurs(J, Etat, Succ),
    length(Succ, 0),
    !,
    heuristique(J, Etat, Val).

% Cas 3 : Évaluation du sous-arbre et retour du meilleur couple [Coup, Valeur]
negamax(J, Etat, P, Pmax, [Coup, Val]) :-
    successeurs(J, Etat, Succ),
    !,
    loop_negamax(J, P, Pmax, Succ, ListCouples),
    meilleur(ListCouples, [Coup, V1]),
    Val is -V1.
    
%*******************************************************

% retourne la liste des couples [Coup, Etat_Suivant] pour la situation Etat
successeurs(J, Etat, Succ) :-
	copy_term(Etat, Etat_Suiv),
	findall([Coup,Etat_Suiv],
		    successeur(J, Etat_Suiv, Coup),
		    Succ).
		    
testSuccesseur :-
	situation_initiale(S),
	successeurs(x, S, LSucc),
	forall(member([Coup, Succ], LSucc), 
		(write(Coup), nl, 
		printState(Succ), nl)
	).

%*******************************************************

% retourne la liste des couples [Coup, Valeur_Situation_Suivante] à partir de la liste des [Coup, Situation_Suivante], en appliquant l'algorithme negamax sur chacun d'entre eux.
loop_negamax(_, _, _ ,[], []) :- !.

loop_negamax(J, P, Pmax, [[Coup, Suiv] | Succ], [[Coup, Vsuiv] | Reste_Couples]) :-
	% Récursion pour traiter le reste des successeurs
	loop_negamax(J, P, Pmax, Succ, Reste_Couples),
	% Récupération de l'adversaire de J
	adversaire(J, A),
	% Incrément de la profondeur avant l'appel de négamax
	Pnew is P+1,
	% Calcul de la valeur de negamax pour la situation Suiv.
	% On n'a pas besoin de connaitre le coup de l'adversaire en profondeur P+1 qui donne cette valeur, seul le coup de J en P nous intéresse (et on le connait déjà). D'ou le _ dans les arguments passés à negamax.
	negamax(A, Suiv, Pnew, Pmax, [_, Vsuiv]).

%*******************************************************

% Retourne le couple [Coup, Valeur] dont la valeur est la plus faible (car convention negamax)
meilleur([E], E) :- !.

meilleur([[C,V] | RestCouples], [BestC, BestV]) :-
    meilleur(RestCouples, [TempC, TempV]),
    min([TempC,TempV], [C,V], [BestC, BestV]).
    
min([C1,V1], [C2,V2], [C,V]) :-
	(V1 < V2) -> 
		V = V1,
		C = C1
	;
		V = V2,
		C = C2.

testMeilleur :-
	meilleur([[[1,2], -5], [[3,2], 2], [[3,3], -6], [[1,1], 7]], [[3,3], -6]),
	meilleur([[[1,2], 5]], [[1,2], 5]).

%*******************************************************

% Retourne le coup et la valeur retournés par Negamax depuis l'état initial
main(BestMove, Value, Pmax) :-
	situation_initiale(S0),
	joueur_initial(J),
	negamax(J, S0, 1, Pmax, [BestMove, Value]).

% Bug pour I = 9
testMain :-
	forall(between(1, 9, I), (
		main(B, V, I),
		write('I = '), write(I), nl,
		write('B = '), write(B), nl,
		write('V = '), write(V), nl, nl
	)).
	
%*******************************************************

% Applique Negamax et joue le coup suggéré successivement jusqu'à remplissage de la grille
testNegamax :-
	situation_initiale(S0),
	joueur_initial(J),
	iter(J, S0).
	
iter(_, S) :-
	situation_terminale(S),
	!,
	write('Match nul !'), nl.
	
iter(_, S) :-
	alignement(Ali, S),
	alignement_gagnant(Ali, J), 
	!,
	write(Ali), nl,
	write(S), nl,
	write(J), write(' a gagné !'), nl.
	
iter(J, S) :-
	negamax(J, S, 1, 9, [BestMove, Val]),
	successeur(J, S, BestMove),
	write(BestMove), write(' -> '), write(Val), nl,
	printState(S), nl,
	adversaire(J, A),
	iter(A, S).