216 lines
6.7 KiB
Prolog
216 lines
6.7 KiB
Prolog
/*
|
|
Ce programme met en oeuvre l'algorithme Minmax (avec convention
|
|
negamax) et l'illustre sur le jeu du TicTacToe (morpion 3x3)
|
|
*/
|
|
|
|
:- [tictactoe].
|
|
|
|
|
|
/****************************************************
|
|
ALGORITHME MINMAX avec convention NEGAMAX : negamax/5
|
|
*****************************************************/
|
|
|
|
/*
|
|
negamax(+J, +Etat, +P, +Pmax, [?Coup, ?Val])
|
|
|
|
SPECIFICATIONS :
|
|
|
|
retourne pour un joueur J donne, devant jouer dans
|
|
une situation donnee Etat, de profondeur donnee P,
|
|
le meilleur couple [Coup, Valeur] apres une analyse
|
|
pouvant aller jusqu'a la profondeur Pmax.
|
|
|
|
Il y a 3 cas a decrire (donc 3 clauses pour negamax/5)
|
|
|
|
1/ la profondeur maximale est atteinte : on ne peut pas
|
|
developper cet Etat ;
|
|
il n'y a donc pas de coup possible a jouer (Coup = rien)
|
|
et l'evaluation de Etat est faite par l'heuristique.
|
|
|
|
2/ la profondeur maximale n'est pas atteinte mais J ne
|
|
peut pas jouer ; au TicTacToe un joueur ne peut pas jouer
|
|
quand le tableau est complet (totalement instancie) ;
|
|
il n'y a pas de coup a jouer (Coup = rien)
|
|
et l'evaluation de Etat est faite par l'heuristique.
|
|
|
|
3/ la profondeur maxi n'est pas atteinte et J peut encore
|
|
jouer. Il faut evaluer le sous-arbre complet issu de Etat ;
|
|
|
|
- on determine d'abord la liste de tous les couples
|
|
[Coup_possible, Situation_suivante] via le predicat
|
|
successeurs/3 (deja fourni, voir plus bas).
|
|
|
|
- cette liste est passee a un predicat intermediaire :
|
|
loop_negamax/5, charge d'appliquer negamax sur chaque
|
|
Situation_suivante ; loop_negamax/5 retourne une liste de
|
|
couples [Coup_possible, Valeur]
|
|
|
|
- parmi cette liste, on garde le meilleur couple, c-a-d celui
|
|
qui a la plus petite valeur (cf. predicat meilleur/2);
|
|
soit [C1,V1] ce couple optimal. Le predicat meilleur/2
|
|
effectue cette selection.
|
|
|
|
- finalement le couple retourne par negamax est [Coup, V2]
|
|
avec : V2 is -V1 (cf. convention negamax vue en cours).
|
|
|
|
A FAIRE : ECRIRE ici les clauses de negamax/5
|
|
.....................................
|
|
*/
|
|
|
|
% cas 1
|
|
negamax(J, Etat, Pmax, Pmax, [[], Val]) :-
|
|
heuristique(J, Etat, Val), !.
|
|
|
|
% cas 2
|
|
negamax(J, Etat, _, _, [[], Val]):-
|
|
ground(Etat),
|
|
heuristique(J, Etat, Val), !.
|
|
|
|
% cas 3
|
|
negamax(J, Etat, P, Pmax, [Coup, Val]):-
|
|
successeurs(J,Etat,Succ),
|
|
loop_negamax(J,P,Pmax,Succ, List),
|
|
meilleur(List, [Coup,MVal]),
|
|
Val is MVal*(-1).
|
|
|
|
|
|
/*******************************************
|
|
DEVELOPPEMENT D'UNE SITUATION NON TERMINALE
|
|
successeurs/3
|
|
*******************************************/
|
|
|
|
/*
|
|
successeurs(+J,+Etat, ?Succ)
|
|
|
|
retourne la liste des couples [Coup, Etat_Suivant]
|
|
pour un joueur donne dans une situation donnee
|
|
*/
|
|
|
|
successeurs(J,Etat,Succ) :-
|
|
copy_term(Etat, Etat_Suiv),
|
|
findall([Coup,Etat_Suiv],
|
|
successeur(J,Etat_Suiv,Coup),
|
|
Succ).
|
|
|
|
/*************************************
|
|
Boucle permettant d'appliquer negamax
|
|
a chaque situation suivante :
|
|
*************************************/
|
|
|
|
/*
|
|
loop_negamax(+J,+P,+Pmax,+Successeurs,?Liste_Couples)
|
|
retourne la liste des couples [Coup, Valeur_Situation_Suivante]
|
|
a partir de la liste des couples [Coup, Situation_Suivante]
|
|
*/
|
|
|
|
loop_negamax(_,_,_,[],[]).
|
|
loop_negamax(J,P,Pmax,[[Coup,Suiv]|Succ], [[Coup,Vsuiv]|Reste_Couples]) :-
|
|
loop_negamax(J,P,Pmax,Succ,Reste_Couples),
|
|
adversaire(J,A),
|
|
Pnew is P+1,
|
|
negamax(A,Suiv,Pnew,Pmax, [_,Vsuiv]).
|
|
|
|
/*
|
|
A FAIRE : commenter chaque litteral de la 2eme clause de loop_negamax/5,
|
|
en particulier la forme du terme [_,Vsuiv] dans le dernier
|
|
litteral ?
|
|
*/
|
|
|
|
/*
|
|
J --> Symbole du joueur
|
|
P --> profondeur actuelle
|
|
Pmax --> profondeur maximale
|
|
[[Coup, Suiv] | Succ] --> Itération sur la liste de couple (Coup avec l'état Suiv où on arrive) puis le reste de la liste Succ
|
|
[[Coup,Vsuiv] | Reste_Couples] --> Liste de couple (Coup, VSuiv). VSuiv indique si c'est un bon ou mauvais coup à jouer
|
|
*/
|
|
|
|
|
|
/*********************************
|
|
Selection du couple qui a la plus
|
|
petite valeur V
|
|
*********************************/
|
|
|
|
/*
|
|
meilleur(+Liste_de_Couples, ?Meilleur_Couple)*/
|
|
|
|
/*
|
|
SPECIFICATIONS :
|
|
On suppose que chaque element de la liste est du type [C,V]
|
|
- le meilleur dans une liste a un seul element est cet element
|
|
- le meilleur dans une liste [X|L] avec L \= [], est obtenu en comparant
|
|
X et Y,le meilleur couple de L
|
|
Entre X et Y on garde celui qui a la petite valeur de V.
|
|
|
|
A FAIRE : ECRIRE ici les clauses de meilleur/2
|
|
*/
|
|
|
|
meilleur([[Coup, Valeur]], [Coup, Valeur]).
|
|
meilleur([[Coup, Valeur]|Succ], [MCoup,MValeur]):-
|
|
meilleur(Succ, [CX, VX]),
|
|
(Valeur < VX ->
|
|
MCoup = Coup,
|
|
MValeur = Valeur
|
|
;
|
|
MCoup = CX,
|
|
MValeur = VX
|
|
).
|
|
|
|
|
|
% Tests du prédicat meilleur
|
|
:- meilleur([[[3,4], 6]],[[3,4], 6]).
|
|
:- meilleur([[[1,2],7],[[1,4],8],[[2,2],2]],[[2,2],2]).
|
|
|
|
|
|
|
|
/******************
|
|
PROGRAMME PRINCIPAL
|
|
*******************/
|
|
|
|
% ?B --> meilleur coup / ?V --> valeur du meilleur coup
|
|
% Prédicat main
|
|
main(B,V,Pmax) :-
|
|
situation_initiale(SI),
|
|
negamax(x,SI,0,Pmax,[B,V]).
|
|
|
|
% Deuxieme predicat main avec posibilite de choisir le joueur J et la situation S
|
|
main2(J,S,B,V,Pmax):-
|
|
negamax(J,S,0,Pmax,[B,V]).
|
|
|
|
/*
|
|
A FAIRE :
|
|
Completer puis tester le programme principal pour plusieurs valeurs de la profondeur maximale.
|
|
Pmax = 1, 2, 3, 4 ...
|
|
Commentez les resultats obtenus.
|
|
*/
|
|
|
|
|
|
% Q1
|
|
% Tests sur la profondeur de Pmax
|
|
:- main([],0,0). % avec Pmax = 0 --> on ne lance pas la recherche de meilleur coup
|
|
:- main([2,2],4,1).
|
|
:- main([2,2], 1, 2).
|
|
:- main([2,2],3,5).
|
|
% main(B,V,9). --> débordement de pile
|
|
% Pour l'état initial, peu importe le nombre Pmax on obtient toujours la case du milieu en coup à jouer.
|
|
% Cependant, la valeur V change,on effet elle est plus petite quand P est pair (prise en compte plus forte du coup de l'adversaire)
|
|
% De plus la valeur V diminue également au fur et à mesure quand on se rapproche de la grille finale (9 coups joués) car si tous les jouoeurs jouent bien, il n'y a aucun gagnants.
|
|
|
|
% Exemple d'une partie ou les 2 joueurs jouent les coups optimaux --> pas de gagnants
|
|
:- A=[[_,_,_],[_,_,_],[_,_,_]], main2(x,A,[2,2],3,3).
|
|
:- A=[[_,_,_],[_,x,_],[_,_,_]], main2(o,A,[3,3],-1,3).
|
|
:- A=[[_,_,_],[_,x,_],[_,_,o]], main2(x,A,[2,1],3,3).
|
|
:- A=[[_,_,_],[x,x,_],[_,_,o]], main2(o,A,[2,3],-1,3).
|
|
:- A=[[_,_,_],[x,x,o],[_,_,o]], main2(x,A,[1,3],2,3).
|
|
:- A=[[_,_,x],[x,x,o],[_,_,o]], main2(o,A,[3,1],0,3).
|
|
:- A=[[_,_,x],[x,x,o],[o,_,o]], main2(x,A,[3,2],0,3).
|
|
:- A=[[_,_,x],[x,x,o],[o,x,o]], main2(o,A,[1,2],0,3).
|
|
:- A=[[_,o,x],[x,x,o],[o,x,o]], main2(x,A,[1,1],0,3).
|
|
:- A=[[x,o,x],[x,x,o],[o,x,o]], main2(x,A,[],0,3).
|
|
|
|
%Q2 en utilisant des rotations comme pour le jeu de bois du S1. On pourrait voir ainsi si la situation n'a pas deja ete
|
|
% calculee
|
|
|
|
% Q3 Que le coup gagnant soit quand on a 4 symboles identiques allignes. Il faudra aussi changer le predicat successeur
|
|
% (en effet on ne peut mettre des jetons que sur d'autres jetons ou sur le sol)
|
|
|
|
% Q4 // Insert alpha beta
|