/*********************************
DESCRIPTION DU JEU DU TIC-TAC-TOE
*********************************/

situation_initiale([ [_,_,_],
                     [_,_,_],
                     [_,_,_] ]) .

% Convention (arbitraire) : c'est x qui commence
joueur_initial(x).

% Definition de la relation adversaire/2
adversaire(x,o).
adversaire(o,x).

situation_terminale(Situation) :-
	ground(Situation).

/***************************
DEFINITIONS D'UN ALIGNEMENT
***************************/
alignement(L, Matrix) :- ligne(L,Matrix).
alignement(C, Matrix) :- colonne(C,Matrix).
alignement(D, Matrix) :- diagonale(D,Matrix).

ligne(L, M) :- 
	nth1(_, M, L).
 
colonne(C, M) :-
    colonne(C, M, _).

colonne([E | Crest], [L | Mrest], Ncol) :-
    nth1(Ncol, L, E),
    colonne(Crest, Mrest, Ncol).

colonne([], [], _).
		
diagonale(D, M) :- 
	premiere_diag(1,D,M).

diagonale(D, M) :-
    length(M, N),
   	seconde_diag(N,D,M).
	
premiere_diag(_, [], []).
premiere_diag(K, [E | D], [Ligne | M]) :-
	nth1(K, Ligne, E),
	K1 is K + 1,
	premiere_diag(K1, D, M).

seconde_diag(_,[],[]).
seconde_diag(K, [E | D], [Ligne | M]) :-
	nth1(K, Ligne, E),
	K1 is K - 1,
	seconde_diag(K1, D, M).

% Alignement potentiel possible pour le joueur J
possible([X | L], J) :- unifiable(X, J), possible(L, J), !.
possible([], _).

unifiable(A, _) :- 
    var(A),
    !.
unifiable(_, B) :- 
    var(B), 
    !.
unifiable(A, B) :- 
    A = B.

% Vérifie que Ali est un alignement gagnant pour J
alignement_gagnant(Ali, J) :- 
    ground(Ali),
    maplist(=(J), Ali).

% Un alignement perdant pour J est un alignement gagnant pour son adversaire
alignement_perdant(Ali, J) :- 
    adversaire(J, O),
    alignement_gagnant(Ali, O).


/* ****************************
DEFINITION D'UN ETAT SUCCESSEUR
****************************** */
successeur(J, Etat, [Nl, Nc]) :- 
     nth1(Nl, Etat, L),
     nth1(Nc, L, Current),
     \+ ground(Current),
     Current = J.

/**************************************
EVALUATION HEURISTIQUE D'UNE SITUATION
**************************************/

/*
1/ l'heuristique est +infini si la situation J est gagnante pour J
2/ l'heuristique est -infini si la situation J est perdante pour J
3/ sinon, on fait la difference entre :
	le nombre d'alignements possibles pour J
moins
	le nombre d'alignements possibles pour l'adversaire de J
*/

%1
heuristique(J, Situation, H) :-
    alignement(Alig, Situation),
    alignement_gagnant(Alig, J),
    H = 10000,				% grand nombre approximant +infini
    !.

% 2
heuristique(J, Situation, H) :-
    alignement(Alig, Situation),
    alignement_perdant(Alig, J),
    H = -10000,				% grand nombre approximant -infini
    !.

% 3
heuristique(J, Situation, H) :-    % cas 3
    findall(Alig, alignement(Alig, Situation), L),
    adversaire(J, O),
    findall(AligPoss, (member(AligPoss, L), possible(AligPoss, J)), LpossJ),
    findall(AligPoss, (member(AligPoss, L), possible(AligPoss, O)), LpossO),
    length(LpossJ, NbJ),
    length(LpossO, NbO),
    H is NbJ - NbO.
    
% Affiche la grille
printState([]).
printState([R | Rest]) :-
	printRow(R),
	nl,
	printState(Rest).
	
printRow([]).
printRow([X | Rest]) :-
	(ground(X) ->
		write(X) 
	;
		write('_')
	),
	printRow(Rest).
	
	
% ----- Tests unitaires -----

testPossible :-
	A = [_,_,_], 
	possible(A, x),
	B = [x,_,x], 
	possible(B, x),
	C = [_,o,x], 
	\+ possible(C, x).
	
testAlignementGagnant :-
	A = [o,x,o],
	B = [o,_,o],
	C = [o,o,o],
	\+ alignement_gagnant(A, o),
	\+ alignement_gagnant(B, o),
	\+ alignement_gagnant(A, _),
	alignement_gagnant(C, o),
	alignement_gagnant(C, J),
	J == o.

testHeuristique :-
    LS = [
          [[[ _,_,_ ],
            [ _,_,_ ],
            [ _,_,_ ]], 0],

          [[[ _,_,_ ],
            [ _,o,_ ],
            [ _,_,_ ]], 4],

          [[[ x,x,o ],
            [ o,o,x ],
            [ x,o,x ]], 0],
            
          [[[ x,_,_ ],
            [ o,o,x ],
            [ x,o,x ]], -1],

          [[[ x,x,x ],
            [ o,o,x ],
            [ x,o,o ]], -10000]
         ],
    forall(member([S, Ho], LS), (
        heuristique(o, S, Ho),
        Hx is -Ho,
        heuristique(x, S, Hx)
    )).