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
41const 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
48static const int weight[5] = { 0, 1, 7, 22, 100 };
49
50static void update_overlap(spot_index);
51
52static bool
53is_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
63static void
64sortframes_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
78static int
79old_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 */
98int
99makemove(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
234static void
235update_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 */
284static void
285update_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 */
305static void
306update_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