/*Voici une solution du morpion avec: */
/*-representation des positions par une liste de 9 max, min ou  f */
/*-fonction d evaluation h qui compte les possibilites de gain de max.*/
/* les cases libres sont marquees "f"   */
/* move (Pos1, Joueur, Pos2) */

move([f|L],J,[J|L]).
move([K|L],J,[K|G]):-move(L,J,G).



/*finale(Pos,Joueur)*/

finale([A,B,C,D,E,F,G,H,I],J):-
A=B,B=C,C\==f,C=J,!;
D=E,E=F,F\==f,F=J,!;
G=H,H=I,I\==f,I=J,!;
A=D,D=G,G\==f,G=J,!;
B=E,E=H,H\==f,H=J,!;
C=F,F=I,I\==f,I=J,!;
A=E,E=I,I\==f,I=J,!;
C=E,E=G,G\==f,G=J,!;
not(move([A,B,C,D,E,F,G,H,I],_,_)),J=nul.


/*h(Pos,Val)*/

hfinale(max,100).
hfinale(min,-100).
hfinale(nul,0).

h(Pos,V):-finale(Pos,J),hfinale(J,V),!.

h([A,B,C,D,E,F,G,H,I],V):- aux([A,B,C,D,E,F,G,H,I],1,V).

aux([A,B,C,D,E,F,G,H,I],1,V):- aux([A,B,C,D,E,F,G,H,I],2,V1),((A\==min,B\==min,C\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],2,V):- aux([A,B,C,D,E,F,G,H,I],3,V1),((D\==min,E\==min,F\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],3,V):- aux([A,B,C,D,E,F,G,H,I],4,V1),((G\==min,H\==min,I\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],4,V):- aux([A,B,C,D,E,F,G,H,I],5,V1),((A\==min,D\==min,G\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],5,V):- aux([A,B,C,D,E,F,G,H,I],6,V1),((B\==min,E\==min,H\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],6,V):- aux([A,B,C,D,E,F,G,H,I],7,V1),((C\==min,F\==min,I\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],7,V):- aux([A,B,C,D,E,F,G,H,I],8,V1),((A\==min,E\==min,I\==min)->V is V1+1; V is V1).
aux([A,B,C,D,E,F,G,H,I],8,V):- ((C\==min,E\==min,G\==min)->V is 1; V
is 0).




/*minimax(Joueur,Position,Valeur,NouvellePosition,Hauteur_de_recherche)*/

/* si Position est finale, on s arrete et Valeur est hfinale de Position*/
/* sinon si Hauteur est 0 on evalue avec h */
/* sinon on descend dans l arbre de jeu... */


minimax(_,P,V,_,_):-finale(P,J),hfinale(J,V).
minimax(_,P,V,_,0):-h(P,V),!.

minimax(max,P,V,Next,H):- setof(X,move(P,max,X),Fils), H1 is H-1,
mapminimax(min,Fils,Valeurs,H1), maximum(Valeurs,c(Next,V)).

minimax(min,P,V,Next,H):- setof(X,move(P,min,X),Fils), H1 is H-1,
mapminimax(max,Fils,Valeurs,H1), minimum(Valeurs,c(Next,V)).

mapminimax(_,[],[],_).
mapminimax(J,[P|L],[c(P,V)|G],H):- minimax(J,P,V,_,H), mapminimax(J,L,G,H).

maximum([X],X).
maximum([c(P,X)|L],c(S,M)):-maximum(L,c(Q,N)),max(X,N,M),(M=:=X -> S=P; S=Q).

minimum([X],X).
minimum([c(P,X)|L],c(S,M)):-minimum(L,c(Q,N)),min(X,N,M),(M=:=X -> S=P; S=Q).

max(N,M,N):- N>=M,!.
max(N,M,M):- N<M.

min(N,M,N):- N=<M,!.
min(N,M,M):- N>M.


/* affichage d une position*/

imprime(max):-write('o').
imprime(min):-write('x').
imprime(f):-write(' ').

imprime([A,B,C,D,E,F,G,H,I]):- nl,write('Nouvelle position'),nl,write('-------'),nl,
write('|'),imprime(A),write('|'),imprime(B),write('|'),imprime(C),write('|'),nl,
           write('-------'),nl,
write('|'),imprime(D),write('|'),imprime(E),write('|'),imprime(F),write('|'),nl,
           write('-------'),nl,
write('|'),imprime(G),write('|'),imprime(H),write('|'),imprime(I),write('|'),nl,
           write('-------'),nl.

/* le prédicat jeu(Niveau,Joueur) : l utilisateur joue contre la machine */
/* qui implement minimax a niveau de profondeur  Niveau; si Joueur=min*/
/* l utilisateur commence , si Joueur= max la machine*/


jeu(Niveau,max):-jeu_aux([f,f,f,f,f,f,f,f,f],Niveau). 
jeu(Niveau,min):-imprime([f,f,f,f,f,f,f,f,f]),
write('a vous: entrer un indice de case libre, suivi de point'),nl,
utilisateur_joue([f,f,f,f,f,f,f,f,f],N),imprime(N),  write('retour chariot pour continuer'),nl,
get_char(_), jeu_aux(N,Niveau).



jeu_aux(Pos,Niv):-minimax(max,Pos,V,Next,Niv),imprime(Next),
            (finale(Next,K) -> 
            (K=nul-> (write('match nul'),nl);
            (write('je gagne'),nl)) ;
            write('a vous: entrer un indice de case libre, suivi de point'),nl,
            utilisateur_joue(Next,N),
            imprime(N),
            (finale(N,K) -> 
            (K=nul-> (write('match nul'),nl);
            (write(' tu gagne'),nl)); 
            write('retour chariot pour continuer'),nl,
            get_char(_), jeu_aux(N,Niv))).





utilisateur_joue(P,N):- read(X), (test(1,P,N,X) -> !; 
(write('entrer un indice de case libre, suivi de point'),nl,utilisateur_joue(P,N))).
test(10,_,_,_).
test(M,[f|L],[min|J],M):-S is M+1, test(S,L,J,M).
test(M,[X|L],[X|J],N):- M=\= N , S is M+1, test(S,L,J,N).