Import of 4.4BSD-Lite2 source

9 files changed, 3307 insertions, 0 deletions

diff --git a/gomoku/Makefile b/gomoku/Makefile
new file mode 100644
index 00000000..025ed084
--- /dev/null
+++ b/gomoku/Makefile
@@ -0,0 +1,10 @@
+#	@(#)Makefile	8.1 (Berkeley) 7/24/94
+
+PROG=	gomoku
+SRCS=	bdinit.c bdisp.c main.c makemove.c pickmove.c stoc.c
+MAN6=	gomoku.0
+DPADD=	${LIBCURSES} ${LIBTERM}
+LDADD=	-lcurses -ltermlib
+HIDEGAME=hidegame
+
+.include <bsd.prog.mk>
diff --git a/gomoku/bdinit.c b/gomoku/bdinit.c
new file mode 100644
index 00000000..dd3c1799
--- /dev/null
+++ b/gomoku/bdinit.c
@@ -0,0 +1,246 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)bdinit.c	8.2 (Berkeley) 5/3/95";
+#endif /* not lint */
+
+#include <string.h>
+#include "gomoku.h"
+
+bdinit(bp)
+	struct spotstr *bp;
+{
+	register int i, j, r;
+	register struct spotstr *sp;
+	register struct combostr *cbp;
+
+	movenum = 1;
+
+	/* mark the borders as such */
+	sp = bp;
+	for (i = BSZ2; --i >= 0; sp++) {
+		sp->s_occ = BORDER;		/* top border */
+		sp->s_flg = BFLAGALL;
+	}
+
+	/* fill entire board with EMPTY spots */
+	memset(frames, 0, sizeof(frames));
+	cbp = frames;
+	for (j = 0; ++j < BSZ1; sp++) {			/* for each row */
+		for (i = 0; ++i < BSZ1; sp++) {		/* for each column */
+			sp->s_occ = EMPTY;
+			sp->s_flg = 0;
+			sp->s_wval = 0;
+			if (j < 5) {
+				/* directions 1, 2, 3 are blocked */
+				sp->s_flg |= (BFLAG << 1) | (BFLAG << 2) |
+					(BFLAG << 3);
+				sp->s_fval[BLACK][1].s = MAXCOMBO;
+				sp->s_fval[BLACK][2].s = MAXCOMBO;
+				sp->s_fval[BLACK][3].s = MAXCOMBO;
+				sp->s_fval[WHITE][1].s = MAXCOMBO;
+				sp->s_fval[WHITE][2].s = MAXCOMBO;
+				sp->s_fval[WHITE][3].s = MAXCOMBO;
+			} else if (j == 5) {
+				/* five spaces, blocked on one side */
+				sp->s_fval[BLACK][1].s = 0x500;
+				sp->s_fval[BLACK][2].s = 0x500;
+				sp->s_fval[BLACK][3].s = 0x500;
+				sp->s_fval[WHITE][1].s = 0x500;
+				sp->s_fval[WHITE][2].s = 0x500;
+				sp->s_fval[WHITE][3].s = 0x500;
+			} else {
+				/* six spaces, not blocked */
+				sp->s_fval[BLACK][1].s = 0x401;
+				sp->s_fval[BLACK][2].s = 0x401;
+				sp->s_fval[BLACK][3].s = 0x401;
+				sp->s_fval[WHITE][1].s = 0x401;
+				sp->s_fval[WHITE][2].s = 0x401;
+				sp->s_fval[WHITE][3].s = 0x401;
+			}
+			if (i > (BSZ - 4)) {
+				/* directions 0, 1 are blocked */
+				sp->s_flg |= BFLAG | (BFLAG << 1);
+				sp->s_fval[BLACK][0].s = MAXCOMBO;
+				sp->s_fval[BLACK][1].s = MAXCOMBO;
+				sp->s_fval[WHITE][0].s = MAXCOMBO;
+				sp->s_fval[WHITE][1].s = MAXCOMBO;
+			} else if (i == (BSZ - 4)) {
+				sp->s_fval[BLACK][0].s = 0x500;
+				sp->s_fval[WHITE][0].s = 0x500;
+				/* if direction 1 is not blocked */
+				if (!(sp->s_flg & (BFLAG << 1))) {
+					sp->s_fval[BLACK][1].s = 0x500;
+					sp->s_fval[WHITE][1].s = 0x500;
+				}
+			} else {
+				sp->s_fval[BLACK][0].s = 0x401;
+				sp->s_fval[WHITE][0].s = 0x401;
+				if (i < 5) {
+					/* direction 3 is blocked */
+					sp->s_flg |= (BFLAG << 3);
+					sp->s_fval[BLACK][3].s = MAXCOMBO;
+					sp->s_fval[WHITE][3].s = MAXCOMBO;
+				} else if (i == 5 &&
+				    !(sp->s_flg & (BFLAG << 3))) {
+					sp->s_fval[BLACK][3].s = 0x500;
+					sp->s_fval[WHITE][3].s = 0x500;
+				}
+			}
+			/*
+			 * Allocate a frame structure for non blocked frames.
+			 */
+			for (r = 4; --r >= 0; ) {
+				if (sp->s_flg & (BFLAG << r))
+					continue;
+				cbp->c_combo.s = sp->s_fval[BLACK][r].s;
+				cbp->c_vertex = sp - board;
+				cbp->c_nframes = 1;
+				cbp->c_dir = r;
+				sp->s_frame[r] = cbp;
+				cbp++;
+			}
+		}
+		sp->s_occ = BORDER;		/* left & right border */
+		sp->s_flg = BFLAGALL;
+	}
+
+	/* mark the borders as such */
+	for (i = BSZ1; --i >= 0; sp++) {
+		sp->s_occ = BORDER;		/* bottom border */
+		sp->s_flg = BFLAGALL;
+	}
+
+	sortframes[BLACK] = (struct combostr *)0;
+	sortframes[WHITE] = (struct combostr *)0;
+	init_overlap();
+}
+
+/*
+ * Initialize the overlap array.
+ * Each entry in the array is a bit mask with eight bits corresponding
+ * to whether frame B overlaps frame A (as indexed by overlap[A * FAREA + B]).
+ * The eight bits coorespond to whether A and B are open ended (length 6) or
+ * closed (length 5).
+ *	0	A closed and B closed
+ *	1	A closed and B open
+ *	2	A open and B closed
+ *	3	A open and B open
+ *	4	A closed and B closed and overlaps in more than one spot
+ *	5	A closed and B open and overlaps in more than one spot
+ *	6	A open and B closed and overlaps in more than one spot
+ *	7	A open and B open and overlaps in more than one spot
+ * As pieces are played, it can make frames not overlap if there are no
+ * common open spaces shared between the two frames.
+ */
+init_overlap()
+{
+	register struct spotstr *sp1, *sp2;
+	register struct combostr *cbp;
+	register int i, f, r, n, d1, d2;
+	int mask, bmask, vertex, s;
+	u_char *str;
+	short *ip;
+
+	memset(overlap, 0, sizeof(overlap));
+	memset(intersect, 0, sizeof(intersect));
+	str = &overlap[FAREA * FAREA];
+	ip = &intersect[FAREA * FAREA];
+	for (cbp = frames + FAREA; --cbp >= frames; ) {		/* each frame */
+	    str -= FAREA;
+	    ip -= FAREA;
+	    sp1 = &board[vertex = cbp->c_vertex];
+	    d1 = dd[r = cbp->c_dir];
+	    /*
+	     * s = 5 if closed, 6 if open.
+	     * At this point black & white are the same.
+	     */
+	    s = 5 + sp1->s_fval[BLACK][r].c.b;
+	    /* for each spot in frame A */
+	    for (i = 0; i < s; i++, sp1 += d1, vertex += d1) {
+		/* the sixth spot in frame A only overlaps if it is open */
+		mask = (i == 5) ? 0xC : 0xF;
+		/* for each direction */
+		for (r = 4; --r >= 0; ) {
+		    bmask = BFLAG << r;
+		    sp2 = sp1;
+		    d2 = dd[r];
+		    /* for each frame that intersects at spot sp1 */
+		    for (f = 0; f < 6; f++, sp2 -= d2) {
+			if (sp2->s_occ == BORDER)
+			    break;
+			if (sp2->s_flg & bmask)
+			    continue;
+			n = sp2->s_frame[r] - frames;
+			ip[n] = vertex;
+			str[n] |= (f == 5) ? mask & 0xA : mask;
+			if (r == cbp->c_dir) {
+			    /* compute the multiple spot overlap values */
+			    switch (i) {
+			    case 0:	/* sp1 is the first spot in A */
+				if (f == 4)
+				    str[n] |= 0xA0;
+				else if (f != 5)
+				    str[n] |= 0xF0;
+				break;
+			    case 1:	/* sp1 is the second spot in A */
+				if (f == 5)
+				    str[n] |= 0xA0;
+				else
+				    str[n] |= 0xF0;
+				break;
+			    case 4:	/* sp1 is the penultimate spot in A */
+				if (f == 0)
+				    str[n] |= 0xC0;
+				else
+				    str[n] |= 0xF0;
+				break;
+			    case 5:	/* sp1 is the last spot in A */
+				if (f == 1)
+				    str[n] |= 0xC0;
+				else if (f != 0)
+				    str[n] |= 0xF0;
+				break;
+			    default:
+				str[n] |= 0xF0;
+			    }
+			}
+		    }
+		}
+	    }
+	}
+}
diff --git a/gomoku/bdisp.c b/gomoku/bdisp.c
new file mode 100644
index 00000000..da7dfb4f
--- /dev/null
+++ b/gomoku/bdisp.c
@@ -0,0 +1,275 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)bdisp.c	8.2 (Berkeley) 5/3/95";
+#endif /* not lint */
+
+#include "gomoku.h"
+#include <stdio.h>
+#include <curses.h>
+
+#define	SCRNH		24		/* assume 24 lines for the moment */
+#define	SCRNW		80		/* assume 80 chars for the moment */
+
+static	int	lastline;
+static	char	pcolor[] = "*O.?";
+
+/*
+ * Initialize screen display.
+ */
+cursinit()
+{
+
+	initscr();
+	noecho();
+	cbreak();
+	leaveok(stdscr, TRUE);
+}
+
+/*
+ * Restore screen display.
+ */
+cursfini()
+{
+
+	leaveok(stdscr, FALSE);
+	move(23, 0);
+	clrtoeol();
+	refresh();
+	endwin();
+}
+
+/*
+ * Initialize board display.
+ */
+bdisp_init()
+{
+	register int i, j;
+
+	/* top border */
+	for (i = 1; i < BSZ1; i++) {
+		move(0, 2 * i + 1);
+		addch(letters[i]);
+	}
+	/* left and right edges */
+	for (j = BSZ1; --j > 0; ) {
+		move(20 - j, 0);
+		printw("%2d ", j);
+		move(20 - j, 2 * BSZ1 + 1);
+		printw("%d ", j);
+	}
+	/* bottom border */
+	for (i = 1; i < BSZ1; i++) {
+		move(20, 2 * i + 1);
+		addch(letters[i]);
+	}
+	bdwho(0);
+	move(0, 47);
+	addstr("#  black  white");
+	lastline = 0;
+	bdisp();
+}
+
+/*
+ * Update who is playing whom.
+ */
+bdwho(update)
+	int update;
+{
+	int i;
+	extern char *plyr[];
+
+	move(21, 0);
+	clrtoeol();
+	i = 6 - strlen(plyr[BLACK]) / 2;
+	move(21, i > 0 ? i : 0);
+	printw("BLACK/%s", plyr[BLACK]);
+	i = 30 - strlen(plyr[WHITE]) / 2;
+	move(21, i);
+	printw("WHITE/%s", plyr[WHITE]);
+	move(21, 19);
+	addstr(" vs. ");
+	if (update)
+		refresh();
+}
+
+/*
+ * Update the board display after a move.
+ */
+bdisp()
+{
+	register int i, j, c;
+	register struct spotstr *sp;
+
+	for (j = BSZ1; --j > 0; ) {
+		for (i = 1; i < BSZ1; i++) {
+			move(BSZ1 - j, 2 * i + 1);
+			sp = &board[i + j * BSZ1];
+			if (debug > 1 && sp->s_occ == EMPTY) {
+				if (sp->s_flg & IFLAGALL)
+					c = '+';
+				else if (sp->s_flg & CFLAGALL)
+					c = '-';
+				else
+					c = '.';
+			} else
+				c = pcolor[sp->s_occ];
+			addch(c);
+		}
+	}
+	refresh();
+}
+
+#ifdef DEBUG
+/*
+ * Dump board display to a file.
+ */
+bdump(fp)
+	FILE *fp;
+{
+	register int i, j, c;
+	register struct spotstr *sp;
+
+	/* top border */
+	fprintf(fp, "   A B C D E F G H J K L M N O P Q R S T\n");
+
+	for (j = BSZ1; --j > 0; ) {
+		/* left edge */
+		fprintf(fp, "%2d ", j);
+		for (i = 1; i < BSZ1; i++) {
+			sp = &board[i + j * BSZ1];
+			if (debug > 1 && sp->s_occ == EMPTY) {
+				if (sp->s_flg & IFLAGALL)
+					c = '+';
+				else if (sp->s_flg & CFLAGALL)
+					c = '-';
+				else
+					c = '.';
+			} else
+				c = pcolor[sp->s_occ];
+			putc(c, fp);
+			putc(' ', fp);
+		}
+		/* right edge */
+		fprintf(fp, "%d\n", j);
+	}
+
+	/* bottom border */
+	fprintf(fp, "   A B C D E F G H J K L M N O P Q R S T\n");
+}
+#endif /* DEBUG */
+
+/*
+ * Display a transcript entry
+ */
+dislog(str)
+	char *str;
+{
+
+	if (++lastline >= SCRNH - 1) {
+		/* move 'em up */
+		lastline = 1;
+	}
+	if (strlen(str) >= SCRNW - 46)
+		str[SCRNW - 46 - 1] = '\0';
+	move(lastline, 46);
+	addstr(str);
+	clrtoeol();
+	move(lastline + 1, 46);
+	clrtoeol();
+}
+
+/*
+ * Display a question.
+ */
+ask(str)
+	char *str;
+{
+	int len = strlen(str);
+
+	move(23, 0);
+	addstr(str);
+	clrtoeol();
+	move(23, len);
+	refresh();
+}
+
+getline(buf, size)
+	char *buf;
+	int size;
+{
+	register char *cp, *end;
+	register int c;
+	extern int interactive;
+
+	cp = buf;
+	end = buf + size - 1;	/* save room for the '\0' */
+	while (cp < end && (c = getchar()) != EOF && c != '\n' && c != '\r') {
+		*cp++ = c;
+		if (interactive) {
+			switch (c) {
+			case 0x0c: /* ^L */
+				wrefresh(curscr);
+				cp--;
+				continue;
+			case 0x15: /* ^U */
+			case 0x18: /* ^X */
+				while (cp > buf) {
+					cp--;
+					addch('\b');
+				}
+				clrtoeol();
+				break;
+			case '\b':
+			case 0x7f: /* DEL */
+				if (cp == buf + 1) {
+					cp--;
+					continue;
+				}
+				cp -= 2;
+				addch('\b');
+				c = ' ';
+				/* FALLTHROUGH */
+			default:
+				addch(c);
+			}
+			refresh();
+		}
+	}
+	*cp = '\0';
+	return(c != EOF);
+}
diff --git a/gomoku/gomoku.6 b/gomoku/gomoku.6
new file mode 100644
index 00000000..7888e1cd
--- /dev/null
+++ b/gomoku/gomoku.6
@@ -0,0 +1,92 @@
+.\" 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.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. All advertising materials mentioning features or use of this software
+.\"    must display the following acknowledgement:
+.\"	This product includes software developed by the University of
+.\"	California, Berkeley and its contributors.
+.\" 4. Neither the name of the University nor the names of its contributors
+.\"    may be used to endorse or promote products derived from this software
+.\"    without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\"     @(#)gomoku.6	8.2 (Berkeley) 8/4/94
+.\"
+.Dd August 4, 1994
+.Dt GOMOKU 6
+.Os BSD 4.4
+.Sh NAME
+.Nm gomoku
+.Nd game of 5 in a row
+.Sh SYNOPSIS
+.Nm gomoku
+.Op Fl bcdu
+.Op Fl D Ar debugfile
+.Op Ar inputfile
+.Sh DESCRIPTION
+.Nm Gomoku
+is a two player game were the object is to get 5 in a row horizontally,
+vertically or diagonally on a 19 by 19 grid. By convention, black always
+moves first.
+With no arguments,
+.Nm gomoku
+will display a playing board and prompt for moves from the user.
+Valid moves are a letter for the column and a number for the row of an empty
+board location. Entering ``quit" or ``resign" will end the game.
+You can save the current state of the game by entering ``save" and
+supplying a file name when prompted.
+The optional file
+.Ar inputfile
+can be used to restore a saved game.
+.Pp
+The options are:
+.Bl -tag -width Ds
+.It Fl b
+This option sets background mode. Input moves are read from standard input,
+the computer picks a move, and prints it to standard output. The first
+input line should be either ``black" or ``white" to specify whether
+.Nm gomoku
+has the first move or not respectively. This
+option was intended for game tournaments where a referee program handles
+the board display and pits one program against another.
+.It Fl c
+Computer verses computer.
+.Nm Gomoku
+will play a game against itself. This is mostly used for testing.
+.It Fl d
+Print debugging information. Repeating this option more than
+once yields more detailed information.
+.It Fl D Ar debugfile
+Print the debug information to
+.Ar debugfile
+instead of to the standard output.
+.It Fl u
+User verses user. This is mostly used for testing.
+.Sh AUTHOR
+Ralph Campbell
+.Sh ACKNOWLEDGEMENTS
+The board display routines were based on the
+.Nm goref
+program written by Peter Langston.
diff --git a/gomoku/gomoku.h b/gomoku/gomoku.h
new file mode 100644
index 00000000..173e329f
--- /dev/null
+++ b/gomoku/gomoku.h
@@ -0,0 +1,266 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)gomoku.h	8.2 (Berkeley) 5/3/95
+ */
+
+#include <sys/types.h>
+
+/* board dimensions */
+#define BSZ	19
+#define BSZ1	(BSZ+1)
+#define BSZ2	(BSZ+2)
+#define BAREA	(BSZ2*BSZ1+1)
+
+/* frame dimentions (based on 5 in a row) */
+#define FSZ1	BSZ
+#define FSZ2	(BSZ-4)
+#define FAREA	(FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2)
+
+#define MUP	(BSZ1)
+#define MDOWN	(-BSZ1)
+#define MLEFT	(-1)
+#define MRIGHT	(1)
+
+/* values for s_occ */
+#define BLACK	0
+#define WHITE	1
+#define EMPTY	2
+#define BORDER	3
+
+/* return values for makemove() */
+#define MOVEOK	0
+#define RESIGN	1
+#define ILLEGAL	2
+#define WIN	3
+#define TIE	4
+#define SAVE	5
+
+#define A 1
+#define B 2
+#define C 3
+#define D 4
+#define E 5
+#define F 6
+#define G 7
+#define H 8
+#define J 9
+#define K 10
+#define L 11
+#define M 12
+#define N 13
+#define O 14
+#define P 15
+#define Q 16
+#define R 17
+#define S 18
+#define T 19
+
+#define PT(x,y)		((x) + BSZ1 * (y))
+
+/*
+ * A 'frame' is a group of five or six contiguous board locations.
+ * An open ended frame is one with spaces on both ends; otherwise, its closed.
+ * A 'combo' is a group of intersecting frames and consists of two numbers:
+ * 'A' is the number of moves to make the combo non-blockable.
+ * 'B' is the minimum number of moves needed to win once it can't be blocked.
+ * A 'force' is a combo that is one move away from being non-blockable
+ *
+ * Single frame combo values:
+ *     <A,B>	board values
+ *	5,0	. . . . . O
+ *	4,1	. . . . . .
+ *	4,0	. . . . X O
+ *	3,1	. . . . X .
+ *	3,0	. . . X X O
+ *	2,1	. . . X X .
+ *	2,0	. . X X X O
+ *	1,1	. . X X X .
+ *	1,0	. X X X X O
+ *	0,1	. X X X X .
+ *	0,0	X X X X X O
+ *
+ * The rule for combining two combos (<A1,B1> <A2,B2>)
+ * with V valid intersection points, is:
+ *	A' = A1 + A2 - 2 - V
+ *	B' = MIN(A1 + B1 - 1, A2 + B2 - 1)
+ * Each time a frame is added to the combo, the number of moves to complete
+ * the force is the number of moves needed to 'fill' the frame plus one at
+ * the intersection point. The number of moves to win is the number of moves
+ * to complete the best frame minus the last move to complete the force.
+ * Note that it doesn't make sense to combine a <1,x> with anything since
+ * it is already a force. Also, the frames have to be independent so a
+ * single move doesn't affect more than one frame making up the combo.
+ *
+ * Rules for comparing which of two combos (<A1,B1> <A2,B2>) is better:
+ * Both the same color:
+ *	<A',B'> = (A1 < A2 || A1 == A2 && B1 <= B2) ? <A1,B1> : <A2,B2>
+ *	We want to complete the force first, then the combo with the
+ *	fewest moves to win.
+ * Different colors, <A1,B1> is the combo for the player with the next move:
+ *	<A',B'> = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? <A2,B2> : <A1,B1>
+ *	We want to block 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 or the same number of moves to win).
+ */
+
+#define MAXA		6
+#define MAXB		2
+#define MAXCOMBO	0x600
+
+union	comboval {
+	struct {
+#if BYTE_ORDER == BIG_ENDIAN
+		u_char	a;	/* # moves to complete force */
+		u_char	b;	/* # moves to win */
+#endif
+#if BYTE_ORDER == LITTLE_ENDIAN
+		u_char	b;	/* # moves to win */
+		u_char	a;	/* # moves to complete force */
+#endif
+	} c;
+	u_short	s;
+};
+
+/*
+ * This structure is used to record information about single frames (F) and
+ * combinations of two more frames (C).
+ * For combinations of two or more frames, there is an additional
+ * array of pointers to the frames of the combination which is sorted
+ * by the index into the frames[] array. This is used to prevent duplication
+ * since frame A combined with B is the same as B with A.
+ *	struct combostr *c_sort[size c_nframes];
+ * The leaves of the tree (frames) are numbered 0 (bottom, leftmost)
+ * to c_nframes - 1 (top, right). This is stored in c_frameindex and
+ * c_dir if C_LOOP is set.
+ */
+struct combostr {
+	struct combostr	*c_next;	/* list of combos at the same level */
+	struct combostr	*c_prev;	/* list of combos at the same level */
+	struct combostr	*c_link[2];	/* C:previous level or F:NULL */
+	union comboval	c_linkv[2];	/* C:combo value for link[0,1] */
+	union comboval	c_combo;	/* C:combo value for this level */
+	u_short		c_vertex;	/* C:intersection or F:frame head */
+	u_char		c_nframes;	/* number of frames in the combo */
+	u_char		c_dir;		/* C:loop frame or F:frame direction */
+	u_char		c_flg;		/* C:combo flags */
+	u_char		c_frameindex;	/* C:intersection frame index */
+	u_char		c_framecnt[2];	/* number of frames left to attach */
+	u_char		c_emask[2];	/* C:bit mask of completion spots for
+					 * link[0] and link[1] */
+	u_char		c_voff[2];	/* C:vertex offset within frame */
+};
+
+/* flag values for c_flg */
+#define C_OPEN_0	0x01		/* link[0] is an open ended frame */
+#define C_OPEN_1	0x02		/* link[1] is an open ended frame */
+#define C_LOOP		0x04		/* link[1] intersects previous frame */
+#define C_MARK		0x08		/* indicates combo processed */
+
+/*
+ * This structure is used for recording the completion points of
+ * multi frame combos.
+ */
+struct	elist {
+	struct elist	*e_next;	/* list of completion points */
+	struct combostr	*e_combo;	/* the whole combo */
+	u_char		e_off;		/* offset in frame of this empty spot */
+	u_char		e_frameindex;	/* intersection frame index */
+	u_char		e_framecnt;	/* number of frames left to attach */
+	u_char		e_emask;	/* real value of the frame's emask */
+	union comboval	e_fval;		/* frame combo value */
+};
+
+/*
+ * One spot structure for each location on the board.
+ * A frame consists of the combination for the current spot plus the five spots
+ * 0: right, 1: right & down, 2: down, 3: down & left.
+ */
+struct	spotstr {
+	short		s_occ;		/* color of occupant */
+	short		s_wval;		/* weighted value */
+	int		s_flg;		/* flags for graph walks */
+	struct combostr	*s_frame[4];	/* level 1 combo for frame[dir] */
+	union comboval	s_fval[2][4];	/* combo value for [color][frame] */
+	union comboval	s_combo[2];	/* minimum combo value for BLK & WHT */
+	u_char		s_level[2];	/* number of frames in the min combo */
+	u_char		s_nforce[2];	/* number of <1,x> combos */
+	struct elist	*s_empty;	/* level n combo completion spots */
+	struct elist	*s_nempty;	/* level n+1 combo completion spots */
+	int		dummy[2];	/* XXX */
+};
+
+/* flag values for s_flg */
+#define CFLAG		0x000001	/* frame is part of a combo */
+#define CFLAGALL	0x00000F	/* all frame directions marked */
+#define IFLAG		0x000010	/* legal intersection point */
+#define IFLAGALL	0x0000F0	/* any intersection points? */
+#define FFLAG		0x000100	/* frame is part of a <1,x> combo */
+#define FFLAGALL	0x000F00	/* all force frames */
+#define MFLAG		0x001000	/* frame has already been seen */
+#define MFLAGALL	0x00F000	/* all frames seen */
+#define BFLAG		0x010000	/* frame intersects border or dead */
+#define BFLAGALL	0x0F0000	/* all frames dead */
+
+/*
+ * This structure is used to store overlap information between frames.
+ */
+struct	ovlp_info {
+	int		o_intersect;	/* intersection spot */
+	struct combostr	*o_fcombo;	/* the connecting combo */
+	u_char		o_link;		/* which link to update (0 or 1) */
+	u_char		o_off;		/* offset in frame of intersection */
+	u_char		o_frameindex;	/* intersection frame index */
+};
+
+extern	char	*letters;
+extern	char	fmtbuf[];
+extern	char	pdir[];
+
+extern	int     dd[4];
+extern	struct	spotstr	board[BAREA];		/* info for board */
+extern	struct	combostr frames[FAREA];		/* storage for single frames */
+extern	struct	combostr *sortframes[2];	/* sorted, non-empty frames */
+extern	u_char	overlap[FAREA * FAREA];		/* frame [a][b] overlap */
+extern	short	intersect[FAREA * FAREA];	/* frame [a][b] intersection */
+extern	int	movelog[BSZ * BSZ];		/* history of moves */
+extern	int	movenum;
+extern	int	debug;
+
+extern	char    *copy();
+extern	char    *stoc();
+extern	char    *tail();
+
+#define ASSERT(x)
diff --git a/gomoku/main.c b/gomoku/main.c
new file mode 100644
index 00000000..d6a076c2
--- /dev/null
+++ b/gomoku/main.c
@@ -0,0 +1,532 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char copyright[] =
+"@(#) Copyright (c) 1994\n\
+	The Regents of the University of California.  All rights reserved.\n";
+#endif /* not lint */
+
+#ifndef lint
+static char sccsid[] = "@(#)main.c	8.4 (Berkeley) 5/4/95";
+#endif /* not lint */
+
+#include <curses.h>
+#include <err.h>
+#include <signal.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "gomoku.h"
+
+#define USER	0		/* get input from standard input */
+#define PROGRAM	1		/* get input from program */
+#define INPUTF	2		/* get input from a file */
+
+int	interactive = 1;	/* true if interactive */
+int	debug;			/* true if debugging */
+int	test;			/* both moves come from 1: input, 2: computer */
+char	*prog;			/* name of program */
+FILE	*debugfp;		/* file for debug output */
+FILE	*inputfp;		/* file for debug input */
+
+char	pdir[4]		= "-\\|/";
+char	fmtbuf[128];
+
+struct	spotstr	board[BAREA];		/* info for board */
+struct	combostr frames[FAREA];		/* storage for all frames */
+struct	combostr *sortframes[2];	/* sorted list of non-empty frames */
+u_char	overlap[FAREA * FAREA];		/* true if frame [a][b] overlap */
+short	intersect[FAREA * FAREA];	/* frame [a][b] intersection */
+int	movelog[BSZ * BSZ];		/* log of all the moves */
+int	movenum;			/* current move number */
+char	*plyr[2];			/* who's who */
+
+extern void quit();
+#ifdef DEBUG
+extern void whatsup();
+#endif
+
+main(argc, argv)
+	int argc;
+	char **argv;
+{
+	char buf[128];
+	int color, curmove, i, ch;
+	int input[2];
+	static char *fmt[2] = {
+		"%3d %-6s",
+		"%3d        %-6s"
+	};
+
+	prog = strrchr(argv[0], '/');
+	if (prog)
+		prog++;
+	else
+		prog = argv[0];
+
+	while ((ch = getopt(argc, argv, "bcdD:u")) != EOF) {
+		switch (ch) {
+		case 'b':	/* background */
+			interactive = 0;
+			break;
+		case 'd':	/* debugging */
+			debug++;
+			break;
+		case 'D':	/* log debug output to file */
+			if ((debugfp = fopen(optarg, "w")) == NULL)
+				err(1, "%s", optarg);
+			break;
+		case 'u':	/* testing: user verses user */
+			test = 1;
+			break;
+		case 'c':	/* testing: computer verses computer */
+			test = 2;
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+	if (argc) {
+		if ((inputfp = fopen(*argv, "r")) == NULL)
+			err(1, "%s", *argv);
+	}
+
+	if (!debug)
+#ifdef SVR4
+		srand(time(0));
+#else
+		srandom(time(0));
+#endif
+	if (interactive)
+		cursinit();		/* initialize curses */
+again:
+	bdinit(board);			/* initialize board contents */
+
+	if (interactive) {
+		plyr[BLACK] = plyr[WHITE] = "???";
+		bdisp_init();		/* initialize display of board */
+#ifdef DEBUG
+		signal(SIGINT, whatsup);
+#else
+		signal(SIGINT, quit);
+#endif
+
+		if (inputfp == NULL && test == 0) {
+			for (;;) {
+				ask("black or white? ");
+				getline(buf, sizeof(buf));
+				if (buf[0] == 'b' || buf[0] == 'B') {
+					color = BLACK;
+					break;
+				}
+				if (buf[0] == 'w' || buf[0] == 'W') {
+					color = WHITE;
+					break;
+				}
+				move(22, 0);
+				printw("Black moves first. Please enter `black' or `white'\n");
+			}
+			move(22, 0);
+			clrtoeol();
+		}
+	} else {
+		setbuf(stdout, 0);
+		getline(buf, sizeof(buf));
+		if (strcmp(buf, "black") == 0)
+			color = BLACK;
+		else if (strcmp(buf, "white") == 0)
+			color = WHITE;
+		else {
+			sprintf(fmtbuf,
+			    "Huh?  Expected `black' or `white', got `%s'\n",
+			    buf);
+			panic(fmtbuf);
+		}
+	}
+
+	if (inputfp) {
+		input[BLACK] = INPUTF;
+		input[WHITE] = INPUTF;
+	} else {
+		switch (test) {
+		case 0: /* user verses program */
+			input[color] = USER;
+			input[!color] = PROGRAM;
+			break;
+
+		case 1: /* user verses user */
+			input[BLACK] = USER;
+			input[WHITE] = USER;
+			break;
+
+		case 2: /* program verses program */
+			input[BLACK] = PROGRAM;
+			input[WHITE] = PROGRAM;
+			break;
+		}
+	}
+	if (interactive) {
+		plyr[BLACK] = input[BLACK] == USER ? "you" : prog;
+		plyr[WHITE] = input[WHITE] == USER ? "you" : prog;
+		bdwho(1);
+	}
+
+	for (color = BLACK; ; color = !color) {
+	top:
+		switch (input[color]) {
+		case INPUTF: /* input comes from a file */
+			curmove = readinput(inputfp);
+			if (curmove != ILLEGAL)
+				break;
+			switch (test) {
+			case 0: /* user verses program */
+				input[color] = USER;
+				input[!color] = PROGRAM;
+				break;
+
+			case 1: /* user verses user */
+				input[BLACK] = USER;
+				input[WHITE] = USER;
+				break;
+
+			case 2: /* program verses program */
+				input[BLACK] = PROGRAM;
+				input[WHITE] = PROGRAM;
+				break;
+			}
+			plyr[BLACK] = input[BLACK] == USER ? "you" : prog;
+			plyr[WHITE] = input[WHITE] == USER ? "you" : prog;
+			bdwho(1);
+			goto top;
+
+		case USER: /* input comes from standard input */
+		getinput:
+			if (interactive)
+				ask("move? ");
+			if (!getline(buf, sizeof(buf))) {
+				curmove = RESIGN;
+				break;
+			}
+			if (buf[0] == '\0')
+				goto getinput;
+			curmove = ctos(buf);
+			if (interactive) {
+				if (curmove == SAVE) {
+					FILE *fp;
+
+					ask("save file name? ");
+					(void)getline(buf, sizeof(buf));
+					if ((fp = fopen(buf, "w")) == NULL) {
+						log("cannot create save file");
+						goto getinput;
+					}
+					for (i = 0; i < movenum - 1; i++)
+						fprintf(fp, "%s\n",
+							stoc(movelog[i]));
+					fclose(fp);
+					goto getinput;
+				}
+				if (curmove != RESIGN &&
+				    board[curmove].s_occ != EMPTY) {
+					log("Illegal move");
+					goto getinput;
+				}
+			}
+			break;
+
+		case PROGRAM: /* input comes from the program */
+			curmove = pickmove(color);
+			break;
+		}
+		if (interactive) {
+			sprintf(fmtbuf, fmt[color], movenum, stoc(curmove));
+			log(fmtbuf);
+		}
+		if ((i = makemove(color, curmove)) != MOVEOK)
+			break;
+		if (interactive)
+			bdisp();
+	}
+	if (interactive) {
+		move(22, 0);
+		switch (i) {
+		case WIN:
+			if (input[color] == PROGRAM)
+				addstr("Ha ha, I won");
+			else
+				addstr("Rats! you won");
+			break;
+		case TIE:
+			addstr("Wow! its a tie");
+			break;
+		case ILLEGAL:
+			addstr("Illegal move");
+			break;
+		}
+		clrtoeol();
+		bdisp();
+		if (i != RESIGN) {
+		replay:
+			ask("replay? ");
+			if (getline(buf, sizeof(buf)) &&
+			    buf[0] == 'y' || buf[0] == 'Y')
+				goto again;
+			if (strcmp(buf, "save") == 0) {
+				FILE *fp;
+
+				ask("save file name? ");
+				(void)getline(buf, sizeof(buf));
+				if ((fp = fopen(buf, "w")) == NULL) {
+					log("cannot create save file");
+					goto replay;
+				}
+				for (i = 0; i < movenum - 1; i++)
+					fprintf(fp, "%s\n",
+						stoc(movelog[i]));
+				fclose(fp);
+				goto replay;
+			}
+		}
+	}
+	quit();
+}
+
+readinput(fp)
+	FILE *fp;
+{
+	char *cp;
+	int c;
+
+	cp = fmtbuf;
+	while ((c = getc(fp)) != EOF && c != '\n')
+		*cp++ = c;
+	*cp = '\0';
+	return (ctos(fmtbuf));
+}
+
+#ifdef DEBUG
+/*
+ * Handle strange situations.
+ */
+void
+whatsup(signum)
+	int signum;
+{
+	int i, pnum, n, s1, s2, d1, d2;
+	struct spotstr *sp;
+	FILE *fp;
+	char *str;
+	struct elist *ep;
+	struct combostr *cbp;
+
+	if (!interactive)
+		quit();
+top:
+	ask("cmd? ");
+	if (!getline(fmtbuf, sizeof(fmtbuf)))
+		quit();
+	switch (*fmtbuf) {
+	case '\0':
+		goto top;
+	case 'q':		/* conservative quit */
+		quit();
+	case 'd':		/* set debug level */
+		debug = fmtbuf[1] - '0';
+		sprintf(fmtbuf, "Debug set to %d", debug);
+		dlog(fmtbuf);
+		sleep(1);
+	case 'c':
+		break;
+	case 'b':		/* back up a move */
+		if (movenum > 1) {
+			movenum--;
+			board[movelog[movenum - 1]].s_occ = EMPTY;
+			bdisp();
+		}
+		goto top;
+	case 's':		/* suggest a move */
+		i = fmtbuf[1] == 'b' ? BLACK : WHITE;
+		sprintf(fmtbuf, "suggest %c %s", i == BLACK ? 'B' : 'W',
+			stoc(pickmove(i)));
+		dlog(fmtbuf);
+		goto top;
+	case 'f':		/* go forward a move */
+		board[movelog[movenum - 1]].s_occ = movenum & 1 ? BLACK : WHITE;
+		movenum++;
+		bdisp();
+		goto top;
+	case 'l':		/* print move history */
+		if (fmtbuf[1] == '\0') {
+			for (i = 0; i < movenum - 1; i++)
+				dlog(stoc(movelog[i]));
+			goto top;
+		}
+		if ((fp = fopen(fmtbuf + 1, "w")) == NULL)
+			goto top;
+		for (i = 0; i < movenum - 1; i++) {
+			fprintf(fp, "%s", stoc(movelog[i]));
+			if (++i < movenum - 1)
+				fprintf(fp, " %s\n", stoc(movelog[i]));
+			else
+				fputc('\n', fp);
+		}
+		bdump(fp);
+		fclose(fp);
+		goto top;
+	case 'o':
+		n = 0;
+		for (str = fmtbuf + 1; *str; str++)
+			if (*str == ',') {
+				for (d1 = 0; d1 < 4; d1++)
+					if (str[-1] == pdir[d1])
+						break;
+				str[-1] = '\0';
+				sp = &board[s1 = ctos(fmtbuf + 1)];
+				n = (sp->s_frame[d1] - frames) * FAREA;
+				*str++ = '\0';
+				break;
+			}
+		sp = &board[s2 = ctos(str)];
+		while (*str)
+			str++;
+		for (d2 = 0; d2 < 4; d2++)
+			if (str[-1] == pdir[d2])
+				break;
+		n += sp->s_frame[d2] - frames;
+		str = fmtbuf;
+		sprintf(str, "overlap %s%c,", stoc(s1), pdir[d1]);
+		str += strlen(str);
+		sprintf(str, "%s%c = %x", stoc(s2), pdir[d2], overlap[n]);
+		dlog(fmtbuf);
+		goto top;
+	case 'p':
+		sp = &board[i = ctos(fmtbuf + 1)];
+		sprintf(fmtbuf, "V %s %x/%d %d %x/%d %d %d %x", stoc(i),
+			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, sp->s_flg);
+		dlog(fmtbuf);
+		sprintf(fmtbuf, "FB %s %x %x %x %x", stoc(i),
+			sp->s_fval[BLACK][0].s, sp->s_fval[BLACK][1].s,
+			sp->s_fval[BLACK][2].s, sp->s_fval[BLACK][3].s);
+		dlog(fmtbuf);
+		sprintf(fmtbuf, "FW %s %x %x %x %x", stoc(i),
+			sp->s_fval[WHITE][0].s, sp->s_fval[WHITE][1].s,
+			sp->s_fval[WHITE][2].s, sp->s_fval[WHITE][3].s);
+		dlog(fmtbuf);
+		goto top;
+	case 'e':	/* e {b|w} [0-9] spot */
+		str = fmtbuf + 1;
+		if (*str >= '0' && *str <= '9')
+			n = *str++ - '0';
+		else
+			n = 0;
+		sp = &board[i = ctos(str)];
+		for (ep = sp->s_empty; ep; ep = ep->e_next) {
+			cbp = ep->e_combo;
+			if (n) {
+				if (cbp->c_nframes > n)
+					continue;
+				if (cbp->c_nframes != n)
+					break;
+			}
+			printcombo(cbp, fmtbuf);
+			dlog(fmtbuf);
+		}
+		goto top;
+	default:
+syntax:
+		dlog("Options are:");
+		dlog("q    - quit");
+		dlog("c    - continue");
+		dlog("d#   - set debug level to #");
+		dlog("p#   - print values at #");
+		goto top;
+	}
+}
+#endif /* DEBUG */
+
+/*
+ * Display debug info.
+ */
+dlog(str)
+	char *str;
+{
+
+	if (debugfp)
+		fprintf(debugfp, "%s\n", str);
+	if (interactive)
+		dislog(str);
+	else
+		fprintf(stderr, "%s\n", str);
+}
+
+log(str)
+	char *str;
+{
+
+	if (debugfp)
+		fprintf(debugfp, "%s\n", str);
+	if (interactive)
+		dislog(str);
+	else
+		printf("%s\n", str);
+}
+
+void
+quit()
+{
+	if (interactive) {
+		bdisp();		/* show final board */
+		cursfini();
+	}
+	exit(0);
+}
+
+/*
+ * Die gracefully.
+ */
+panic(str)
+	char *str;
+{
+	fprintf(stderr, "%s: %s\n", prog, str);
+	fputs("resign\n", stdout);
+	quit();
+}
diff --git a/gomoku/makemove.c b/gomoku/makemove.c
new file mode 100644
index 00000000..b67b3e77
--- /dev/null
+++ b/gomoku/makemove.c
@@ -0,0 +1,301 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)makemove.c	8.2 (Berkeley) 5/3/95";
+#endif /* not lint */
+
+#include "gomoku.h"
+
+		/* direction deltas */
+int     dd[4] = {
+	MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT
+};
+
+int	weight[5] = { 0, 1, 7, 22, 100 };
+
+/*
+ * Return values:
+ *	MOVEOK	everything is OK.
+ *	RESIGN	Player resigned.
+ *	ILLEGAL	Illegal move.
+ *	WIN	The the winning move was just played.
+ *	TIE	The game is a tie.
+ */
+makemove(us, mv)
+	int us, mv;
+{
+	register struct spotstr *sp, *fsp;
+	register union comboval *cp;
+	struct spotstr *osp;
+	struct combostr *cbp, *cbp1;
+	union comboval *cp1;
+	register int i, f, r, d, n;
+	int space, val, bmask;
+
+	/* check for end of game */
+	if (mv == RESIGN)
+		return(RESIGN);
+
+	/* check for illegal move */
+	sp = &board[mv];
+	if (sp->s_occ != EMPTY)
+		return(ILLEGAL);
+
+	/* make move */
+	sp->s_occ = us;
+	movelog[movenum - 1] = mv;
+	if (++movenum == BSZ * BSZ)
+		return(TIE);
+
+	/* compute new frame values */
+	sp->s_wval = 0;
+	osp = sp;
+	for (r = 4; --r >= 0; ) {			/* for each direction */
+	    d = dd[r];
+	    fsp = osp;
+	    bmask = BFLAG << r;
+	    for (f = 5; --f >= 0; fsp -= d) {		/* for each frame */
+		if (fsp->s_occ == BORDER)
+		    goto nextr;
+		if (fsp->s_flg & bmask)
+		    continue;
+
+		/* remove this frame from the sorted list of frames */
+		cbp = fsp->s_frame[r];
+		if (cbp->c_next) {
+			if (sortframes[BLACK] == cbp)
+			    sortframes[BLACK] = cbp->c_next;
+			if (sortframes[WHITE] == cbp)
+			    sortframes[WHITE] = cbp->c_next;
+			cbp->c_next->c_prev = cbp->c_prev;
+			cbp->c_prev->c_next = cbp->c_next;
+		}
+
+		/* compute old weight value for this frame */
+		cp = &fsp->s_fval[BLACK][r];
+		if (cp->s <= 0x500)
+		    val = weight[5 - cp->c.a - cp->c.b];
+		else
+		    val = 0;
+		cp = &fsp->s_fval[WHITE][r];
+		if (cp->s <= 0x500)
+		    val += weight[5 - cp->c.a - cp->c.b];
+
+		/* compute new combo value for this frame */
+		sp = fsp;
+		space = sp->s_occ == EMPTY;
+		n = 0;
+		for (i = 5; --i >= 0; sp += d) {	/* for each spot */
+		    if (sp->s_occ == us)
+			n++;
+		    else if (sp->s_occ == EMPTY)
+			sp->s_wval -= val;
+		    else {
+			/* this frame is now blocked, adjust values */
+			fsp->s_flg |= bmask;
+			fsp->s_fval[BLACK][r].s = MAXCOMBO;
+			fsp->s_fval[WHITE][r].s = MAXCOMBO;
+			while (--i >= 0) {
+			    sp += d;
+			    if (sp->s_occ == EMPTY)
+				sp->s_wval -= val;
+			}
+			goto nextf;
+		    }
+		}
+
+		/* check for game over */
+		if (n == 5)
+		    return(WIN);
+
+		/* compute new value & combo number for this frame & color */
+		fsp->s_fval[!us][r].s = MAXCOMBO;
+		cp = &fsp->s_fval[us][r];
+		/* both ends open? */
+		if (space && sp->s_occ == EMPTY) {
+		    cp->c.a = 4 - n;
+		    cp->c.b = 1;
+		} else {
+		    cp->c.a = 5 - n;
+		    cp->c.b = 0;
+		}
+		val = weight[n];
+		sp = fsp;
+		for (i = 5; --i >= 0; sp += d)		/* for each spot */
+		    if (sp->s_occ == EMPTY)
+			sp->s_wval += val;
+
+		/* add this frame to the sorted list of frames by combo value */
+		cbp1 = sortframes[us];
+		if (!cbp1)
+		    sortframes[us] = cbp->c_next = cbp->c_prev = cbp;
+		else {
+		    cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
+		    if (cp->s <= cp1->s) {
+			/* insert at the head of the list */
+			sortframes[us] = cbp;
+		    } else {
+			do {
+			    cbp1 = cbp1->c_next;
+			    cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir];
+			    if (cp->s <= cp1->s)
+				break;
+			} while (cbp1 != sortframes[us]);
+		    }
+		    cbp->c_next = cbp1;
+		    cbp->c_prev = cbp1->c_prev;
+		    cbp1->c_prev->c_next = cbp;
+		    cbp1->c_prev = cbp;
+		}
+
+	    nextf:
+		;
+	    }
+
+	    /* both ends open? */
+	    if (fsp->s_occ == EMPTY) {
+		cp = &fsp->s_fval[BLACK][r];
+		if (cp->c.b) {
+		    cp->c.a += 1;
+		    cp->c.b = 0;
+		}
+		cp = &fsp->s_fval[WHITE][r];
+		if (cp->c.b) {
+		    cp->c.a += 1;
+		    cp->c.b = 0;
+		}
+	    }
+
+	nextr:
+	    ;
+	}
+
+	update_overlap(osp);
+
+	return(MOVEOK);
+}
+
+/*
+ * fix up the overlap array due to updating spot osp.
+ */
+update_overlap(osp)
+	struct spotstr *osp;
+{
+	register struct spotstr *sp, *sp1, *sp2;
+	register int i, f, r, r1, d, d1, n;
+	int a, b, bmask, bmask1;
+	struct spotstr *esp;
+	char *str;
+
+	for (r = 4; --r >= 0; ) {			/* for each direction */
+	    d = dd[r];
+	    sp1 = osp;
+	    bmask = BFLAG << r;
+	    for (f = 0; f < 6; f++, sp1 -= d) {		/* for each frame */
+		if (sp1->s_occ == BORDER)
+		    break;
+		if (sp1->s_flg & bmask)
+		    continue;
+		/*
+		 * Update all other frames that intersect the current one
+		 * to indicate whether they still overlap or not.
+		 * Since F1 overlap F2 == F2 overlap F1, we only need to
+		 * do the rows 0 <= r1 <= r. The r1 == r case is special
+		 * since the two frames can overlap at more than one point.
+		 */
+		str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA];
+		sp2 = sp1 - d;
+		for (i = f + 1; i < 6; i++, sp2 -= d) {
+		    if (sp2->s_occ == BORDER)
+			break;
+		    if (sp2->s_flg & bmask)
+			continue;
+		    /*
+		     * count the number of empty spots to see if there is
+		     * still an overlap.
+		     */
+		    n = 0;
+		    sp = sp1;
+		    for (b = i - f; b < 5; b++, sp += d) {
+			if (sp->s_occ == EMPTY) {
+			    esp = sp;	/* save the intersection point */
+			    n++;
+			}
+		    }
+		    b = sp2->s_frame[r] - frames;
+		    if (n == 0) {
+			if (sp->s_occ == EMPTY) {
+			    str[b] &= 0xA;
+			    overlap[b * FAREA + a] &= 0xC;
+			    intersect[a * FAREA + b] = n = sp - board;
+			    intersect[b * FAREA + a] = n;
+			} else {
+			    str[b] = 0;
+			    overlap[b * FAREA + a] = 0;
+			}
+		    } else if (n == 1) {
+			if (sp->s_occ == EMPTY) {
+			    str[b] &= 0xAF;
+			    overlap[b * FAREA + a] &= 0xCF;
+			} else {
+			    str[b] &= 0xF;
+			    overlap[b * FAREA + a] &= 0xF;
+			}
+			intersect[a * FAREA + b] = n = esp - board;
+			intersect[b * FAREA + a] = n;
+		    }
+		    /* else no change, still multiple overlap */
+		}
+
+		/* the other directions can only intersect at spot osp */
+		for (r1 = r; --r1 >= 0; ) {
+		    d1 = dd[r1];
+		    bmask1 = BFLAG << r1;
+		    sp = osp;
+		    for (i = 6; --i >= 0; sp -= d1) {	/* for each spot */
+			if (sp->s_occ == BORDER)
+			    break;
+			if (sp->s_flg & bmask1)
+			    continue;
+			b = sp->s_frame[r1] - frames;
+			str[b] = 0;
+			overlap[b * FAREA + a] = 0;
+		    }
+		}
+	    }
+	}
+}
diff --git a/gomoku/pickmove.c b/gomoku/pickmove.c
new file mode 100644
index 00000000..197d3c5c
--- /dev/null
+++ b/gomoku/pickmove.c
@@ -0,0 +1,1479 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)pickmove.c	8.2 (Berkeley) 5/3/95";
+#endif /* not lint */
+
+#include <stdio.h>
+#include <curses.h>
+#include <machine/limits.h>
+
+#include "gomoku.h"
+
+#define BITS_PER_INT	(sizeof(int) * CHAR_BIT)
+#define MAPSZ		(BAREA / BITS_PER_INT)
+
+#define BIT_SET(a, b)	((a)[(b)/BITS_PER_INT] |= (1 << ((b) % BITS_PER_INT)))
+#define BIT_CLR(a, b)	((a)[(b)/BITS_PER_INT] &= ~(1 << ((b) % BITS_PER_INT)))
+#define BIT_TEST(a, b)	((a)[(b)/BITS_PER_INT] & (1 << ((b) % BITS_PER_INT)))
+
+struct	combostr *hashcombos[FAREA];	/* hash list for finding duplicates */
+struct	combostr *sortcombos;		/* combos at higher levels */
+int	combolen;			/* number of combos in sortcombos */
+int	nextcolor;			/* color of next move */
+int	elistcnt;			/* count of struct elist allocated */
+int	combocnt;			/* count of struct combostr allocated */
+int	forcemap[MAPSZ];		/* map for blocking <1,x> combos */
+int	tmpmap[MAPSZ];			/* map for blocking <1,x> combos */
+int	nforce;				/* count of opponent <1,x> combos */
+
+pickmove(us)
+	int us;
+{
+	register struct spotstr *sp, *sp1, *sp2;
+	register union comboval *Ocp, *Tcp;
+	char *str;
+	int i, j, m;
+
+	/* 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 + 1;
+		sp->s_combo[WHITE].s = MAXCOMBO + 1;
+		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);
+	}
+	nforce = 0;
+	memset(forcemap, 0, sizeof(forcemap));
+
+	/* 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].c.a == 1 ||
+		    sp->s_combo[WHITE].c.a == 1)) {
+			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);
+		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);
+		dlog(fmtbuf);
+		/*
+		 * Check for more than one force that can't
+		 * all be blocked with one move.
+		 */
+		sp = (us == BLACK) ? sp2 : sp1;
+		m = sp - board;
+		if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m))
+			dlog("*** Can't be blocked");
+	}
+	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, s, s1;
+
+	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;
+	s = sp - board;
+	s1 = sp1 - board;
+	if (BIT_TEST(forcemap, s) && !BIT_TEST(forcemap, s1))
+		return (1);
+	if (!BIT_TEST(forcemap, s) && BIT_TEST(forcemap, s1))
+		return (0);
+	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 non-empty frames and
+ * update the minimum combo values for each empty spot.
+ * Also, try to combine frames to find more complex (chained) moves.
+ */
+scanframes(color)
+	int color;
+{
+	register struct combostr *cbp, *ecbp;
+	register struct spotstr *sp;
+	register union comboval *cp;
+	register struct elist *ep, *nep;
+	register int i, r, d, n;
+	union comboval 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
+	 * and try making all combinations of two frames intersecting at
+	 * an empty spot.
+	 */
+	n = combolen;
+	ecbp = cbp;
+	do {
+		sp = &board[cbp->c_vertex];
+		cp = &sp->s_fval[color][r = cbp->c_dir];
+		d = dd[r];
+		if (cp->c.b) {
+			/*
+			 * Since this is the first spot of an open ended
+			 * frame, we treat it as a closed frame.
+			 */
+			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;
+			}
+			/*
+			 * Try combining other frames that intersect
+			 * at this spot.
+			 */
+			makecombo2(cbp, sp, 0, cb.s);
+			if (cp->s != 0x101)
+				cb.s = cp->s;
+			else if (color != nextcolor)
+				memset(tmpmap, 0, sizeof(tmpmap));
+			sp += d;
+			i = 1;
+		} else {
+			cb.s = cp->s;
+			i = 0;
+		}
+		for (; i < 5; i++, 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]++;
+				if (color != nextcolor) {
+					n = sp - board;
+					BIT_SET(tmpmap, n);
+				}
+			}
+			/*
+			 * Try combining other frames that intersect
+			 * at this spot.
+			 */
+			makecombo2(cbp, sp, i, cb.s);
+		}
+		if (cp->s == 0x101 && color != nextcolor) {
+			if (nforce == 0)
+				memcpy(forcemap, tmpmap, sizeof(tmpmap));
+			else {
+				for (i = 0; i < MAPSZ; i++)
+					forcemap[i] &= tmpmap[i];
+			}
+		}
+		/* 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.
+	 * Limit the search depth early in the game.
+	 */
+	d = 2;
+	while (d <= ((movenum + 1) >> 1) && combolen > n) {
+		if (debug) {
+			sprintf(fmtbuf, "%cL%d %d %d %d", "BW"[color],
+				d, combolen - n, combocnt, elistcnt);
+			dlog(fmtbuf);
+			refresh();
+		}
+		n = combolen;
+		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; ep; ep = nep) {
+			cbp = ep->e_combo;
+			if (cbp->c_combo.s <= sp->s_combo[color].s) {
+				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_nframes < sp->s_level[color])
+					sp->s_level[color] = cbp->c_nframes;
+			}
+			nep = ep->e_next;
+			free(ep);
+			elistcnt--;
+		}
+		sp->s_empty = (struct elist *)0;
+		for (ep = sp->s_nempty; ep; ep = nep) {
+			cbp = ep->e_combo;
+			if (cbp->c_combo.s <= sp->s_combo[color].s) {
+				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_nframes < sp->s_level[color])
+					sp->s_level[color] = cbp->c_nframes;
+			}
+			nep = ep->e_next;
+			free(ep);
+			elistcnt--;
+		}
+		sp->s_nempty = (struct elist *)0;
+	}
+
+	/* remove old combos */
+	if ((cbp = sortcombos) != (struct combostr *)0) {
+		struct combostr *ncbp;
+
+		/* scan the list */
+		ecbp = cbp;
+		do {
+			ncbp = cbp->c_next;
+			free(cbp);
+			combocnt--;
+		} while ((cbp = ncbp) != ecbp);
+		sortcombos = (struct combostr *)0;
+	}
+	combolen = 0;
+
+#ifdef DEBUG
+	if (combocnt) {
+		sprintf(fmtbuf, "scanframes: %c combocnt %d", "BW"[color],
+			combocnt);
+		dlog(fmtbuf);
+		whatsup(0);
+	}
+	if (elistcnt) {
+		sprintf(fmtbuf, "scanframes: %c elistcnt %d", "BW"[color],
+			elistcnt);
+		dlog(fmtbuf);
+		whatsup(0);
+	}
+#endif
+}
+
+/*
+ * Compute all level 2 combos of frames intersecting spot 'osp'
+ * within the frame 'ocbp' and combo value 's'.
+ */
+makecombo2(ocbp, osp, off, s)
+	struct combostr *ocbp;
+	struct spotstr *osp;
+	int off;
+	int s;
+{
+	register struct spotstr *sp, *fsp;
+	register struct combostr *ncbp;
+	register int f, r, d, c;
+	int baseB, fcnt, emask, bmask, n;
+	union comboval ocb, fcb;
+	struct combostr **scbpp, *fcbp;
+
+	/* try to combine a new frame with those found so far */
+	ocb.s = s;
+	baseB = ocb.c.a + ocb.c.b - 1;
+	fcnt = ocb.c.a - 2;
+	emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
+	for (r = 4; --r >= 0; ) {			/* for each direction */
+	    /* don't include frames that overlap in the same direction */
+	    if (r == ocbp->c_dir)
+		continue;
+	    d = dd[r];
+	    /*
+	     * Frame A combined with B is the same value as B combined with A
+	     * so skip frames that have already been processed (MFLAG).
+	     * Also skip blocked frames (BFLAG) and frames that are <1,x>
+	     * since combining another frame with it isn't valid.
+	     */
+	    bmask = (BFLAG | FFLAG | MFLAG) << r;
+	    fsp = osp;
+	    for (f = 0; f < 5; f++, fsp -= d) {		/* for each frame */
+		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 == 0 && 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 > 4)
+		    continue;
+		n = fcb.c.a + fcb.c.b - 1;
+		if (baseB < n)
+		    n = baseB;
+
+		/* make a new combo! */
+		ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
+		    2 * sizeof(struct combostr *));
+		scbpp = (struct combostr **)(ncbp + 1);
+		fcbp = fsp->s_frame[r];
+		if (ocbp < fcbp) {
+		    scbpp[0] = ocbp;
+		    scbpp[1] = fcbp;
+		} else {
+		    scbpp[0] = fcbp;
+		    scbpp[1] = ocbp;
+		}
+		ncbp->c_combo.c.a = c;
+		ncbp->c_combo.c.b = n;
+		ncbp->c_link[0] = ocbp;
+		ncbp->c_link[1] = fcbp;
+		ncbp->c_linkv[0].s = ocb.s;
+		ncbp->c_linkv[1].s = fcb.s;
+		ncbp->c_voff[0] = off;
+		ncbp->c_voff[1] = f;
+		ncbp->c_vertex = osp - board;
+		ncbp->c_nframes = 2;
+		ncbp->c_dir = 0;
+		ncbp->c_frameindex = 0;
+		ncbp->c_flg = (ocb.c.b) ? C_OPEN_0 : 0;
+		if (fcb.c.b)
+		    ncbp->c_flg |= C_OPEN_1;
+		ncbp->c_framecnt[0] = fcnt;
+		ncbp->c_emask[0] = emask;
+		ncbp->c_framecnt[1] = fcb.c.a - 2;
+		ncbp->c_emask[1] = ncbp->c_framecnt[1] ?
+		    ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0;
+		combocnt++;
+
+		if (c == 1 && debug > 1 || debug > 3) {
+		    sprintf(fmtbuf, "%c c %d %d m %x %x o %d %d",
+			"bw"[curcolor],
+			ncbp->c_framecnt[0], ncbp->c_framecnt[1],
+			ncbp->c_emask[0], ncbp->c_emask[1],
+			ncbp->c_voff[0], ncbp->c_voff[1]);
+		    dlog(fmtbuf);
+		    printcombo(ncbp, fmtbuf);
+		    dlog(fmtbuf);
+		}
+		if (c > 1) {
+		    /* record the empty spots that will complete this combo */
+		    makeempty(ncbp);
+
+		    /* add the new combo to the end of the list */
+		    appendcombo(ncbp, curcolor);
+		} else {
+		    updatecombo(ncbp, curcolor);
+		    free(ncbp);
+		    combocnt--;
+		}
+#ifdef DEBUG
+		if (c == 1 && debug > 1 || debug > 5) {
+		    markcombo(ncbp);
+		    bdisp();
+		    whatsup(0);
+		    clearcombo(ncbp, 0);
+		}
+#endif /* DEBUG */
+	    }
+	}
+}
+
+/*
+ * Scan the sorted list of frames and try to add a frame to
+ * combinations of 'level' number of frames.
+ */
+addframes(level)
+	int level;
+{
+	register struct combostr *cbp, *ecbp;
+	register struct spotstr *sp, *fsp;
+	register struct elist *ep, *nep;
+	register int i, r, d;
+	struct combostr **cbpp, *pcbp;
+	union comboval fcb, cb;
+
+	curlevel = level;
+
+	/* scan for combos at empty spots */
+	i = curcolor;
+	for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
+		for (ep = sp->s_empty; ep; ep = nep) {
+			cbp = ep->e_combo;
+			if (cbp->c_combo.s <= sp->s_combo[i].s) {
+				if (cbp->c_combo.s != sp->s_combo[i].s) {
+					sp->s_combo[i].s = cbp->c_combo.s;
+					sp->s_level[i] = cbp->c_nframes;
+				} else if (cbp->c_nframes < sp->s_level[i])
+					sp->s_level[i] = cbp->c_nframes;
+			}
+			nep = ep->e_next;
+			free(ep);
+			elistcnt--;
+		}
+		sp->s_empty = sp->s_nempty;
+		sp->s_nempty = (struct elist *)0;
+	}
+
+	/* try to add frames to the uncompleted combos at level curlevel */
+	cbp = ecbp = sortframes[curcolor];
+	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 closed 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, 0, 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 = 1; i < 5; i++, sp += d) {
+			if (sp->s_occ != EMPTY)
+				continue;
+			makecombo(cbp, sp, i, fcb.s);
+		}
+	} while ((cbp = cbp->c_next) != ecbp);
+
+	/* put all the combos in the hash list on the sorted list */
+	cbpp = &hashcombos[FAREA];
+	do {
+		cbp = *--cbpp;
+		if (cbp == (struct combostr *)0)
+			continue;
+		*cbpp = (struct combostr *)0;
+		ecbp = sortcombos;
+		if (ecbp == (struct combostr *)0)
+			sortcombos = cbp;
+		else {
+			/* append to sort list */
+			pcbp = ecbp->c_prev;
+			pcbp->c_next = cbp;
+			ecbp->c_prev = cbp->c_prev;
+			cbp->c_prev->c_next = ecbp;
+			cbp->c_prev = pcbp;
+		}
+	} while (cbpp != hashcombos);
+}
+
+/*
+ * Compute all level N combos of frames intersecting spot 'osp'
+ * within the frame 'ocbp' and combo value 's'.
+ */
+makecombo(ocbp, osp, off, s)
+	struct combostr *ocbp;
+	struct spotstr *osp;
+	int off;
+	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 **scbpp;
+	int baseB, fcnt, emask, verts, d;
+	union comboval ocb, cb;
+	struct ovlp_info vertices[1];
+
+	ocb.s = s;
+	baseB = ocb.c.a + ocb.c.b - 1;
+	fcnt = ocb.c.a - 2;
+	emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
+	for (ep = osp->s_empty; ep; ep = ep->e_next) {
+	    /* check for various kinds of overlap */
+	    cbp = ep->e_combo;
+	    verts = checkframes(cbp, ocbp, osp, s, vertices);
+	    if (verts < 0)
+		continue;
+
+	    /* check to see if this frame forms a valid loop */
+	    if (verts) {
+		sp = &board[vertices[0].o_intersect];
+#ifdef DEBUG
+		if (sp->s_occ != EMPTY) {
+		    sprintf(fmtbuf, "loop: %c %s", "BW"[curcolor],
+			stoc(sp - board));
+		    dlog(fmtbuf);
+		    whatsup(0);
+		}
+#endif
+		/*
+		 * It is a valid loop if the intersection spot
+		 * of the frame we are trying to attach is one
+		 * of the completion spots of the combostr
+		 * we are trying to attach the frame to.
+		 */
+		for (nep = sp->s_empty; nep; nep = nep->e_next) {
+		    if (nep->e_combo == cbp)
+			goto fnd;
+		    if (nep->e_combo->c_nframes < cbp->c_nframes)
+			break;
+		}
+		/* frame overlaps but not at a valid spot */
+		continue;
+	    fnd:
+		;
+	    }
+
+	    /* compute the first half of the combo value */
+	    c = cbp->c_combo.c.a + ocb.c.a - verts - 3;
+	    if (c > 4)
+		continue;
+
+	    /* compute the second half of the combo value */
+	    n = ep->e_fval.c.a + ep->e_fval.c.b - 1;
+	    if (baseB < n)
+		n = baseB;
+
+	    /* make a new combo! */
+	    ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
+		(cbp->c_nframes + 1) * sizeof(struct combostr *));
+	    scbpp = (struct combostr **)(ncbp + 1);
+	    if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) {
+		free(ncbp);
+		continue;
+	    }
+	    combocnt++;
+
+	    ncbp->c_combo.c.a = c;
+	    ncbp->c_combo.c.b = n;
+	    ncbp->c_link[0] = cbp;
+	    ncbp->c_link[1] = ocbp;
+	    ncbp->c_linkv[1].s = ocb.s;
+	    ncbp->c_voff[1] = off;
+	    ncbp->c_vertex = osp - board;
+	    ncbp->c_nframes = cbp->c_nframes + 1;
+	    ncbp->c_flg = ocb.c.b ? C_OPEN_1 : 0;
+	    ncbp->c_frameindex = ep->e_frameindex;
+	    /*
+	     * Update the completion spot mask of the frame we
+	     * are attaching 'ocbp' to so the intersection isn't
+	     * listed twice.
+	     */
+	    ncbp->c_framecnt[0] = ep->e_framecnt;
+	    ncbp->c_emask[0] = ep->e_emask;
+	    if (verts) {
+		ncbp->c_flg |= C_LOOP;
+		ncbp->c_dir = vertices[0].o_frameindex;
+		ncbp->c_framecnt[1] = fcnt - 1;
+		if (ncbp->c_framecnt[1]) {
+		    n = (vertices[0].o_intersect - ocbp->c_vertex) /
+			dd[ocbp->c_dir];
+		    ncbp->c_emask[1] = emask & ~(1 << n);
+		} else
+		    ncbp->c_emask[1] = 0;
+		ncbp->c_voff[0] = vertices[0].o_off;
+	    } else {
+		ncbp->c_dir = 0;
+		ncbp->c_framecnt[1] = fcnt;
+		ncbp->c_emask[1] = emask;
+		ncbp->c_voff[0] = ep->e_off;
+	    }
+
+	    if (c == 1 && debug > 1 || debug > 3) {
+		sprintf(fmtbuf, "%c v%d i%d d%d c %d %d m %x %x o %d %d",
+		    "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir,
+		    ncbp->c_framecnt[0], ncbp->c_framecnt[1],
+		    ncbp->c_emask[0], ncbp->c_emask[1],
+		    ncbp->c_voff[0], ncbp->c_voff[1]);
+		dlog(fmtbuf);
+		printcombo(ncbp, fmtbuf);
+		dlog(fmtbuf);
+	    }
+	    if (c > 1) {
+		/* record the empty spots that will complete this combo */
+		makeempty(ncbp);
+		combolen++;
+	    } else {
+		/* update board values */
+		updatecombo(ncbp, curcolor);
+	    }
+#ifdef DEBUG
+	    if (c == 1 && debug > 1 || debug > 4) {
+		markcombo(ncbp);
+		bdisp();
+		whatsup(0);
+		clearcombo(ncbp, 0);
+	    }
+#endif /* DEBUG */
+	}
+}
+
+#define MAXDEPTH	100
+struct elist	einfo[MAXDEPTH];
+struct combostr	*ecombo[MAXDEPTH];	/* separate from elist to save space */
+
+/*
+ * Add the combostr 'ocbp' to the empty spots list for each empty spot
+ * in 'ocbp' that will complete the combo.
+ */
+makeempty(ocbp)
+	struct combostr *ocbp;
+{
+	struct combostr *cbp, *tcbp, **cbpp;
+	struct elist *ep, *nep, **epp;
+	struct spotstr *sp;
+	int s, d, m, emask, i;
+	int nframes;
+
+	if (debug > 2) {
+		sprintf(fmtbuf, "E%c ", "bw"[curcolor]);
+		printcombo(ocbp, fmtbuf + 3);
+		dlog(fmtbuf);
+	}
+
+	/* should never happen but check anyway */
+	if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
+		return;
+
+	/*
+	 * The lower level combo can be pointed to by more than one
+	 * higher level 'struct combostr' so we can't modify the
+	 * lower level. Therefore, higher level combos store the
+	 * real mask of the lower level frame in c_emask[0] and the
+	 * frame number in c_frameindex.
+	 *
+	 * First we traverse the tree from top to bottom and save the
+	 * connection info. Then we traverse the tree from bottom to
+	 * top overwriting lower levels with the newer emask information.
+	 */
+	ep = &einfo[nframes];
+	cbpp = &ecombo[nframes];
+	for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+		ep--;
+		ep->e_combo = cbp;
+		*--cbpp = cbp->c_link[1];
+		ep->e_off = cbp->c_voff[1];
+		ep->e_frameindex = cbp->c_frameindex;
+		ep->e_fval.s = cbp->c_linkv[1].s;
+		ep->e_framecnt = cbp->c_framecnt[1];
+		ep->e_emask = cbp->c_emask[1];
+	}
+	cbp = ep->e_combo;
+	ep--;
+	ep->e_combo = cbp;
+	*--cbpp = cbp->c_link[0];
+	ep->e_off = cbp->c_voff[0];
+	ep->e_frameindex = 0;
+	ep->e_fval.s = cbp->c_linkv[0].s;
+	ep->e_framecnt = cbp->c_framecnt[0];
+	ep->e_emask = cbp->c_emask[0];
+
+	/* now update the emask info */
+	s = 0;
+	for (i = 2, ep += 2; i < nframes; i++, ep++) {
+		cbp = ep->e_combo;
+		nep = &einfo[ep->e_frameindex];
+		nep->e_framecnt = cbp->c_framecnt[0];
+		nep->e_emask = cbp->c_emask[0];
+
+		if (cbp->c_flg & C_LOOP) {
+			s++;
+			/*
+			 * Account for the fact that this frame connects
+			 * to a previous one (thus forming a loop).
+			 */
+			nep = &einfo[cbp->c_dir];
+			if (--nep->e_framecnt)
+				nep->e_emask &= ~(1 << cbp->c_voff[0]);
+			else
+				nep->e_emask = 0;
+		}
+	}
+
+	/*
+	 * We only need to update the emask values of "complete" loops
+	 * to include the intersection spots.
+	 */
+	if (s && ocbp->c_combo.c.a == 2) {
+		/* process loops from the top down */
+		ep = &einfo[nframes];
+		do {
+			ep--;
+			cbp = ep->e_combo;
+			if (!(cbp->c_flg & C_LOOP))
+				continue;
+
+			/*
+			 * Update the emask values to include the
+			 * intersection spots.
+			 */
+			nep = &einfo[cbp->c_dir];
+			nep->e_framecnt = 1;
+			nep->e_emask = 1 << cbp->c_voff[0];
+			ep->e_framecnt = 1;
+			ep->e_emask = 1 << ep->e_off;
+			ep = &einfo[ep->e_frameindex];
+			do {
+				ep->e_framecnt = 1;
+				ep->e_emask = 1 << ep->e_off;
+				ep = &einfo[ep->e_frameindex];
+			} while (ep > nep);
+		} while (ep != einfo);
+	}
+
+	/* check all the frames for completion spots */
+	for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
+		/* skip this frame if there are no incomplete spots in it */
+		if ((emask = ep->e_emask) == 0)
+			continue;
+		cbp = *cbpp;
+		sp = &board[cbp->c_vertex];
+		d = dd[cbp->c_dir];
+		for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) {
+			if (sp->s_occ != EMPTY || !(emask & m))
+				continue;
+
+			/* add the combo to the list of empty spots */
+			nep = (struct elist *)malloc(sizeof(struct elist));
+			nep->e_combo = ocbp;
+			nep->e_off = s;
+			nep->e_frameindex = i;
+			if (ep->e_framecnt > 1) {
+				nep->e_framecnt = ep->e_framecnt - 1;
+				nep->e_emask = emask & ~m;
+			} else {
+				nep->e_framecnt = 0;
+				nep->e_emask = 0;
+			}
+			nep->e_fval.s = ep->e_fval.s;
+			if (debug > 2) {
+				sprintf(fmtbuf, "e %s o%d i%d c%d m%x %x",
+					stoc(sp - board),
+					nep->e_off,
+					nep->e_frameindex,
+					nep->e_framecnt,
+					nep->e_emask,
+					nep->e_fval.s);
+				dlog(fmtbuf);
+			}
+
+			/* sort by the number of frames in the combo */
+			nep->e_next = sp->s_nempty;
+			sp->s_nempty = nep;
+			elistcnt++;
+		}
+	}
+}
+
+/*
+ * 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, flg, s;
+	union comboval cb;
+
+	/* save the top level value for the whole combo */
+	cb.c.a = cbp->c_combo.c.a;
+	nframes = cbp->c_nframes;
+
+	if (color != nextcolor)
+		memset(tmpmap, 0, sizeof(tmpmap));
+
+	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+		flg = cbp->c_flg;
+		cb.c.b = cbp->c_combo.c.b;
+		if (color == nextcolor) {
+			/* update the board value for the vertex */
+			sp = &board[cbp->c_vertex];
+			sp->s_nforce[color]++;
+			if (cb.s <= sp->s_combo[color].s) {
+				if (cb.s != sp->s_combo[color].s) {
+					sp->s_combo[color].s = cb.s;
+					sp->s_level[color] = nframes;
+				} else if (nframes < sp->s_level[color])
+					sp->s_level[color] = nframes;
+			}
+		} else {
+			/* update the board values for each spot in frame */
+			sp = &board[s = tcbp->c_vertex];
+			d = dd[tcbp->c_dir];
+			i = (flg & C_OPEN_1) ? 6 : 5;
+			for (; --i >= 0; sp += d, s += d) {
+				if (sp->s_occ != EMPTY)
+					continue;
+				sp->s_nforce[color]++;
+				if (cb.s <= sp->s_combo[color].s) {
+					if (cb.s != sp->s_combo[color].s) {
+						sp->s_combo[color].s = cb.s;
+						sp->s_level[color] = nframes;
+					} else if (nframes < sp->s_level[color])
+						sp->s_level[color] = nframes;
+				}
+				BIT_SET(tmpmap, s);
+			}
+		}
+
+		/* 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[s = cbp->c_vertex];
+		d = dd[cbp->c_dir];
+		i = (flg & C_OPEN_0) ? 6 : 5;
+		for (; --i >= 0; sp += d, s += d) {
+			if (sp->s_occ != EMPTY)
+				continue;
+			sp->s_nforce[color]++;
+			if (cb.s <= sp->s_combo[color].s) {
+				if (cb.s != sp->s_combo[color].s) {
+					sp->s_combo[color].s = cb.s;
+					sp->s_level[color] = nframes;
+				} else if (nframes < sp->s_level[color])
+					sp->s_level[color] = nframes;
+			}
+			BIT_SET(tmpmap, s);
+		}
+		if (nforce == 0)
+			memcpy(forcemap, tmpmap, sizeof(tmpmap));
+		else {
+			for (i = 0; i < MAPSZ; i++)
+				forcemap[i] &= tmpmap[i];
+		}
+		nforce++;
+	}
+
+	/* mark the frame as being part of a <1,x> combo */
+	board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir;
+}
+
+/*
+ * Add combo to the end of the list.
+ */
+appendcombo(cbp, color)
+	struct combostr *cbp;
+	int color;
+{
+	struct combostr *pcbp, *ncbp;
+
+	combolen++;
+	ncbp = sortcombos;
+	if (ncbp == (struct combostr *)0) {
+		sortcombos = 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 zero if it is valid to combine frame 'fcbp' with the frames
+ * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops).
+ * Return positive if combining frame 'fcbp' to the frames in 'cbp'
+ * would form some kind of valid loop. Also return the intersection spots
+ * in 'vertices[]' beside the known intersection at spot 'osp'.
+ * Return -1 if 'fcbp' should not be combined with 'cbp'.
+ * 's' is the combo value for frame 'fcpb'.
+ */
+checkframes(cbp, fcbp, osp, s, vertices)
+	struct combostr *cbp;
+	struct combostr *fcbp;
+	struct spotstr *osp;
+	int s;
+	struct ovlp_info *vertices;
+{
+	struct combostr *tcbp, *lcbp;
+	int i, n, mask, flg, verts, loop, index, fcnt;
+	union comboval cb;
+	u_char *str;
+	short *ip;
+
+	cb.s = s;
+	fcnt = cb.c.a - 2;
+	verts = 0;
+	loop = 0;
+	index = cbp->c_nframes;
+	n = (fcbp - frames) * FAREA;
+	str = &overlap[n];
+	ip = &intersect[n];
+	/*
+	 * i == which overlap bit to test based on whether 'fcbp' is
+	 * an open or closed frame.
+	 */
+	i = cb.c.b ? 2 : 0;
+	for (; tcbp = cbp->c_link[1]; lcbp = cbp, cbp = cbp->c_link[0]) {
+		if (tcbp == fcbp)
+			return (-1);	/* fcbp is already included */
+
+		/* check for intersection of 'tcbp' with 'fcbp' */
+		index--;
+		mask = str[tcbp - frames];
+		flg = cbp->c_flg;
+		n = i + ((flg & C_OPEN_1) != 0);
+		if (mask & (1 << n)) {
+			/*
+			 * The two frames are not independent if they
+			 * both lie in the same line and intersect at
+			 * more than one point.
+			 */
+			if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
+				return (-1);
+			/*
+			 * If this is not the spot we are attaching
+			 * 'fcbp' to and it is a reasonable intersection
+			 * spot, then there might be a loop.
+			 */
+			n = ip[tcbp - frames];
+			if (osp != &board[n]) {
+				/* check to see if this is a valid loop */
+				if (verts)
+					return (-1);
+				if (fcnt == 0 || cbp->c_framecnt[1] == 0)
+					return (-1);
+				/*
+				 * Check to be sure the intersection is not
+				 * one of the end points if it is an open
+				 * ended frame.
+				 */
+				if ((flg & C_OPEN_1) &&
+				    (n == tcbp->c_vertex ||
+				     n == tcbp->c_vertex + 5 * dd[tcbp->c_dir]))
+					return (-1);	/* invalid overlap */
+				if (cb.c.b &&
+				    (n == fcbp->c_vertex ||
+				     n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
+					return (-1);	/* invalid overlap */
+
+				vertices->o_intersect = n;
+				vertices->o_fcombo = cbp;
+				vertices->o_link = 1;
+				vertices->o_off = (n - tcbp->c_vertex) /
+					dd[tcbp->c_dir];
+				vertices->o_frameindex = index;
+				verts++;
+			}
+		}
+		n = i + ((flg & C_OPEN_0) != 0);
+	}
+	if (cbp == fcbp)
+		return (-1);	/* fcbp is already included */
+
+	/* check for intersection of 'cbp' with 'fcbp' */
+	mask = str[cbp - frames];
+	if (mask & (1 << n)) {
+		/*
+		 * The two frames are not independent if they
+		 * both lie in the same line and intersect at
+		 * more than one point.
+		 */
+		if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
+			return (-1);
+		/*
+		 * If this is not the spot we are attaching
+		 * 'fcbp' to and it is a reasonable intersection
+		 * spot, then there might be a loop.
+		 */
+		n = ip[cbp - frames];
+		if (osp != &board[n]) {
+			/* check to see if this is a valid loop */
+			if (verts)
+				return (-1);
+			if (fcnt == 0 || lcbp->c_framecnt[0] == 0)
+				return (-1);
+			/*
+			 * Check to be sure the intersection is not
+			 * one of the end points if it is an open
+			 * ended frame.
+			 */
+			if ((flg & C_OPEN_0) &&
+			    (n == cbp->c_vertex ||
+			     n == cbp->c_vertex + 5 * dd[cbp->c_dir]))
+				return (-1);	/* invalid overlap */
+			if (cb.c.b &&
+			    (n == fcbp->c_vertex ||
+			     n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
+				return (-1);	/* invalid overlap */
+
+			vertices->o_intersect = n;
+			vertices->o_fcombo = lcbp;
+			vertices->o_link = 0;
+			vertices->o_off = (n - cbp->c_vertex) /
+				dd[cbp->c_dir];
+			vertices->o_frameindex = 0;
+			verts++;
+		}
+	}
+	return (verts);
+}
+
+/*
+ * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and
+ * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array.
+ * Return true if this list of frames is already in the hash list.
+ * Otherwise, add the new combo to the hash list.
+ */
+sortcombo(scbpp, cbpp, fcbp)
+	struct combostr **scbpp;
+	struct combostr **cbpp;
+	struct combostr *fcbp;
+{
+	struct combostr **spp, **cpp;
+	struct combostr *cbp, *ecbp;
+	int n, inx;
+
+#ifdef DEBUG
+	if (debug > 3) {
+		char *str;
+
+		sprintf(fmtbuf, "sortc: %s%c l%d", stoc(fcbp->c_vertex),
+			pdir[fcbp->c_dir], curlevel);
+		dlog(fmtbuf);
+		str = fmtbuf;
+		for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) {
+			sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
+				pdir[(*cpp)->c_dir]);
+			str += strlen(str);
+		}
+		dlog(fmtbuf);
+	}
+#endif /* DEBUG */
+
+	/* first build the new sorted list */
+	n = curlevel + 1;
+	spp = scbpp + n;
+	cpp = cbpp + curlevel;
+	do {
+		cpp--;
+		if (fcbp > *cpp) {
+			*--spp = fcbp;
+			do
+				*--spp = *cpp;
+			while (cpp-- != cbpp);
+			goto inserted;
+		}
+		*--spp = *cpp;
+	} while (cpp != cbpp);
+	*--spp = fcbp;
+inserted:
+
+	/* now check to see if this list of frames has already been seen */
+	cbp = hashcombos[inx = *scbpp - frames];
+	if (cbp == (struct combostr *)0) {
+		/*
+		 * Easy case, this list hasn't been seen.
+		 * Add it to the hash list.
+		 */
+		fcbp = (struct combostr *)
+			((char *)scbpp - sizeof(struct combostr));
+		hashcombos[inx] = fcbp;
+		fcbp->c_next = fcbp->c_prev = fcbp;
+		return (0);
+	}
+	ecbp = cbp;
+	do {
+		cbpp = (struct combostr **)(cbp + 1);
+		cpp = cbpp + n;
+		spp = scbpp + n;
+		cbpp++;	/* first frame is always the same */
+		do {
+			if (*--spp != *--cpp)
+				goto next;
+		} while (cpp != cbpp);
+		/* we found a match */
+#ifdef DEBUG
+		if (debug > 3) {
+			char *str;
+
+			sprintf(fmtbuf, "sort1: n%d", n);
+			dlog(fmtbuf);
+			str = fmtbuf;
+			for (cpp = scbpp; cpp < scbpp + n; cpp++) {
+				sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
+					pdir[(*cpp)->c_dir]);
+				str += strlen(str);
+			}
+			dlog(fmtbuf);
+			printcombo(cbp, fmtbuf);
+			dlog(fmtbuf);
+			str = fmtbuf;
+			cbpp--;
+			for (cpp = cbpp; cpp < cbpp + n; cpp++) {
+				sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
+					pdir[(*cpp)->c_dir]);
+				str += strlen(str);
+			}
+			dlog(fmtbuf);
+		}
+#endif /* DEBUG */
+		return (1);
+	next:
+		;
+	} while ((cbp = cbp->c_next) != ecbp);
+	/*
+	 * This list of frames hasn't been seen.
+	 * Add it to the hash list.
+	 */
+	ecbp = cbp->c_prev;
+	fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr));
+	fcbp->c_next = cbp;
+	fcbp->c_prev = ecbp;
+	cbp->c_prev = fcbp;
+	ecbp->c_next = fcbp;
+	return (0);
+}
+
+/*
+ * Print the combo into string 'str'.
+ */
+printcombo(cbp, str)
+	struct combostr *cbp;
+	char *str;
+{
+	struct combostr *tcbp;
+
+	sprintf(str, "%x/%d", cbp->c_combo.s, cbp->c_nframes);
+	str += strlen(str);
+	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+		sprintf(str, " %s%c%x", stoc(tcbp->c_vertex), pdir[tcbp->c_dir],
+			cbp->c_flg);
+		str += strlen(str);
+	}
+	sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
+}
+
+#ifdef DEBUG
+markcombo(ocbp)
+	struct combostr *ocbp;
+{
+	struct combostr *cbp, *tcbp, **cbpp;
+	struct elist *ep, *nep, **epp;
+	struct spotstr *sp;
+	int s, d, m, i;
+	int nframes;
+	int r, n, flg, cmask, omask;
+
+	/* should never happen but check anyway */
+	if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
+		return;
+
+	/*
+	 * The lower level combo can be pointed to by more than one
+	 * higher level 'struct combostr' so we can't modify the
+	 * lower level. Therefore, higher level combos store the
+	 * real mask of the lower level frame in c_emask[0] and the
+	 * frame number in c_frameindex.
+	 *
+	 * First we traverse the tree from top to bottom and save the
+	 * connection info. Then we traverse the tree from bottom to
+	 * top overwriting lower levels with the newer emask information.
+	 */
+	ep = &einfo[nframes];
+	cbpp = &ecombo[nframes];
+	for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+		ep--;
+		ep->e_combo = cbp;
+		*--cbpp = cbp->c_link[1];
+		ep->e_off = cbp->c_voff[1];
+		ep->e_frameindex = cbp->c_frameindex;
+		ep->e_fval.s = cbp->c_linkv[1].s;
+		ep->e_framecnt = cbp->c_framecnt[1];
+		ep->e_emask = cbp->c_emask[1];
+	}
+	cbp = ep->e_combo;
+	ep--;
+	ep->e_combo = cbp;
+	*--cbpp = cbp->c_link[0];
+	ep->e_off = cbp->c_voff[0];
+	ep->e_frameindex = 0;
+	ep->e_fval.s = cbp->c_linkv[0].s;
+	ep->e_framecnt = cbp->c_framecnt[0];
+	ep->e_emask = cbp->c_emask[0];
+
+	/* now update the emask info */
+	s = 0;
+	for (i = 2, ep += 2; i < nframes; i++, ep++) {
+		cbp = ep->e_combo;
+		nep = &einfo[ep->e_frameindex];
+		nep->e_framecnt = cbp->c_framecnt[0];
+		nep->e_emask = cbp->c_emask[0];
+
+		if (cbp->c_flg & C_LOOP) {
+			s++;
+			/*
+			 * Account for the fact that this frame connects
+			 * to a previous one (thus forming a loop).
+			 */
+			nep = &einfo[cbp->c_dir];
+			if (--nep->e_framecnt)
+				nep->e_emask &= ~(1 << cbp->c_voff[0]);
+			else
+				nep->e_emask = 0;
+		}
+	}
+
+	/*
+	 * We only need to update the emask values of "complete" loops
+	 * to include the intersection spots.
+	 */
+	if (s && ocbp->c_combo.c.a == 2) {
+		/* process loops from the top down */
+		ep = &einfo[nframes];
+		do {
+			ep--;
+			cbp = ep->e_combo;
+			if (!(cbp->c_flg & C_LOOP))
+				continue;
+
+			/*
+			 * Update the emask values to include the
+			 * intersection spots.
+			 */
+			nep = &einfo[cbp->c_dir];
+			nep->e_framecnt = 1;
+			nep->e_emask = 1 << cbp->c_voff[0];
+			ep->e_framecnt = 1;
+			ep->e_emask = 1 << ep->e_off;
+			ep = &einfo[ep->e_frameindex];
+			do {
+				ep->e_framecnt = 1;
+				ep->e_emask = 1 << ep->e_off;
+				ep = &einfo[ep->e_frameindex];
+			} while (ep > nep);
+		} while (ep != einfo);
+	}
+
+	/* mark all the frames with the completion spots */
+	for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
+		m = ep->e_emask;
+		cbp = *cbpp;
+		sp = &board[cbp->c_vertex];
+		d = dd[s = cbp->c_dir];
+		cmask = CFLAG << s;
+		omask = (IFLAG | CFLAG) << s;
+		s = ep->e_fval.c.b ? 6 : 5;
+		for (; --s >= 0; sp += d, m >>= 1)
+			sp->s_flg |= (m & 1) ? omask : cmask;
+	}
+}
+
+clearcombo(cbp, open)
+	struct combostr *cbp;
+	int open;
+{
+	register struct spotstr *sp;
+	struct combostr *tcbp;
+	int d, n, mask;
+
+	for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+		clearcombo(tcbp, cbp->c_flg & C_OPEN_1);
+		open = cbp->c_flg & C_OPEN_0;
+	}
+	sp = &board[cbp->c_vertex];
+	d = dd[n = cbp->c_dir];
+	mask = ~((IFLAG | CFLAG) << n);
+	n = open ? 6 : 5;
+	for (; --n >= 0; sp += d)
+		sp->s_flg &= mask;
+}
+
+list_eq(scbpp, cbpp, n)
+	struct combostr **scbpp;
+	struct combostr **cbpp;
+	int n;
+{
+	struct combostr **spp, **cpp;
+
+	spp = scbpp + n;
+	cpp = cbpp + n;
+	do {
+		if (*--spp != *--cpp)
+			return (0);
+	} while (cpp != cbpp);
+	/* we found a match */
+	return (1);
+}
+#endif /* DEBUG */
diff --git a/gomoku/stoc.c b/gomoku/stoc.c
new file mode 100644
index 00000000..63669151
--- /dev/null
+++ b/gomoku/stoc.c
@@ -0,0 +1,106 @@
+/*
+ * 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.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)stoc.c	8.1 (Berkeley) 7/24/94";
+#endif /* not lint */
+
+#include "gomoku.h"
+#include <ctype.h>
+
+char	*letters	= "<ABCDEFGHJKLMNOPQRST>";
+
+struct mvstr {
+	int	m_code;
+	char	*m_text;
+};
+static	struct	mvstr	mv[] = {
+	RESIGN,		"resign",
+	RESIGN,		"quit",
+	SAVE,		"save",
+	-1,		0
+};
+
+/*
+ * Turn the spot number form of a move into the character form.
+ */
+char *
+stoc(s)
+	int s;
+{
+	static char buf[32];
+	register int i;
+
+	for (i = 0; mv[i].m_code >= 0; i++)
+		if (s == mv[i].m_code)
+			return(mv[i].m_text);
+	sprintf(buf, "%c%d", letters[s % BSZ1], s / BSZ1);
+	return(buf);
+}
+
+/*
+ * Turn the character form of a move into the spot number form.
+ */
+ctos(mp)
+	char *mp;
+{
+	register int i;
+
+	for (i = 0; mv[i].m_code >= 0; i++)
+		if (strcmp(mp, mv[i].m_text) == 0)
+			return(mv[i].m_code);
+	if (!isalpha(mp[0]))
+		return(ILLEGAL);
+	i = atoi(&mp[1]);
+	if (i < 1 || i > 19)
+		return(ILLEGAL);
+	return(PT(lton(mp[0]), i));
+}
+
+/*
+ * Turn a letter into a number.
+ */
+lton(c)
+	int c;
+{
+	register int i;
+
+	if (islower(c))
+		c = toupper(c);
+	for (i = 1; i <= BSZ && letters[i] != c; i++)
+		;
+	return(i);
+}