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