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