update from Ralph

SCCS-vsn: games/gomoku/bdinit.c 8.2
SCCS-vsn: games/gomoku/bdisp.c 8.2
SCCS-vsn: games/gomoku/gomoku.h 8.2
SCCS-vsn: games/gomoku/main.c 8.3
SCCS-vsn: games/gomoku/makemove.c 8.2
SCCS-vsn: games/gomoku/pickmove.c 8.2

diff --git a/usr/src/games/gomoku/bdinit.c b/usr/src/games/gomoku/bdinit.c
index 25464f7..7fcc51b 100644 (file)
--- a/usr/src/games/gomoku/bdinit.c
+++ b/usr/src/games/gomoku/bdinit.c
@@ -9,9 +9,10 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)bdinit.c   8.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)bdinit.c   8.2 (Berkeley) %G%";

 #endif /* not lint */
 
 #endif /* not lint */
 

+#include <string.h>

 #include "gomoku.h"
 
 bdinit(bp)
 #include "gomoku.h"
 
 bdinit(bp)


@@ -31,6 +32,7 @@ bdinit(bp)
        }
 
        /* fill entire board with EMPTY spots */
        }
 
        /* 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 */
        cbp = frames;
        for (j = 0; ++j < BSZ1; sp++) {                 /* for each row */
                for (i = 0; ++i < BSZ1; sp++) {         /* for each column */


@@ -99,16 +101,10 @@ bdinit(bp)
                        for (r = 4; --r >= 0; ) {
                                if (sp->s_flg & (BFLAG << r))
                                        continue;
                        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_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_frame[r] = cbp;
                                cbp++;
                        }


@@ -130,13 +126,20 @@ bdinit(bp)
 
 /*
  * Initialize the overlap array.
 
 /*
  * 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
+ * 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()
 {
  */
 init_overlap()
 {


@@ -144,33 +147,72 @@ init_overlap()
        register struct combostr *cbp;
        register int i, f, r, n, d1, d2;
        int mask, bmask, vertex, s;
        register struct combostr *cbp;
        register int i, f, r, n, d1, d2;
        int mask, bmask, vertex, s;

-       char *str;
+       u_char *str;

        short *ip;
 
        memset(overlap, 0, sizeof(overlap));
        memset(intersect, 0, sizeof(intersect));
        str = &overlap[FAREA * FAREA];
        ip = &intersect[FAREA * FAREA];
        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; ) {
+       for (cbp = frames + FAREA; --cbp >= frames; ) {         /* each frame */

            str -= FAREA;
            ip -= FAREA;
            sp1 = &board[vertex = cbp->c_vertex];
            d1 = dd[r = cbp->c_dir];
            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;
+           /*
+            * 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 (r = 4; --r >= 0; ) {
                    bmask = BFLAG << r;
                    sp2 = sp1;
                    d2 = dd[r];

-                   for (f = 6; --f >= 0; sp2 -= d2) {
+                   /* 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;
                        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;
                        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/usr/src/games/gomoku/bdisp.c b/usr/src/games/gomoku/bdisp.c
index 2a1e447..937e6a9 100644 (file)
--- a/usr/src/games/gomoku/bdisp.c
+++ b/usr/src/games/gomoku/bdisp.c
@@ -9,7 +9,7 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)bdisp.c    8.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)bdisp.c    8.2 (Berkeley) %G%";

 #endif /* not lint */
 
 #include "gomoku.h"
 #endif /* not lint */
 
 #include "gomoku.h"


@@ -20,6 +20,7 @@ static char sccsid[] = "@(#)bdisp.c   8.1 (Berkeley) %G%";
 #define        SCRNW           80              /* assume 80 chars for the moment */
 
 static int     lastline;
 #define        SCRNW           80              /* assume 80 chars for the moment */
 
 static int     lastline;

+static char    pcolor[] = "*O.?";

 
 /*
  * Initialize screen display.
 
 /*
  * Initialize screen display.


@@ -120,7 +121,7 @@ bdisp()
                                else
                                        c = '.';
                        } else
                                else
                                        c = '.';
                        } else

-                               c = "*O.?"[sp->s_occ];
+                               c = pcolor[sp->s_occ];

                        addch(c);
                }
        }
                        addch(c);
                }
        }


@@ -153,7 +154,7 @@ bdump(fp)
                                else
                                        c = '.';
                        } else
                                else
                                        c = '.';
                        } else

-                               c = "*O.?"[sp->s_occ];
+                               c = pcolor[sp->s_occ];

                        putc(c, fp);
                        putc(' ', fp);
                }
                        putc(c, fp);
                        putc(' ', fp);
                }


@@ -229,6 +230,10 @@ getline(buf, size)
                                break;
                        case '\b':
                        case 0x7f: /* DEL */
                                break;
                        case '\b':
                        case 0x7f: /* DEL */

+                               if (cp == buf + 1) {
+                                       cp--;
+                                       continue;
+                               }

                                cp -= 2;
                                addch('\b');
                                c = ' ';
                                cp -= 2;
                                addch('\b');
                                c = ' ';

diff --git a/usr/src/games/gomoku/gomoku.h b/usr/src/games/gomoku/gomoku.h
index 569006a..5cebe0d 100644 (file)
--- a/usr/src/games/gomoku/gomoku.h
+++ b/usr/src/games/gomoku/gomoku.h
@@ -7,7 +7,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %sccs.include.redist.c%
  *

- *     @(#)gomoku.h    8.1 (Berkeley) %G%
+ *     @(#)gomoku.h    8.2 (Berkeley) %G%

  */
 
 #include <sys/types.h>
  */
 
 #include <sys/types.h>


@@ -113,9 +113,8 @@
 #define MAXA           6
 #define MAXB           2
 #define MAXCOMBO       0x600
 #define MAXA           6
 #define MAXB           2
 #define MAXCOMBO       0x600

-#define MAXDEPTH       5

 
 

-union  combo {
+union  comboval {

        struct {
 #if BYTE_ORDER == BIG_ENDIAN
                u_char  a;      /* # moves to complete force */
        struct {
 #if BYTE_ORDER == BIG_ENDIAN
                u_char  a;      /* # moves to complete force */


@@ -130,29 +129,52 @@ union     combo {
 };
 
 /*
 };
 
 /*

- * 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.
+ * 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 {
        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 */
+       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_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 */
+       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 s_flg */
-#define C_LOOP         0x01            /* link[1] intersects previous 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 {

-       struct elist    *e_next;        /* list of combos */
-       struct combostr *e_combo;       /* the combo */
-       struct combostr *e_frame;       /* the 1st level combo that connects */
+       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 */

 };
 
 /*
 };
 
 /*


@@ -164,12 +186,14 @@ struct    spotstr {
        short           s_occ;          /* color of occupant */
        short           s_wval;         /* weighted value */
        int             s_flg;          /* flags for graph walks */
        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 */
+       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 */
        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] */
+       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 */
 };
 
 /* flag values for s_flg */


@@ -184,15 +208,26 @@ struct    spotstr {
 #define BFLAG          0x010000        /* frame intersects border or dead */
 #define BFLAGALL       0x0F0000        /* all frames dead */
 
 #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    *letters;

-extern char    *color[];

 extern char    fmtbuf[];
 extern char    fmtbuf[];

+extern char    pdir[];

 
 extern int     dd[4];
 extern struct  spotstr board[BAREA];           /* info for board */
 
 extern int     dd[4];
 extern struct  spotstr board[BAREA];           /* info for board */

-extern struct  combostr frames[FAREA];         /* storage for all frames */
+extern struct  combostr frames[FAREA];         /* storage for single frames */

 extern struct  combostr *sortframes[2];        /* sorted, non-empty frames */
 extern struct  combostr *sortframes[2];        /* sorted, non-empty frames */

-extern char    overlap[FAREA * FAREA];         /* frame [a][b] overlap */
+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 short   intersect[FAREA * FAREA];       /* frame [a][b] intersection */
 extern int     movelog[BSZ * BSZ];             /* history of moves */
 extern int     movenum;

diff --git a/usr/src/games/gomoku/main.c b/usr/src/games/gomoku/main.c
index ca9b302..c374b1d 100644 (file)
--- a/usr/src/games/gomoku/main.c
+++ b/usr/src/games/gomoku/main.c
@@ -15,7 +15,7 @@ static char copyright[] =
 #endif /* not lint */
 
 #ifndef lint
 #endif /* not lint */
 
 #ifndef lint

-static char sccsid[] = "@(#)main.c     8.2 (Berkeley) %G%";
+static char sccsid[] = "@(#)main.c     8.3 (Berkeley) %G%";

 #endif /* not lint */
 
 #include <stdio.h>
 #endif /* not lint */
 
 #include <stdio.h>


@@ -38,19 +38,23 @@ char        *prog;                  /* name of program */
 FILE   *debugfp;               /* file for debug output */
 FILE   *inputfp;               /* file for debug input */
 
 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   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 */
+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 */
 
 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;
 main(argc, argv)
        int argc;
        char **argv;


@@ -58,7 +62,6 @@ main(argc, argv)
        char buf[128];
        int color, curmove, i, ch;
        int input[2];
        char buf[128];
        int color, curmove, i, ch;
        int input[2];

-       extern void whatsup(), quit();

        static char *fmt[2] = {
                "%3d %-6s",
                "%3d        %-6s"
        static char *fmt[2] = {
                "%3d %-6s",
                "%3d        %-6s"


@@ -95,7 +98,6 @@ main(argc, argv)
        if (argc) {
                if ((inputfp = fopen(*argv, "r")) == NULL)
                        err(1, "%s", *argv);
        if (argc) {
                if ((inputfp = fopen(*argv, "r")) == NULL)
                        err(1, "%s", *argv);

-               test = 3;

        }
 
        if (!debug)
        }
 
        if (!debug)


@@ -118,10 +120,10 @@ again:
                signal(SIGINT, quit);
 #endif
 
                signal(SIGINT, quit);
 #endif
 

-               if (test == 0) {
+               if (inputfp == NULL && test == 0) {

                        for (;;) {
                                ask("black or white? ");
                        for (;;) {
                                ask("black or white? ");

-                               getline(buf, sizeof buf);
+                               getline(buf, sizeof(buf));

                                if (buf[0] == 'b' || buf[0] == 'B') {
                                        color = BLACK;
                                        break;
                                if (buf[0] == 'b' || buf[0] == 'B') {
                                        color = BLACK;
                                        break;


@@ -138,7 +140,7 @@ again:
                }
        } else {
                setbuf(stdout, 0);
                }
        } else {
                setbuf(stdout, 0);

-               getline(buf, sizeof buf);
+               getline(buf, sizeof(buf));

                if (strcmp(buf, "black") == 0)
                        color = BLACK;
                else if (strcmp(buf, "white") == 0)
                if (strcmp(buf, "black") == 0)
                        color = BLACK;
                else if (strcmp(buf, "white") == 0)


@@ -151,25 +153,26 @@ again:
                }
        }
 
                }
        }
 

-       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 */
+       if (inputfp) {

                input[BLACK] = INPUTF;
                input[WHITE] = INPUTF;
                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;
        }
        if (interactive) {
                plyr[BLACK] = input[BLACK] == USER ? "you" : prog;


@@ -178,22 +181,38 @@ again:
        }
 
        for (color = BLACK; ; color = !color) {
        }
 
        for (color = BLACK; ; color = !color) {

+       top:

                switch (input[color]) {
                case INPUTF: /* input comes from a file */
                        curmove = readinput(inputfp);
                        if (curmove != ILLEGAL)
                                break;
                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";
+                       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);
                        bdwho(1);

-                       /* FALLTHROUGH */
+                       goto top;

 
                case USER: /* input comes from standard input */
                getinput:
                        if (interactive)
                                ask("move? ");
 
                case USER: /* input comes from standard input */
                getinput:
                        if (interactive)
                                ask("move? ");

-                       if (!getline(buf, sizeof buf)) {
+                       if (!getline(buf, sizeof(buf))) {

                                curmove = RESIGN;
                                break;
                        }
                                curmove = RESIGN;
                                break;
                        }


@@ -205,7 +224,7 @@ again:
                                        FILE *fp;
 
                                        ask("save file name? ");
                                        FILE *fp;
 
                                        ask("save file name? ");

-                                       (void)getline(buf, sizeof buf);
+                                       (void)getline(buf, sizeof(buf));

                                        if ((fp = fopen(buf, "w")) == NULL) {
                                                log("cannot create save file");
                                                goto getinput;
                                        if ((fp = fopen(buf, "w")) == NULL) {
                                                log("cannot create save file");
                                                goto getinput;


@@ -258,14 +277,14 @@ again:
                if (i != RESIGN) {
                replay:
                        ask("replay? ");
                if (i != RESIGN) {
                replay:
                        ask("replay? ");

-                       if (getline(buf, sizeof buf) &&
+                       if (getline(buf, sizeof(buf)) &&

                            buf[0] == 'y' || buf[0] == 'Y')
                                goto again;
                        if (strcmp(buf, "save") == 0) {
                                FILE *fp;
 
                                ask("save file name? ");
                            buf[0] == 'y' || buf[0] == 'Y')
                                goto again;
                        if (strcmp(buf, "save") == 0) {
                                FILE *fp;
 
                                ask("save file name? ");

-                               (void)getline(buf, sizeof buf);
+                               (void)getline(buf, sizeof(buf));

                                if ((fp = fopen(buf, "w")) == NULL) {
                                        log("cannot create save file");
                                        goto replay;
                                if ((fp = fopen(buf, "w")) == NULL) {
                                        log("cannot create save file");
                                        goto replay;


@@ -302,7 +321,7 @@ void
 whatsup(signum)
        int signum;
 {
 whatsup(signum)
        int signum;
 {

-       int i, pnum, n;
+       int i, pnum, n, s1, s2, d1, d2;

        struct spotstr *sp;
        FILE *fp;
        char *str;
        struct spotstr *sp;
        FILE *fp;
        char *str;


@@ -313,9 +332,11 @@ whatsup(signum)
                quit();
 top:
        ask("cmd? ");
                quit();
 top:
        ask("cmd? ");

-       if (!getline(fmtbuf, 128))
+       if (!getline(fmtbuf, sizeof(fmtbuf)))

                quit();
        switch (*fmtbuf) {
                quit();
        switch (*fmtbuf) {

+       case '\0':
+               goto top;

        case 'q':               /* conservative quit */
                quit();
        case 'd':               /* set debug level */
        case 'q':               /* conservative quit */
                quit();
        case 'd':               /* set debug level */


@@ -332,6 +353,12 @@ top:
                        bdisp();
                }
                goto top;
                        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++;
        case 'f':               /* go forward a move */
                board[movelog[movenum - 1]].s_occ = movenum & 1 ? BLACK : WHITE;
                movenum++;


@@ -355,6 +382,32 @@ top:
                bdump(fp);
                fclose(fp);
                goto top;
                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),
        case 'p':
                sp = &board[i = ctos(fmtbuf + 1)];
                sprintf(fmtbuf, "V %s %x/%d %d %x/%d %d %d %x", stoc(i),


@@ -372,31 +425,23 @@ top:
                        sp->s_fval[WHITE][2].s, sp->s_fval[WHITE][3].s);
                dlog(fmtbuf);
                goto top;
                        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);
+       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:
                }
                goto top;
        default:


@@ -420,7 +465,7 @@ dlog(str)
 
        if (debugfp)
                fprintf(debugfp, "%s\n", str);
 
        if (debugfp)
                fprintf(debugfp, "%s\n", str);

-       else if (interactive)
+       if (interactive)

                dislog(str);
        else
                fprintf(stderr, "%s\n", str);
                dislog(str);
        else
                fprintf(stderr, "%s\n", str);

diff --git a/usr/src/games/gomoku/makemove.c b/usr/src/games/gomoku/makemove.c
index 7082b26..a13cbfc 100644 (file)
--- a/usr/src/games/gomoku/makemove.c
+++ b/usr/src/games/gomoku/makemove.c
@@ -9,7 +9,7 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)makemove.c 8.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)makemove.c 8.2 (Berkeley) %G%";

 #endif /* not lint */
 
 #include "gomoku.h"
 #endif /* not lint */
 
 #include "gomoku.h"


@@ -33,10 +33,10 @@ makemove(us, mv)
        int us, mv;
 {
        register struct spotstr *sp, *fsp;
        int us, mv;
 {
        register struct spotstr *sp, *fsp;

-       register union combo *cp;
+       register union comboval *cp;

        struct spotstr *osp;
        struct combostr *cbp, *cbp1;
        struct spotstr *osp;
        struct combostr *cbp, *cbp1;

-       union combo *cp1;
+       union comboval *cp1;

        register int i, f, r, d, n;
        int space, val, bmask;
 
        register int i, f, r, d, n;
        int space, val, bmask;
 


@@ -178,5 +178,98 @@ makemove(us, mv)
            ;
        }
 
            ;
        }
 

+       update_overlap(osp);
+

        return(MOVEOK);
 }
        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/usr/src/games/gomoku/pickmove.c b/usr/src/games/gomoku/pickmove.c
index 3a996d5..16750c3 100644 (file)
--- a/usr/src/games/gomoku/pickmove.c
+++ b/usr/src/games/gomoku/pickmove.c
@@ -9,25 +9,39 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)pickmove.c 8.1 (Berkeley) %G%";
+static char sccsid[] = "@(#)pickmove.c 8.2 (Berkeley) %G%";

 #endif /* not lint */
 
 #include <stdio.h>
 #include <curses.h>
 #endif /* not lint */
 
 #include <stdio.h>
 #include <curses.h>

+#include <machine/limits.h>

 
 #include "gomoku.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 */
+#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)))

 
 

-extern char pdir[];
+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;
 
 pickmove(us)
        int us;
 {
        register struct spotstr *sp, *sp1, *sp2;

-       register union combo *Ocp, *Tcp;
+       register union comboval *Ocp, *Tcp;
+       char *str;
+       int i, j, m;

 
        /* first move is easy */
        if (movenum == 1)
 
        /* first move is easy */
        if (movenum == 1)


@@ -35,19 +49,16 @@ pickmove(us)
 
        /* initialize all the board values */
        for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
 
        /* 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_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);
        }
                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();
+       nforce = 0;
+       memset(forcemap, 0, sizeof(forcemap));

 
        /* compute new values */
        nextcolor = us;
 
        /* compute new values */
        nextcolor = us;


@@ -58,8 +69,8 @@ pickmove(us)
        for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
                if (sp->s_occ != EMPTY)
                        continue;
        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)) {
+               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],
                        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],


@@ -75,21 +86,30 @@ pickmove(us)
                if (better(sp, sp2, WHITE))
                        sp2 = sp;
        }
                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],
        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]);
+                       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],
                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]);
+                       sp2->s_nforce[BLACK], sp2->s_wval);

                dlog(fmtbuf);
                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];
        }
        if (us == BLACK) {
                Ocp = &sp1->s_combo[BLACK];


@@ -120,7 +140,7 @@ better(sp, sp1, us)
        struct spotstr *sp1;
        int us;
 {
        struct spotstr *sp1;
        int us;
 {

-       int them;
+       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 (1);


@@ -136,6 +156,12 @@ better(sp, sp1, us)
                return (0);
 
        them = !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)
        if (sp->s_combo[them].s < sp1->s_combo[them].s)
                return (1);
        if (sp->s_combo[them].s != sp1->s_combo[them].s)


@@ -161,21 +187,23 @@ better(sp, sp1, us)
 #endif
 }
 
 #endif
 }
 

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

 
 /*
 
 /*

- * Scan the sorted list of frames and update the minimum combo values.
+ * 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;
  */
 scanframes(color)
        int color;
 {
        register struct combostr *cbp, *ecbp;
        register struct spotstr *sp;

-       register union combo *cp;
-       register struct elist *ep;
+       register union comboval *cp;
+       register struct elist *ep, *nep;

        register int i, r, d, n;
        register int i, r, d, n;

-       union combo cb;
+       union comboval cb;

 
        curcolor = color;
 
 
        curcolor = color;
 


@@ -198,102 +226,191 @@ scanframes(color)
                return;
        }
 
                return;
        }
 

-       /* update the minimum combo value for each spot in the frame */
-       n = combolen[color];
+       /*
+        * 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) {
        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;
                        }
                        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);
+                       /*
+                        * Try combining other frames that intersect
+                        * at this spot.
+                        */
+                       makecombo2(cbp, sp, 0, cb.s);

                        if (cp->s != 0x101)
                                cb.s = cp->s;
                        if (cp->s != 0x101)
                                cb.s = cp->s;

+                       else if (color != nextcolor)
+                               memset(tmpmap, 0, sizeof(tmpmap));

                        sp += d;
                        sp += d;

-                       i = 4;
+                       i = 1;

                } else {
                        cb.s = cp->s;
                } else {
                        cb.s = cp->s;

-                       i = 5;
+                       i = 0;

                }
                }

-               for (; --i >= 0; sp += d) {     /* for each spot */
+               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 (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)
+                       if (cp->s == 0x101) {

                                sp->s_nforce[color]++;
                                sp->s_nforce[color]++;

-                       makecombo2(cbp, sp, cb.s);
+                               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);
 
                }
                /* 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. */
+       /*
+        * Try to make new 3rd level combos, 4th level, etc.
+        * Limit the search depth early in the game.
+        */

        d = 2;
        d = 2;

-       while (combolen[color] > n) {
+       while (d <= ((movenum + 1) >> 1) && combolen > n) {

                if (debug) {
                if (debug) {

-                       sprintf(fmtbuf, "%cL%d %d", "BW"[color], d,
-                               combolen[color] - n);
+                       sprintf(fmtbuf, "%cL%d %d %d %d", "BW"[color],
+                               d, combolen - n, combocnt, elistcnt);

                        dlog(fmtbuf);
                        refresh();
                }
                        dlog(fmtbuf);
                        refresh();
                }

-               n = combolen[color];
+               n = combolen;

                addframes(d);
                d++;
        }
 
        /* scan for combos at empty spots */
        for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
                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) {
+               for (ep = sp->s_empty; ep; ep = nep) {

                        cbp = ep->e_combo;
                        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;
+                       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'.
  */
 }
 
 /*
  * Compute all level 2 combos of frames intersecting spot 'osp'
  * within the frame 'ocbp' and combo value 's'.
  */

-makecombo2(ocbp, osp, s)
+makecombo2(ocbp, osp, off, s)

        struct combostr *ocbp;
        struct spotstr *osp;
        struct combostr *ocbp;
        struct spotstr *osp;

+       int off;

        int s;
 {
        register struct spotstr *sp, *fsp;
        int s;
 {
        register struct spotstr *sp, *fsp;

-       register struct combostr *cbp;
+       register struct combostr *ncbp;

        register int f, r, d, c;
        register int f, r, d, c;

-       int baseB, bmask, n;
-       union combo ocb, fcb;
+       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;
 
        /* 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 */
        for (r = 4; --r >= 0; ) {                       /* for each direction */

-           /* don't include frames that overlap ones already included */
+           /* don't include frames that overlap in the same direction */

            if (r == ocbp->c_dir)
                continue;
            d = dd[r];
            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;
            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.
-                */
+           for (f = 0; f < 5; f++, fsp -= d) {         /* for each frame */

                if (fsp->s_occ == BORDER)
                    break;
                if (fsp->s_flg & bmask)
                if (fsp->s_occ == BORDER)
                    break;
                if (fsp->s_flg & bmask)


@@ -309,79 +426,124 @@ makecombo2(ocbp, osp, s)
                 * If this is the end point of the frame,
                 * use the closed ended value for the 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) {
+               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;
                    fcb.c.a++;
                    fcb.c.b = 0;
                }
 
                /* compute combo value */
                c = fcb.c.a + ocb.c.a - 3;

-               if (c > 3)
+               if (c > 4)

                    continue;
                n = fcb.c.a + fcb.c.b - 1;
                if (baseB < n)
                    n = baseB;
 
                /* make a new combo! */
                    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;
+               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) {
 
                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);
+                   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);
                    dlog(fmtbuf);

-#ifdef DEBUG
-                   markcombo(cbp, curcolor, 0);
-                   bdisp();
-                   whatsup(0);
-                   clearcombo(cbp, curcolor, 0);
-#endif

                }
                if (c > 1) {
                }
                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);
+                   /* record the empty spots that will complete this combo */
+                   makeempty(ncbp);

 
                    /* add the new combo to the end of the list */
 
                    /* add the new combo to the end of the list */

-                   appendcombo(cbp, curcolor);
+                   appendcombo(ncbp, curcolor);

                } else {
                } else {

-                   updatecombo(cbp, curcolor);
-                   free(cbp);
+                   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 combine into combos.
+ * 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;
  */
 addframes(level)
        int level;
 {
        register struct combostr *cbp, *ecbp;
        register struct spotstr *sp, *fsp;

+       register struct elist *ep, *nep;

        register int i, r, d;
        register int i, r, d;

-       union combo fcb, cb;
+       struct combostr **cbpp, *pcbp;
+       union comboval fcb, cb;

 
        curlevel = level;
 
 
        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);
+       /* 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;
+       }

 
 

-       cbp = ecbp;
+       /* 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;
        do {
                fsp = &board[cbp->c_vertex];
                r = cbp->c_dir;


@@ -391,7 +553,7 @@ addframes(level)
 
                /*
                 * Don't include <1,x> combo frames,
 
                /*
                 * Don't include <1,x> combo frames,

-                * treat it as a blocked three in a row instead.
+                * treat it as a closed three in a row instead.

                 */
                fcb.s = fsp->s_fval[curcolor][r].s;
                if (fcb.s == 0x101)
                 */
                fcb.s = fsp->s_fval[curcolor][r].s;
                if (fcb.s == 0x101)


@@ -407,7 +569,7 @@ addframes(level)
                                cb.c.b = 0;
                        } else
                                cb.s = fcb.s;
                                cb.c.b = 0;
                        } else
                                cb.s = fcb.s;

-                       makecombo(cbp, fsp, cb.s);
+                       makecombo(cbp, fsp, 0, cb.s);

                }
 
                /*
                }
 
                /*


@@ -416,24 +578,42 @@ addframes(level)
                 */
                d = dd[r];
                sp = fsp + d;
                 */
                d = dd[r];
                sp = fsp + d;

-               for (i = 4; --i >= 0; sp += d) {
+               for (i = 1; i < 5; i++, sp += d) {

                        if (sp->s_occ != EMPTY)
                                continue;
                        if (sp->s_occ != EMPTY)
                                continue;

-                       makecombo(cbp, sp, fcb.s);
+                       makecombo(cbp, sp, i, fcb.s);

                }
                }

-
-               /* mark frame as having been processed */
-               fsp->s_flg |= MFLAG << r;

        } while ((cbp = cbp->c_next) != ecbp);
        } 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'.
  */
 }
 
 /*
  * Compute all level N combos of frames intersecting spot 'osp'
  * within the frame 'ocbp' and combo value 's'.
  */

-makecombo(ocbp, osp, s)
+makecombo(ocbp, osp, off, s)

        struct combostr *ocbp;
        struct spotstr *osp;
        struct combostr *ocbp;
        struct spotstr *osp;

+       int off;

        int s;
 {
        register struct combostr *cbp, *ncbp;
        int s;
 {
        register struct combostr *cbp, *ncbp;


@@ -441,199 +621,289 @@ makecombo(ocbp, osp, s)
        register struct elist *ep;
        register int n, c;
        struct elist *nep, **epp;
        register struct elist *ep;
        register int n, c;
        struct elist *nep, **epp;

-       struct combostr *fcbp;
-       int baseB, verts, d;
-       union combo ocb, cb;
+       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;
 
        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 */
+       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;
            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)
+           verts = checkframes(cbp, ocbp, osp, s, vertices);
+           if (verts < 0)

                continue;
 
            /* check to see if this frame forms a valid loop */
                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;
+           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
                }
 #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 */
                /* frame overlaps but not at a valid spot */

-               if (verts == 0 || ocb.c.a < 3)
-                   continue;
+               continue;
+           fnd:
+               ;

            }
 
            }
 

-           /* 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;
+           /* 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! */
            if (baseB < n)
                n = baseB;
 
            /* make a new combo! */

-           ncbp = (struct combostr *)malloc(sizeof(struct combostr));
-           c -= verts;
+           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_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_vertex = osp - board;
            ncbp->c_nframes = cbp->c_nframes + 1;

-           ncbp->c_refcnt = 0;
+           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) {
            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;
+               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 {
            } else {

-               ncbp->c_flg = 0;

                ncbp->c_dir = 0;
                ncbp->c_dir = 0;

-               if (ocb.c.a > 2)
-                   makeempty(ncbp, ocbp, ocb.c.b);
+               ncbp->c_framecnt[1] = fcnt;
+               ncbp->c_emask[1] = emask;
+               ncbp->c_voff[0] = ep->e_off;

            }
            }

-           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);
+           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);
                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]);
+               printcombo(ncbp, fmtbuf);

                dlog(fmtbuf);
                dlog(fmtbuf);

-#ifdef DEBUG
-               markcombo(ncbp, curcolor, 0);
-               bdisp();
-               whatsup(0);
-               clearcombo(ncbp, curcolor, 0);
-#endif

            }
            if (c > 1) {
            }
            if (c > 1) {

-               /* add the new combo to the end of the list */
-               appendcombo(ncbp, curcolor);
+               /* record the empty spots that will complete this combo */
+               makeempty(ncbp);
+               combolen++;

            } else {
            } else {

+               /* update board values */

                updatecombo(ncbp, curcolor);
                updatecombo(ncbp, curcolor);

-               free(ncbp);

            }
            }

+#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 '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.
+ * Add the combostr 'ocbp' to the empty spots list for each empty spot
+ * in 'ocbp' that will complete the combo.

  */
  */

-makeempty(cbp, fcbp, s)
-       struct combostr *cbp;
-       struct combostr *fcbp;
-       int s;
+makeempty(ocbp)
+       struct combostr *ocbp;

 {
 {

-       struct spotstr *sp, *vsp;
-       struct elist *ep, **epp;
-       int d;
+       struct combostr *cbp, *tcbp, **cbpp;
+       struct elist *ep, *nep, **epp;
+       struct spotstr *sp;
+       int s, d, m, emask, i;
+       int nframes;

 
        if (debug > 2) {
 
        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));
+               sprintf(fmtbuf, "E%c ", "bw"[curcolor]);
+               printcombo(ocbp, fmtbuf + 3);

                dlog(fmtbuf);
        }
                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));
+       /* 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;
                ep->e_combo = cbp;

-               ep->e_frame = fcbp;
-               if (debug > 2) {
-                       sprintf(fmtbuf, "e %s", stoc(sp - board));
-                       dlog(fmtbuf);
+               *--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 */
-               epp = &sp->s_empty[curcolor];
-               while (*epp) {
-                       if (cbp->c_nframes >= (*epp)->e_combo->c_nframes)
-                               break;
-                       epp = &(*epp)->e_next;
+                       /* sort by the number of frames in the combo */
+                       nep->e_next = sp->s_nempty;
+                       sp->s_nempty = nep;
+                       elistcnt++;

                }
                }

-               ep->e_next = *epp;
-               *epp = ep;

        }
 }
 
        }
 }
 


@@ -651,40 +921,47 @@ updatecombo(cbp, color)
        register struct spotstr *sp;
        register struct combostr *tcbp;
        register int i, d;
        register struct spotstr *sp;
        register struct combostr *tcbp;
        register int i, d;

-       int nframes, vertex;
-       union combo cb;
+       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]) {
 
        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 (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;
+                       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 */
                } 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;
+                       sp = &board[s = tcbp->c_vertex];

                        d = dd[tcbp->c_dir];
                        d = dd[tcbp->c_dir];

-                       cb.s = cbp->c_combo.s;
-                       nframes = cbp->c_nframes;
-                       for (; --i >= 0; sp += d) {
+                       i = (flg & C_OPEN_1) ? 6 : 5;
+                       for (; --i >= 0; sp += d, s += d) {
+                               if (sp->s_occ != EMPTY)
+                                       continue;

                                sp->s_nforce[color]++;
                                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;
+                               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);

                        }
                }
 
                        }
                }
 


@@ -694,74 +971,35 @@ updatecombo(cbp, color)
 
        if (color != nextcolor) {
                /* update the board values for each spot in frame */
 
        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;
+               sp = &board[s = cbp->c_vertex];

                d = dd[cbp->c_dir];
                d = dd[cbp->c_dir];

-               for (; --i >= 0; sp += d) {
+               i = (flg & C_OPEN_0) ? 6 : 5;
+               for (; --i >= 0; sp += d, s += d) {
+                       if (sp->s_occ != EMPTY)
+                               continue;

                        sp->s_nforce[color]++;
                        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;
+                       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;
 }
 
        }
 
        /* 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.
  */
 /*
  * Add combo to the end of the list.
  */


@@ -771,10 +1009,10 @@ appendcombo(cbp, color)
 {
        struct combostr *pcbp, *ncbp;
 
 {
        struct combostr *pcbp, *ncbp;
 

-       combolen[color]++;
-       ncbp = sortcombos[color];
+       combolen++;
+       ncbp = sortcombos;

        if (ncbp == (struct combostr *)0) {
        if (ncbp == (struct combostr *)0) {

-               sortcombos[color] = cbp;
+               sortcombos = cbp;

                cbp->c_next = cbp;
                cbp->c_prev = cbp;
                return;
                cbp->c_next = cbp;
                cbp->c_prev = cbp;
                return;


@@ -787,94 +1025,429 @@ appendcombo(cbp, color)
 }
 
 /*
 }
 
 /*

- * 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.
+ * 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, vertex, ecbp)
+checkframes(cbp, fcbp, osp, s, vertices)

        struct combostr *cbp;
        struct combostr *fcbp;
        struct combostr *cbp;
        struct combostr *fcbp;

-       int vertex;
-       struct combostr *ecbp;
+       struct spotstr *osp;
+       int s;
+       struct ovlp_info *vertices;

 {
 {

-       struct combostr *tcbp;
-       char *str;
-       int i, n, mask;
+       struct combostr *tcbp, *lcbp;
+       int i, n, mask, flg, verts, loop, index, fcnt;
+       union comboval cb;
+       u_char *str;

        short *ip;
 
        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];
        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))
+       /*
+        * 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);
                        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 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++;
+               }

        }
        }

-#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))));
+       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
 #ifdef DEBUG

-markcombo(cbp, color, vertex)
+               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;
        struct combostr *cbp;

-       int color;
-       int vertex;
+       char *str;

 {
 {

-       register struct spotstr *sp;

        struct combostr *tcbp;
        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;
+       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, color, vertex)
+clearcombo(cbp, open)

        struct combostr *cbp;
        struct combostr *cbp;

-       int color;
-       int vertex;
+       int open;

 {
        register struct spotstr *sp;
        struct combostr *tcbp;
 {
        register struct spotstr *sp;
        struct combostr *tcbp;

-       int i, d, r, n, mask;
+       int d, n, mask;

 
 

-       for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0])
-               clearcombo(tcbp, color, vertex = cbp->c_vertex);
+       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];
        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)
+       d = dd[n = cbp->c_dir];
+       mask = ~((IFLAG | CFLAG) << n);
+       n = open ? 6 : 5;
+       for (; --n >= 0; sp += d)

                sp->s_flg &= mask;
 }
                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 */
 #endif /* DEBUG */