xref: /original-bsd/games/gomoku/pickmove.c (revision 8af5b582)

/*
 * Copyright (c) 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Ralph Campbell.
 *
 * %sccs.include.redist.c%
 */

#ifndef lint
static char sccsid[] = "@(#)pickmove.c	8.1 (Berkeley) 07/24/94";
#endif /* not lint */

#include <stdio.h>
#include <curses.h>

#include "gomoku.h"

struct	combostr *sortcombos[2];	/* combos at higher levels */
int	combolen[2];			/* number of combos in sortcombos */
int	nextcolor;			/* color of next move */

extern char pdir[];

pickmove(us)
	int us;
{
	register struct spotstr *sp, *sp1, *sp2;
	register union combo *Ocp, *Tcp;

	/* first move is easy */
	if (movenum == 1)
		return (PT(K,10));

	/* initialize all the board values */
	for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
		sp->s_combo[BLACK].s = MAXCOMBO;
		sp->s_combo[WHITE].s = MAXCOMBO;
		sp->s_level[BLACK] = 255;
		sp->s_level[WHITE] = 255;
		sp->s_nforce[BLACK] = 0;
		sp->s_nforce[WHITE] = 0;
		sp->s_flg &= ~(FFLAGALL | MFLAGALL);
	}

	/* remove old combos */
	removecombos(BLACK);
	removecombos(WHITE);
	removeemptyspots();

	/* compute new values */
	nextcolor = us;
	scanframes(BLACK);
	scanframes(WHITE);

	/* find the spot with the highest value */
	for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
		if (sp->s_occ != EMPTY)
			continue;
		if (debug && (sp->s_combo[BLACK].s < 0x200 ||
		    sp->s_combo[WHITE].s < 0x200)) {
			sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board),
				sp->s_combo[BLACK].s, sp->s_level[BLACK],
				sp->s_nforce[BLACK],
				sp->s_combo[WHITE].s, sp->s_level[WHITE],
				sp->s_nforce[WHITE],
				sp->s_wval);
			dlog(fmtbuf);
		}
		/* pick the best black move */
		if (better(sp, sp1, BLACK))
			sp1 = sp;
		/* pick the best white move */
		if (better(sp, sp2, WHITE))
			sp2 = sp;
	}
	if (debug) {
		sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d %d",
			stoc(sp1 - board),
			sp1->s_combo[BLACK].s, sp1->s_level[BLACK],
			sp1->s_nforce[BLACK],
			sp1->s_combo[WHITE].s, sp1->s_level[WHITE],
			sp1->s_nforce[WHITE], sp1->s_wval, combolen[BLACK]);
		dlog(fmtbuf);
		sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d %d",
			stoc(sp2 - board),
			sp2->s_combo[WHITE].s, sp2->s_level[WHITE],
			sp2->s_nforce[WHITE],
			sp2->s_combo[BLACK].s, sp2->s_level[BLACK],
			sp2->s_nforce[BLACK], sp2->s_wval, combolen[WHITE]);
		dlog(fmtbuf);
	}
	if (us == BLACK) {
		Ocp = &sp1->s_combo[BLACK];
		Tcp = &sp2->s_combo[WHITE];
	} else {
		Tcp = &sp1->s_combo[BLACK];
		Ocp = &sp2->s_combo[WHITE];
		sp = sp1;
		sp1 = sp2;
		sp2 = sp;
	}
	/*
	 * Block their combo only if we have to (i.e., if they are one move
	 * away from completing a force and we don't have a force that
	 * we can complete which takes fewer moves to win).
	 */
	if (Tcp->c.a <= 1 && (Ocp->c.a > 1 ||
	    Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b))
		return (sp2 - board);
	return (sp1 - board);
}

/*
 * Return true if spot 'sp' is better than spot 'sp1' for color 'us'.
 */
better(sp, sp1, us)
	struct spotstr *sp;
	struct spotstr *sp1;
	int us;
{
	int them;

	if (sp->s_combo[us].s < sp1->s_combo[us].s)
		return (1);
	if (sp->s_combo[us].s != sp1->s_combo[us].s)
		return (0);
	if (sp->s_level[us] < sp1->s_level[us])
		return (1);
	if (sp->s_level[us] != sp1->s_level[us])
		return (0);
	if (sp->s_nforce[us] > sp1->s_nforce[us])
		return (1);
	if (sp->s_nforce[us] != sp1->s_nforce[us])
		return (0);

	them = !us;
	if (sp->s_combo[them].s < sp1->s_combo[them].s)
		return (1);
	if (sp->s_combo[them].s != sp1->s_combo[them].s)
		return (0);
	if (sp->s_level[them] < sp1->s_level[them])
		return (1);
	if (sp->s_level[them] != sp1->s_level[them])
		return (0);
	if (sp->s_nforce[them] > sp1->s_nforce[them])
		return (1);
	if (sp->s_nforce[them] != sp1->s_nforce[them])
		return (0);

	if (sp->s_wval > sp1->s_wval)
		return (1);
	if (sp->s_wval != sp1->s_wval)
		return (0);

#ifdef SVR4
	return (rand() & 1);
#else
	return (random() & 1);
#endif
}

int		curcolor;	/* implicit parameter to makecombo() */
int		curlevel;	/* implicit parameter to makecombo() */

/*
 * Scan the sorted list of frames and update the minimum combo values.
 */
scanframes(color)
	int color;
{
	register struct combostr *cbp, *ecbp;
	register struct spotstr *sp;
	register union combo *cp;
	register struct elist *ep;
	register int i, r, d, n;
	union combo cb;

	curcolor = color;

	/* check for empty list of frames */
	cbp = sortframes[color];
	if (cbp == (struct combostr *)0)
		return;

	/* quick check for four in a row */
	sp = &board[cbp->c_vertex];
	cb.s = sp->s_fval[color][d = cbp->c_dir].s;
	if (cb.s < 0x101) {
		d = dd[d];
		for (i = 5 + cb.c.b; --i >= 0; sp += d) {
			if (sp->s_occ != EMPTY)
				continue;
			sp->s_combo[color].s = cb.s;
			sp->s_level[color] = 1;
		}
		return;
	}

	/* update the minimum combo value for each spot in the frame */
	n = combolen[color];
	ecbp = cbp;
	do {
		sp = &board[cbp->c_vertex];
		cp = &sp->s_fval[color][r = cbp->c_dir];
		d = dd[r];
		if (cp->c.b) {
			cb.c.a = cp->c.a + 1;
			cb.c.b = 0;
			if (cb.s < sp->s_combo[color].s) {
				sp->s_combo[color].s = cb.s;
				sp->s_level[color] = 1;
			}
			makecombo2(cbp, sp, cb.s);
			if (cp->s != 0x101)
				cb.s = cp->s;
			sp += d;
			i = 4;
		} else {
			cb.s = cp->s;
			i = 5;
		}
		for (; --i >= 0; sp += d) {	/* for each spot */
			if (sp->s_occ != EMPTY)
				continue;
			if (cp->s < sp->s_combo[color].s) {
				sp->s_combo[color].s = cp->s;
				sp->s_level[color] = 1;
			}
			if (cp->s == 0x101)
				sp->s_nforce[color]++;
			makecombo2(cbp, sp, cb.s);
		}
		/* mark frame as having been processed */
		board[cbp->c_vertex].s_flg |= MFLAG << r;
	} while ((cbp = cbp->c_next) != ecbp);

	/* try to make new 3rd level combos, 4th level, etc. */
	d = 2;
	while (combolen[color] > n) {
		if (debug) {
			sprintf(fmtbuf, "%cL%d %d", "BW"[color], d,
				combolen[color] - n);
			dlog(fmtbuf);
			refresh();
		}
		n = combolen[color];
		addframes(d);
		d++;
	}

	/* scan for combos at empty spots */
	for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
		for (ep = sp->s_empty[color]; ep; ep = ep->e_next) {
			cbp = ep->e_combo;
			if (cbp->c_combo.s < sp->s_combo[color].s) {
				sp->s_combo[color].s = cbp->c_combo.s;
				sp->s_level[color] = cbp->c_nframes;
			} else if (cbp->c_combo.s == sp->s_combo[color].s &&
			    cbp->c_nframes < sp->s_level[color])
				sp->s_level[color] = cbp->c_nframes;
		}
	}
}

/*
 * Compute all level 2 combos of frames intersecting spot 'osp'
 * within the frame 'ocbp' and combo value 's'.
 */
makecombo2(ocbp, osp, s)
	struct combostr *ocbp;
	struct spotstr *osp;
	int s;
{
	register struct spotstr *sp, *fsp;
	register struct combostr *cbp;
	register int f, r, d, c;
	int baseB, bmask, n;
	union combo ocb, fcb;

	/* try to combine a new frame with those found so far */
	ocb.s = s;
	baseB = ocb.c.a + ocb.c.b - 1;
	for (r = 4; --r >= 0; ) {			/* for each direction */
	    /* don't include frames that overlap ones already included */
	    if (r == ocbp->c_dir)
		continue;
	    d = dd[r];
	    bmask = (BFLAG | FFLAG | MFLAG) << r;
	    fsp = osp;
	    for (f = 5; --f >= 0; fsp -= d) {		/* for each frame */
		/*
		 * Don't include frames that are blocked or
		 * part of a <1,x> combo.
		 */
		if (fsp->s_occ == BORDER)
		    break;
		if (fsp->s_flg & bmask)
		    continue;

		/* don't include frames of the wrong color */
		fcb.s = fsp->s_fval[curcolor][r].s;
		if (fcb.c.a >= MAXA)
		    continue;

		/*
		 * Get the combo value for this frame.
		 * If this is the end point of the frame,
		 * use the closed ended value for the frame.
		 */
		if (f == 4 && fcb.c.b || fcb.s == 0x101) {
		    fcb.c.a++;
		    fcb.c.b = 0;
		}

		/* compute combo value */
		c = fcb.c.a + ocb.c.a - 3;
		if (c > 3)
		    continue;
		n = fcb.c.a + fcb.c.b - 1;
		if (baseB < n)
		    n = baseB;

		/* make a new combo! */
		cbp = (struct combostr *)malloc(sizeof(struct combostr));
		cbp->c_combo.c.a = c;
		cbp->c_combo.c.b = n;
		cbp->c_link[0] = ocbp;
		cbp->c_link[1] = fsp->s_frame[r];
		cbp->c_vertex = osp - board;
		cbp->c_nframes = 2;
		cbp->c_dir = 0;
		cbp->c_flg = 0;
		cbp->c_refcnt = 0;

		if (c == 1 && debug > 1 || debug > 3) {
		    sprintf(fmtbuf, "%c %s %x/2 r%d f%d %x",
			curcolor == BLACK ? 'b' : 'w',
			stoc(osp - board), cbp->c_combo.s, r, f, ocb.s);
		    dlog(fmtbuf);
#ifdef DEBUG
		    markcombo(cbp, curcolor, 0);
		    bdisp();
		    whatsup(0);
		    clearcombo(cbp, curcolor, 0);
#endif
		}
		if (c > 1) {
		    if (ocb.c.a > 2)
			makeempty(cbp, ocbp, ocb.c.b);
		    if (fcb.c.a > 2)
			makeempty(cbp, cbp->c_link[1], fcb.c.b);

		    /* add the new combo to the end of the list */
		    appendcombo(cbp, curcolor);
		} else {
		    updatecombo(cbp, curcolor);
		    free(cbp);
		}
	    }
	}
}

/*
 * Scan the sorted list of frames and try to combine into combos.
 */
addframes(level)
	int level;
{
	register struct combostr *cbp, *ecbp;
	register struct spotstr *sp, *fsp;
	register int i, r, d;
	union combo fcb, cb;

	curlevel = level;

	/* clear MFLAG for this level */
	cbp = ecbp = sortframes[curcolor];
	do {
		board[cbp->c_vertex].s_flg &= ~MFLAGALL;
	} while ((cbp = cbp->c_next) != ecbp);

	cbp = ecbp;
	do {
		fsp = &board[cbp->c_vertex];
		r = cbp->c_dir;
		/* skip frames that are part of a <1,x> combo */
		if (fsp->s_flg & (FFLAG << r))
			continue;

		/*
		 * Don't include <1,x> combo frames,
		 * treat it as a blocked three in a row instead.
		 */
		fcb.s = fsp->s_fval[curcolor][r].s;
		if (fcb.s == 0x101)
			fcb.s = 0x200;

		/*
		 * If this is an open ended frame, use
		 * the combo value with the end closed.
		 */
		if (fsp->s_occ == EMPTY) {
			if (fcb.c.b) {
				cb.c.a = fcb.c.a + 1;
				cb.c.b = 0;
			} else
				cb.s = fcb.s;
			makecombo(cbp, fsp, cb.s);
		}

		/*
		 * The next four spots are handled the same for both
		 * open and closed ended frames.
		 */
		d = dd[r];
		sp = fsp + d;
		for (i = 4; --i >= 0; sp += d) {
			if (sp->s_occ != EMPTY)
				continue;
			makecombo(cbp, sp, fcb.s);
		}

		/* mark frame as having been processed */
		fsp->s_flg |= MFLAG << r;
	} while ((cbp = cbp->c_next) != ecbp);
}

/*
 * Compute all level N combos of frames intersecting spot 'osp'
 * within the frame 'ocbp' and combo value 's'.
 */
makecombo(ocbp, osp, s)
	struct combostr *ocbp;
	struct spotstr *osp;
	int s;
{
	register struct combostr *cbp, *ncbp;
	register struct spotstr *sp;
	register struct elist *ep;
	register int n, c;
	struct elist *nep, **epp;
	struct combostr *fcbp;
	int baseB, verts, d;
	union combo ocb, cb;

	ocb.s = s;
	baseB = ocb.c.a + ocb.c.b - 1;
	for (ep = osp->s_empty[curcolor]; ep; ep = ep->e_next) {
	    /* don't try to combine this combo if it is the wrong level */
	    cbp = ep->e_combo;
	    if (cbp->c_nframes > curlevel)
		continue;
	    if (cbp->c_nframes != curlevel)
		break;

	    /* don't include frames that overlap ones already included */
	    ncbp = ep->e_frame;
	    if (ncbp->c_dir == ocbp->c_dir ||
		(cbp->c_flg & C_LOOP) && cbp->c_dir == ocbp->c_dir ||
		(n = checkframes(cbp, ocbp, osp - board, ncbp)) < 0)
		    continue;

	    /* compute first half of combo value */
	    c = cbp->c_combo.c.a + ocb.c.a - 3;
	    if (c > 3)
		continue;

	    /* check to see if this frame forms a valid loop */
	    verts = 0;
	    if (n) {
		sp = &board[ocbp->c_vertex];
		d = dd[ocbp->c_dir];
		if (n = ocb.c.b)
			sp += d;
		for (; n < 5; n++, sp += d) {
		    if (sp->s_occ != EMPTY || sp == osp)
			continue;
		    for (nep = sp->s_empty[curcolor]; nep; nep = nep->e_next) {
			if (nep->e_combo == cbp) {
			    verts++;
			    fcbp = nep->e_frame;
			    continue;
			}
			if (nep->e_combo->c_nframes < cbp->c_nframes)
			    break;
		    }
		}
#if 0
		{
		char *str;
		sprintf(fmtbuf, "%c v%d %s%c",
		    curcolor == BLACK ? 'b' : 'w', verts,
		    stoc(ocbp->c_vertex), pdir[ocbp->c_dir]);
		str = fmtbuf + strlen(fmtbuf);
		for (; cbp->c_link[1]; cbp = cbp->c_link[0]) {
		    sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex),
			pdir[cbp->c_link[1]->c_dir]);
		    str += strlen(str);
		}
		sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
		dlog(fmtbuf);
		cbp = ep->e_combo;
		}
#endif
		/* frame overlaps but not at a valid spot */
		if (verts == 0 || ocb.c.a < 3)
		    continue;
	    }

	    /* compute second half of combo value */
	    cb.s = board[ncbp->c_vertex].s_fval[curcolor][ncbp->c_dir].s;
	    n = cb.c.a + cb.c.b - 1;
	    if (baseB < n)
		n = baseB;

	    /* make a new combo! */
	    ncbp = (struct combostr *)malloc(sizeof(struct combostr));
	    c -= verts;
	    ncbp->c_combo.c.a = c;
	    ncbp->c_combo.c.b = n;
	    ncbp->c_link[0] = cbp;
	    ncbp->c_link[1] = ocbp;
	    ncbp->c_vertex = osp - board;
	    ncbp->c_nframes = cbp->c_nframes + 1;
	    ncbp->c_refcnt = 0;
	    if (verts) {
		ncbp->c_flg = C_LOOP;
		ncbp->c_dir = fcbp->c_dir;

		/* add the combo to the list of empty spots */
		nep = (struct elist *)malloc(sizeof(struct elist));
		nep->e_combo = ncbp;
		nep->e_frame = ocbp;
		if (debug > 2) {
		    sprintf(fmtbuf, "e %s", stoc(ncbp->c_vertex));
		    dlog(fmtbuf);
		}

		/* sort by the number of frames in the combo */
		epp = &board[ncbp->c_vertex].s_empty[curcolor];
		while (*epp) {
		    if (cbp->c_nframes >= (*epp)->e_combo->c_nframes)
			break;
		    epp = &(*epp)->e_next;
		}
		nep->e_next = *epp;
		*epp = nep;
	    } else {
		ncbp->c_flg = 0;
		ncbp->c_dir = 0;
		if (ocb.c.a > 2)
		    makeempty(ncbp, ocbp, ocb.c.b);
	    }
	    if (verts > 1 && debug || c == 1 && debug > 1 || debug > 2) {
		char *str;

		sprintf(fmtbuf, "%c %s%c %x v%d %x/%d",
		    curcolor == BLACK ? 'b' : 'w',
		    stoc(osp - board), pdir[ocbp->c_dir], ocb.s,
		    verts, ncbp->c_combo.s, ncbp->c_nframes);
		dlog(fmtbuf);
		str = fmtbuf;
		for (cbp = ncbp; cbp->c_link[1]; cbp = cbp->c_link[0]) {
		    sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex),
			pdir[cbp->c_link[1]->c_dir]);
		    str += strlen(str);
		}
		sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
		dlog(fmtbuf);
#ifdef DEBUG
		markcombo(ncbp, curcolor, 0);
		bdisp();
		whatsup(0);
		clearcombo(ncbp, curcolor, 0);
#endif
	    }
	    if (c > 1) {
		/* add the new combo to the end of the list */
		appendcombo(ncbp, curcolor);
	    } else {
		updatecombo(ncbp, curcolor);
		free(ncbp);
	    }
	}
}

/*
 * Add the combostr 'cbp' to the empty spots list for each empty spot
 * in the frame 'fcbp' except for the intersection.
 * 's' is zero if 'fcbp' is a closed ended frame, else it is one.
 * Return the number of valid intersections with ocbp for detecting loops.
 */
makeempty(cbp, fcbp, s)
	struct combostr *cbp;
	struct combostr *fcbp;
	int s;
{
	struct spotstr *sp, *vsp;
	struct elist *ep, **epp;
	int d;

	if (debug > 2) {
		sprintf(fmtbuf, "E %s%c s%d", stoc(fcbp->c_vertex),
			pdir[fcbp->c_dir], s);
		sprintf(fmtbuf + strlen(fmtbuf), " %s", stoc(cbp->c_vertex));
		dlog(fmtbuf);
	}
	vsp = &board[cbp->c_vertex];
	sp = &board[fcbp->c_vertex];
	d = dd[fcbp->c_dir];
	if (s)
		sp += d;
	for (; s < 5; s++, sp += d) {
		if (sp->s_occ != EMPTY || sp == vsp)
			continue;

		/* add the combo to the list of empty spots */
		ep = (struct elist *)malloc(sizeof(struct elist));
		ep->e_combo = cbp;
		ep->e_frame = fcbp;
		if (debug > 2) {
			sprintf(fmtbuf, "e %s", stoc(sp - board));
			dlog(fmtbuf);
		}

		/* sort by the number of frames in the combo */
		epp = &sp->s_empty[curcolor];
		while (*epp) {
			if (cbp->c_nframes >= (*epp)->e_combo->c_nframes)
				break;
			epp = &(*epp)->e_next;
		}
		ep->e_next = *epp;
		*epp = ep;
	}
}

/*
 * Update the board value based on the combostr.
 * This is called only if 'cbp' is a <1,x> combo.
 * We handle things differently depending on whether the next move
 * would be trying to "complete" the combo or trying to block it.
 */
updatecombo(cbp, color)
	struct combostr *cbp;
	int color;
{
	register struct framestr *fp;
	register struct spotstr *sp;
	register struct combostr *tcbp;
	register int i, d;
	int nframes, vertex;
	union combo cb;

	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
		if (color == nextcolor) {
			/* update the board value for the vertex */
			sp = &board[cbp->c_vertex];
			sp->s_nforce[color]++;
			if (cbp->c_combo.s < sp->s_combo[color].s) {
				sp->s_combo[color].s = cbp->c_combo.s;
				sp->s_level[color] = cbp->c_nframes;
			} else if (cbp->c_combo.s == sp->s_combo[color].s &&
			    cbp->c_nframes < sp->s_level[color])
				sp->s_level[color] = cbp->c_nframes;
		} else {
			/* update the board values for each spot in frame */
			vertex = cbp->c_vertex;
			sp = &board[tcbp->c_vertex];
			if (sp->s_fval[color][tcbp->c_dir].c.b &&
			    tcbp->c_vertex != vertex)
				i = 6;
			else
				i = 5;
			d = dd[tcbp->c_dir];
			cb.s = cbp->c_combo.s;
			nframes = cbp->c_nframes;
			for (; --i >= 0; sp += d) {
				sp->s_nforce[color]++;
				if (cb.s < sp->s_combo[color].s) {
					sp->s_combo[color].s = cb.s;
					sp->s_level[color] = nframes;
				} else if (cb.s == sp->s_combo[color].s &&
				    cbp->c_nframes < sp->s_level[color])
					sp->s_level[color] = nframes;
			}
		}

		/* mark the frame as being part of a <1,x> combo */
		board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir;
	}

	if (color != nextcolor) {
		/* update the board values for each spot in frame */
		sp = &board[cbp->c_vertex];
		if (sp->s_fval[color][cbp->c_dir].c.b &&
		    cbp->c_vertex != vertex)
			i = 6;
		else
			i = 5;
		d = dd[cbp->c_dir];
		for (; --i >= 0; sp += d) {
			sp->s_nforce[color]++;
			if (cb.s < sp->s_combo[color].s) {
				sp->s_combo[color].s = cb.s;
				sp->s_level[color] = nframes;
			} else if (cb.s == sp->s_combo[color].s &&
			    cbp->c_nframes < sp->s_level[color])
				sp->s_level[color] = nframes;
		}
	}

	/* mark the frame as being part of a <1,x> combo */
	board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir;
}

/*
 * Free all elist structures.
 */
removeemptyspots()
{
	register struct elist *ep, *nep;
	register struct spotstr *sp;
	int i;

	for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
		for (i = BLACK; i <= WHITE; i++) {
			for (ep = sp->s_empty[i]; ep; ep = nep) {
				nep = ep->e_next;
				free(ep);
			}
			sp->s_empty[i] = (struct elist *)0;
		}
	}
}

/*
 * Remove all combo structures.
 */
removecombos(color)
	int color;
{
	register struct combostr *cbp, *ncbp, *endcbp;

	/* check the list */
	if ((cbp = sortcombos[color]) == (struct combostr *)0)
		return;

	/* scan the list */
	endcbp = cbp;
	do {
		ncbp = cbp->c_next;
		cbp->c_next = (struct combostr *)0;
		cbp->c_prev = (struct combostr *)0;
		free(cbp);
		cbp = ncbp;
	} while (cbp != endcbp);

	sortcombos[color] = (struct combostr *)0;
	combolen[color] = 0;
}

/*
 * Add combo to the end of the list.
 */
appendcombo(cbp, color)
	struct combostr *cbp;
	int color;
{
	struct combostr *pcbp, *ncbp;

	combolen[color]++;
	ncbp = sortcombos[color];
	if (ncbp == (struct combostr *)0) {
		sortcombos[color] = cbp;
		cbp->c_next = cbp;
		cbp->c_prev = cbp;
		return;
	}
	pcbp = ncbp->c_prev;
	cbp->c_next = ncbp;
	cbp->c_prev = pcbp;
	ncbp->c_prev = cbp;
	pcbp->c_next = cbp;
}

/*
 * Return positive if frame 'fcbp' overlaps any of the frames in 'cbp'
 * other than the frame 'ecbp'.
 * Return -1 if any of the frames in 'cbp' are marked or part of a <1,x> combo.
 * Else, return zero.
 */
checkframes(cbp, fcbp, vertex, ecbp)
	struct combostr *cbp;
	struct combostr *fcbp;
	int vertex;
	struct combostr *ecbp;
{
	struct combostr *tcbp;
	char *str;
	int i, n, mask;
	short *ip;

	n = (fcbp - frames) * FAREA;
	str = &overlap[n];
	ip = &intersect[n];
	i = vertex == fcbp->c_vertex ? 2 : 0;
	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
#if 0
		if (board[tcbp->c_vertex].s_flg & (FFLAG << tcbp->c_dir))
			return (-1);
#endif
		vertex = cbp->c_vertex;
		if (tcbp == ecbp)
			continue;
		n = tcbp - frames;
		if (board[ip[n]].s_occ != EMPTY)
			continue;
		mask = str[n];
		if (mask & (1 << (i + (tcbp->c_vertex == vertex))))
			return (1);
	}
#if 0
	if (board[cbp->c_vertex].s_flg & (FFLAG << cbp->c_dir))
		return (-1);
#endif
	if (cbp == ecbp)
		return (0);
	n = cbp - frames;
	if (board[ip[n]].s_occ != EMPTY)
		return (0);
	mask = str[n];
	return (mask & (1 << (i + (cbp->c_vertex == vertex))));
}

#ifdef DEBUG
markcombo(cbp, color, vertex)
	struct combostr *cbp;
	int color;
	int vertex;
{
	register struct spotstr *sp;
	struct combostr *tcbp;
	int i, d, r, n, mask;

	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0])
		markcombo(tcbp, color, vertex = cbp->c_vertex);
	sp = &board[cbp->c_vertex];
	d = dd[r = cbp->c_dir];
	mask = (IFLAG | CFLAG) << r;
	n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5;
	for (i = 0; i < n; i++, sp += d) {
		if (n == 6 && (i == 0 || i == 5))
			sp->s_flg |= CFLAG << r;
		else
			sp->s_flg |= mask;
	}
}

clearcombo(cbp, color, vertex)
	struct combostr *cbp;
	int color;
	int vertex;
{
	register struct spotstr *sp;
	struct combostr *tcbp;
	int i, d, r, n, mask;

	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0])
		clearcombo(tcbp, color, vertex = cbp->c_vertex);
	sp = &board[cbp->c_vertex];
	d = dd[r = cbp->c_dir];
	mask = ~((IFLAG | CFLAG) << r);
	n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5;
	for (i = 0; i < n; i++, sp += d)
		sp->s_flg &= mask;
}
#endif /* DEBUG */