1 /* 2 * Copyright (c) 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Ralph Campbell. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)pickmove.c 8.1 (Berkeley) 07/24/94"; 13 #endif /* not lint */ 14 15 #include <stdio.h> 16 #include <curses.h> 17 18 #include "gomoku.h" 19 20 struct combostr *sortcombos[2]; /* combos at higher levels */ 21 int combolen[2]; /* number of combos in sortcombos */ 22 int nextcolor; /* color of next move */ 23 24 extern char pdir[]; 25 26 pickmove(us) 27 int us; 28 { 29 register struct spotstr *sp, *sp1, *sp2; 30 register union combo *Ocp, *Tcp; 31 32 /* first move is easy */ 33 if (movenum == 1) 34 return (PT(K,10)); 35 36 /* initialize all the board values */ 37 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { 38 sp->s_combo[BLACK].s = MAXCOMBO; 39 sp->s_combo[WHITE].s = MAXCOMBO; 40 sp->s_level[BLACK] = 255; 41 sp->s_level[WHITE] = 255; 42 sp->s_nforce[BLACK] = 0; 43 sp->s_nforce[WHITE] = 0; 44 sp->s_flg &= ~(FFLAGALL | MFLAGALL); 45 } 46 47 /* remove old combos */ 48 removecombos(BLACK); 49 removecombos(WHITE); 50 removeemptyspots(); 51 52 /* compute new values */ 53 nextcolor = us; 54 scanframes(BLACK); 55 scanframes(WHITE); 56 57 /* find the spot with the highest value */ 58 for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) { 59 if (sp->s_occ != EMPTY) 60 continue; 61 if (debug && (sp->s_combo[BLACK].s < 0x200 || 62 sp->s_combo[WHITE].s < 0x200)) { 63 sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board), 64 sp->s_combo[BLACK].s, sp->s_level[BLACK], 65 sp->s_nforce[BLACK], 66 sp->s_combo[WHITE].s, sp->s_level[WHITE], 67 sp->s_nforce[WHITE], 68 sp->s_wval); 69 dlog(fmtbuf); 70 } 71 /* pick the best black move */ 72 if (better(sp, sp1, BLACK)) 73 sp1 = sp; 74 /* pick the best white move */ 75 if (better(sp, sp2, WHITE)) 76 sp2 = sp; 77 } 78 if (debug) { 79 sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d %d", 80 stoc(sp1 - board), 81 sp1->s_combo[BLACK].s, sp1->s_level[BLACK], 82 sp1->s_nforce[BLACK], 83 sp1->s_combo[WHITE].s, sp1->s_level[WHITE], 84 sp1->s_nforce[WHITE], sp1->s_wval, combolen[BLACK]); 85 dlog(fmtbuf); 86 sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d %d", 87 stoc(sp2 - board), 88 sp2->s_combo[WHITE].s, sp2->s_level[WHITE], 89 sp2->s_nforce[WHITE], 90 sp2->s_combo[BLACK].s, sp2->s_level[BLACK], 91 sp2->s_nforce[BLACK], sp2->s_wval, combolen[WHITE]); 92 dlog(fmtbuf); 93 } 94 if (us == BLACK) { 95 Ocp = &sp1->s_combo[BLACK]; 96 Tcp = &sp2->s_combo[WHITE]; 97 } else { 98 Tcp = &sp1->s_combo[BLACK]; 99 Ocp = &sp2->s_combo[WHITE]; 100 sp = sp1; 101 sp1 = sp2; 102 sp2 = sp; 103 } 104 /* 105 * Block their combo only if we have to (i.e., if they are one move 106 * away from completing a force and we don't have a force that 107 * we can complete which takes fewer moves to win). 108 */ 109 if (Tcp->c.a <= 1 && (Ocp->c.a > 1 || 110 Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b)) 111 return (sp2 - board); 112 return (sp1 - board); 113 } 114 115 /* 116 * Return true if spot 'sp' is better than spot 'sp1' for color 'us'. 117 */ 118 better(sp, sp1, us) 119 struct spotstr *sp; 120 struct spotstr *sp1; 121 int us; 122 { 123 int them; 124 125 if (sp->s_combo[us].s < sp1->s_combo[us].s) 126 return (1); 127 if (sp->s_combo[us].s != sp1->s_combo[us].s) 128 return (0); 129 if (sp->s_level[us] < sp1->s_level[us]) 130 return (1); 131 if (sp->s_level[us] != sp1->s_level[us]) 132 return (0); 133 if (sp->s_nforce[us] > sp1->s_nforce[us]) 134 return (1); 135 if (sp->s_nforce[us] != sp1->s_nforce[us]) 136 return (0); 137 138 them = !us; 139 if (sp->s_combo[them].s < sp1->s_combo[them].s) 140 return (1); 141 if (sp->s_combo[them].s != sp1->s_combo[them].s) 142 return (0); 143 if (sp->s_level[them] < sp1->s_level[them]) 144 return (1); 145 if (sp->s_level[them] != sp1->s_level[them]) 146 return (0); 147 if (sp->s_nforce[them] > sp1->s_nforce[them]) 148 return (1); 149 if (sp->s_nforce[them] != sp1->s_nforce[them]) 150 return (0); 151 152 if (sp->s_wval > sp1->s_wval) 153 return (1); 154 if (sp->s_wval != sp1->s_wval) 155 return (0); 156 157 #ifdef SVR4 158 return (rand() & 1); 159 #else 160 return (random() & 1); 161 #endif 162 } 163 164 int curcolor; /* implicit parameter to makecombo() */ 165 int curlevel; /* implicit parameter to makecombo() */ 166 167 /* 168 * Scan the sorted list of frames and update the minimum combo values. 169 */ 170 scanframes(color) 171 int color; 172 { 173 register struct combostr *cbp, *ecbp; 174 register struct spotstr *sp; 175 register union combo *cp; 176 register struct elist *ep; 177 register int i, r, d, n; 178 union combo cb; 179 180 curcolor = color; 181 182 /* check for empty list of frames */ 183 cbp = sortframes[color]; 184 if (cbp == (struct combostr *)0) 185 return; 186 187 /* quick check for four in a row */ 188 sp = &board[cbp->c_vertex]; 189 cb.s = sp->s_fval[color][d = cbp->c_dir].s; 190 if (cb.s < 0x101) { 191 d = dd[d]; 192 for (i = 5 + cb.c.b; --i >= 0; sp += d) { 193 if (sp->s_occ != EMPTY) 194 continue; 195 sp->s_combo[color].s = cb.s; 196 sp->s_level[color] = 1; 197 } 198 return; 199 } 200 201 /* update the minimum combo value for each spot in the frame */ 202 n = combolen[color]; 203 ecbp = cbp; 204 do { 205 sp = &board[cbp->c_vertex]; 206 cp = &sp->s_fval[color][r = cbp->c_dir]; 207 d = dd[r]; 208 if (cp->c.b) { 209 cb.c.a = cp->c.a + 1; 210 cb.c.b = 0; 211 if (cb.s < sp->s_combo[color].s) { 212 sp->s_combo[color].s = cb.s; 213 sp->s_level[color] = 1; 214 } 215 makecombo2(cbp, sp, cb.s); 216 if (cp->s != 0x101) 217 cb.s = cp->s; 218 sp += d; 219 i = 4; 220 } else { 221 cb.s = cp->s; 222 i = 5; 223 } 224 for (; --i >= 0; sp += d) { /* for each spot */ 225 if (sp->s_occ != EMPTY) 226 continue; 227 if (cp->s < sp->s_combo[color].s) { 228 sp->s_combo[color].s = cp->s; 229 sp->s_level[color] = 1; 230 } 231 if (cp->s == 0x101) 232 sp->s_nforce[color]++; 233 makecombo2(cbp, sp, cb.s); 234 } 235 /* mark frame as having been processed */ 236 board[cbp->c_vertex].s_flg |= MFLAG << r; 237 } while ((cbp = cbp->c_next) != ecbp); 238 239 /* try to make new 3rd level combos, 4th level, etc. */ 240 d = 2; 241 while (combolen[color] > n) { 242 if (debug) { 243 sprintf(fmtbuf, "%cL%d %d", "BW"[color], d, 244 combolen[color] - n); 245 dlog(fmtbuf); 246 refresh(); 247 } 248 n = combolen[color]; 249 addframes(d); 250 d++; 251 } 252 253 /* scan for combos at empty spots */ 254 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { 255 for (ep = sp->s_empty[color]; ep; ep = ep->e_next) { 256 cbp = ep->e_combo; 257 if (cbp->c_combo.s < sp->s_combo[color].s) { 258 sp->s_combo[color].s = cbp->c_combo.s; 259 sp->s_level[color] = cbp->c_nframes; 260 } else if (cbp->c_combo.s == sp->s_combo[color].s && 261 cbp->c_nframes < sp->s_level[color]) 262 sp->s_level[color] = cbp->c_nframes; 263 } 264 } 265 } 266 267 /* 268 * Compute all level 2 combos of frames intersecting spot 'osp' 269 * within the frame 'ocbp' and combo value 's'. 270 */ 271 makecombo2(ocbp, osp, s) 272 struct combostr *ocbp; 273 struct spotstr *osp; 274 int s; 275 { 276 register struct spotstr *sp, *fsp; 277 register struct combostr *cbp; 278 register int f, r, d, c; 279 int baseB, bmask, n; 280 union combo ocb, fcb; 281 282 /* try to combine a new frame with those found so far */ 283 ocb.s = s; 284 baseB = ocb.c.a + ocb.c.b - 1; 285 for (r = 4; --r >= 0; ) { /* for each direction */ 286 /* don't include frames that overlap ones already included */ 287 if (r == ocbp->c_dir) 288 continue; 289 d = dd[r]; 290 bmask = (BFLAG | FFLAG | MFLAG) << r; 291 fsp = osp; 292 for (f = 5; --f >= 0; fsp -= d) { /* for each frame */ 293 /* 294 * Don't include frames that are blocked or 295 * part of a <1,x> combo. 296 */ 297 if (fsp->s_occ == BORDER) 298 break; 299 if (fsp->s_flg & bmask) 300 continue; 301 302 /* don't include frames of the wrong color */ 303 fcb.s = fsp->s_fval[curcolor][r].s; 304 if (fcb.c.a >= MAXA) 305 continue; 306 307 /* 308 * Get the combo value for this frame. 309 * If this is the end point of the frame, 310 * use the closed ended value for the frame. 311 */ 312 if (f == 4 && fcb.c.b || fcb.s == 0x101) { 313 fcb.c.a++; 314 fcb.c.b = 0; 315 } 316 317 /* compute combo value */ 318 c = fcb.c.a + ocb.c.a - 3; 319 if (c > 3) 320 continue; 321 n = fcb.c.a + fcb.c.b - 1; 322 if (baseB < n) 323 n = baseB; 324 325 /* make a new combo! */ 326 cbp = (struct combostr *)malloc(sizeof(struct combostr)); 327 cbp->c_combo.c.a = c; 328 cbp->c_combo.c.b = n; 329 cbp->c_link[0] = ocbp; 330 cbp->c_link[1] = fsp->s_frame[r]; 331 cbp->c_vertex = osp - board; 332 cbp->c_nframes = 2; 333 cbp->c_dir = 0; 334 cbp->c_flg = 0; 335 cbp->c_refcnt = 0; 336 337 if (c == 1 && debug > 1 || debug > 3) { 338 sprintf(fmtbuf, "%c %s %x/2 r%d f%d %x", 339 curcolor == BLACK ? 'b' : 'w', 340 stoc(osp - board), cbp->c_combo.s, r, f, ocb.s); 341 dlog(fmtbuf); 342 #ifdef DEBUG 343 markcombo(cbp, curcolor, 0); 344 bdisp(); 345 whatsup(0); 346 clearcombo(cbp, curcolor, 0); 347 #endif 348 } 349 if (c > 1) { 350 if (ocb.c.a > 2) 351 makeempty(cbp, ocbp, ocb.c.b); 352 if (fcb.c.a > 2) 353 makeempty(cbp, cbp->c_link[1], fcb.c.b); 354 355 /* add the new combo to the end of the list */ 356 appendcombo(cbp, curcolor); 357 } else { 358 updatecombo(cbp, curcolor); 359 free(cbp); 360 } 361 } 362 } 363 } 364 365 /* 366 * Scan the sorted list of frames and try to combine into combos. 367 */ 368 addframes(level) 369 int level; 370 { 371 register struct combostr *cbp, *ecbp; 372 register struct spotstr *sp, *fsp; 373 register int i, r, d; 374 union combo fcb, cb; 375 376 curlevel = level; 377 378 /* clear MFLAG for this level */ 379 cbp = ecbp = sortframes[curcolor]; 380 do { 381 board[cbp->c_vertex].s_flg &= ~MFLAGALL; 382 } while ((cbp = cbp->c_next) != ecbp); 383 384 cbp = ecbp; 385 do { 386 fsp = &board[cbp->c_vertex]; 387 r = cbp->c_dir; 388 /* skip frames that are part of a <1,x> combo */ 389 if (fsp->s_flg & (FFLAG << r)) 390 continue; 391 392 /* 393 * Don't include <1,x> combo frames, 394 * treat it as a blocked three in a row instead. 395 */ 396 fcb.s = fsp->s_fval[curcolor][r].s; 397 if (fcb.s == 0x101) 398 fcb.s = 0x200; 399 400 /* 401 * If this is an open ended frame, use 402 * the combo value with the end closed. 403 */ 404 if (fsp->s_occ == EMPTY) { 405 if (fcb.c.b) { 406 cb.c.a = fcb.c.a + 1; 407 cb.c.b = 0; 408 } else 409 cb.s = fcb.s; 410 makecombo(cbp, fsp, cb.s); 411 } 412 413 /* 414 * The next four spots are handled the same for both 415 * open and closed ended frames. 416 */ 417 d = dd[r]; 418 sp = fsp + d; 419 for (i = 4; --i >= 0; sp += d) { 420 if (sp->s_occ != EMPTY) 421 continue; 422 makecombo(cbp, sp, fcb.s); 423 } 424 425 /* mark frame as having been processed */ 426 fsp->s_flg |= MFLAG << r; 427 } while ((cbp = cbp->c_next) != ecbp); 428 } 429 430 /* 431 * Compute all level N combos of frames intersecting spot 'osp' 432 * within the frame 'ocbp' and combo value 's'. 433 */ 434 makecombo(ocbp, osp, s) 435 struct combostr *ocbp; 436 struct spotstr *osp; 437 int s; 438 { 439 register struct combostr *cbp, *ncbp; 440 register struct spotstr *sp; 441 register struct elist *ep; 442 register int n, c; 443 struct elist *nep, **epp; 444 struct combostr *fcbp; 445 int baseB, verts, d; 446 union combo ocb, cb; 447 448 ocb.s = s; 449 baseB = ocb.c.a + ocb.c.b - 1; 450 for (ep = osp->s_empty[curcolor]; ep; ep = ep->e_next) { 451 /* don't try to combine this combo if it is the wrong level */ 452 cbp = ep->e_combo; 453 if (cbp->c_nframes > curlevel) 454 continue; 455 if (cbp->c_nframes != curlevel) 456 break; 457 458 /* don't include frames that overlap ones already included */ 459 ncbp = ep->e_frame; 460 if (ncbp->c_dir == ocbp->c_dir || 461 (cbp->c_flg & C_LOOP) && cbp->c_dir == ocbp->c_dir || 462 (n = checkframes(cbp, ocbp, osp - board, ncbp)) < 0) 463 continue; 464 465 /* compute first half of combo value */ 466 c = cbp->c_combo.c.a + ocb.c.a - 3; 467 if (c > 3) 468 continue; 469 470 /* check to see if this frame forms a valid loop */ 471 verts = 0; 472 if (n) { 473 sp = &board[ocbp->c_vertex]; 474 d = dd[ocbp->c_dir]; 475 if (n = ocb.c.b) 476 sp += d; 477 for (; n < 5; n++, sp += d) { 478 if (sp->s_occ != EMPTY || sp == osp) 479 continue; 480 for (nep = sp->s_empty[curcolor]; nep; nep = nep->e_next) { 481 if (nep->e_combo == cbp) { 482 verts++; 483 fcbp = nep->e_frame; 484 continue; 485 } 486 if (nep->e_combo->c_nframes < cbp->c_nframes) 487 break; 488 } 489 } 490 #if 0 491 { 492 char *str; 493 sprintf(fmtbuf, "%c v%d %s%c", 494 curcolor == BLACK ? 'b' : 'w', verts, 495 stoc(ocbp->c_vertex), pdir[ocbp->c_dir]); 496 str = fmtbuf + strlen(fmtbuf); 497 for (; cbp->c_link[1]; cbp = cbp->c_link[0]) { 498 sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex), 499 pdir[cbp->c_link[1]->c_dir]); 500 str += strlen(str); 501 } 502 sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]); 503 dlog(fmtbuf); 504 cbp = ep->e_combo; 505 } 506 #endif 507 /* frame overlaps but not at a valid spot */ 508 if (verts == 0 || ocb.c.a < 3) 509 continue; 510 } 511 512 /* compute second half of combo value */ 513 cb.s = board[ncbp->c_vertex].s_fval[curcolor][ncbp->c_dir].s; 514 n = cb.c.a + cb.c.b - 1; 515 if (baseB < n) 516 n = baseB; 517 518 /* make a new combo! */ 519 ncbp = (struct combostr *)malloc(sizeof(struct combostr)); 520 c -= verts; 521 ncbp->c_combo.c.a = c; 522 ncbp->c_combo.c.b = n; 523 ncbp->c_link[0] = cbp; 524 ncbp->c_link[1] = ocbp; 525 ncbp->c_vertex = osp - board; 526 ncbp->c_nframes = cbp->c_nframes + 1; 527 ncbp->c_refcnt = 0; 528 if (verts) { 529 ncbp->c_flg = C_LOOP; 530 ncbp->c_dir = fcbp->c_dir; 531 532 /* add the combo to the list of empty spots */ 533 nep = (struct elist *)malloc(sizeof(struct elist)); 534 nep->e_combo = ncbp; 535 nep->e_frame = ocbp; 536 if (debug > 2) { 537 sprintf(fmtbuf, "e %s", stoc(ncbp->c_vertex)); 538 dlog(fmtbuf); 539 } 540 541 /* sort by the number of frames in the combo */ 542 epp = &board[ncbp->c_vertex].s_empty[curcolor]; 543 while (*epp) { 544 if (cbp->c_nframes >= (*epp)->e_combo->c_nframes) 545 break; 546 epp = &(*epp)->e_next; 547 } 548 nep->e_next = *epp; 549 *epp = nep; 550 } else { 551 ncbp->c_flg = 0; 552 ncbp->c_dir = 0; 553 if (ocb.c.a > 2) 554 makeempty(ncbp, ocbp, ocb.c.b); 555 } 556 if (verts > 1 && debug || c == 1 && debug > 1 || debug > 2) { 557 char *str; 558 559 sprintf(fmtbuf, "%c %s%c %x v%d %x/%d", 560 curcolor == BLACK ? 'b' : 'w', 561 stoc(osp - board), pdir[ocbp->c_dir], ocb.s, 562 verts, ncbp->c_combo.s, ncbp->c_nframes); 563 dlog(fmtbuf); 564 str = fmtbuf; 565 for (cbp = ncbp; cbp->c_link[1]; cbp = cbp->c_link[0]) { 566 sprintf(str, " %s%c", stoc(cbp->c_link[1]->c_vertex), 567 pdir[cbp->c_link[1]->c_dir]); 568 str += strlen(str); 569 } 570 sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]); 571 dlog(fmtbuf); 572 #ifdef DEBUG 573 markcombo(ncbp, curcolor, 0); 574 bdisp(); 575 whatsup(0); 576 clearcombo(ncbp, curcolor, 0); 577 #endif 578 } 579 if (c > 1) { 580 /* add the new combo to the end of the list */ 581 appendcombo(ncbp, curcolor); 582 } else { 583 updatecombo(ncbp, curcolor); 584 free(ncbp); 585 } 586 } 587 } 588 589 /* 590 * Add the combostr 'cbp' to the empty spots list for each empty spot 591 * in the frame 'fcbp' except for the intersection. 592 * 's' is zero if 'fcbp' is a closed ended frame, else it is one. 593 * Return the number of valid intersections with ocbp for detecting loops. 594 */ 595 makeempty(cbp, fcbp, s) 596 struct combostr *cbp; 597 struct combostr *fcbp; 598 int s; 599 { 600 struct spotstr *sp, *vsp; 601 struct elist *ep, **epp; 602 int d; 603 604 if (debug > 2) { 605 sprintf(fmtbuf, "E %s%c s%d", stoc(fcbp->c_vertex), 606 pdir[fcbp->c_dir], s); 607 sprintf(fmtbuf + strlen(fmtbuf), " %s", stoc(cbp->c_vertex)); 608 dlog(fmtbuf); 609 } 610 vsp = &board[cbp->c_vertex]; 611 sp = &board[fcbp->c_vertex]; 612 d = dd[fcbp->c_dir]; 613 if (s) 614 sp += d; 615 for (; s < 5; s++, sp += d) { 616 if (sp->s_occ != EMPTY || sp == vsp) 617 continue; 618 619 /* add the combo to the list of empty spots */ 620 ep = (struct elist *)malloc(sizeof(struct elist)); 621 ep->e_combo = cbp; 622 ep->e_frame = fcbp; 623 if (debug > 2) { 624 sprintf(fmtbuf, "e %s", stoc(sp - board)); 625 dlog(fmtbuf); 626 } 627 628 /* sort by the number of frames in the combo */ 629 epp = &sp->s_empty[curcolor]; 630 while (*epp) { 631 if (cbp->c_nframes >= (*epp)->e_combo->c_nframes) 632 break; 633 epp = &(*epp)->e_next; 634 } 635 ep->e_next = *epp; 636 *epp = ep; 637 } 638 } 639 640 /* 641 * Update the board value based on the combostr. 642 * This is called only if 'cbp' is a <1,x> combo. 643 * We handle things differently depending on whether the next move 644 * would be trying to "complete" the combo or trying to block it. 645 */ 646 updatecombo(cbp, color) 647 struct combostr *cbp; 648 int color; 649 { 650 register struct framestr *fp; 651 register struct spotstr *sp; 652 register struct combostr *tcbp; 653 register int i, d; 654 int nframes, vertex; 655 union combo cb; 656 657 for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { 658 if (color == nextcolor) { 659 /* update the board value for the vertex */ 660 sp = &board[cbp->c_vertex]; 661 sp->s_nforce[color]++; 662 if (cbp->c_combo.s < sp->s_combo[color].s) { 663 sp->s_combo[color].s = cbp->c_combo.s; 664 sp->s_level[color] = cbp->c_nframes; 665 } else if (cbp->c_combo.s == sp->s_combo[color].s && 666 cbp->c_nframes < sp->s_level[color]) 667 sp->s_level[color] = cbp->c_nframes; 668 } else { 669 /* update the board values for each spot in frame */ 670 vertex = cbp->c_vertex; 671 sp = &board[tcbp->c_vertex]; 672 if (sp->s_fval[color][tcbp->c_dir].c.b && 673 tcbp->c_vertex != vertex) 674 i = 6; 675 else 676 i = 5; 677 d = dd[tcbp->c_dir]; 678 cb.s = cbp->c_combo.s; 679 nframes = cbp->c_nframes; 680 for (; --i >= 0; sp += d) { 681 sp->s_nforce[color]++; 682 if (cb.s < sp->s_combo[color].s) { 683 sp->s_combo[color].s = cb.s; 684 sp->s_level[color] = nframes; 685 } else if (cb.s == sp->s_combo[color].s && 686 cbp->c_nframes < sp->s_level[color]) 687 sp->s_level[color] = nframes; 688 } 689 } 690 691 /* mark the frame as being part of a <1,x> combo */ 692 board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir; 693 } 694 695 if (color != nextcolor) { 696 /* update the board values for each spot in frame */ 697 sp = &board[cbp->c_vertex]; 698 if (sp->s_fval[color][cbp->c_dir].c.b && 699 cbp->c_vertex != vertex) 700 i = 6; 701 else 702 i = 5; 703 d = dd[cbp->c_dir]; 704 for (; --i >= 0; sp += d) { 705 sp->s_nforce[color]++; 706 if (cb.s < sp->s_combo[color].s) { 707 sp->s_combo[color].s = cb.s; 708 sp->s_level[color] = nframes; 709 } else if (cb.s == sp->s_combo[color].s && 710 cbp->c_nframes < sp->s_level[color]) 711 sp->s_level[color] = nframes; 712 } 713 } 714 715 /* mark the frame as being part of a <1,x> combo */ 716 board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir; 717 } 718 719 /* 720 * Free all elist structures. 721 */ 722 removeemptyspots() 723 { 724 register struct elist *ep, *nep; 725 register struct spotstr *sp; 726 int i; 727 728 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { 729 for (i = BLACK; i <= WHITE; i++) { 730 for (ep = sp->s_empty[i]; ep; ep = nep) { 731 nep = ep->e_next; 732 free(ep); 733 } 734 sp->s_empty[i] = (struct elist *)0; 735 } 736 } 737 } 738 739 /* 740 * Remove all combo structures. 741 */ 742 removecombos(color) 743 int color; 744 { 745 register struct combostr *cbp, *ncbp, *endcbp; 746 747 /* check the list */ 748 if ((cbp = sortcombos[color]) == (struct combostr *)0) 749 return; 750 751 /* scan the list */ 752 endcbp = cbp; 753 do { 754 ncbp = cbp->c_next; 755 cbp->c_next = (struct combostr *)0; 756 cbp->c_prev = (struct combostr *)0; 757 free(cbp); 758 cbp = ncbp; 759 } while (cbp != endcbp); 760 761 sortcombos[color] = (struct combostr *)0; 762 combolen[color] = 0; 763 } 764 765 /* 766 * Add combo to the end of the list. 767 */ 768 appendcombo(cbp, color) 769 struct combostr *cbp; 770 int color; 771 { 772 struct combostr *pcbp, *ncbp; 773 774 combolen[color]++; 775 ncbp = sortcombos[color]; 776 if (ncbp == (struct combostr *)0) { 777 sortcombos[color] = cbp; 778 cbp->c_next = cbp; 779 cbp->c_prev = cbp; 780 return; 781 } 782 pcbp = ncbp->c_prev; 783 cbp->c_next = ncbp; 784 cbp->c_prev = pcbp; 785 ncbp->c_prev = cbp; 786 pcbp->c_next = cbp; 787 } 788 789 /* 790 * Return positive if frame 'fcbp' overlaps any of the frames in 'cbp' 791 * other than the frame 'ecbp'. 792 * Return -1 if any of the frames in 'cbp' are marked or part of a <1,x> combo. 793 * Else, return zero. 794 */ 795 checkframes(cbp, fcbp, vertex, ecbp) 796 struct combostr *cbp; 797 struct combostr *fcbp; 798 int vertex; 799 struct combostr *ecbp; 800 { 801 struct combostr *tcbp; 802 char *str; 803 int i, n, mask; 804 short *ip; 805 806 n = (fcbp - frames) * FAREA; 807 str = &overlap[n]; 808 ip = &intersect[n]; 809 i = vertex == fcbp->c_vertex ? 2 : 0; 810 for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { 811 #if 0 812 if (board[tcbp->c_vertex].s_flg & (FFLAG << tcbp->c_dir)) 813 return (-1); 814 #endif 815 vertex = cbp->c_vertex; 816 if (tcbp == ecbp) 817 continue; 818 n = tcbp - frames; 819 if (board[ip[n]].s_occ != EMPTY) 820 continue; 821 mask = str[n]; 822 if (mask & (1 << (i + (tcbp->c_vertex == vertex)))) 823 return (1); 824 } 825 #if 0 826 if (board[cbp->c_vertex].s_flg & (FFLAG << cbp->c_dir)) 827 return (-1); 828 #endif 829 if (cbp == ecbp) 830 return (0); 831 n = cbp - frames; 832 if (board[ip[n]].s_occ != EMPTY) 833 return (0); 834 mask = str[n]; 835 return (mask & (1 << (i + (cbp->c_vertex == vertex)))); 836 } 837 838 #ifdef DEBUG 839 markcombo(cbp, color, vertex) 840 struct combostr *cbp; 841 int color; 842 int vertex; 843 { 844 register struct spotstr *sp; 845 struct combostr *tcbp; 846 int i, d, r, n, mask; 847 848 for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) 849 markcombo(tcbp, color, vertex = cbp->c_vertex); 850 sp = &board[cbp->c_vertex]; 851 d = dd[r = cbp->c_dir]; 852 mask = (IFLAG | CFLAG) << r; 853 n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5; 854 for (i = 0; i < n; i++, sp += d) { 855 if (n == 6 && (i == 0 || i == 5)) 856 sp->s_flg |= CFLAG << r; 857 else 858 sp->s_flg |= mask; 859 } 860 } 861 862 clearcombo(cbp, color, vertex) 863 struct combostr *cbp; 864 int color; 865 int vertex; 866 { 867 register struct spotstr *sp; 868 struct combostr *tcbp; 869 int i, d, r, n, mask; 870 871 for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) 872 clearcombo(tcbp, color, vertex = cbp->c_vertex); 873 sp = &board[cbp->c_vertex]; 874 d = dd[r = cbp->c_dir]; 875 mask = ~((IFLAG | CFLAG) << r); 876 n = sp->s_fval[color][r].c.b && cbp->c_vertex != vertex ? 6 : 5; 877 for (i = 0; i < n; i++, sp += d) 878 sp->s_flg &= mask; 879 } 880 #endif /* DEBUG */ 881