1 /* $NetBSD: makemove.c,v 1.11 2009/08/12 06:19:17 dholland Exp $ */
2
3 /*
4 * Copyright (c) 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Ralph Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
34 * @(#)makemove.c 8.2 (Berkeley) 5/3/95
35 */
36
37 #include "gomoku.h"
38
39 /* direction deltas */
40 const int dd[4] = {
41 MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT
42 };
43
44 static const int weight[5] = { 0, 1, 7, 22, 100 };
45
46 static void update_overlap(struct spotstr *);
47
48 /*
49 * Return values:
50 * MOVEOK everything is OK.
51 * RESIGN Player resigned.
52 * ILLEGAL Illegal move.
53 * WIN The winning move was just played.
54 * TIE The game is a tie.
55 */
56 int
makemove(int us,int mv)57 makemove(int us, int mv)
58 {
59 struct spotstr *sp, *fsp;
60 union comboval *cp;
61 struct spotstr *osp;
62 struct combostr *cbp, *cbp1;
63 union comboval *cp1;
64 int i, f, r, d, n;
65 int space, val, bmask;
66
67 /* check for end of game */
68 if (mv == RESIGN)
69 return(RESIGN);
70
71 /* check for illegal move */
72 sp = &board[mv];
73 if (sp->s_occ != EMPTY)
74 return(ILLEGAL);
75
76 /* make move */
77 sp->s_occ = us;
78 movelog[movenum - 1] = mv;
79 if (++movenum == BSZ * BSZ)
80 return(TIE);
81
82 /* compute new frame values */
83 sp->s_wval = 0;
84 osp = sp;
85 for (r = 4; --r >= 0; ) { /* for each direction */
86 d = dd[r];
87 fsp = osp;
88 bmask = BFLAG << r;
89 for (f = 5; --f >= 0; fsp -= d) { /* for each frame */
90 if (fsp->s_occ == BORDER)
91 goto nextr;
92 if (fsp->s_flags & bmask)
93 continue;
94
95 /* remove this frame from the sorted list of frames */
96 cbp = fsp->s_frame[r];
97 if (cbp->c_next) {
98 if (sortframes[BLACK] == cbp)
99 sortframes[BLACK] = cbp->c_next;
100 if (sortframes[WHITE] == cbp)
101 sortframes[WHITE] = cbp->c_next;
102 cbp->c_next->c_prev = cbp->c_prev;
103 cbp->c_prev->c_next = cbp->c_next;
104 }
105
106 /* compute old weight value for this frame */
107 cp = &fsp->s_fval[BLACK][r];
108 if (cp->s <= 0x500)
109 val = weight[5 - cp->c.a - cp->c.b];
110 else
111 val = 0;
112 cp = &fsp->s_fval[WHITE][r];
113 if (cp->s <= 0x500)
114 val += weight[5 - cp->c.a - cp->c.b];
115
116 /* compute new combo value for this frame */
117 sp = fsp;
118 space = sp->s_occ == EMPTY;
119 n = 0;
120 for (i = 5; --i >= 0; sp += d) { /* for each spot */
121 if (sp->s_occ == us)
122 n++;
123 else if (sp->s_occ == EMPTY)
124 sp->s_wval -= val;
125 else {
126 /* this frame is now blocked, adjust values */
127 fsp->s_flags |= bmask;
128 fsp->s_fval[BLACK][r].s = MAXCOMBO;
129 fsp->s_fval[WHITE][r].s = MAXCOMBO;
130 while (--i >= 0) {
131 sp += d;
132 if (sp->s_occ == EMPTY)
133 sp->s_wval -= val;
134 }
135 goto nextf;
136 }
137 }
138
139 /* check for game over */
140 if (n == 5)
141 return(WIN);
142
143 /* compute new value & combo number for this frame & color */
144 fsp->s_fval[!us][r].s = MAXCOMBO;
145 cp = &fsp->s_fval[us][r];
146 /* both ends open? */
147 if (space && sp->s_occ == EMPTY) {
148 cp->c.a = 4 - n;
149 cp->c.b = 1;
150 } else {
151 cp->c.a = 5 - n;
152 cp->c.b = 0;
153 }
154 val = weight[n];
155 sp = fsp;
156 for (i = 5; --i >= 0; sp += d) /* for each spot */
157 if (sp->s_occ == EMPTY)
158 sp->s_wval += val;
159
160 /* add this frame to the sorted list of frames by combo value */
161 cbp1 = sortframes[us];
162 if (!cbp1)
163 sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
164 else {
165 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
166 if (cp->s <= cp1->s) {
167 /* insert at the head of the list */
168 sortframes[us] = cbp;
169 } else {
170 do {
171 cbp1 = cbp1->c_next;
172 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
173 if (cp->s <= cp1->s)
174 break;
175 } while (cbp1 != sortframes[us]);
176 }
177 cbp->c_next = cbp1;
178 cbp->c_prev = cbp1->c_prev;
179 cbp1->c_prev->c_next = cbp;
180 cbp1->c_prev = cbp;
181 }
182
183 nextf:
184 ;
185 }
186
187 /* both ends open? */
188 if (fsp->s_occ == EMPTY) {
189 cp = &fsp->s_fval[BLACK][r];
190 if (cp->c.b) {
191 cp->c.a += 1;
192 cp->c.b = 0;
193 }
194 cp = &fsp->s_fval[WHITE][r];
195 if (cp->c.b) {
196 cp->c.a += 1;
197 cp->c.b = 0;
198 }
199 }
200
201 nextr:
202 ;
203 }
204
205 update_overlap(osp);
206
207 return(MOVEOK);
208 }
209
210 /*
211 * fix up the overlap array due to updating spot osp.
212 */
213 static void
update_overlap(struct spotstr * osp)214 update_overlap(struct spotstr *osp)
215 {
216 struct spotstr *sp, *sp1, *sp2;
217 int i, f, r, r1, d, d1, n;
218 int a, b, bmask, bmask1;
219 struct spotstr *esp;
220 u_char *str;
221
222 esp = NULL;
223 for (r = 4; --r >= 0; ) { /* for each direction */
224 d = dd[r];
225 sp1 = osp;
226 bmask = BFLAG << r;
227 for (f = 0; f < 6; f++, sp1 -= d) { /* for each frame */
228 if (sp1->s_occ == BORDER)
229 break;
230 if (sp1->s_flags & bmask)
231 continue;
232 /*
233 * Update all other frames that intersect the current one
234 * to indicate whether they still overlap or not.
235 * Since F1 overlap F2 == F2 overlap F1, we only need to
236 * do the rows 0 <= r1 <= r. The r1 == r case is special
237 * since the two frames can overlap at more than one point.
238 */
239 str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA];
240 sp2 = sp1 - d;
241 for (i = f + 1; i < 6; i++, sp2 -= d) {
242 if (sp2->s_occ == BORDER)
243 break;
244 if (sp2->s_flags & bmask)
245 continue;
246 /*
247 * count the number of empty spots to see if there is
248 * still an overlap.
249 */
250 n = 0;
251 sp = sp1;
252 for (b = i - f; b < 5; b++, sp += d) {
253 if (sp->s_occ == EMPTY) {
254 esp = sp; /* save the intersection point */
255 n++;
256 }
257 }
258 b = sp2->s_frame[r] - frames;
259 if (n == 0) {
260 if (sp->s_occ == EMPTY) {
261 str[b] &= 0xA;
262 overlap[b * FAREA + a] &= 0xC;
263 intersect[a * FAREA + b] = n = sp - board;
264 intersect[b * FAREA + a] = n;
265 } else {
266 str[b] = 0;
267 overlap[b * FAREA + a] = 0;
268 }
269 } else if (n == 1) {
270 if (sp->s_occ == EMPTY) {
271 str[b] &= 0xAF;
272 overlap[b * FAREA + a] &= 0xCF;
273 } else {
274 str[b] &= 0xF;
275 overlap[b * FAREA + a] &= 0xF;
276 }
277 intersect[a * FAREA + b] = n = esp - board;
278 intersect[b * FAREA + a] = n;
279 }
280 /* else no change, still multiple overlap */
281 }
282
283 /* the other directions can only intersect at spot osp */
284 for (r1 = r; --r1 >= 0; ) {
285 d1 = dd[r1];
286 bmask1 = BFLAG << r1;
287 sp = osp;
288 for (i = 6; --i >= 0; sp -= d1) { /* for each spot */
289 if (sp->s_occ == BORDER)
290 break;
291 if (sp->s_flags & bmask1)
292 continue;
293 b = sp->s_frame[r1] - frames;
294 str[b] = 0;
295 overlap[b * FAREA + a] = 0;
296 }
297 }
298 }
299 }
300 }
301