-
Notifications
You must be signed in to change notification settings - Fork 0
/
greedy.pl
206 lines (157 loc) · 5.39 KB
/
greedy.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/*************
* INSA Lyon - Département informatique - 4IF
* Hexanôme : H4412
* Rahim BELATECHE
* Matheus DE BARROS SILVA
* Benoit DELEGLISE
* Allan GUIGAL
* Alexis METWALLI
* Matthieu ROUX
* Mathieu SAUGIER
******************/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Méthode Greedy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Code implémentant les algorithmes et les règles de Greedy
%%% Basé sur l'implémentation de l'algorithme Greedy du profil git : https://github.com/dimashky
%%%
%%% Le but de cette méthode, à chaque coup, est d'effectuer le meilleur coup pour :
%%% - soit gagner au coup actuel, si possible (attaque)
%%% -> implémenté dans possibilite_gagner(+Col,-Res,+CouleurJCourant)
%%% - soit chercher le meilleur coup pour empêcher l'adversaire de gagner (défense)
%%% -> implémenté dans meilleur_coup(+Col,-Res,-ColRes,+CouleurJoueur)
:- module(greedy, [glouton/2]).
:- dynamic top/2.
:- use_module(util).
:- use_module(jeu).
:- use_module(ia).
%%%%%%%%%%%%%% Règles de l'algorithme Greedy %%%%%%%%%%%%%%%
%traverse(+C,+R,+incC,+IncR,-V)
%Permet de trouver le nombre de jetons qui permettent de gagner à partir du jeton (C,R)
%dans toutes les directions (vertical, horizontal, diagonal)
%le sens de visite dépend de (IncC,IncR), si c'est (1,0) par exemple permet d'aller vers le haut
traverse(C,R,IncC,IncR,Res):-
NewC is C + IncC,
NewR is R + IncR,
case(C,R,C1),
case(NewC,NewR,C2),
C1 == C2,
traverse(NewC,NewR,IncC,IncR,Res1),
Res is Res1 + 1,!.
traverse(_,_,_,_,Res):-
Res is 1.
%check(+Col,+Row)
%Cette méthode vérifie la situation de victoire à partir du jeton (X,Y)
%appelle traverse afin de visiter dans toutes les directions
%renvoie vrai si cas de victoire, faux sinon
check(X,Y):-
traverse(X,Y,1,0,R1),
traverse(X,Y,-1,0,R2),
R is R1 + R2 - 1 ,
R >= 4,!.
%Vertical
check(X,Y):-
traverse(X,Y,0,1,R1),
traverse(X,Y,0,-1,R2),
R is R1 + R2 - 1,
R >= 4,!.
%Main Diagonal Check
check(X,Y):-
traverse(X,Y,1,1,R1),
traverse(X,Y,-1,-1,R2),
R is R1 + R2 - 1,
R >= 4,!.
%Secondary Diagonal Check
check(X,Y):-
traverse(X,Y,1,-1,R1),
traverse(X,Y,-1,1,R2),
R is R1 + R2 - 1,
R >= 4,!.
%Cette méthode part du jeton (X,Y) et renvoie le nombre de jetons consécutifs de la même couleur
%que le jeton initial
get_max(X,Y,RES):-
traverse(X,Y,1,0,R11),traverse(X,Y,-1,0,R12),R1 is R11 + R12 - 1,
traverse(X,Y,0,1,R21),traverse(X,Y,0,-1,R22),R2 is R21 + R22 - 1,
traverse(X,Y,1,1,R31),traverse(X,Y,-1,-1,R32),R3 is R31 + R32 - 1,
traverse(X,Y,1,-1,R41),traverse(X,Y,-1,1,R42),R4 is R41 + R42 - 1,
RES1 is max(R1,R2),RES2 is max(R3,R4),RES is max(RES1,RES2).
%possibilite_gagner(+Col,-Res,+CouleurJCourant)
%Permet de vérifier si l'on peut arriver à un état de victoire avec un seul coup
possiblite_gagner(COL,RES,CouleurJCourant):-
R is 6,
top(COL,X),
NX is X + 1,
R == NX,
NCOL is COL + 1,
possiblite_gagner(NCOL,RES,CouleurJCourant),!.
possiblite_gagner(COL,RES,CouleurJCourant):-
placerJeton(COL,Ligne,CouleurJCourant),
%assert(top(COL,LigneIncr))
top(COL,NX), %NX is height of COL
check(COL,NX),
RES is COL,
remove(COL,Ligne,CouleurJCourant),!.
possiblite_gagner(COL,RES,CouleurJCourant):-
top(COL,X),
%NX is X - 1,
%assert(top(COL,NX)),
%retract(top(COL,X)),
retract(case(COL,X,CouleurJCourant)),
NCOL is COL + 1,
possiblite_gagner(NCOL,RES,CouleurJCourant).
%top(+COL,-Ligne)
%Permet de renvoyer dans Ligne le nombre de jetons d'une colonne donnée
top(COL,Ligne) :- calculPositionJeton(COL,1,X), Ligne is X-1.
%insert(COL,LigneIncr,Couleur) :- placerJeton(COL,LigneIncr,Couleur).
%enlève le jeton de la colonne COL et la ligne NY et de la couleur CouleurJCourant
remove(COL,NY,CouleurJCourant) :-
retract(case(COL,NY,CouleurJCourant)).
col_max(X,Y,COL1,_,RES,COL):-
X >= Y,
RES is X,
COL is COL1,!.
col_max(_,Y,_,COL2,RES,COL):-
RES is Y,
COL is COL2,!.
%meilleur_coup(+Col,-Res,-ColRes,+CouleurJoueur)
%Permet de trouver la meilleure case où mettre le jeton pour que l'adversaire gagne
%Elle trouve la colonne qui a le plus grand nombre de pièces de l'adversaire
%Elle met un jeton afin d'empêcher une suite de 4 jetons de l'adversaire
meilleur_coup(COL,RES,_,_):-
C is 7,
COL > C,
RES is 0,!.
meilleur_coup(COL,RES,COL_RES,CouleurJCourant):-
R is 6,
top(COL,X),
NX is X + 1,
R == NX,
NCOL is COL + 1,
meilleur_coup(NCOL,RES,COL_RES,CouleurJCourant),!.
meilleur_coup(COL,RES,COL_RES,CouleurJCourant):-
ennemi(CouleurJCourant,CouleurAdverse),
placerJeton(COL,Ligne,CouleurAdverse),
top(COL,X),
get_max(COL,X,RES1),
remove(COL,Ligne,CouleurAdverse),
NCOL is COL + 1,
meilleur_coup(NCOL,RES2,COL_RES1,CouleurJCourant),
col_max(RES1,RES2,COL,COL_RES1,RES,COL_RES).
%calculPositionJeton(+X,+LigneToCheck,-Ligne)
% calculPositionJeton/3(+Colonne,+LigneToCheck,-Ligne)
% Calcule la première ligne vide d'une colonne.
% Retourne l'indice de cette ligne vide.
calculPositionJeton(X,YCheck,YCheck) :-
caseVide(X,YCheck),
!.
calculPositionJeton(X,YCheck,Y) :-
incr(YCheck, YCheck1),
calculPositionJeton(X,YCheck1,Y).
%glouton(-Coup,+CouleurJCourant)
%Permet de renvoyer dans C la meilleure colonne où mettre le jeton afin de :
% - soit arriver à un état de victoire
% - soit empêcher l'adversaire d'atteindre la victoire
glouton(C, CouleurJCourant):-
possiblite_gagner(1,C,CouleurJCourant),!.
glouton(C, CouleurJCourant):-
meilleur_coup(1,_,C,CouleurJCourant).