1 /* $NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig 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
35 #include <sys/cdefs.h>
36 /* @(#)makemove.c 8.2 (Berkeley) 5/3/95 */
37 __RCSID("$NetBSD: makemove.c,v 1.43 2022/06/19 10:23:48 rillig Exp $");
38
39 #include "gomoku.h"
40
41 const int dd[4] = { /* direction deltas */
42 1, /* right */
43 -(BSZ + 1) + 1, /* down + right */
44 -(BSZ + 1), /* down */
45 -(BSZ + 1) - 1 /* down + left */
46 };
47
48 static const int weight[5] = { 0, 1, 7, 22, 100 };
49
50 static void update_overlap(spot_index);
51
52 static bool
is_tie(void)53 is_tie(void)
54 {
55
56 for (int y = 1; y <= BSZ; y++)
57 for (int x = 1; x <= BSZ; x++)
58 if (board[PT(x, y)].s_wval != 0)
59 return false;
60 return true;
61 }
62
63 static void
sortframes_remove(struct combostr * cbp)64 sortframes_remove(struct combostr *cbp)
65 {
66
67 if (cbp->c_next == NULL)
68 return;
69
70 if (sortframes[BLACK] == cbp)
71 sortframes[BLACK] = cbp->c_next;
72 if (sortframes[WHITE] == cbp)
73 sortframes[WHITE] = cbp->c_next;
74 cbp->c_next->c_prev = cbp->c_prev;
75 cbp->c_prev->c_next = cbp->c_next;
76 }
77
78 static int
old_weight_value(const struct spotstr * sp,direction r)79 old_weight_value(const struct spotstr *sp, direction r)
80 {
81 union comboval cb;
82 int val = 0;
83 if ((cb = sp->s_fval[BLACK][r]).s <= 0x500)
84 val += weight[5 - cb.cv_force - cb.cv_win];
85 if ((cb = sp->s_fval[WHITE][r]).s <= 0x500)
86 val += weight[5 - cb.cv_force - cb.cv_win];
87 return val;
88 }
89
90 /*
91 * Return values:
92 * MOVEOK everything is OK.
93 * RESIGN Player resigned.
94 * ILLEGAL Illegal move.
95 * WIN The winning move was just played.
96 * TIE The game is a tie.
97 */
98 int
makemove(player_color us,spot_index mv)99 makemove(player_color us, spot_index mv)
100 {
101
102 /* check for end of game */
103 if (mv == RESIGN)
104 return RESIGN;
105
106 /* check for illegal move */
107 struct spotstr *sp = &board[mv];
108 if (sp->s_occ != EMPTY)
109 return ILLEGAL;
110
111 /* make move */
112 sp->s_occ = us;
113 game.moves[game.nmoves++] = mv;
114
115 /* compute new frame values */
116 sp->s_wval = 0;
117 for (direction r = 4; r-- > 0; ) {
118 int d = dd[r];
119 struct spotstr *fsp = &board[mv];
120
121 for (int f = 5; --f >= 0; fsp -= d) { /* for each frame */
122 if (fsp->s_occ == BORDER)
123 goto nextr;
124 if (is_blocked(fsp, r))
125 continue;
126
127 struct combostr *cbp = &frames[fsp->s_frame[r]];
128 sortframes_remove(cbp);
129
130 int val = old_weight_value(fsp, r);
131
132 /* compute new combo value for this frame */
133 bool space = fsp->s_occ == EMPTY;
134 int n = 0;
135 sp = fsp;
136 for (int off = 5; off-- > 0; sp += d) { /* for each spot */
137 if (sp->s_occ == us)
138 n++;
139 else if (sp->s_occ == EMPTY)
140 sp->s_wval -= val;
141 else {
142 set_blocked(fsp, r);
143 /* adjust values */
144 fsp->s_fval[BLACK][r].s = 0x600;
145 fsp->s_fval[WHITE][r].s = 0x600;
146 while (off-- > 0) {
147 sp += d;
148 if (sp->s_occ == EMPTY)
149 sp->s_wval -= val;
150 }
151 goto nextf;
152 }
153 }
154
155 /* check for game over */
156 if (n == 5) {
157 game.win_spot = (spot_index)(fsp - board);
158 game.win_dir = r;
159 return WIN;
160 }
161
162 /* compute new value & combo number for this frame & color */
163 player_color them = us != BLACK ? BLACK : WHITE;
164 fsp->s_fval[them][r].s = 0x600;
165 union comboval *cp = &fsp->s_fval[us][r];
166 /* both ends open? */
167 if (space && sp->s_occ == EMPTY) {
168 cp->cv_force = 4 - n;
169 cp->cv_win = 1;
170 } else {
171 cp->cv_force = 5 - n;
172 cp->cv_win = 0;
173 }
174 val = weight[n];
175 sp = fsp;
176 for (int off = 5; off-- > 0; sp += d) /* for each spot */
177 if (sp->s_occ == EMPTY)
178 sp->s_wval += val;
179
180 /* add this frame to the sorted list of frames by combo value */
181 struct combostr *cbp1 = sortframes[us];
182 if (cbp1 == NULL)
183 sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
184 else {
185 union comboval *cp1 =
186 &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
187 if (cp->s <= cp1->s) {
188 /* insert at the head of the list */
189 sortframes[us] = cbp;
190 } else {
191 do {
192 cbp1 = cbp1->c_next;
193 cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
194 if (cp->s <= cp1->s)
195 break;
196 } while (cbp1 != sortframes[us]);
197 }
198 cbp->c_next = cbp1;
199 cbp->c_prev = cbp1->c_prev;
200 cbp1->c_prev->c_next = cbp;
201 cbp1->c_prev = cbp;
202 }
203
204 nextf:
205 ;
206 }
207
208 /* both ends open? */
209 if (fsp->s_occ == EMPTY) {
210 union comboval *cp = &fsp->s_fval[BLACK][r];
211 if (cp->cv_win != 0) {
212 cp->cv_force++;
213 cp->cv_win = 0;
214 }
215 cp = &fsp->s_fval[WHITE][r];
216 if (cp->cv_win != 0) {
217 cp->cv_force++;
218 cp->cv_win = 0;
219 }
220 }
221
222 nextr:
223 ;
224 }
225
226 update_overlap(mv);
227
228 if (is_tie())
229 return TIE;
230
231 return MOVEOK;
232 }
233
234 static void
update_overlap_same_direction(spot_index s1,spot_index s2,frame_index a,int d,int off_minus_f,direction r)235 update_overlap_same_direction(spot_index s1, spot_index s2,
236 frame_index a, int d, int off_minus_f,
237 direction r)
238 {
239 /*
240 * count the number of empty spots to see if there is
241 * still an overlap.
242 */
243 int n = 0;
244 spot_index s = s1;
245 spot_index es = 0;
246 for (int b = off_minus_f; b < 5; b++, s += d) {
247 if (board[s].s_occ == EMPTY) {
248 es = s; /* save the intersection point */
249 n++;
250 }
251 }
252
253 frame_index b = board[s2].s_frame[r];
254 if (n == 0) {
255 if (board[s].s_occ == EMPTY) {
256 overlap[a * FAREA + b] &= 0xA;
257 overlap[b * FAREA + a] &= 0xC;
258 intersect[a * FAREA + b] = s;
259 intersect[b * FAREA + a] = s;
260 } else {
261 overlap[a * FAREA + b] = 0;
262 overlap[b * FAREA + a] = 0;
263 }
264 } else if (n == 1) {
265 if (board[s].s_occ == EMPTY) {
266 overlap[a * FAREA + b] &= 0xAF;
267 overlap[b * FAREA + a] &= 0xCF;
268 } else {
269 overlap[a * FAREA + b] &= 0xF;
270 overlap[b * FAREA + a] &= 0xF;
271 }
272 intersect[a * FAREA + b] = es;
273 intersect[b * FAREA + a] = es;
274 }
275 /* else no change, still multiple overlap */
276 }
277
278 /*
279 * The last move was at 'os', which is part of frame 'a'. There are 6 frames
280 * with direction 'rb' that cross frame 'a' in 'os'. Since the spot 'os'
281 * cannot be used as a double threat anymore, mark each of these crossing
282 * frames as non-overlapping with frame 'a'.
283 */
284 static void
update_overlap_different_direction(spot_index os,frame_index a,direction rb)285 update_overlap_different_direction(spot_index os, frame_index a, direction rb)
286 {
287
288 int db = dd[rb];
289 for (int off = 0; off < 6; off++) {
290 const struct spotstr *sp = &board[os - db * off];
291 if (sp->s_occ == BORDER)
292 break;
293 if (is_blocked(sp, rb))
294 continue;
295
296 frame_index b = sp->s_frame[rb];
297 overlap[a * FAREA + b] = 0;
298 overlap[b * FAREA + a] = 0;
299 }
300 }
301
302 /*
303 * fix up the overlap array according to the changed 'os'.
304 */
305 static void
update_overlap(spot_index os)306 update_overlap(spot_index os)
307 {
308
309 for (direction r = 4; r-- > 0; ) {
310 int d = dd[r];
311 spot_index s1 = os;
312
313 /* for each frame 'a' that contains the spot 'os' */
314 for (int f = 0; f < 6; f++, s1 -= d) {
315 if (board[s1].s_occ == BORDER)
316 break;
317 if (is_blocked(&board[s1], r))
318 continue;
319
320 /*
321 * Update all other frames that intersect the current one
322 * to indicate whether they still overlap or not.
323 * Since F1 overlap F2 == F2 overlap F1, we only need to
324 * do the rows 0 <= r1 <= r. The r1 == r case is special
325 * since the two frames can overlap in more than one spot.
326 */
327 frame_index a = board[s1].s_frame[r];
328
329 spot_index s2 = s1 - d;
330 for (int off = f + 1; off < 6; off++, s2 -= d) {
331 if (board[s2].s_occ == BORDER)
332 break;
333 if (is_blocked(&board[s2], r))
334 continue;
335
336 update_overlap_same_direction(s1, s2, a, d, off - f, r);
337 }
338
339 /* the other directions can only intersect at spot 'os' */
340 for (direction rb = 0; rb < r; rb++)
341 update_overlap_different_direction(os, a, rb);
342 }
343 }
344 }
345