from Ralph Campbell
authorKirk McKusick <mckusick@ucbvax.Berkeley.EDU>
Mon, 25 Jul 1994 13:58:11 +0000 (05:58 -0800)
committerKirk McKusick <mckusick@ucbvax.Berkeley.EDU>
Mon, 25 Jul 1994 13:58:11 +0000 (05:58 -0800)
SCCS-vsn: games/gomoku/Makefile 8.1
SCCS-vsn: games/gomoku/bdinit.c 8.1
SCCS-vsn: games/gomoku/bdisp.c 8.1
SCCS-vsn: games/gomoku/gomoku.6 8.1
SCCS-vsn: games/gomoku/gomoku.h 8.1
SCCS-vsn: games/gomoku/main.c 8.1
SCCS-vsn: games/gomoku/makemove.c 8.1
SCCS-vsn: games/gomoku/pickmove.c 8.1
SCCS-vsn: games/gomoku/stoc.c 8.1

usr/src/games/gomoku/Makefile [new file with mode: 0644]
usr/src/games/gomoku/bdinit.c [new file with mode: 0644]
usr/src/games/gomoku/bdisp.c [new file with mode: 0644]
usr/src/games/gomoku/gomoku.6 [new file with mode: 0644]
usr/src/games/gomoku/gomoku.h [new file with mode: 0644]
usr/src/games/gomoku/main.c [new file with mode: 0644]
usr/src/games/gomoku/makemove.c [new file with mode: 0644]
usr/src/games/gomoku/pickmove.c [new file with mode: 0644]
usr/src/games/gomoku/stoc.c [new file with mode: 0644]

diff --git a/usr/src/games/gomoku/Makefile b/usr/src/games/gomoku/Makefile
new file mode 100644 (file)
index 0000000..1071ef3
--- /dev/null
@@ -0,0 +1,10 @@
+#      @(#)Makefile    8.1 (Berkeley) %G%
+
+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/usr/src/games/gomoku/bdinit.c b/usr/src/games/gomoku/bdinit.c
new file mode 100644 (file)
index 0000000..25464f7
--- /dev/null
@@ -0,0 +1,178 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)bdinit.c   8.1 (Berkeley) %G%";
+#endif /* not lint */
+
+#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 */
+       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_next = (struct combostr *)0;
+                               cbp->c_prev = (struct combostr *)0;
+                               cbp->c_link[0] = (struct combostr *)0;
+                               cbp->c_link[1] = (struct combostr *)0;
+                               cbp->c_combo.s = sp->s_fval[BLACK][r].s;
+                               cbp->c_vertex = sp - board;
+                               cbp->c_nframes = 1;
+                               cbp->c_dir = r;
+                               cbp->c_flg = 0;
+                               cbp->c_refcnt = 0;
+                               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 four bits corresponding
+ * to whether frame A overlaps frame B. The four combinations are
+ * whether A and B are open ended (length 6) or closed (length 5).
+ *     0       A open and B open
+ *     1       A open and B closed
+ *     2       A closed and B open
+ *     3       A closed and B closed
+ */
+init_overlap()
+{
+       register struct spotstr *sp1, *sp2;
+       register struct combostr *cbp;
+       register int i, f, r, n, d1, d2;
+       int mask, bmask, vertex, s;
+       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; ) {
+           str -= FAREA;
+           ip -= FAREA;
+           sp1 = &board[vertex = cbp->c_vertex];
+           d1 = dd[r = cbp->c_dir];
+           s = sp1->s_fval[BLACK][r].c.b;
+           for (i = 5 + s; --i >= 0; sp1 += d1, vertex += d1) {
+               mask = (s && i == 0) ? 0xC : 0xF;
+               for (r = 4; --r >= 0; ) {
+                   bmask = BFLAG << r;
+                   sp2 = sp1;
+                   d2 = dd[r];
+                   for (f = 6; --f >= 0; sp2 -= d2) {
+                       if (sp2->s_occ == BORDER)
+                           break;
+                       if (sp2->s_flg & bmask)
+                           continue;
+                       n = sp2->s_frame[r] - frames;
+                       str[n] |= (f == 0) ? mask & 0x5 : mask;
+                       ip[n] = vertex;
+                   }
+               }
+           }
+       }
+}
diff --git a/usr/src/games/gomoku/bdisp.c b/usr/src/games/gomoku/bdisp.c
new file mode 100644 (file)
index 0000000..2a1e447
--- /dev/null
@@ -0,0 +1,244 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)bdisp.c    8.1 (Berkeley) %G%";
+#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;
+
+/*
+ * 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 = "*O.?"[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 = "*O.?"[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 */
+                               cp -= 2;
+                               addch('\b');
+                               c = ' ';
+                               /* FALLTHROUGH */
+                       default:
+                               addch(c);
+                       }
+                       refresh();
+               }
+       }
+       *cp = '\0';
+       return(c != EOF);
+}
diff --git a/usr/src/games/gomoku/gomoku.6 b/usr/src/games/gomoku/gomoku.6
new file mode 100644 (file)
index 0000000..dfec56f
--- /dev/null
@@ -0,0 +1,62 @@
+.\" Copyright (c) 1994
+.\"    The Regents of the University of California.  All rights reserved.
+.\"
+.\" This code is derived from software contributed to Berkeley by
+.\" Ralph Campbell.
+.\"
+.\" %sccs.include.redist.roff%
+.\"
+.\"     @(#)gomoku.6   8.1 (Berkeley) %G%
+.\"
+.Dd 
+.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
diff --git a/usr/src/games/gomoku/gomoku.h b/usr/src/games/gomoku/gomoku.h
new file mode 100644 (file)
index 0000000..569006a
--- /dev/null
@@ -0,0 +1,205 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ *
+ *     @(#)gomoku.h    8.1 (Berkeley) %G%
+ */
+
+#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
+#define MAXDEPTH       5
+
+union  combo {
+       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 combinations of two more frames.
+ * This is so we can do it incrementally in makemove() and because
+ * we don't want to combine frames with <1,x> combos.
+ */
+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];     /* previous level or NULL if level 1 */
+       union combo     c_combo;        /* combo value for this level */
+       u_short         c_vertex;       /* intersection or frame head */
+       u_char          c_nframes;      /* number of frames in the combo */
+       u_char          c_dir;          /* which direction */
+       u_char          c_flg;          /* combo flags */
+       u_char          c_refcnt;       /* # higher levels that point to us */
+};
+
+/* flag values for s_flg */
+#define C_LOOP         0x01            /* link[1] intersects previous frame */
+
+struct elist {
+       struct elist    *e_next;        /* list of combos */
+       struct combostr *e_combo;       /* the combo */
+       struct combostr *e_frame;       /* the 1st level combo that connects */
+};
+
+/*
+ * 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 */
+       union combo     s_fval[2][4];   /* combo value for [color][frame] */
+       union combo     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 combostr *s_frame[4];    /* level 1 combo for frame[dir] */
+       struct elist    *s_empty[2];    /* level n combo for [color] */
+};
+
+/* 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 */
+
+extern char    *letters;
+extern char    *color[];
+extern char    fmtbuf[];
+
+extern int     dd[4];
+extern struct  spotstr board[BAREA];           /* info for board */
+extern struct  combostr frames[FAREA];         /* storage for all frames */
+extern struct  combostr *sortframes[2];        /* sorted, non-empty frames */
+extern 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/usr/src/games/gomoku/main.c b/usr/src/games/gomoku/main.c
new file mode 100644 (file)
index 0000000..552f4b6
--- /dev/null
@@ -0,0 +1,444 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char 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.1 (Berkeley) %G%";
+#endif /* not lint */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <signal.h>
+#include <curses.h>
+#include <err.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   *color[]        = { "black", "white", "empty", "border" };
+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 */
+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 */
+
+main(argc, argv)
+       int argc;
+       char **argv;
+{
+       char buf[128];
+       int color, curmove, i, ch;
+       int input[2];
+       extern void whatsup(), quit();
+       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);
+               test = 3;
+       }
+
+       if (!debug)
+#ifdef SVR4
+               srandom(time(0));
+#else
+               srand(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 (test != 3) {
+                       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);
+               }
+       }
+
+       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;
+
+       case 3: /* user verses program */
+               input[BLACK] = INPUTF;
+               input[WHITE] = INPUTF;
+       }
+       if (interactive) {
+               plyr[BLACK] = input[BLACK] == USER ? "you" : prog;
+               plyr[WHITE] = input[WHITE] == USER ? "you" : prog;
+               bdwho(1);
+       }
+
+       for (color = BLACK; ; color = !color) {
+               switch (input[color]) {
+               case INPUTF: /* input comes from a file */
+                       curmove = readinput(inputfp);
+                       if (curmove != ILLEGAL)
+                               break;
+                       input[color] = USER;
+                       input[!color] = PROGRAM;
+                       plyr[color] = "you";
+                       bdwho(1);
+                       /* FALLTHROUGH */
+
+               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) {
+                       ask("replay? ");
+                       if (getline(buf, sizeof buf) &&
+                           buf[0] == 'y' || buf[0] == 'Y')
+                               goto again;
+               }
+       }
+       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;
+       struct spotstr *sp;
+       FILE *fp;
+       char *str;
+       struct elist *ep;
+       struct combostr *cbp;
+
+       if (!interactive)
+               quit();
+top:
+       ask("cmd? ");
+       if (!getline(fmtbuf, 128))
+               quit();
+       switch (*fmtbuf) {
+       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 '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 '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 'P':
+               sp = &board[i = ctos(fmtbuf + 1)];
+               for (pnum = BLACK; pnum <= WHITE; pnum++) {
+                       for (ep = sp->s_empty[pnum]; ep; ep = ep->e_next) {
+                               cbp = ep->e_combo;
+                               str = fmtbuf;
+                               sprintf(str, "C%c %s", "BW"[pnum], stoc(i));
+                               str += strlen(str);
+                               if (cbp->c_nframes == 2) {
+                                       sprintf(str, " %s%c",
+                                               stoc(cbp->c_link[0]->c_vertex),
+                                               pdir[cbp->c_link[0]->c_dir]);
+                                       str += strlen(str);
+                                       sprintf(str, " %s%c %x/%d",
+                                               stoc(cbp->c_link[1]->c_vertex),
+                                               pdir[cbp->c_link[1]->c_dir],
+                                               cbp->c_combo.s, cbp->c_nframes);
+                               } else {
+                                       sprintf(str, " %s%c %x/%d",
+                                               stoc(cbp->c_vertex),
+                                               pdir[ep->e_frame->c_dir],
+                                               cbp->c_combo.s, cbp->c_nframes);
+                               }
+                               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);
+       else 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/usr/src/games/gomoku/makemove.c b/usr/src/games/gomoku/makemove.c
new file mode 100644 (file)
index 0000000..7082b26
--- /dev/null
@@ -0,0 +1,182 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)makemove.c 8.1 (Berkeley) %G%";
+#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 combo *cp;
+       struct spotstr *osp;
+       struct combostr *cbp, *cbp1;
+       union combo *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:
+           ;
+       }
+
+       return(MOVEOK);
+}
diff --git a/usr/src/games/gomoku/pickmove.c b/usr/src/games/gomoku/pickmove.c
new file mode 100644 (file)
index 0000000..3a996d5
--- /dev/null
@@ -0,0 +1,880 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)pickmove.c 8.1 (Berkeley) %G%";
+#endif /* not lint */
+
+#include <stdio.h>
+#include <curses.h>
+
+#include "gomoku.h"
+
+struct combostr *sortcombos[2];        /* combos at higher levels */
+int    combolen[2];                    /* number of combos in sortcombos */
+int    nextcolor;                      /* color of next move */
+
+extern char pdir[];
+
+pickmove(us)
+       int us;
+{
+       register struct spotstr *sp, *sp1, *sp2;
+       register union combo *Ocp, *Tcp;
+
+       /* first move is easy */
+       if (movenum == 1)
+               return (PT(K,10));
+
+       /* initialize all the board values */
+       for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
+               sp->s_combo[BLACK].s = MAXCOMBO;
+               sp->s_combo[WHITE].s = MAXCOMBO;
+               sp->s_level[BLACK] = 255;
+               sp->s_level[WHITE] = 255;
+               sp->s_nforce[BLACK] = 0;
+               sp->s_nforce[WHITE] = 0;
+               sp->s_flg &= ~(FFLAGALL | MFLAGALL);
+       }
+
+       /* remove old combos */
+       removecombos(BLACK);
+       removecombos(WHITE);
+       removeemptyspots();
+
+       /* compute new values */
+       nextcolor = us;
+       scanframes(BLACK);
+       scanframes(WHITE);
+
+       /* find the spot with the highest value */
+       for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
+               if (sp->s_occ != EMPTY)
+                       continue;
+               if (debug && (sp->s_combo[BLACK].s < 0x200 ||
+                   sp->s_combo[WHITE].s < 0x200)) {
+                       sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board),
+                               sp->s_combo[BLACK].s, sp->s_level[BLACK],
+                               sp->s_nforce[BLACK],
+                               sp->s_combo[WHITE].s, sp->s_level[WHITE],
+                               sp->s_nforce[WHITE],
+                               sp->s_wval);
+                       dlog(fmtbuf);
+               }
+               /* pick the best black move */
+               if (better(sp, sp1, BLACK))
+                       sp1 = sp;
+               /* pick the best white move */
+               if (better(sp, sp2, WHITE))
+                       sp2 = sp;
+       }
+       if (debug) {
+               sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d %d",
+                       stoc(sp1 - board),
+                       sp1->s_combo[BLACK].s, sp1->s_level[BLACK],
+                       sp1->s_nforce[BLACK],
+                       sp1->s_combo[WHITE].s, sp1->s_level[WHITE],
+                       sp1->s_nforce[WHITE], sp1->s_wval, combolen[BLACK]);
+               dlog(fmtbuf);
+               sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d %d",
+                       stoc(sp2 - board),
+                       sp2->s_combo[WHITE].s, sp2->s_level[WHITE],
+                       sp2->s_nforce[WHITE],
+                       sp2->s_combo[BLACK].s, sp2->s_level[BLACK],
+                       sp2->s_nforce[BLACK], sp2->s_wval, combolen[WHITE]);
+               dlog(fmtbuf);
+       }
+       if (us == BLACK) {
+               Ocp = &sp1->s_combo[BLACK];
+               Tcp = &sp2->s_combo[WHITE];
+       } else {
+               Tcp = &sp1->s_combo[BLACK];
+               Ocp = &sp2->s_combo[WHITE];
+               sp = sp1;
+               sp1 = sp2;
+               sp2 = sp;
+       }
+       /*
+        * Block their combo only if we have to (i.e., if they are one move
+        * away from completing a force and we don't have a force that
+        * we can complete which takes fewer moves to win).
+        */
+       if (Tcp->c.a <= 1 && (Ocp->c.a > 1 ||
+           Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b))
+               return (sp2 - board);
+       return (sp1 - board);
+}
+
+/*
+ * Return true if spot 'sp' is better than spot 'sp1' for color 'us'.
+ */
+better(sp, sp1, us)
+       struct spotstr *sp;
+       struct spotstr *sp1;
+       int us;
+{
+       int them;
+
+       if (sp->s_combo[us].s < sp1->s_combo[us].s)
+               return (1);
+       if (sp->s_combo[us].s != sp1->s_combo[us].s)
+               return (0);
+       if (sp->s_level[us] < sp1->s_level[us])
+               return (1);
+       if (sp->s_level[us] != sp1->s_level[us])
+               return (0);
+       if (sp->s_nforce[us] > sp1->s_nforce[us])
+               return (1);
+       if (sp->s_nforce[us] != sp1->s_nforce[us])
+               return (0);
+
+       them = !us;
+       if (sp->s_combo[them].s < sp1->s_combo[them].s)
+               return (1);
+       if (sp->s_combo[them].s != sp1->s_combo[them].s)
+               return (0);
+       if (sp->s_level[them] < sp1->s_level[them])
+               return (1);
+       if (sp->s_level[them] != sp1->s_level[them])
+               return (0);
+       if (sp->s_nforce[them] > sp1->s_nforce[them])
+               return (1);
+       if (sp->s_nforce[them] != sp1->s_nforce[them])
+               return (0);
+
+       if (sp->s_wval > sp1->s_wval)
+               return (1);
+       if (sp->s_wval != sp1->s_wval)
+               return (0);
+
+#ifdef SVR4
+       return (rand() & 1);
+#else
+       return (random() & 1);
+#endif
+}
+
+int            curcolor;       /* implicit parameter to makecombo() */
+int            curlevel;       /* implicit parameter to makecombo() */
+
+/*
+ * Scan the sorted list of frames and update the minimum combo values.
+ */
+scanframes(color)
+       int color;
+{
+       register struct combostr *cbp, *ecbp;
+       register struct spotstr *sp;
+       register union combo *cp;
+       register struct elist *ep;
+       register int i, r, d, n;
+       union combo cb;
+
+       curcolor = color;
+
+       /* check for empty list of frames */
+       cbp = sortframes[color];
+       if (cbp == (struct combostr *)0)
+               return;
+
+       /* quick check for four in a row */
+       sp = &board[cbp->c_vertex];
+       cb.s = sp->s_fval[color][d = cbp->c_dir].s;
+       if (cb.s < 0x101) {
+               d = dd[d];
+               for (i = 5 + cb.c.b; --i >= 0; sp += d) {
+                       if (sp->s_occ != EMPTY)
+                               continue;
+                       sp->s_combo[color].s = cb.s;
+                       sp->s_level[color] = 1;
+               }
+               return;
+       }
+
+       /* update the minimum combo value for each spot in the frame */
+       n = combolen[color];
+       ecbp = cbp;
+       do {
+               sp = &board[cbp->c_vertex];
+               cp = &sp->s_fval[color][r = cbp->c_dir];
+               d = dd[r];
+               if (cp->c.b) {
+                       cb.c.a = cp->c.a + 1;
+                       cb.c.b = 0;
+                       if (cb.s < sp->s_combo[color].s) {
+                               sp->s_combo[color].s = cb.s;
+                               sp->s_level[color] = 1;
+                       }
+                       makecombo2(cbp, sp, cb.s);
+                       if (cp->s != 0x101)
+                               cb.s = cp->s;
+                       sp += d;
+                       i = 4;
+               } else {
+                       cb.s = cp->s;
+                       i = 5;
+               }
+               for (; --i >= 0; sp += d) {     /* for each spot */
+                       if (sp->s_occ != EMPTY)
+                               continue;
+                       if (cp->s < sp->s_combo[color].s) {
+                               sp->s_combo[color].s = cp->s;
+                               sp->s_level[color] = 1;
+                       }
+                       if (cp->s == 0x101)
+                               sp->s_nforce[color]++;
+                       makecombo2(cbp, sp, cb.s);
+               }
+               /* mark frame as having been processed */
+               board[cbp->c_vertex].s_flg |= MFLAG << r;
+       } while ((cbp = cbp->c_next) != ecbp);
+
+       /* try to make new 3rd level combos, 4th level, etc. */
+       d = 2;
+       while (combolen[color] > n) {
+               if (debug) {
+                       sprintf(fmtbuf, "%cL%d %d", "BW"[color], d,
+                               combolen[color] - n);
+                       dlog(fmtbuf);
+                       refresh();
+               }
+               n = combolen[color];
+               addframes(d);
+               d++;
+       }
+
+       /* scan for combos at empty spots */
+       for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
+               for (ep = sp->s_empty[color]; ep; ep = ep->e_next) {
+                       cbp = ep->e_combo;
+                       if (cbp->c_combo.s < sp->s_combo[color].s) {
+                               sp->s_combo[color].s = cbp->c_combo.s;
+                               sp->s_level[color] = cbp->c_nframes;
+                       } else if (cbp->c_combo.s == sp->s_combo[color].s &&
+                           cbp->c_nframes < sp->s_level[color])
+                               sp->s_level[color] = cbp->c_nframes;
+               }
+       }
+}
+
+/*
+ * Compute all level 2 combos of frames intersecting spot 'osp'
+ * within the frame 'ocbp' and combo value 's'.
+ */
+makecombo2(ocbp, osp, s)
+       struct combostr *ocbp;
+       struct spotstr *osp;
+       int s;
+{
+       register struct spotstr *sp, *fsp;
+       register struct combostr *cbp;
+       register int f, r, d, c;
+       int baseB, bmask, n;
+       union combo ocb, fcb;
+
+       /* try to combine a new frame with those found so far */
+       ocb.s = s;
+       baseB = ocb.c.a + ocb.c.b - 1;
+       for (r = 4; --r >= 0; ) {                       /* for each direction */
+           /* don't include frames that overlap ones already included */
+           if (r == ocbp->c_dir)
+               continue;
+           d = dd[r];
+           bmask = (BFLAG | FFLAG | MFLAG) << r;
+           fsp = osp;
+           for (f = 5; --f >= 0; fsp -= d) {           /* for each frame */
+               /*
+                * Don't include frames that are blocked or
+                * part of a <1,x> combo.
+                */
+               if (fsp->s_occ == BORDER)
+                   break;
+               if (fsp->s_flg & bmask)
+                   continue;
+
+               /* don't include frames of the wrong color */
+               fcb.s = fsp->s_fval[curcolor][r].s;
+               if (fcb.c.a >= MAXA)
+                   continue;
+
+               /*
+                * Get the combo value for this frame.
+                * If this is the end point of the frame,
+                * use the closed ended value for the frame.
+                */
+               if (f == 4 && fcb.c.b || fcb.s == 0x101) {
+                   fcb.c.a++;
+                   fcb.c.b = 0;
+               }
+
+               /* compute combo value */
+               c = fcb.c.a + ocb.c.a - 3;
+               if (c > 3)
+                   continue;
+               n = fcb.c.a + fcb.c.b - 1;
+               if (baseB < n)
+                   n = baseB;
+
+               /* make a new combo! */
+               cbp = (struct combostr *)malloc(sizeof(struct combostr));
+               cbp->c_combo.c.a = c;
+               cbp->c_combo.c.b = n;
+               cbp->c_link[0] = ocbp;
+               cbp->c_link[1] = fsp->s_frame[r];
+               cbp->c_vertex = osp - board;
+               cbp->c_nframes = 2;
+               cbp->c_dir = 0;
+               cbp->c_flg = 0;
+               cbp->c_refcnt = 0;
+
+               if (c == 1 && debug > 1 || debug > 3) {
+                   sprintf(fmtbuf, "%c %s %x/2 r%d f%d %x",
+                       curcolor == BLACK ? 'b' : 'w',
+                       stoc(osp - board), cbp->c_combo.s, r, f, ocb.s);
+                   dlog(fmtbuf);
+#ifdef DEBUG
+                   markcombo(cbp, curcolor, 0);
+                   bdisp();
+                   whatsup(0);
+                   clearcombo(cbp, curcolor, 0);
+#endif
+               }
+               if (c > 1) {
+                   if (ocb.c.a > 2)
+                       makeempty(cbp, ocbp, ocb.c.b);
+                   if (fcb.c.a > 2)
+                       makeempty(cbp, cbp->c_link[1], fcb.c.b);
+
+                   /* add the new combo to the end of the list */
+                   appendcombo(cbp, curcolor);
+               } else {
+                   updatecombo(cbp, curcolor);
+                   free(cbp);
+               }
+           }
+       }
+}
+
+/*
+ * Scan the sorted list of frames and try to combine into combos.
+ */
+addframes(level)
+       int level;
+{
+       register struct combostr *cbp, *ecbp;
+       register struct spotstr *sp, *fsp;
+       register int i, r, d;
+       union combo fcb, cb;
+
+       curlevel = level;
+
+       /* clear MFLAG for this level */
+       cbp = ecbp = sortframes[curcolor];
+       do {
+               board[cbp->c_vertex].s_flg &= ~MFLAGALL;
+       } while ((cbp = cbp->c_next) != ecbp);
+
+       cbp = ecbp;
+       do {
+               fsp = &board[cbp->c_vertex];
+               r = cbp->c_dir;
+               /* skip frames that are part of a <1,x> combo */
+               if (fsp->s_flg & (FFLAG << r))
+                       continue;
+
+               /*
+                * Don't include <1,x> combo frames,
+                * treat it as a blocked three in a row instead.
+                */
+               fcb.s = fsp->s_fval[curcolor][r].s;
+               if (fcb.s == 0x101)
+                       fcb.s = 0x200;
+
+               /*
+                * If this is an open ended frame, use
+                * the combo value with the end closed.
+                */
+               if (fsp->s_occ == EMPTY) {
+                       if (fcb.c.b) {
+                               cb.c.a = fcb.c.a + 1;
+                               cb.c.b = 0;
+                       } else
+                               cb.s = fcb.s;
+                       makecombo(cbp, fsp, cb.s);
+               }
+
+               /*
+                * The next four spots are handled the same for both
+                * open and closed ended frames.
+                */
+               d = dd[r];
+               sp = fsp + d;
+               for (i = 4; --i >= 0; sp += d) {
+                       if (sp->s_occ != EMPTY)
+                               continue;
+                       makecombo(cbp, sp, fcb.s);
+               }
+
+               /* mark frame as having been processed */
+               fsp->s_flg |= MFLAG << r;
+       } while ((cbp = cbp->c_next) != ecbp);
+}
+
+/*
+ * Compute all level N combos of frames intersecting spot 'osp'
+ * within the frame 'ocbp' and combo value 's'.
+ */
+makecombo(ocbp, osp, s)
+       struct combostr *ocbp;
+       struct spotstr *osp;
+       int s;
+{
+       register struct combostr *cbp, *ncbp;
+       register struct spotstr *sp;
+       register struct elist *ep;
+       register int n, c;
+       struct elist *nep, **epp;
+       struct combostr *fcbp;
+       int baseB, verts, d;
+       union combo ocb, cb;
+
+       ocb.s = s;
+       baseB = ocb.c.a + ocb.c.b - 1;
+       for (ep = osp->s_empty[curcolor]; ep; ep = ep->e_next) {
+           /* don't try to combine this combo if it is the wrong level */
+           cbp = ep->e_combo;
+           if (cbp->c_nframes > curlevel)
+               continue;
+           if (cbp->c_nframes != curlevel)
+               break;
+
+           /* don't include frames that overlap ones already included */
+           ncbp = ep->e_frame;
+           if (ncbp->c_dir == ocbp->c_dir ||
+               (cbp->c_flg & C_LOOP) && cbp->c_dir == ocbp->c_dir ||
+               (n = checkframes(cbp, ocbp, osp - board, ncbp)) < 0)
+                   continue;
+
+           /* compute first half of combo value */
+           c = cbp->c_combo.c.a + ocb.c.a - 3;
+           if (c > 3)
+               continue;
+
+           /* check to see if this frame forms a valid loop */
+           verts = 0;
+           if (n) {
+               sp = &board[ocbp->c_vertex];
+               d = dd[ocbp->c_dir];
+               if (n = ocb.c.b)
+                       sp += d;
+               for (; n < 5; n++, sp += d) {
+                   if (sp->s_occ != EMPTY || sp == osp)
+                       continue;
+                   for (nep = sp->s_empty[curcolor]; nep; nep = nep->e_next) {
+                       if (nep->e_combo == cbp) {
+                           verts++;
+                           fcbp = nep->e_frame;
+                           continue;
+                       }
+                       if (nep->e_combo->c_nframes < cbp->c_nframes)
+                           break;
+                   }
+               }
+#if 0
+               {
+               char *str;
+               sprintf(fmtbuf, "%c v%d %s%c",
+                   curcolor == BLACK ? 'b' : 'w', verts,
+                   stoc(ocbp->c_vertex), pdir[ocbp->c_dir]);
+               str = fmtbuf + strlen(fmtbuf);
+               for (; cbp->c_link[1]; cbp = cbp->c_link[0]) {
+                   sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex),
+                       pdir[cbp->c_link[1]->c_dir]);
+                   str += strlen(str);
+               }
+               sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
+               dlog(fmtbuf);
+               cbp = ep->e_combo;
+               }
+#endif
+               /* frame overlaps but not at a valid spot */
+               if (verts == 0 || ocb.c.a < 3)
+                   continue;
+           }
+
+           /* compute second half of combo value */
+           cb.s = board[ncbp->c_vertex].s_fval[curcolor][ncbp->c_dir].s;
+           n = cb.c.a + cb.c.b - 1;
+           if (baseB < n)
+               n = baseB;
+
+           /* make a new combo! */
+           ncbp = (struct combostr *)malloc(sizeof(struct combostr));
+           c -= verts;
+           ncbp->c_combo.c.a = c;
+           ncbp->c_combo.c.b = n;
+           ncbp->c_link[0] = cbp;
+           ncbp->c_link[1] = ocbp;
+           ncbp->c_vertex = osp - board;
+           ncbp->c_nframes = cbp->c_nframes + 1;
+           ncbp->c_refcnt = 0;
+           if (verts) {
+               ncbp->c_flg = C_LOOP;
+               ncbp->c_dir = fcbp->c_dir;
+
+               /* add the combo to the list of empty spots */
+               nep = (struct elist *)malloc(sizeof(struct elist));
+               nep->e_combo = ncbp;
+               nep->e_frame = ocbp;
+               if (debug > 2) {
+                   sprintf(fmtbuf, "e %s", stoc(ncbp->c_vertex));
+                   dlog(fmtbuf);
+               }
+
+               /* sort by the number of frames in the combo */
+               epp = &board[ncbp->c_vertex].s_empty[curcolor];
+               while (*epp) {
+                   if (cbp->c_nframes >= (*epp)->e_combo->c_nframes)
+                       break;
+                   epp = &(*epp)->e_next;
+               }
+               nep->e_next = *epp;
+               *epp = nep;
+           } else {
+               ncbp->c_flg = 0;
+               ncbp->c_dir = 0;
+               if (ocb.c.a > 2)
+                   makeempty(ncbp, ocbp, ocb.c.b);
+           }
+           if (verts > 1 && debug || c == 1 && debug > 1 || debug > 2) {
+               char *str;
+
+               sprintf(fmtbuf, "%c %s%c %x v%d %x/%d",
+                   curcolor == BLACK ? 'b' : 'w',
+                   stoc(osp - board), pdir[ocbp->c_dir], ocb.s,
+                   verts, ncbp->c_combo.s, ncbp->c_nframes);
+               dlog(fmtbuf);
+               str = fmtbuf;
+               for (cbp = ncbp; cbp->c_link[1]; cbp = cbp->c_link[0]) {
+                   sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex),
+                       pdir[cbp->c_link[1]->c_dir]);
+                   str += strlen(str);
+               }
+               sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
+               dlog(fmtbuf);
+#ifdef DEBUG
+               markcombo(ncbp, curcolor, 0);
+               bdisp();
+               whatsup(0);
+               clearcombo(ncbp, curcolor, 0);
+#endif
+           }
+           if (c > 1) {
+               /* add the new combo to the end of the list */
+               appendcombo(ncbp, curcolor);
+           } else {
+               updatecombo(ncbp, curcolor);
+               free(ncbp);
+           }
+       }
+}
+
+/*
+ * Add the combostr 'cbp' to the empty spots list for each empty spot
+ * in the frame 'fcbp' except for the intersection.
+ * 's' is zero if 'fcbp' is a closed ended frame, else it is one.
+ * Return the number of valid intersections with ocbp for detecting loops.
+ */
+makeempty(cbp, fcbp, s)
+       struct combostr *cbp;
+       struct combostr *fcbp;
+       int s;
+{
+       struct spotstr *sp, *vsp;
+       struct elist *ep, **epp;
+       int d;
+
+       if (debug > 2) {
+               sprintf(fmtbuf, "E %s%c s%d", stoc(fcbp->c_vertex),
+                       pdir[fcbp->c_dir], s);
+               sprintf(fmtbuf + strlen(fmtbuf), " %s", stoc(cbp->c_vertex));
+               dlog(fmtbuf);
+       }
+       vsp = &board[cbp->c_vertex];
+       sp = &board[fcbp->c_vertex];
+       d = dd[fcbp->c_dir];
+       if (s)
+               sp += d;
+       for (; s < 5; s++, sp += d) {
+               if (sp->s_occ != EMPTY || sp == vsp)
+                       continue;
+
+               /* add the combo to the list of empty spots */
+               ep = (struct elist *)malloc(sizeof(struct elist));
+               ep->e_combo = cbp;
+               ep->e_frame = fcbp;
+               if (debug > 2) {
+                       sprintf(fmtbuf, "e %s", stoc(sp - board));
+                       dlog(fmtbuf);
+               }
+
+               /* sort by the number of frames in the combo */
+               epp = &sp->s_empty[curcolor];
+               while (*epp) {
+                       if (cbp->c_nframes >= (*epp)->e_combo->c_nframes)
+                               break;
+                       epp = &(*epp)->e_next;
+               }
+               ep->e_next = *epp;
+               *epp = ep;
+       }
+}
+
+/*
+ * Update the board value based on the combostr.
+ * This is called only if 'cbp' is a <1,x> combo.
+ * We handle things differently depending on whether the next move
+ * would be trying to "complete" the combo or trying to block it.
+ */
+updatecombo(cbp, color)
+       struct combostr *cbp;
+       int color;
+{
+       register struct framestr *fp;
+       register struct spotstr *sp;
+       register struct combostr *tcbp;
+       register int i, d;
+       int nframes, vertex;
+       union combo cb;
+
+       for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+               if (color == nextcolor) {
+                       /* update the board value for the vertex */
+                       sp = &board[cbp->c_vertex];
+                       sp->s_nforce[color]++;
+                       if (cbp->c_combo.s < sp->s_combo[color].s) {
+                               sp->s_combo[color].s = cbp->c_combo.s;
+                               sp->s_level[color] = cbp->c_nframes;
+                       } else if (cbp->c_combo.s == sp->s_combo[color].s &&
+                           cbp->c_nframes < sp->s_level[color])
+                               sp->s_level[color] = cbp->c_nframes;
+               } else {
+                       /* update the board values for each spot in frame */
+                       vertex = cbp->c_vertex;
+                       sp = &board[tcbp->c_vertex];
+                       if (sp->s_fval[color][tcbp->c_dir].c.b &&
+                           tcbp->c_vertex != vertex)
+                               i = 6;
+                       else
+                               i = 5;
+                       d = dd[tcbp->c_dir];
+                       cb.s = cbp->c_combo.s;
+                       nframes = cbp->c_nframes;
+                       for (; --i >= 0; sp += d) {
+                               sp->s_nforce[color]++;
+                               if (cb.s < sp->s_combo[color].s) {
+                                       sp->s_combo[color].s = cb.s;
+                                       sp->s_level[color] = nframes;
+                               } else if (cb.s == sp->s_combo[color].s &&
+                                   cbp->c_nframes < sp->s_level[color])
+                                       sp->s_level[color] = nframes;
+                       }
+               }
+
+               /* mark the frame as being part of a <1,x> combo */
+               board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir;
+       }
+
+       if (color != nextcolor) {
+               /* update the board values for each spot in frame */
+               sp = &board[cbp->c_vertex];
+               if (sp->s_fval[color][cbp->c_dir].c.b &&
+                   cbp->c_vertex != vertex)
+                       i = 6;
+               else
+                       i = 5;
+               d = dd[cbp->c_dir];
+               for (; --i >= 0; sp += d) {
+                       sp->s_nforce[color]++;
+                       if (cb.s < sp->s_combo[color].s) {
+                               sp->s_combo[color].s = cb.s;
+                               sp->s_level[color] = nframes;
+                       } else if (cb.s == sp->s_combo[color].s &&
+                           cbp->c_nframes < sp->s_level[color])
+                               sp->s_level[color] = nframes;
+               }
+       }
+
+       /* mark the frame as being part of a <1,x> combo */
+       board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir;
+}
+
+/*
+ * Free all elist structures.
+ */
+removeemptyspots()
+{
+       register struct elist *ep, *nep;
+       register struct spotstr *sp;
+       int i;
+
+       for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
+               for (i = BLACK; i <= WHITE; i++) {
+                       for (ep = sp->s_empty[i]; ep; ep = nep) {
+                               nep = ep->e_next;
+                               free(ep);
+                       }
+                       sp->s_empty[i] = (struct elist *)0;
+               }
+       }
+}
+
+/*
+ * Remove all combo structures.
+ */
+removecombos(color)
+       int color;
+{
+       register struct combostr *cbp, *ncbp, *endcbp;
+
+       /* check the list */
+       if ((cbp = sortcombos[color]) == (struct combostr *)0)
+               return;
+
+       /* scan the list */
+       endcbp = cbp;
+       do {
+               ncbp = cbp->c_next;
+               cbp->c_next = (struct combostr *)0;
+               cbp->c_prev = (struct combostr *)0;
+               free(cbp);
+               cbp = ncbp;
+       } while (cbp != endcbp);
+
+       sortcombos[color] = (struct combostr *)0;
+       combolen[color] = 0;
+}
+
+/*
+ * Add combo to the end of the list.
+ */
+appendcombo(cbp, color)
+       struct combostr *cbp;
+       int color;
+{
+       struct combostr *pcbp, *ncbp;
+
+       combolen[color]++;
+       ncbp = sortcombos[color];
+       if (ncbp == (struct combostr *)0) {
+               sortcombos[color] = cbp;
+               cbp->c_next = cbp;
+               cbp->c_prev = cbp;
+               return;
+       }
+       pcbp = ncbp->c_prev;
+       cbp->c_next = ncbp;
+       cbp->c_prev = pcbp;
+       ncbp->c_prev = cbp;
+       pcbp->c_next = cbp;
+}
+
+/*
+ * Return positive if frame 'fcbp' overlaps any of the frames in 'cbp'
+ * other than the frame 'ecbp'.
+ * Return -1 if any of the frames in 'cbp' are marked or part of a <1,x> combo.
+ * Else, return zero.
+ */
+checkframes(cbp, fcbp, vertex, ecbp)
+       struct combostr *cbp;
+       struct combostr *fcbp;
+       int vertex;
+       struct combostr *ecbp;
+{
+       struct combostr *tcbp;
+       char *str;
+       int i, n, mask;
+       short *ip;
+
+       n = (fcbp - frames) * FAREA;
+       str = &overlap[n];
+       ip = &intersect[n];
+       i = vertex == fcbp->c_vertex ? 2 : 0;
+       for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
+#if 0
+               if (board[tcbp->c_vertex].s_flg & (FFLAG << tcbp->c_dir))
+                       return (-1);
+#endif
+               vertex = cbp->c_vertex;
+               if (tcbp == ecbp)
+                       continue;
+               n = tcbp - frames;
+               if (board[ip[n]].s_occ != EMPTY)
+                       continue;
+               mask = str[n];
+               if (mask & (1 << (i + (tcbp->c_vertex == vertex))))
+                       return (1);
+       }
+#if 0
+       if (board[cbp->c_vertex].s_flg & (FFLAG << cbp->c_dir))
+               return (-1);
+#endif
+       if (cbp == ecbp)
+               return (0);
+       n = cbp - frames;
+       if (board[ip[n]].s_occ != EMPTY)
+               return (0);
+       mask = str[n];
+       return (mask & (1 << (i + (cbp->c_vertex == vertex))));
+}
+
+#ifdef DEBUG
+markcombo(cbp, color, vertex)
+       struct combostr *cbp;
+       int color;
+       int vertex;
+{
+       register struct spotstr *sp;
+       struct combostr *tcbp;
+       int i, d, r, n, mask;
+
+       for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0])
+               markcombo(tcbp, color, vertex = cbp->c_vertex);
+       sp = &board[cbp->c_vertex];
+       d = dd[r = cbp->c_dir];
+       mask = (IFLAG | CFLAG) << r;
+       n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5;
+       for (i = 0; i < n; i++, sp += d) {
+               if (n == 6 && (i == 0 || i == 5))
+                       sp->s_flg |= CFLAG << r;
+               else
+                       sp->s_flg |= mask;
+       }
+}
+
+clearcombo(cbp, color, vertex)
+       struct combostr *cbp;
+       int color;
+       int vertex;
+{
+       register struct spotstr *sp;
+       struct combostr *tcbp;
+       int i, d, r, n, mask;
+
+       for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0])
+               clearcombo(tcbp, color, vertex = cbp->c_vertex);
+       sp = &board[cbp->c_vertex];
+       d = dd[r = cbp->c_dir];
+       mask = ~((IFLAG | CFLAG) << r);
+       n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5;
+       for (i = 0; i < n; i++, sp += d)
+               sp->s_flg &= mask;
+}
+#endif /* DEBUG */
diff --git a/usr/src/games/gomoku/stoc.c b/usr/src/games/gomoku/stoc.c
new file mode 100644 (file)
index 0000000..e50f5c9
--- /dev/null
@@ -0,0 +1,80 @@
+/*
+ * Copyright (c) 1994
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ralph Campbell.
+ *
+ * %sccs.include.redist.c%
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)stoc.c     8.1 (Berkeley) %G%";
+#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);
+}