games/gomoku/pickmove.c

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