games/gomoku/pickmove.c

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