/*Voici une solution du morpion avec: */
/*-representation des positions par une liste de 9 max, min ou  f */
/*-fonction h triviale (1 si max a gagné, -1 si min a gagné, 0 sinon).*/
/* 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)*/

h(P,1):-finale(P,max),!.
h(P,-1):-finale(P,min),!.
h(_,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,_,H):-((finale(P,_),!);H=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).


/* 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,_,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 gagnes'),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).