191 lines
4 KiB
Prolog
191 lines
4 KiB
Prolog
/*********************************
|
|
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)
|
|
)).
|