1 /*
2 * Copyright (c) 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Ralph Campbell.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char sccsid[] = "@(#)makemove.c 8.2 (Berkeley) 05/03/95";
13 #endif /* not lint */
14
15 #include "gomoku.h"
16
17 /* direction deltas */
18 int dd[4] = {
19 MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT
20 };
21
22 int weight[5] = { 0, 1, 7, 22, 100 };
23
24 /*
25 * Return values:
26 * MOVEOK everything is OK.
27 * RESIGN Player resigned.
28 * ILLEGAL Illegal move.
29 * WIN The the winning move was just played.
30 * TIE The game is a tie.
31 */
makemove(us,mv)32 makemove(us, mv)
33 int us, mv;
34 {
35 register struct spotstr *sp, *fsp;
36 register union comboval *cp;
37 struct spotstr *osp;
38 struct combostr *cbp, *cbp1;
39 union comboval *cp1;
40 register int i, f, r, d, n;
41 int space, val, bmask;
42
43 /* check for end of game */
44 if (mv == RESIGN)
45 return(RESIGN);
46
47 /* check for illegal move */
48 sp = &board[mv];
49 if (sp->s_occ != EMPTY)
50 return(ILLEGAL);
51
52 /* make move */
53 sp->s_occ = us;
54 movelog[movenum - 1] = mv;
55 if (++movenum == BSZ * BSZ)
56 return(TIE);
57
58 /* compute new frame values */
59 sp->s_wval = 0;
60 osp = sp;
61 for (r = 4; --r >= 0; ) { /* for each direction */
62 d = dd[r];
63 fsp = osp;
64 bmask = BFLAG << r;
65 for (f = 5; --f >= 0; fsp -= d) { /* for each frame */
66 if (fsp->s_occ == BORDER)
67 goto nextr;
68 if (fsp->s_flg & bmask)
69 continue;
70
71 /* remove this frame from the sorted list of frames */
72 cbp = fsp->s_frame[r];
73 if (cbp->c_next) {
74 if (sortframes[BLACK] == cbp)
75 sortframes[BLACK] = cbp->c_next;
76 if (sortframes[WHITE] == cbp)
77 sortframes[WHITE] = cbp->c_next;
78 cbp->c_next->c_prev = cbp->c_prev;
79 cbp->c_prev->c_next = cbp->c_next;
80 }
81
82 /* compute old weight value for this frame */
83 cp = &fsp->s_fval[BLACK][r];
84 if (cp->s <= 0x500)
85 val = weight[5 - cp->c.a - cp->c.b];
86 else
87 val = 0;
88 cp = &fsp->s_fval[WHITE][r];
89 if (cp->s <= 0x500)
90 val += weight[5 - cp->c.a - cp->c.b];
91
92 /* compute new combo value for this frame */
93 sp = fsp;
94 space = sp->s_occ == EMPTY;
95 n = 0;
96 for (i = 5; --i >= 0; sp += d) { /* for each spot */
97 if (sp->s_occ == us)
98 n++;
99 else if (sp->s_occ == EMPTY)
100 sp->s_wval -= val;
101 else {
102 /* this frame is now blocked, adjust values */
103 fsp->s_flg |= bmask;
104 fsp->s_fval[BLACK][r].s = MAXCOMBO;
105 fsp->s_fval[WHITE][r].s = MAXCOMBO;
106 while (--i >= 0) {
107 sp += d;
108 if (sp->s_occ == EMPTY)
109 sp->s_wval -= val;
110 }
111 goto nextf;
112 }
113 }
114
115 /* check for game over */
116 if (n == 5)
117 return(WIN);
118
119 /* compute new value & combo number for this frame & color */
120 fsp->s_fval[!us][r].s = MAXCOMBO;
121 cp = &fsp->s_fval[us][r];
122 /* both ends open? */
123 if (space && sp->s_occ == EMPTY) {
124 cp->c.a = 4 - n;
125 cp->c.b = 1;
126 } else {
127 cp->c.a = 5 - n;
128 cp->c.b = 0;
129 }
130 val = weight[n];
131 sp = fsp;
132 for (i = 5; --i >= 0; sp += d) /* for each spot */
133 if (sp->s_occ == EMPTY)
134 sp->s_wval += val;
135
136 /* add this frame to the sorted list of frames by combo value */
137 cbp1 = sortframes[us];
138 if (!cbp1)
139 sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
140 else {
141 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
142 if (cp->s <= cp1->s) {
143 /* insert at the head of the list */
144 sortframes[us] = cbp;
145 } else {
146 do {
147 cbp1 = cbp1->c_next;
148 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
149 if (cp->s <= cp1->s)
150 break;
151 } while (cbp1 != sortframes[us]);
152 }
153 cbp->c_next = cbp1;
154 cbp->c_prev = cbp1->c_prev;
155 cbp1->c_prev->c_next = cbp;
156 cbp1->c_prev = cbp;
157 }
158
159 nextf:
160 ;
161 }
162
163 /* both ends open? */
164 if (fsp->s_occ == EMPTY) {
165 cp = &fsp->s_fval[BLACK][r];
166 if (cp->c.b) {
167 cp->c.a += 1;
168 cp->c.b = 0;
169 }
170 cp = &fsp->s_fval[WHITE][r];
171 if (cp->c.b) {
172 cp->c.a += 1;
173 cp->c.b = 0;
174 }
175 }
176
177 nextr:
178 ;
179 }
180
181 update_overlap(osp);
182
183 return(MOVEOK);
184 }
185
186 /*
187 * fix up the overlap array due to updating spot osp.
188 */
189 update_overlap(osp)
190 struct spotstr *osp;
191 {
192 register struct spotstr *sp, *sp1, *sp2;
193 register int i, f, r, r1, d, d1, n;
194 int a, b, bmask, bmask1;
195 struct spotstr *esp;
196 char *str;
197
198 for (r = 4; --r >= 0; ) { /* for each direction */
199 d = dd[r];
200 sp1 = osp;
201 bmask = BFLAG << r;
202 for (f = 0; f < 6; f++, sp1 -= d) { /* for each frame */
203 if (sp1->s_occ == BORDER)
204 break;
205 if (sp1->s_flg & bmask)
206 continue;
207 /*
208 * Update all other frames that intersect the current one
209 * to indicate whether they still overlap or not.
210 * Since F1 overlap F2 == F2 overlap F1, we only need to
211 * do the rows 0 <= r1 <= r. The r1 == r case is special
212 * since the two frames can overlap at more than one point.
213 */
214 str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA];
215 sp2 = sp1 - d;
216 for (i = f + 1; i < 6; i++, sp2 -= d) {
217 if (sp2->s_occ == BORDER)
218 break;
219 if (sp2->s_flg & bmask)
220 continue;
221 /*
222 * count the number of empty spots to see if there is
223 * still an overlap.
224 */
225 n = 0;
226 sp = sp1;
227 for (b = i - f; b < 5; b++, sp += d) {
228 if (sp->s_occ == EMPTY) {
229 esp = sp; /* save the intersection point */
230 n++;
231 }
232 }
233 b = sp2->s_frame[r] - frames;
234 if (n == 0) {
235 if (sp->s_occ == EMPTY) {
236 str[b] &= 0xA;
237 overlap[b * FAREA + a] &= 0xC;
238 intersect[a * FAREA + b] = n = sp - board;
239 intersect[b * FAREA + a] = n;
240 } else {
241 str[b] = 0;
242 overlap[b * FAREA + a] = 0;
243 }
244 } else if (n == 1) {
245 if (sp->s_occ == EMPTY) {
246 str[b] &= 0xAF;
247 overlap[b * FAREA + a] &= 0xCF;
248 } else {
249 str[b] &= 0xF;
250 overlap[b * FAREA + a] &= 0xF;
251 }
252 intersect[a * FAREA + b] = n = esp - board;
253 intersect[b * FAREA + a] = n;
254 }
255 /* else no change, still multiple overlap */
256 }
257
258 /* the other directions can only intersect at spot osp */
259 for (r1 = r; --r1 >= 0; ) {
260 d1 = dd[r1];
261 bmask1 = BFLAG << r1;
262 sp = osp;
263 for (i = 6; --i >= 0; sp -= d1) { /* for each spot */
264 if (sp->s_occ == BORDER)
265 break;
266 if (sp->s_flg & bmask1)
267 continue;
268 b = sp->s_frame[r1] - frames;
269 str[b] = 0;
270 overlap[b * FAREA + a] = 0;
271 }
272 }
273 }
274 }
275 }
276