gomoku/pickmove.c

   1 /*      $NetBSD: pickmove.c,v 1.20 2010/03/29 05:16:08 dholland Exp $   */
   2
   3 /*
   4  * Copyright (c) 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Ralph Campbell.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #ifndef lint
  37 #if 0
  38 static char sccsid[] = "@(#)pickmove.c  8.2 (Berkeley) 5/3/95";
  39 #else
  40 __RCSID("$NetBSD: pickmove.c,v 1.20 2010/03/29 05:16:08 dholland Exp $");
  41 #endif
  42 #endif /* not lint */
  43
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include <curses.h>
  47 #include <limits.h>
  48
  49 #include "gomoku.h"
  50
  51 #define BITS_PER_INT    (sizeof(int) * CHAR_BIT)
  52 #define MAPSZ           (BAREA / BITS_PER_INT)
  53
  54 #define BIT_SET(a, b)   ((a)[(b)/BITS_PER_INT] |= (1 << ((b) % BITS_PER_INT)))
  55 #define BIT_CLR(a, b)   ((a)[(b)/BITS_PER_INT] &= ~(1 << ((b) % BITS_PER_INT)))
  56 #define BIT_TEST(a, b)  ((a)[(b)/BITS_PER_INT] & (1 << ((b) % BITS_PER_INT)))
  57
  58 static struct combostr *hashcombos[FAREA];/* hash list for finding duplicates */
  59 static struct combostr *sortcombos;     /* combos at higher levels */
  60 static int combolen;                    /* number of combos in sortcombos */
  61 static int nextcolor;                   /* color of next move */
  62 static int elistcnt;                    /* count of struct elist allocated */
  63 static int combocnt;                    /* count of struct combostr allocated */
  64 static int forcemap[MAPSZ];             /* map for blocking <1,x> combos */
  65 static int tmpmap[MAPSZ];               /* map for blocking <1,x> combos */
  66 static int nforce;                      /* count of opponent <1,x> combos */
  67
  68 static int better(const struct spotstr *, const struct spotstr *, int);
  69 static void scanframes(int);
  70 static void makecombo2(struct combostr *, struct spotstr *, int, int);
  71 static void addframes(int);
  72 static void makecombo(struct combostr *, struct spotstr *, int, int);
  73 static void appendcombo(struct combostr *, int);
  74 static void updatecombo(struct combostr *, int);
  75 static void makeempty(struct combostr *);
  76 static int checkframes(struct combostr *, struct combostr *, struct spotstr *,
  77                     int, struct overlap_info *);
  78 static int sortcombo(struct combostr **, struct combostr **, struct combostr *);
  79 static void printcombo(struct combostr *, char *, size_t);
  80
  81 int
  82 pickmove(int us)
  83 {
  84         struct spotstr *sp, *sp1, *sp2;
  85         union comboval *Ocp, *Tcp;
  86         int m;
  87
  88         /* first move is easy */
  89         if (movenum == 1)
  90                 return (PT(K,10));
  91
  92         /* initialize all the board values */
  93         for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
  94                 sp->s_combo[BLACK].s = MAXCOMBO + 1;
  95                 sp->s_combo[WHITE].s = MAXCOMBO + 1;
  96                 sp->s_level[BLACK] = 255;
  97                 sp->s_level[WHITE] = 255;
  98                 sp->s_nforce[BLACK] = 0;
  99                 sp->s_nforce[WHITE] = 0;
 100                 sp->s_flags &= ~(FFLAGALL | MFLAGALL);
 101         }
 102         nforce = 0;
 103         memset(forcemap, 0, sizeof(forcemap));
 104
 105         /* compute new values */
 106         nextcolor = us;
 107         scanframes(BLACK);
 108         scanframes(WHITE);
 109
 110         /* find the spot with the highest value */
 111         for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
 112                 if (sp->s_occ != EMPTY)
 113                         continue;
 114                 if (debug && (sp->s_combo[BLACK].c.a == 1 ||
 115                     sp->s_combo[WHITE].c.a == 1)) {
 116                         debuglog("- %s %x/%d %d %x/%d %d %d", stoc(sp - board),
 117                                 sp->s_combo[BLACK].s, sp->s_level[BLACK],
 118                                 sp->s_nforce[BLACK],
 119                                 sp->s_combo[WHITE].s, sp->s_level[WHITE],
 120                                 sp->s_nforce[WHITE],
 121                                 sp->s_wval);
 122                 }
 123                 /* pick the best black move */
 124                 if (better(sp, sp1, BLACK))
 125                         sp1 = sp;
 126                 /* pick the best white move */
 127                 if (better(sp, sp2, WHITE))
 128                         sp2 = sp;
 129         }
 130
 131         if (debug) {
 132                 debuglog("B %s %x/%d %d %x/%d %d %d",
 133                         stoc(sp1 - board),
 134                         sp1->s_combo[BLACK].s, sp1->s_level[BLACK],
 135                         sp1->s_nforce[BLACK],
 136                         sp1->s_combo[WHITE].s, sp1->s_level[WHITE],
 137                         sp1->s_nforce[WHITE], sp1->s_wval);
 138                 debuglog("W %s %x/%d %d %x/%d %d %d",
 139                         stoc(sp2 - board),
 140                         sp2->s_combo[WHITE].s, sp2->s_level[WHITE],
 141                         sp2->s_nforce[WHITE],
 142                         sp2->s_combo[BLACK].s, sp2->s_level[BLACK],
 143                         sp2->s_nforce[BLACK], sp2->s_wval);
 144                 /*
 145                  * Check for more than one force that can't
 146                  * all be blocked with one move.
 147                  */
 148                 sp = (us == BLACK) ? sp2 : sp1;
 149                 m = sp - board;
 150                 if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m))
 151                         debuglog("*** Can't be blocked");
 152         }
 153         if (us == BLACK) {
 154                 Ocp = &sp1->s_combo[BLACK];
 155                 Tcp = &sp2->s_combo[WHITE];
 156         } else {
 157                 Tcp = &sp1->s_combo[BLACK];
 158                 Ocp = &sp2->s_combo[WHITE];
 159                 sp = sp1;
 160                 sp1 = sp2;
 161                 sp2 = sp;
 162         }
 163         /*
 164          * Block their combo only if we have to (i.e., if they are one move
 165          * away from completing a force and we don't have a force that
 166          * we can complete which takes fewer moves to win).
 167          */
 168         if (Tcp->c.a <= 1 && (Ocp->c.a > 1 ||
 169             Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b))
 170                 return (sp2 - board);
 171         return (sp1 - board);
 172 }
 173
 174 /*
 175  * Return true if spot 'sp' is better than spot 'sp1' for color 'us'.
 176  */
 177 static int
 178 better(const struct spotstr *sp, const struct spotstr *sp1, int us)
 179 {
 180         int them, s, s1;
 181
 182         if (sp->s_combo[us].s < sp1->s_combo[us].s)
 183                 return (1);
 184         if (sp->s_combo[us].s != sp1->s_combo[us].s)
 185                 return (0);
 186         if (sp->s_level[us] < sp1->s_level[us])
 187                 return (1);
 188         if (sp->s_level[us] != sp1->s_level[us])
 189                 return (0);
 190         if (sp->s_nforce[us] > sp1->s_nforce[us])
 191                 return (1);
 192         if (sp->s_nforce[us] != sp1->s_nforce[us])
 193                 return (0);
 194
 195         them = !us;
 196         s = sp - board;
 197         s1 = sp1 - board;
 198         if (BIT_TEST(forcemap, s) && !BIT_TEST(forcemap, s1))
 199                 return (1);
 200         if (!BIT_TEST(forcemap, s) && BIT_TEST(forcemap, s1))
 201                 return (0);
 202         if (sp->s_combo[them].s < sp1->s_combo[them].s)
 203                 return (1);
 204         if (sp->s_combo[them].s != sp1->s_combo[them].s)
 205                 return (0);
 206         if (sp->s_level[them] < sp1->s_level[them])
 207                 return (1);
 208         if (sp->s_level[them] != sp1->s_level[them])
 209                 return (0);
 210         if (sp->s_nforce[them] > sp1->s_nforce[them])
 211                 return (1);
 212         if (sp->s_nforce[them] != sp1->s_nforce[them])
 213                 return (0);
 214
 215         if (sp->s_wval > sp1->s_wval)
 216                 return (1);
 217         if (sp->s_wval != sp1->s_wval)
 218                 return (0);
 219
 220         return (random() & 1);
 221 }
 222
 223 static int curcolor;    /* implicit parameter to makecombo() */
 224 static int curlevel;    /* implicit parameter to makecombo() */
 225
 226 /*
 227  * Scan the sorted list of non-empty frames and
 228  * update the minimum combo values for each empty spot.
 229  * Also, try to combine frames to find more complex (chained) moves.
 230  */
 231 static void
 232 scanframes(int color)
 233 {
 234         struct combostr *cbp, *ecbp;
 235         struct spotstr *sp;
 236         union comboval *cp;
 237         struct elist *ep, *nep;
 238         int i, r, d, n;
 239         union comboval cb;
 240
 241         curcolor = color;
 242
 243         /* check for empty list of frames */
 244         cbp = sortframes[color];
 245         if (cbp == (struct combostr *)0)
 246                 return;
 247
 248         /* quick check for four in a row */
 249         sp = &board[cbp->c_vertex];
 250         cb.s = sp->s_fval[color][d = cbp->c_dir].s;
 251         if (cb.s < 0x101) {
 252                 d = dd[d];
 253                 for (i = 5 + cb.c.b; --i >= 0; sp += d) {
 254                         if (sp->s_occ != EMPTY)
 255                                 continue;
 256                         sp->s_combo[color].s = cb.s;
 257                         sp->s_level[color] = 1;
 258                 }
 259                 return;
 260         }
 261
 262         /*
 263          * Update the minimum combo value for each spot in the frame
 264          * and try making all combinations of two frames intersecting at
 265          * an empty spot.
 266          */
 267         n = combolen;
 268         ecbp = cbp;
 269         do {
 270                 sp = &board[cbp->c_vertex];
 271                 cp = &sp->s_fval[color][r = cbp->c_dir];
 272                 d = dd[r];
 273                 if (cp->c.b) {
 274                         /*
 275                          * Since this is the first spot of an open ended
 276                          * frame, we treat it as a closed frame.
 277                          */
 278                         cb.c.a = cp->c.a + 1;
 279                         cb.c.b = 0;
 280                         if (cb.s < sp->s_combo[color].s) {
 281                                 sp->s_combo[color].s = cb.s;
 282                                 sp->s_level[color] = 1;
 283                         }
 284                         /*
 285                          * Try combining other frames that intersect
 286                          * at this spot.
 287                          */
 288                         makecombo2(cbp, sp, 0, cb.s);
 289                         if (cp->s != 0x101)
 290                                 cb.s = cp->s;
 291                         else if (color != nextcolor)
 292                                 memset(tmpmap, 0, sizeof(tmpmap));
 293                         sp += d;
 294                         i = 1;
 295                 } else {
 296                         cb.s = cp->s;
 297                         i = 0;
 298                 }
 299                 for (; i < 5; i++, sp += d) {   /* for each spot */
 300                         if (sp->s_occ != EMPTY)
 301                                 continue;
 302                         if (cp->s < sp->s_combo[color].s) {
 303                                 sp->s_combo[color].s = cp->s;
 304                                 sp->s_level[color] = 1;
 305                         }
 306                         if (cp->s == 0x101) {
 307                                 sp->s_nforce[color]++;
 308                                 if (color != nextcolor) {
 309                                         n = sp - board;
 310                                         BIT_SET(tmpmap, n);
 311                                 }
 312                         }
 313                         /*
 314                          * Try combining other frames that intersect
 315                          * at this spot.
 316                          */
 317                         makecombo2(cbp, sp, i, cb.s);
 318                 }
 319                 if (cp->s == 0x101 && color != nextcolor) {
 320                         if (nforce == 0)
 321                                 memcpy(forcemap, tmpmap, sizeof(tmpmap));
 322                         else {
 323                                 for (i = 0; (unsigned int)i < MAPSZ; i++)
 324                                         forcemap[i] &= tmpmap[i];
 325                         }
 326                 }
 327                 /* mark frame as having been processed */
 328                 board[cbp->c_vertex].s_flags |= MFLAG << r;
 329         } while ((cbp = cbp->c_next) != ecbp);
 330
 331         /*
 332          * Try to make new 3rd level combos, 4th level, etc.
 333          * Limit the search depth early in the game.
 334          */
 335         d = 2;
 336         while (d <= ((movenum + 1) >> 1) && combolen > n) {
 337                 if (debug) {
 338                         debuglog("%cL%d %d %d %d", "BW"[color],
 339                                 d, combolen - n, combocnt, elistcnt);
 340                         refresh();
 341                 }
 342                 n = combolen;
 343                 addframes(d);
 344                 d++;
 345         }
 346
 347         /* scan for combos at empty spots */
 348         for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
 349                 for (ep = sp->s_empty; ep; ep = nep) {
 350                         cbp = ep->e_combo;
 351                         if (cbp->c_combo.s <= sp->s_combo[color].s) {
 352                                 if (cbp->c_combo.s != sp->s_combo[color].s) {
 353                                         sp->s_combo[color].s = cbp->c_combo.s;
 354                                         sp->s_level[color] = cbp->c_nframes;
 355                                 } else if (cbp->c_nframes < sp->s_level[color])
 356                                         sp->s_level[color] = cbp->c_nframes;
 357                         }
 358                         nep = ep->e_next;
 359                         free(ep);
 360                         elistcnt--;
 361                 }
 362                 sp->s_empty = (struct elist *)0;
 363                 for (ep = sp->s_nempty; ep; ep = nep) {
 364                         cbp = ep->e_combo;
 365                         if (cbp->c_combo.s <= sp->s_combo[color].s) {
 366                                 if (cbp->c_combo.s != sp->s_combo[color].s) {
 367                                         sp->s_combo[color].s = cbp->c_combo.s;
 368                                         sp->s_level[color] = cbp->c_nframes;
 369                                 } else if (cbp->c_nframes < sp->s_level[color])
 370                                         sp->s_level[color] = cbp->c_nframes;
 371                         }
 372                         nep = ep->e_next;
 373                         free(ep);
 374                         elistcnt--;
 375                 }
 376                 sp->s_nempty = (struct elist *)0;
 377         }
 378
 379         /* remove old combos */
 380         if ((cbp = sortcombos) != (struct combostr *)0) {
 381                 struct combostr *ncbp;
 382
 383                 /* scan the list */
 384                 ecbp = cbp;
 385                 do {
 386                         ncbp = cbp->c_next;
 387                         free(cbp);
 388                         combocnt--;
 389                 } while ((cbp = ncbp) != ecbp);
 390                 sortcombos = (struct combostr *)0;
 391         }
 392         combolen = 0;
 393
 394 #ifdef DEBUG
 395         if (combocnt) {
 396                 debuglog("scanframes: %c combocnt %d", "BW"[color],
 397                         combocnt);
 398                 whatsup(0);
 399         }
 400         if (elistcnt) {
 401                 debuglog("scanframes: %c elistcnt %d", "BW"[color],
 402                         elistcnt);
 403                 whatsup(0);
 404         }
 405 #endif
 406 }
 407
 408 /*
 409  * Compute all level 2 combos of frames intersecting spot 'osp'
 410  * within the frame 'ocbp' and combo value 's'.
 411  */
 412 static void
 413 makecombo2(struct combostr *ocbp, struct spotstr *osp, int off, int s)
 414 {
 415         struct spotstr *fsp;
 416         struct combostr *ncbp;
 417         int f, r, d, c;
 418         int baseB, fcnt, emask, bmask, n;
 419         union comboval ocb, fcb;
 420         struct combostr **scbpp, *fcbp;
 421         char tmp[128];
 422
 423         /* try to combine a new frame with those found so far */
 424         ocb.s = s;
 425         baseB = ocb.c.a + ocb.c.b - 1;
 426         fcnt = ocb.c.a - 2;
 427         emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
 428         for (r = 4; --r >= 0; ) {                       /* for each direction */
 429             /* don't include frames that overlap in the same direction */
 430             if (r == ocbp->c_dir)
 431                 continue;
 432             d = dd[r];
 433             /*
 434              * Frame A combined with B is the same value as B combined with A
 435              * so skip frames that have already been processed (MFLAG).
 436              * Also skip blocked frames (BFLAG) and frames that are <1,x>
 437              * since combining another frame with it isn't valid.
 438              */
 439             bmask = (BFLAG | FFLAG | MFLAG) << r;
 440             fsp = osp;
 441             for (f = 0; f < 5; f++, fsp -= d) {         /* for each frame */
 442                 if (fsp->s_occ == BORDER)
 443                     break;
 444                 if (fsp->s_flags & bmask)
 445                     continue;
 446
 447                 /* don't include frames of the wrong color */
 448                 fcb.s = fsp->s_fval[curcolor][r].s;
 449                 if (fcb.c.a >= MAXA)
 450                     continue;
 451
 452                 /*
 453                  * Get the combo value for this frame.
 454                  * If this is the end point of the frame,
 455                  * use the closed ended value for the frame.
 456                  */
 457                 if ((f == 0 && fcb.c.b) || fcb.s == 0x101) {
 458                     fcb.c.a++;
 459                     fcb.c.b = 0;
 460                 }
 461
 462                 /* compute combo value */
 463                 c = fcb.c.a + ocb.c.a - 3;
 464                 if (c > 4)
 465                     continue;
 466                 n = fcb.c.a + fcb.c.b - 1;
 467                 if (baseB < n)
 468                     n = baseB;
 469
 470                 /* make a new combo! */
 471                 ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
 472                     2 * sizeof(struct combostr *));
 473                 if (ncbp == NULL)
 474                     panic("Out of memory!");
 475                 scbpp = (struct combostr **)(ncbp + 1);
 476                 fcbp = fsp->s_frame[r];
 477                 if (ocbp < fcbp) {
 478                     scbpp[0] = ocbp;
 479                     scbpp[1] = fcbp;
 480                 } else {
 481                     scbpp[0] = fcbp;
 482                     scbpp[1] = ocbp;
 483                 }
 484                 ncbp->c_combo.c.a = c;
 485                 ncbp->c_combo.c.b = n;
 486                 ncbp->c_link[0] = ocbp;
 487                 ncbp->c_link[1] = fcbp;
 488                 ncbp->c_linkv[0].s = ocb.s;
 489                 ncbp->c_linkv[1].s = fcb.s;
 490                 ncbp->c_voff[0] = off;
 491                 ncbp->c_voff[1] = f;
 492                 ncbp->c_vertex = osp - board;
 493                 ncbp->c_nframes = 2;
 494                 ncbp->c_dir = 0;
 495                 ncbp->c_frameindex = 0;
 496                 ncbp->c_flags = (ocb.c.b) ? C_OPEN_0 : 0;
 497                 if (fcb.c.b)
 498                     ncbp->c_flags |= C_OPEN_1;
 499                 ncbp->c_framecnt[0] = fcnt;
 500                 ncbp->c_emask[0] = emask;
 501                 ncbp->c_framecnt[1] = fcb.c.a - 2;
 502                 ncbp->c_emask[1] = ncbp->c_framecnt[1] ?
 503                     ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0;
 504                 combocnt++;
 505
 506                 if ((c == 1 && debug > 1) || debug > 3) {
 507                     debuglog("%c c %d %d m %x %x o %d %d",
 508                         "bw"[curcolor],
 509                         ncbp->c_framecnt[0], ncbp->c_framecnt[1],
 510                         ncbp->c_emask[0], ncbp->c_emask[1],
 511                         ncbp->c_voff[0], ncbp->c_voff[1]);
 512                     printcombo(ncbp, tmp, sizeof(tmp));
 513                     debuglog("%s", tmp);
 514                 }
 515                 if (c > 1) {
 516                     /* record the empty spots that will complete this combo */
 517                     makeempty(ncbp);
 518
 519                     /* add the new combo to the end of the list */
 520                     appendcombo(ncbp, curcolor);
 521                 } else {
 522                     updatecombo(ncbp, curcolor);
 523                     free(ncbp);
 524                     combocnt--;
 525                 }
 526 #ifdef DEBUG
 527                 if ((c == 1 && debug > 1) || debug > 5) {
 528                     markcombo(ncbp);
 529                     bdisp();
 530                     whatsup(0);
 531                     clearcombo(ncbp, 0);
 532                 }
 533 #endif /* DEBUG */
 534             }
 535         }
 536 }
 537
 538 /*
 539  * Scan the sorted list of frames and try to add a frame to
 540  * combinations of 'level' number of frames.
 541  */
 542 static void
 543 addframes(int level)
 544 {
 545         struct combostr *cbp, *ecbp;
 546         struct spotstr *sp, *fsp;
 547         struct elist *ep, *nep;
 548         int i, r, d;
 549         struct combostr **cbpp, *pcbp;
 550         union comboval fcb, cb;
 551
 552         curlevel = level;
 553
 554         /* scan for combos at empty spots */
 555         i = curcolor;
 556         for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
 557                 for (ep = sp->s_empty; ep; ep = nep) {
 558                         cbp = ep->e_combo;
 559                         if (cbp->c_combo.s <= sp->s_combo[i].s) {
 560                                 if (cbp->c_combo.s != sp->s_combo[i].s) {
 561                                         sp->s_combo[i].s = cbp->c_combo.s;
 562                                         sp->s_level[i] = cbp->c_nframes;
 563                                 } else if (cbp->c_nframes < sp->s_level[i])
 564                                         sp->s_level[i] = cbp->c_nframes;
 565                         }
 566                         nep = ep->e_next;
 567                         free(ep);
 568                         elistcnt--;
 569                 }
 570                 sp->s_empty = sp->s_nempty;
 571                 sp->s_nempty = (struct elist *)0;
 572         }
 573
 574         /* try to add frames to the uncompleted combos at level curlevel */
 575         cbp = ecbp = sortframes[curcolor];
 576         do {
 577                 fsp = &board[cbp->c_vertex];
 578                 r = cbp->c_dir;
 579                 /* skip frames that are part of a <1,x> combo */
 580                 if (fsp->s_flags & (FFLAG << r))
 581                         continue;
 582
 583                 /*
 584                  * Don't include <1,x> combo frames,
 585                  * treat it as a closed three in a row instead.
 586                  */
 587                 fcb.s = fsp->s_fval[curcolor][r].s;
 588                 if (fcb.s == 0x101)
 589                         fcb.s = 0x200;
 590
 591                 /*
 592                  * If this is an open ended frame, use
 593                  * the combo value with the end closed.
 594                  */
 595                 if (fsp->s_occ == EMPTY) {
 596                         if (fcb.c.b) {
 597                                 cb.c.a = fcb.c.a + 1;
 598                                 cb.c.b = 0;
 599                         } else
 600                                 cb.s = fcb.s;
 601                         makecombo(cbp, fsp, 0, cb.s);
 602                 }
 603
 604                 /*
 605                  * The next four spots are handled the same for both
 606                  * open and closed ended frames.
 607                  */
 608                 d = dd[r];
 609                 sp = fsp + d;
 610                 for (i = 1; i < 5; i++, sp += d) {
 611                         if (sp->s_occ != EMPTY)
 612                                 continue;
 613                         makecombo(cbp, sp, i, fcb.s);
 614                 }
 615         } while ((cbp = cbp->c_next) != ecbp);
 616
 617         /* put all the combos in the hash list on the sorted list */
 618         cbpp = &hashcombos[FAREA];
 619         do {
 620                 cbp = *--cbpp;
 621                 if (cbp == (struct combostr *)0)
 622                         continue;
 623                 *cbpp = (struct combostr *)0;
 624                 ecbp = sortcombos;
 625                 if (ecbp == (struct combostr *)0)
 626                         sortcombos = cbp;
 627                 else {
 628                         /* append to sort list */
 629                         pcbp = ecbp->c_prev;
 630                         pcbp->c_next = cbp;
 631                         ecbp->c_prev = cbp->c_prev;
 632                         cbp->c_prev->c_next = ecbp;
 633                         cbp->c_prev = pcbp;
 634                 }
 635         } while (cbpp != hashcombos);
 636 }
 637
 638 /*
 639  * Compute all level N combos of frames intersecting spot 'osp'
 640  * within the frame 'ocbp' and combo value 's'.
 641  */
 642 static void
 643 makecombo(struct combostr *ocbp, struct spotstr *osp, int off, int s)
 644 {
 645         struct combostr *cbp, *ncbp;
 646         struct spotstr *sp;
 647         struct elist *ep;
 648         int n, c;
 649         struct elist *nep;
 650         struct combostr **scbpp;
 651         int baseB, fcnt, emask, verts;
 652         union comboval ocb;
 653         struct overlap_info vertices[1];
 654         char tmp[128];
 655
 656         /*
 657          * XXX: when I made functions static gcc started warning about
 658          * some members of vertices[0] maybe being used uninitialized.
 659          * For now I'm just going to clear it rather than wade through
 660          * the logic to find out whether gcc or the code is wrong. I
 661          * wouldn't be surprised if it were the code though. - dholland
 662          */
 663         memset(vertices, 0, sizeof(vertices));
 664
 665         ocb.s = s;
 666         baseB = ocb.c.a + ocb.c.b - 1;
 667         fcnt = ocb.c.a - 2;
 668         emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
 669         for (ep = osp->s_empty; ep; ep = ep->e_next) {
 670             /* check for various kinds of overlap */
 671             cbp = ep->e_combo;
 672             verts = checkframes(cbp, ocbp, osp, s, vertices);
 673             if (verts < 0)
 674                 continue;
 675
 676             /* check to see if this frame forms a valid loop */
 677             if (verts) {
 678                 sp = &board[vertices[0].o_intersect];
 679 #ifdef DEBUG
 680                 if (sp->s_occ != EMPTY) {
 681                     debuglog("loop: %c %s", "BW"[curcolor],
 682                         stoc(sp - board));
 683                     whatsup(0);
 684                 }
 685 #endif
 686                 /*
 687                  * It is a valid loop if the intersection spot
 688                  * of the frame we are trying to attach is one
 689                  * of the completion spots of the combostr
 690                  * we are trying to attach the frame to.
 691                  */
 692                 for (nep = sp->s_empty; nep; nep = nep->e_next) {
 693                     if (nep->e_combo == cbp)
 694                         goto fnd;
 695                     if (nep->e_combo->c_nframes < cbp->c_nframes)
 696                         break;
 697                 }
 698                 /* frame overlaps but not at a valid spot */
 699                 continue;
 700             fnd:
 701                 ;
 702             }
 703
 704             /* compute the first half of the combo value */
 705             c = cbp->c_combo.c.a + ocb.c.a - verts - 3;
 706             if (c > 4)
 707                 continue;
 708
 709             /* compute the second half of the combo value */
 710             n = ep->e_fval.c.a + ep->e_fval.c.b - 1;
 711             if (baseB < n)
 712                 n = baseB;
 713
 714             /* make a new combo! */
 715             ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
 716                 (cbp->c_nframes + 1) * sizeof(struct combostr *));
 717             if (ncbp == NULL)
 718                 panic("Out of memory!");
 719             scbpp = (struct combostr **)(ncbp + 1);
 720             if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) {
 721                 free(ncbp);
 722                 continue;
 723             }
 724             combocnt++;
 725
 726             ncbp->c_combo.c.a = c;
 727             ncbp->c_combo.c.b = n;
 728             ncbp->c_link[0] = cbp;
 729             ncbp->c_link[1] = ocbp;
 730             ncbp->c_linkv[1].s = ocb.s;
 731             ncbp->c_voff[1] = off;
 732             ncbp->c_vertex = osp - board;
 733             ncbp->c_nframes = cbp->c_nframes + 1;
 734             ncbp->c_flags = ocb.c.b ? C_OPEN_1 : 0;
 735             ncbp->c_frameindex = ep->e_frameindex;
 736             /*
 737              * Update the completion spot mask of the frame we
 738              * are attaching 'ocbp' to so the intersection isn't
 739              * listed twice.
 740              */
 741             ncbp->c_framecnt[0] = ep->e_framecnt;
 742             ncbp->c_emask[0] = ep->e_emask;
 743             if (verts) {
 744                 ncbp->c_flags |= C_LOOP;
 745                 ncbp->c_dir = vertices[0].o_frameindex;
 746                 ncbp->c_framecnt[1] = fcnt - 1;
 747                 if (ncbp->c_framecnt[1]) {
 748                     n = (vertices[0].o_intersect - ocbp->c_vertex) /
 749                         dd[ocbp->c_dir];
 750                     ncbp->c_emask[1] = emask & ~(1 << n);
 751                 } else
 752                     ncbp->c_emask[1] = 0;
 753                 ncbp->c_voff[0] = vertices[0].o_off;
 754             } else {
 755                 ncbp->c_dir = 0;
 756                 ncbp->c_framecnt[1] = fcnt;
 757                 ncbp->c_emask[1] = emask;
 758                 ncbp->c_voff[0] = ep->e_off;
 759             }
 760
 761             if ((c == 1 && debug > 1) || debug > 3) {
 762                 debuglog("%c v%d i%d d%d c %d %d m %x %x o %d %d",
 763                     "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir,
 764                     ncbp->c_framecnt[0], ncbp->c_framecnt[1],
 765                     ncbp->c_emask[0], ncbp->c_emask[1],
 766                     ncbp->c_voff[0], ncbp->c_voff[1]);
 767                 printcombo(ncbp, tmp, sizeof(tmp));
 768                 debuglog("%s", tmp);
 769             }
 770             if (c > 1) {
 771                 /* record the empty spots that will complete this combo */
 772                 makeempty(ncbp);
 773                 combolen++;
 774             } else {
 775                 /* update board values */
 776                 updatecombo(ncbp, curcolor);
 777             }
 778 #ifdef DEBUG
 779             if ((c == 1 && debug > 1) || debug > 4) {
 780                 markcombo(ncbp);
 781                 bdisp();
 782                 whatsup(0);
 783                 clearcombo(ncbp, 0);
 784             }
 785 #endif /* DEBUG */
 786         }
 787 }
 788
 789 #define MAXDEPTH        100
 790 static struct elist einfo[MAXDEPTH];
 791 static struct combostr *ecombo[MAXDEPTH];       /* separate from elist to save space */
 792
 793 /*
 794  * Add the combostr 'ocbp' to the empty spots list for each empty spot
 795  * in 'ocbp' that will complete the combo.
 796  */
 797 static void
 798 makeempty(struct combostr *ocbp)
 799 {
 800         struct combostr *cbp, *tcbp, **cbpp;
 801         struct elist *ep, *nep;
 802         struct spotstr *sp;
 803         int s, d, m, emask, i;
 804         int nframes;
 805         char tmp[128];
 806
 807         if (debug > 2) {
 808                 printcombo(ocbp, tmp, sizeof(tmp));
 809                 debuglog("E%c %s", "bw"[curcolor], tmp);
 810         }
 811
 812         /* should never happen but check anyway */
 813         if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
 814                 return;
 815
 816         /*
 817          * The lower level combo can be pointed to by more than one
 818          * higher level 'struct combostr' so we can't modify the
 819          * lower level. Therefore, higher level combos store the
 820          * real mask of the lower level frame in c_emask[0] and the
 821          * frame number in c_frameindex.
 822          *
 823          * First we traverse the tree from top to bottom and save the
 824          * connection info. Then we traverse the tree from bottom to
 825          * top overwriting lower levels with the newer emask information.
 826          */
 827         ep = &einfo[nframes];
 828         cbpp = &ecombo[nframes];
 829         for (cbp = ocbp; (tcbp = cbp->c_link[1]) != NULL;
 830             cbp = cbp->c_link[0]) {
 831                 ep--;
 832                 ep->e_combo = cbp;
 833                 *--cbpp = cbp->c_link[1];
 834                 ep->e_off = cbp->c_voff[1];
 835                 ep->e_frameindex = cbp->c_frameindex;
 836                 ep->e_fval.s = cbp->c_linkv[1].s;
 837                 ep->e_framecnt = cbp->c_framecnt[1];
 838                 ep->e_emask = cbp->c_emask[1];
 839         }
 840         cbp = ep->e_combo;
 841         ep--;
 842         ep->e_combo = cbp;
 843         *--cbpp = cbp->c_link[0];
 844         ep->e_off = cbp->c_voff[0];
 845         ep->e_frameindex = 0;
 846         ep->e_fval.s = cbp->c_linkv[0].s;
 847         ep->e_framecnt = cbp->c_framecnt[0];
 848         ep->e_emask = cbp->c_emask[0];
 849
 850         /* now update the emask info */
 851         s = 0;
 852         for (i = 2, ep += 2; i < nframes; i++, ep++) {
 853                 cbp = ep->e_combo;
 854                 nep = &einfo[ep->e_frameindex];
 855                 nep->e_framecnt = cbp->c_framecnt[0];
 856                 nep->e_emask = cbp->c_emask[0];
 857
 858                 if (cbp->c_flags & C_LOOP) {
 859                         s++;
 860                         /*
 861                          * Account for the fact that this frame connects
 862                          * to a previous one (thus forming a loop).
 863                          */
 864                         nep = &einfo[cbp->c_dir];
 865                         if (--nep->e_framecnt)
 866                                 nep->e_emask &= ~(1 << cbp->c_voff[0]);
 867                         else
 868                                 nep->e_emask = 0;
 869                 }
 870         }
 871
 872         /*
 873          * We only need to update the emask values of "complete" loops
 874          * to include the intersection spots.
 875          */
 876         if (s && ocbp->c_combo.c.a == 2) {
 877                 /* process loops from the top down */
 878                 ep = &einfo[nframes];
 879                 do {
 880                         ep--;
 881                         cbp = ep->e_combo;
 882                         if (!(cbp->c_flags & C_LOOP))
 883                                 continue;
 884
 885                         /*
 886                          * Update the emask values to include the
 887                          * intersection spots.
 888                          */
 889                         nep = &einfo[cbp->c_dir];
 890                         nep->e_framecnt = 1;
 891                         nep->e_emask = 1 << cbp->c_voff[0];
 892                         ep->e_framecnt = 1;
 893                         ep->e_emask = 1 << ep->e_off;
 894                         ep = &einfo[ep->e_frameindex];
 895                         do {
 896                                 ep->e_framecnt = 1;
 897                                 ep->e_emask = 1 << ep->e_off;
 898                                 ep = &einfo[ep->e_frameindex];
 899                         } while (ep > nep);
 900                 } while (ep != einfo);
 901         }
 902
 903         /* check all the frames for completion spots */
 904         for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
 905                 /* skip this frame if there are no incomplete spots in it */
 906                 if ((emask = ep->e_emask) == 0)
 907                         continue;
 908                 cbp = *cbpp;
 909                 sp = &board[cbp->c_vertex];
 910                 d = dd[cbp->c_dir];
 911                 for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) {
 912                         if (sp->s_occ != EMPTY || !(emask & m))
 913                                 continue;
 914
 915                         /* add the combo to the list of empty spots */
 916                         nep = (struct elist *)malloc(sizeof(struct elist));
 917                         if (nep == NULL)
 918                             panic("Out of memory!");
 919                         nep->e_combo = ocbp;
 920                         nep->e_off = s;
 921                         nep->e_frameindex = i;
 922                         if (ep->e_framecnt > 1) {
 923                                 nep->e_framecnt = ep->e_framecnt - 1;
 924                                 nep->e_emask = emask & ~m;
 925                         } else {
 926                                 nep->e_framecnt = 0;
 927                                 nep->e_emask = 0;
 928                         }
 929                         nep->e_fval.s = ep->e_fval.s;
 930                         if (debug > 2) {
 931                                 debuglog("e %s o%d i%d c%d m%x %x",
 932                                         stoc(sp - board),
 933                                         nep->e_off,
 934                                         nep->e_frameindex,
 935                                         nep->e_framecnt,
 936                                         nep->e_emask,
 937                                         nep->e_fval.s);
 938                         }
 939
 940                         /* sort by the number of frames in the combo */
 941                         nep->e_next = sp->s_nempty;
 942                         sp->s_nempty = nep;
 943                         elistcnt++;
 944                 }
 945         }
 946 }
 947
 948 /*
 949  * Update the board value based on the combostr.
 950  * This is called only if 'cbp' is a <1,x> combo.
 951  * We handle things differently depending on whether the next move
 952  * would be trying to "complete" the combo or trying to block it.
 953  */
 954 static void
 955 updatecombo(struct combostr *cbp, int color)
 956 {
 957         struct spotstr *sp;
 958         struct combostr *tcbp;
 959         int i, d;
 960         int nframes, flags, s;
 961         union comboval cb;
 962
 963         flags = 0;
 964         /* save the top level value for the whole combo */
 965         cb.c.a = cbp->c_combo.c.a;
 966         nframes = cbp->c_nframes;
 967
 968         if (color != nextcolor)
 969                 memset(tmpmap, 0, sizeof(tmpmap));
 970
 971         for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
 972                 flags = cbp->c_flags;
 973                 cb.c.b = cbp->c_combo.c.b;
 974                 if (color == nextcolor) {
 975                         /* update the board value for the vertex */
 976                         sp = &board[cbp->c_vertex];
 977                         sp->s_nforce[color]++;
 978                         if (cb.s <= sp->s_combo[color].s) {
 979                                 if (cb.s != sp->s_combo[color].s) {
 980                                         sp->s_combo[color].s = cb.s;
 981                                         sp->s_level[color] = nframes;
 982                                 } else if (nframes < sp->s_level[color])
 983                                         sp->s_level[color] = nframes;
 984                         }
 985                 } else {
 986                         /* update the board values for each spot in frame */
 987                         sp = &board[s = tcbp->c_vertex];
 988                         d = dd[tcbp->c_dir];
 989                         i = (flags & C_OPEN_1) ? 6 : 5;
 990                         for (; --i >= 0; sp += d, s += d) {
 991                                 if (sp->s_occ != EMPTY)
 992                                         continue;
 993                                 sp->s_nforce[color]++;
 994                                 if (cb.s <= sp->s_combo[color].s) {
 995                                         if (cb.s != sp->s_combo[color].s) {
 996                                                 sp->s_combo[color].s = cb.s;
 997                                                 sp->s_level[color] = nframes;
 998                                         } else if (nframes < sp->s_level[color])
 999                                                 sp->s_level[color] = nframes;
1000                                 }
1001                                 BIT_SET(tmpmap, s);
1002                         }
1003                 }
1004
1005                 /* mark the frame as being part of a <1,x> combo */
1006                 board[tcbp->c_vertex].s_flags |= FFLAG << tcbp->c_dir;
1007         }
1008
1009         if (color != nextcolor) {
1010                 /* update the board values for each spot in frame */
1011                 sp = &board[s = cbp->c_vertex];
1012                 d = dd[cbp->c_dir];
1013                 i = (flags & C_OPEN_0) ? 6 : 5;
1014                 for (; --i >= 0; sp += d, s += d) {
1015                         if (sp->s_occ != EMPTY)
1016                                 continue;
1017                         sp->s_nforce[color]++;
1018                         if (cb.s <= sp->s_combo[color].s) {
1019                                 if (cb.s != sp->s_combo[color].s) {
1020                                         sp->s_combo[color].s = cb.s;
1021                                         sp->s_level[color] = nframes;
1022                                 } else if (nframes < sp->s_level[color])
1023                                         sp->s_level[color] = nframes;
1024                         }
1025                         BIT_SET(tmpmap, s);
1026                 }
1027                 if (nforce == 0)
1028                         memcpy(forcemap, tmpmap, sizeof(tmpmap));
1029                 else {
1030                         for (i = 0; (unsigned int)i < MAPSZ; i++)
1031                                 forcemap[i] &= tmpmap[i];
1032                 }
1033                 nforce++;
1034         }
1035
1036         /* mark the frame as being part of a <1,x> combo */
1037         board[cbp->c_vertex].s_flags |= FFLAG << cbp->c_dir;
1038 }
1039
1040 /*
1041  * Add combo to the end of the list.
1042  */
1043 static void
1044 appendcombo(struct combostr *cbp, int color __unused)
1045 {
1046         struct combostr *pcbp, *ncbp;
1047
1048         combolen++;
1049         ncbp = sortcombos;
1050         if (ncbp == (struct combostr *)0) {
1051                 sortcombos = cbp;
1052                 cbp->c_next = cbp;
1053                 cbp->c_prev = cbp;
1054                 return;
1055         }
1056         pcbp = ncbp->c_prev;
1057         cbp->c_next = ncbp;
1058         cbp->c_prev = pcbp;
1059         ncbp->c_prev = cbp;
1060         pcbp->c_next = cbp;
1061 }
1062
1063 /*
1064  * Return zero if it is valid to combine frame 'fcbp' with the frames
1065  * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops).
1066  * Return positive if combining frame 'fcbp' to the frames in 'cbp'
1067  * would form some kind of valid loop. Also return the intersection spots
1068  * in 'vertices[]' beside the known intersection at spot 'osp'.
1069  * Return -1 if 'fcbp' should not be combined with 'cbp'.
1070  * 's' is the combo value for frame 'fcpb'.
1071  */
1072 static int
1073 checkframes(struct combostr *cbp, struct combostr *fcbp, struct spotstr *osp,
1074             int s, struct overlap_info *vertices)
1075 {
1076         struct combostr *tcbp, *lcbp;
1077         int i, n, mask, flags, verts, loop, myindex, fcnt;
1078         union comboval cb;
1079         u_char *str;
1080         short *ip;
1081
1082         lcbp = NULL;
1083         flags = 0;
1084
1085         cb.s = s;
1086         fcnt = cb.c.a - 2;
1087         verts = 0;
1088         loop = 0;
1089         myindex = cbp->c_nframes;
1090         n = (fcbp - frames) * FAREA;
1091         str = &overlap[n];
1092         ip = &intersect[n];
1093         /*
1094          * i == which overlap bit to test based on whether 'fcbp' is
1095          * an open or closed frame.
1096          */
1097         i = cb.c.b ? 2 : 0;
1098         for (; (tcbp = cbp->c_link[1]) != NULL;
1099             lcbp = cbp, cbp = cbp->c_link[0]) {
1100                 if (tcbp == fcbp)
1101                         return (-1);    /* fcbp is already included */
1102
1103                 /* check for intersection of 'tcbp' with 'fcbp' */
1104                 myindex--;
1105                 mask = str[tcbp - frames];
1106                 flags = cbp->c_flags;
1107                 n = i + ((flags & C_OPEN_1) != 0);
1108                 if (mask & (1 << n)) {
1109                         /*
1110                          * The two frames are not independent if they
1111                          * both lie in the same line and intersect at
1112                          * more than one point.
1113                          */
1114                         if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
1115                                 return (-1);
1116                         /*
1117                          * If this is not the spot we are attaching
1118                          * 'fcbp' to and it is a reasonable intersection
1119                          * spot, then there might be a loop.
1120                          */
1121                         n = ip[tcbp - frames];
1122                         if (osp != &board[n]) {
1123                                 /* check to see if this is a valid loop */
1124                                 if (verts)
1125                                         return (-1);
1126                                 if (fcnt == 0 || cbp->c_framecnt[1] == 0)
1127                                         return (-1);
1128                                 /*
1129                                  * Check to be sure the intersection is not
1130                                  * one of the end points if it is an open
1131                                  * ended frame.
1132                                  */
1133                                 if ((flags & C_OPEN_1) &&
1134                                     (n == tcbp->c_vertex ||
1135                                      n == tcbp->c_vertex + 5 * dd[tcbp->c_dir]))
1136                                         return (-1);    /* invalid overlap */
1137                                 if (cb.c.b &&
1138                                     (n == fcbp->c_vertex ||
1139                                      n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1140                                         return (-1);    /* invalid overlap */
1141
1142                                 vertices->o_intersect = n;
1143                                 vertices->o_fcombo = cbp;
1144                                 vertices->o_link = 1;
1145                                 vertices->o_off = (n - tcbp->c_vertex) /
1146                                         dd[tcbp->c_dir];
1147                                 vertices->o_frameindex = myindex;
1148                                 verts++;
1149                         }
1150                 }
1151                 n = i + ((flags & C_OPEN_0) != 0);
1152         }
1153         if (cbp == fcbp)
1154                 return (-1);    /* fcbp is already included */
1155
1156         /* check for intersection of 'cbp' with 'fcbp' */
1157         mask = str[cbp - frames];
1158         if (mask & (1 << n)) {
1159                 /*
1160                  * The two frames are not independent if they
1161                  * both lie in the same line and intersect at
1162                  * more than one point.
1163                  */
1164                 if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
1165                         return (-1);
1166                 /*
1167                  * If this is not the spot we are attaching
1168                  * 'fcbp' to and it is a reasonable intersection
1169                  * spot, then there might be a loop.
1170                  */
1171                 n = ip[cbp - frames];
1172                 if (osp != &board[n]) {
1173                         /* check to see if this is a valid loop */
1174                         if (verts)
1175                                 return (-1);
1176                         if (fcnt == 0 || lcbp->c_framecnt[0] == 0)
1177                                 return (-1);
1178                         /*
1179                          * Check to be sure the intersection is not
1180                          * one of the end points if it is an open
1181                          * ended frame.
1182                          */
1183                         if ((flags & C_OPEN_0) &&
1184                             (n == cbp->c_vertex ||
1185                              n == cbp->c_vertex + 5 * dd[cbp->c_dir]))
1186                                 return (-1);    /* invalid overlap */
1187                         if (cb.c.b &&
1188                             (n == fcbp->c_vertex ||
1189                              n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1190                                 return (-1);    /* invalid overlap */
1191
1192                         vertices->o_intersect = n;
1193                         vertices->o_fcombo = lcbp;
1194                         vertices->o_link = 0;
1195                         vertices->o_off = (n - cbp->c_vertex) /
1196                                 dd[cbp->c_dir];
1197                         vertices->o_frameindex = 0;
1198                         verts++;
1199                 }
1200         }
1201         return (verts);
1202 }
1203
1204 /*
1205  * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and
1206  * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array.
1207  * Return true if this list of frames is already in the hash list.
1208  * Otherwise, add the new combo to the hash list.
1209  */
1210 static int
1211 sortcombo(struct combostr **scbpp, struct combostr **cbpp,
1212           struct combostr *fcbp)
1213 {
1214         struct combostr **spp, **cpp;
1215         struct combostr *cbp, *ecbp;
1216         int n, inx;
1217
1218 #ifdef DEBUG
1219         if (debug > 3) {
1220                 char buf[128];
1221                 size_t pos;
1222
1223                 debuglog("sortc: %s%c l%d", stoc(fcbp->c_vertex),
1224                         pdir[fcbp->c_dir], curlevel);
1225                 pos = 0;
1226                 for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) {
1227                         snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1228                                 stoc((*cpp)->c_vertex), pdir[(*cpp)->c_dir]);
1229                         pos += strlen(buf + pos);
1230                 }
1231                 debuglog("%s", buf);
1232         }
1233 #endif /* DEBUG */
1234
1235         /* first build the new sorted list */
1236         n = curlevel + 1;
1237         spp = scbpp + n;
1238         cpp = cbpp + curlevel;
1239         do {
1240                 cpp--;
1241                 if (fcbp > *cpp) {
1242                         *--spp = fcbp;
1243                         do
1244                                 *--spp = *cpp;
1245                         while (cpp-- != cbpp);
1246                         goto inserted;
1247                 }
1248                 *--spp = *cpp;
1249         } while (cpp != cbpp);
1250         *--spp = fcbp;
1251 inserted:
1252
1253         /* now check to see if this list of frames has already been seen */
1254         cbp = hashcombos[inx = *scbpp - frames];
1255         if (cbp == (struct combostr *)0) {
1256                 /*
1257                  * Easy case, this list hasn't been seen.
1258                  * Add it to the hash list.
1259                  */
1260                 fcbp = (struct combostr *)
1261                         ((char *)scbpp - sizeof(struct combostr));
1262                 hashcombos[inx] = fcbp;
1263                 fcbp->c_next = fcbp->c_prev = fcbp;
1264                 return (0);
1265         }
1266         ecbp = cbp;
1267         do {
1268                 cbpp = (struct combostr **)(cbp + 1);
1269                 cpp = cbpp + n;
1270                 spp = scbpp + n;
1271                 cbpp++; /* first frame is always the same */
1272                 do {
1273                         if (*--spp != *--cpp)
1274                                 goto next;
1275                 } while (cpp != cbpp);
1276                 /* we found a match */
1277 #ifdef DEBUG
1278                 if (debug > 3) {
1279                         char buf[128];
1280                         size_t pos;
1281
1282                         debuglog("sort1: n%d", n);
1283                         pos = 0;
1284                         for (cpp = scbpp; cpp < scbpp + n; cpp++) {
1285                                 snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1286                                         stoc((*cpp)->c_vertex),
1287                                         pdir[(*cpp)->c_dir]);
1288                                 pos += strlen(buf + pos);
1289                         }
1290                         debuglog("%s", buf);
1291                         printcombo(cbp, buf, sizeof(buf));
1292                         debuglog("%s", buf);
1293                         cbpp--;
1294                         pos = 0;
1295                         for (cpp = cbpp; cpp < cbpp + n; cpp++) {
1296                                 snprintf(buf + pos, sizeof(buf) - pos, " %s%c",
1297                                         stoc((*cpp)->c_vertex),
1298                                         pdir[(*cpp)->c_dir]);
1299                                 pos += strlen(buf + pos);
1300                         }
1301                         debuglog("%s", buf);
1302                 }
1303 #endif /* DEBUG */
1304                 return (1);
1305         next:
1306                 ;
1307         } while ((cbp = cbp->c_next) != ecbp);
1308         /*
1309          * This list of frames hasn't been seen.
1310          * Add it to the hash list.
1311          */
1312         ecbp = cbp->c_prev;
1313         fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr));
1314         fcbp->c_next = cbp;
1315         fcbp->c_prev = ecbp;
1316         cbp->c_prev = fcbp;
1317         ecbp->c_next = fcbp;
1318         return (0);
1319 }
1320
1321 /*
1322  * Print the combo into string buffer 'buf'.
1323  */
1324 static void
1325 printcombo(struct combostr *cbp, char *buf, size_t max)
1326 {
1327         struct combostr *tcbp;
1328         size_t pos = 0;
1329
1330         snprintf(buf + pos, max - pos, "%x/%d",
1331                 cbp->c_combo.s, cbp->c_nframes);
1332         pos += strlen(buf + pos);
1333
1334         for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1335                 snprintf(buf + pos, max - pos, " %s%c%x",
1336                         stoc(tcbp->c_vertex), pdir[tcbp->c_dir], cbp->c_flags);
1337                 pos += strlen(buf + pos);
1338         }
1339         snprintf(buf + pos, max - pos, " %s%c",
1340                 stoc(cbp->c_vertex), pdir[cbp->c_dir]);
1341 }
1342
1343 #ifdef DEBUG
1344 void
1345 markcombo(struct combostr *ocbp)
1346 {
1347         struct combostr *cbp, *tcbp, **cbpp;
1348         struct elist *ep, *nep;
1349         struct spotstr *sp;
1350         int s, d, m, i;
1351         int nframes;
1352         int cmask, omask;
1353
1354         /* should never happen but check anyway */
1355         if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
1356                 return;
1357
1358         /*
1359          * The lower level combo can be pointed to by more than one
1360          * higher level 'struct combostr' so we can't modify the
1361          * lower level. Therefore, higher level combos store the
1362          * real mask of the lower level frame in c_emask[0] and the
1363          * frame number in c_frameindex.
1364          *
1365          * First we traverse the tree from top to bottom and save the
1366          * connection info. Then we traverse the tree from bottom to
1367          * top overwriting lower levels with the newer emask information.
1368          */
1369         ep = &einfo[nframes];
1370         cbpp = &ecombo[nframes];
1371         for (cbp = ocbp; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1372                 ep--;
1373                 ep->e_combo = cbp;
1374                 *--cbpp = cbp->c_link[1];
1375                 ep->e_off = cbp->c_voff[1];
1376                 ep->e_frameindex = cbp->c_frameindex;
1377                 ep->e_fval.s = cbp->c_linkv[1].s;
1378                 ep->e_framecnt = cbp->c_framecnt[1];
1379                 ep->e_emask = cbp->c_emask[1];
1380         }
1381         cbp = ep->e_combo;
1382         ep--;
1383         ep->e_combo = cbp;
1384         *--cbpp = cbp->c_link[0];
1385         ep->e_off = cbp->c_voff[0];
1386         ep->e_frameindex = 0;
1387         ep->e_fval.s = cbp->c_linkv[0].s;
1388         ep->e_framecnt = cbp->c_framecnt[0];
1389         ep->e_emask = cbp->c_emask[0];
1390
1391         /* now update the emask info */
1392         s = 0;
1393         for (i = 2, ep += 2; i < nframes; i++, ep++) {
1394                 cbp = ep->e_combo;
1395                 nep = &einfo[ep->e_frameindex];
1396                 nep->e_framecnt = cbp->c_framecnt[0];
1397                 nep->e_emask = cbp->c_emask[0];
1398
1399                 if (cbp->c_flags & C_LOOP) {
1400                         s++;
1401                         /*
1402                          * Account for the fact that this frame connects
1403                          * to a previous one (thus forming a loop).
1404                          */
1405                         nep = &einfo[cbp->c_dir];
1406                         if (--nep->e_framecnt)
1407                                 nep->e_emask &= ~(1 << cbp->c_voff[0]);
1408                         else
1409                                 nep->e_emask = 0;
1410                 }
1411         }
1412
1413         /*
1414          * We only need to update the emask values of "complete" loops
1415          * to include the intersection spots.
1416          */
1417         if (s && ocbp->c_combo.c.a == 2) {
1418                 /* process loops from the top down */
1419                 ep = &einfo[nframes];
1420                 do {
1421                         ep--;
1422                         cbp = ep->e_combo;
1423                         if (!(cbp->c_flags & C_LOOP))
1424                                 continue;
1425
1426                         /*
1427                          * Update the emask values to include the
1428                          * intersection spots.
1429                          */
1430                         nep = &einfo[cbp->c_dir];
1431                         nep->e_framecnt = 1;
1432                         nep->e_emask = 1 << cbp->c_voff[0];
1433                         ep->e_framecnt = 1;
1434                         ep->e_emask = 1 << ep->e_off;
1435                         ep = &einfo[ep->e_frameindex];
1436                         do {
1437                                 ep->e_framecnt = 1;
1438                                 ep->e_emask = 1 << ep->e_off;
1439                                 ep = &einfo[ep->e_frameindex];
1440                         } while (ep > nep);
1441                 } while (ep != einfo);
1442         }
1443
1444         /* mark all the frames with the completion spots */
1445         for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
1446                 m = ep->e_emask;
1447                 cbp = *cbpp;
1448                 sp = &board[cbp->c_vertex];
1449                 d = dd[s = cbp->c_dir];
1450                 cmask = CFLAG << s;
1451                 omask = (IFLAG | CFLAG) << s;
1452                 s = ep->e_fval.c.b ? 6 : 5;
1453                 for (; --s >= 0; sp += d, m >>= 1)
1454                         sp->s_flags |= (m & 1) ? omask : cmask;
1455         }
1456 }
1457
1458 void
1459 clearcombo(struct combostr *cbp, int open)
1460 {
1461         struct spotstr *sp;
1462         struct combostr *tcbp;
1463         int d, n, mask;
1464
1465         for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1466                 clearcombo(tcbp, cbp->c_flags & C_OPEN_1);
1467                 open = cbp->c_flags & C_OPEN_0;
1468         }
1469         sp = &board[cbp->c_vertex];
1470         d = dd[n = cbp->c_dir];
1471         mask = ~((IFLAG | CFLAG) << n);
1472         n = open ? 6 : 5;
1473         for (; --n >= 0; sp += d)
1474                 sp->s_flags &= mask;
1475 }
1476
1477 int
1478 list_eq(struct combostr **scbpp, struct combostr **cbpp, int n)
1479 {
1480         struct combostr **spp, **cpp;
1481
1482         spp = scbpp + n;
1483         cpp = cbpp + n;
1484         do {
1485                 if (*--spp != *--cpp)
1486                         return (0);
1487         } while (cpp != cbpp);
1488         /* we found a match */
1489         return (1);
1490 }
1491 #endif /* DEBUG */