![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lines.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / usr / games|
Return to lines.c CVS log | Up to [MW Coherent from dump] / coherent / d / usr / games |
1.1 ! root 1: /* ! 2: * lines.c ! 3: * 4/2/87 ! 4: * Copyright (C) 1984-1987 by Stephen A. Ness. ! 5: * Lines of action, a game by Claude Soucie. ! 6: * Reference: Sid Sackson, "A Gamut of Games," Random House 1969, pp. 34-39. ! 7: */ ! 8: ! 9: /* ! 10: * This program maintains a lot of information about the current position ! 11: * to facilitate speedy generation and evaluation of possible next moves. ! 12: * Moving or unmoving a piece is rather complicated as a result. ! 13: * It also uses pointer arithmetic to do array calculations within loops. ! 14: * The number of positions generated is roughly k*((width+1)^(depth-1)), ! 15: * where k is the number of legal moves for a position (about 36 at start). ! 16: * Not all generated positions need to be evaluated, however. ! 17: * On an IBM PC, this program evaluates about 48 positions per second. ! 18: */ ! 19: ! 20: #include <stdio.h> ! 21: ! 22: #if COHERENT ! 23: #include <sys/timeb.h> ! 24: #endif ! 25: #if MSDOS ! 26: #include <timeb.h> ! 27: #define IBMPC 1 /* Use IBM PC graphic characters. */ ! 28: #endif ! 29: #ifdef DEBUG ! 30: #include <assert.h> ! 31: #endif ! 32: ! 33: /* General definitions. */ ! 34: #define VERSION "1.2" /* Version number. */ ! 35: #define DEPTH 3 /* Initial tree search depth. */ ! 36: #define WIDTH 25 /* Initial tree search width. */ ! 37: #define MAXWIDTH 96 /* Max number of next moves (12 * 8). */ ! 38: #define MAXDEPTH 5 /* Max move tree search depth. */ ! 39: #define NMOVES 200 /* Max number of moves in game. */ ! 40: #define EDGE -1 /* Edge marker for board. */ ! 41: #define WIN 32767 /* Value for winning position. */ ! 42: #define LOSS -32767 /* Value for losing position. */ ! 43: #define MAN(x) ((x)?MAN1:MAN0) /* Graphic character for x's men. */ ! 44: ! 45: /* Graphic characters for printable board. */ ! 46: #if IBMPC ! 47: #define SPACE 32 ! 48: #define VERT 179 ! 49: #define HORIZ 196 ! 50: #define TOPL 218 ! 51: #define TOPM 194 ! 52: #define TOPR 191 ! 53: #define MIDL 195 ! 54: #define MIDM 197 ! 55: #define MIDR 180 ! 56: #define BOTL 192 ! 57: #define BOTM 193 ! 58: #define BOTR 217 ! 59: #define MAN0 4 ! 60: #define MAN1 79 ! 61: #else ! 62: #define SPACE ' ' ! 63: #define VERT '|' ! 64: #define HORIZ '-' ! 65: #define TOPL '+' ! 66: #define TOPM '+' ! 67: #define TOPR '+' ! 68: #define MIDL '+' ! 69: #define MIDM '+' ! 70: #define MIDR '+' ! 71: #define BOTL '+' ! 72: #define BOTM '+' ! 73: #define BOTR '+' ! 74: #define MAN0 'X' ! 75: #define MAN1 'O' ! 76: #endif ! 77: ! 78: char *rules = "\ ! 79: Object: to get all of player's pieces into one connected group.\n\ ! 80: Horizontally, vertically or diagonally adjacent pieces are connected.\n\ ! 81: Movement: A piece may move horizontally, vertically or diagonally, but\n\ ! 82: it MUST move exactly the number of squares given by the total number\n\ ! 83: of pieces (friendly and enemy) in the row, column or diagonal of\n\ ! 84: movement. A piece may jump over friendly pieces, but it may not jump\n\ ! 85: over enemy pieces. A piece may land on an enemy piece, removing it\n\ ! 86: from the game, but it may not land on a friendly piece."; ! 87: ! 88: char *help = "\ ! 89: Commands:\n\ ! 90: \td3\tSet tree search depth to 3.\n\ ! 91: \te\tEvaluate current position.\n\ ! 92: \th\tPrint help information.\n\ ! 93: \ti\tInitialize new board.\n\ ! 94: \tl\tList game on console.\n\ ! 95: \tlfile\tList game to file.\n\ ! 96: \tm\tGenerate next move.\n\ ! 97: \tm1234\tMove from 12 to 34, then generate reply.\n\ ! 98: \tM1234\tMove from 12 to 34, do not generate reply.\n\ ! 99: \tp\tPrint the board.\n\ ! 100: \tq\tQuit.\n\ ! 101: \tr\tPrint rules.\n\ ! 102: \tu\tUndo most recent move.\n\ ! 103: \tv\tPrint move generation information.\n\ ! 104: \tw25\tSet tree search width to 25.\n\ ! 105: \txfile\tExecute moves from list file.\n\ ! 106: \t!cmd\tPass cmd to system for execution (COHERENT, MSDOS only).\n\ ! 107: A command must be followed by a <return>."; ! 108: ! 109: /* Structure to represent moves. */ ! 110: typedef struct move { ! 111: int m_val; /* Value. */ ! 112: char m_from; /* From. */ ! 113: char m_to; /* To. */ ! 114: char m_man; /* Man number. */ ! 115: char m_cap; /* Captured man number. */ ! 116: } MOVE; ! 117: ! 118: /* Globals. */ ! 119: int board[100]; /* Board with edges added. */ ! 120: int boarddist[100][100]; /* Distances between squares on board. */ ! 121: int cindex[100][4]; /* Indices into count for [pos][dir]. */ ! 122: char command[81]; /* Command. */ ! 123: int count[46]; /* Number of men in row, col, diagonal. */ ! 124: int depth = DEPTH; /* Search depth. */ ! 125: int firstman[2]; /* First man number for each player. */ ! 126: int group[25]; /* Grouping of men. */ ! 127: int lastman[2]; /* Last man number for each player. */ ! 128: int loc[25]; /* Locations of men. */ ! 129: int maxgen; /* Largest width of moves generated. */ ! 130: MOVE movelist[NMOVES]; /* Moves to date. */ ! 131: long neval; /* Number of positions evaluated. */ ! 132: MOVE nextmove[MAXDEPTH][MAXWIDTH]; /* Move generation tree. */ ! 133: long ngen; /* Number of moves generated. */ ! 134: int nmove; /* Move number. */ ! 135: int npos; /* Number of positions from which moves generated. */ ! 136: int offset[4]; /* Board offsets for moves. */ ! 137: int opp; /* Opponent. */ ! 138: char pboard[18][37]; /* Printable representation of board. */ ! 139: int plr; /* Player to move next. */ ! 140: int val[2]; /* Value of player's position. */ ! 141: int vflag = 0; /* Verbose flag. */ ! 142: int width = WIDTH; /* Search width. */ ! 143: ! 144: #if COHERENT || MSDOS ! 145: time_t start; /* Move starting time. */ ! 146: extern time_t time(); ! 147: #endif ! 148: ! 149: main() ! 150: { ! 151: register int flag, n; ! 152: MOVE m; ! 153: MOVE *mp = &m; ! 154: ! 155: staticinit(); ! 156: printf("Lines of Action V%s\n(c) 1984-1987 by Stephen A. Ness.\n", VERSION); ! 157: puts("Type 'h' followed by <return> if you need help."); ! 158: initialize(); ! 159: for (;;) { ! 160: printf("? "); ! 161: if (gets(command)==NULL) ! 162: exit(0); ! 163: switch(command[0]) { ! 164: case 'd': ! 165: setparam(&depth, "depth", MAXDEPTH); ! 166: break; ! 167: case 'e': ! 168: n = value(); ! 169: printf("board(%c)=%d board(%c)=%d value=%d\n", MAN0, val[0], MAN1, val[1], n); ! 170: break; ! 171: case 'h': ! 172: printf("%s\nPlayer %c moves next.\n", help, MAN(plr)); ! 173: break; ! 174: case 'i': ! 175: initialize(); ! 176: break; ! 177: case 'l': ! 178: listgame(); ! 179: break; ! 180: case 'm': ! 181: flag = 1; ! 182: if (command[1]=='\0') ! 183: goto reply; ! 184: goto moveit; ! 185: case 'M': ! 186: flag = 0; ! 187: moveit: if (legalmove(atoi(&command[1]),mp)) { ! 188: dodisp(mp, 0); ! 189: domove(mp); ! 190: if (gameover()) ! 191: break; ! 192: } ! 193: else { ! 194: puts("Illegal move -- try again"); ! 195: break; ! 196: } ! 197: if (flag) ! 198: printboard(); ! 199: reply: if (flag) { ! 200: if (vflag) { ! 201: #if COHERENT || MSDOS ! 202: start = time(NULL); ! 203: #endif ! 204: ngen = neval = 0L; ! 205: npos = maxgen = 0; ! 206: } ! 207: findbest(mp, depth, LOSS); ! 208: if (mp->m_man == 0) { /* Stalemate */ ! 209: puts("Game drawn by stalemate."); ! 210: puts("Type i to play again or q to quit."); ! 211: break; ! 212: } ! 213: if (vflag) { ! 214: #if COHERENT || MSDOS ! 215: printf("Elapsed time %ld seconds.\n", time(NULL)-start); ! 216: #endif ! 217: printf("Generated %ld moves from %d positions.\nEvaluated %ld positions.\nMaximum width %d.\n", ngen, npos, neval, maxgen); ! 218: } ! 219: printf("%c moves %d%c%d.\n", MAN(plr), mp->m_from, (mp->m_cap)?'*':'-', mp->m_to); ! 220: dodisp(mp, 0); ! 221: domove(mp); ! 222: if (gameover()) ! 223: break; ! 224: } ! 225: printboard(); ! 226: break; ! 227: case 'p': ! 228: printboard(); ! 229: break; ! 230: case 'q': ! 231: exit(0); ! 232: break; ! 233: case 'r': ! 234: puts(rules); ! 235: break; ! 236: case 'u': ! 237: domove(NULL); ! 238: dodisp(&movelist[nmove], 1); ! 239: printboard(); ! 240: break; ! 241: case 'v': ! 242: vflag = 1; ! 243: break; ! 244: case 'w': ! 245: setparam(&width, "width", MAXWIDTH); ! 246: break; ! 247: case 'x': ! 248: execfile(); ! 249: break; ! 250: #if COHERENT || MSDOS ! 251: case '!': ! 252: system(&command[1]); ! 253: break; ! 254: #endif ! 255: default: ! 256: puts("Command not recognized -- try again."); ! 257: puts("Type h<return> if you need help."); ! 258: break; ! 259: } ! 260: } ! 261: } ! 262: ! 263: /* Compare next moves. Called indirectly by qsort. */ ! 264: compnext(p1, p2) char *p1, *p2; ! 265: { ! 266: register int val1, val2; ! 267: ! 268: val1 = ((MOVE *)p1)->m_val; ! 269: val2 = ((MOVE *)p2)->m_val; ! 270: return ((val1 < val2) ? -1 : ((val1 == val2) ? 0 : 1)); ! 271: } ! 272: ! 273: /* Display character c at pos on printable board. */ ! 274: display(c,pos) ! 275: { ! 276: pboard[2*(pos/10)-1][4*(pos%10)-2] = c; ! 277: } ! 278: ! 279: /* Update printable display for move *mp. */ ! 280: /* Separated from domove() for speed. */ ! 281: dodisp(mp, undo) register MOVE *mp; int undo; ! 282: { ! 283: if (undo) { /* Undo move */ ! 284: display(SPACE, mp->m_to); ! 285: display(MAN(plr), mp->m_from); ! 286: if (mp->m_cap) ! 287: display(MAN(opp), mp->m_to); ! 288: } ! 289: else { ! 290: display(SPACE, mp->m_from); ! 291: display(MAN(plr), mp->m_to); ! 292: } ! 293: } ! 294: ! 295: /* Combine adjacent pieces into groups. */ ! 296: dogroup(n) int n; ! 297: { ! 298: int i, j, first, last, man, mgroup, igroup; ! 299: register k; ! 300: register int *gp; ! 301: int *bp, *offp, *gfp; ! 302: ! 303: first = firstman[n]; ! 304: last = lastman[n]; ! 305: gp = gfp = &group[first]; ! 306: for (k=first; k<=last; k++) ! 307: *gp++ = k; /* Put man i in group i initially */ ! 308: for (i=first; i<=last; i++) { ! 309: bp = &board[loc[i]]; ! 310: offp = &offset[0]; ! 311: igroup = group[i]; /* Note that i<>group[i] sometimes */ ! 312: for (j=0; j<4; j++) { ! 313: man = *(bp+*offp++); /* Occupant of adjacent square */ ! 314: if ((first<=man)&&(man<=last)&&(group[man]!=igroup)) { ! 315: /* Join group[man] to group[i] */ ! 316: mgroup = group[man]; ! 317: gp = gfp; ! 318: for (k=first; k<=last; k++) { ! 319: if (*gp==mgroup) ! 320: *gp = igroup; ! 321: gp++; ! 322: } ! 323: } ! 324: } ! 325: } ! 326: } ! 327: ! 328: /* Make a legal move. */ ! 329: /* Does an unmove if mp is NULL. */ ! 330: /* Note that unmove is opp moving rather than plr. */ ! 331: /* The printable display is not updated. */ ! 332: domove(mp) ! 333: register MOVE *mp; ! 334: { ! 335: int i, from, to, man, cap, last, uflag; ! 336: register int *cifp, *citp; ! 337: ! 338: if (mp==NULL) { /* Unmove */ ! 339: if (nmove == 0) { ! 340: puts("Cannot unmove."); ! 341: return; ! 342: } ! 343: uflag = 1; ! 344: mp = &movelist[--nmove]; ! 345: from = mp->m_to; ! 346: to = mp->m_from; ! 347: val[opp] = -1; /* Value of opp's position changes */ ! 348: } ! 349: else { /* Normal move */ ! 350: if (nmove >= NMOVES) { ! 351: puts("Out of space on move list"); ! 352: exit(1); ! 353: } ! 354: uflag = 0; ! 355: movelist[nmove++] = *mp; /* Structure assignment */ ! 356: from = mp->m_from; ! 357: to = mp->m_to; ! 358: val[plr] = -1; /* Value of plr's position changes */ ! 359: } ! 360: man = mp->m_man; ! 361: cap = mp->m_cap; ! 362: #if DEBUG ! 363: printf("%smove %d from=%d to=%d cap=%d\n", (uflag)?"un":"", man, from, to, cap); ! 364: #endif ! 365: board[from] = 0; /* Vacate from location */ ! 366: if (cap) { /* Capture */ ! 367: if (uflag) { /* Rename cap as last, resurrect cap */ ! 368: val[plr] = -1; /* Value of plr's position changes */ ! 369: last = ++lastman[plr]; ! 370: i = loc[last] = loc[cap]; ! 371: board[i] = last; ! 372: cifp = &cindex[from][0]; ! 373: for (i=0; i<4; i++) ! 374: ++count[*cifp++]; ! 375: i = from; ! 376: } ! 377: else { /* Rename last man as cap */ ! 378: val[opp] = -1; /* Value of opp's position changes */ ! 379: citp = &cindex[to][0]; ! 380: for (i=0; i<4; i++) ! 381: --count[*citp++]; ! 382: i = loc[lastman[opp]--]; ! 383: } ! 384: board[i] = cap; ! 385: loc[cap] = i; ! 386: } ! 387: board[to] = man; /* Occupy to location */ ! 388: loc[man] = to; ! 389: cifp = &cindex[from][0]; ! 390: citp = &cindex[to][0]; ! 391: for (i=0; i<4; i++) { /* Adjust counts at from and to */ ! 392: --count[*cifp++]; ! 393: ++count[*citp++]; ! 394: } ! 395: opp = plr; ! 396: plr = 1 - plr; ! 397: } ! 398: ! 399: /* Evaluate position of player n and return its value. */ ! 400: /* The value is the sum of the distances between players not in same group. */ ! 401: eval(n) int n; ! 402: { ! 403: register int value; ! 404: register int *jp; ! 405: int i, j, first, last, igroup; ! 406: int *ip, *bdp, *gp, *gfp; ! 407: dogroup(n); /* Find groups of men */ ! 408: value = 0; ! 409: first = firstman[n]; ! 410: last = lastman[n]; ! 411: gfp = &group[first]; ! 412: ip = &loc[first]; ! 413: for (i=first; i<last; i++) { /* Man number i */ ! 414: #if DEBUG ! 415: assert(ip==&loc[i]); ! 416: assert(gfp==&group[i]); ! 417: #endif ! 418: igroup = *gfp++; /* igroup = group[i] */ ! 419: bdp = &boarddist[*ip++][0]; /* &boarddist[ipos][0] */ ! 420: gp = gfp; ! 421: jp = ip; ! 422: for (j=i+1; j<=last; j++) { /* Man number j */ ! 423: #if DEBUG ! 424: assert(gp==&group[j]); ! 425: assert(jp==&loc[j]); ! 426: #endif ! 427: if (*gp++ == igroup) /* group[j] == group[i] */ ! 428: jp++; ! 429: else ! 430: value += *(bdp+(*jp++)); /* boarddist[ipos][jpos] */ ! 431: } ! 432: } ! 433: return(value); ! 434: } ! 435: ! 436: /* Execute moves from list file. */ ! 437: execfile() ! 438: { ! 439: char *filename; ! 440: FILE *fp; ! 441: int count, from0, to0, from1, to1, eflag; ! 442: MOVE m; ! 443: register MOVE *mp; ! 444: ! 445: filename = &command[1]; ! 446: fp = fopen(filename, "r"); ! 447: if (fp == NULL) { ! 448: printf("Cannot open list file \"%s\"\n", filename); ! 449: return; ! 450: } ! 451: mp = &m; ! 452: eflag = 1; ! 453: while ((count = fscanf(fp, "%*d.%d%*c%d%d%*c%d", &from0, &to0, &from1, &to1)) != EOF) { ! 454: if ((count != 2) && (count != 4)) ! 455: goto done; ! 456: if (legalmove(100*from0+to0, mp)) { ! 457: dodisp(mp, 0); ! 458: domove(mp); ! 459: } ! 460: else ! 461: goto done; ! 462: if (count == 4) { ! 463: if (legalmove(100*from1+to1, mp)) { ! 464: dodisp(mp, 0); ! 465: domove(mp); ! 466: } ! 467: else ! 468: goto done; ! 469: } ! 470: } ! 471: eflag = 0; ! 472: done: ! 473: printboard(); ! 474: if (eflag) ! 475: puts("Bad list file"); ! 476: if (fclose(fp) == EOF) ! 477: printf("Cannot close list file \"%s\"\n", filename); ! 478: } ! 479: ! 480: /* Recursively find best move, searching to max depth d. */ ! 481: /* Store the move through mp (if non-NULL) and return its value. */ ! 482: /* Value less than limit means better move already known at previous level. */ ! 483: /* Value after move is from opp's point of view, hence lowest best for plr. */ ! 484: findbest(mp, d, limit) MOVE *mp; int d, limit; ! 485: { ! 486: register int n; ! 487: register MOVE *np; ! 488: int i, bestn, count; ! 489: MOVE *nextp, *bestnp; ! 490: ! 491: nextp = &nextmove[d-1][0]; ! 492: count = genmoves(nextp); ! 493: #if DEBUG ! 494: printf("findbest(%d) count=%d limit=%d:\n", d, count, limit); ! 495: #endif ! 496: if (count == 0) { /* Stalemate -- draw or loss? */ ! 497: if (mp) ! 498: mp->m_man = 0; /* To indicate stalemate */ ! 499: return(0); /* Let's call it a draw for now... */ ! 500: } ! 501: /* Find static values of next moves. */ ! 502: /* Needed for d>1 to determine WIN or LOSS positions. */ ! 503: bestnp = np = nextp; ! 504: bestn = WIN; ! 505: for (i=0; i<count; i++) { ! 506: domove(np); /* Try a move */ ! 507: np->m_val = n = value(); /* Evaluate position */ ! 508: #if DEBUG ! 509: printf("\tfrom=%d to=%d val=%d\n", np->m_from, np->m_to, n); ! 510: #endif ! 511: domove(NULL); /* And undo it */ ! 512: if (n < bestn) { ! 513: bestn = n; ! 514: bestnp = np; ! 515: if ((n == LOSS) || ((n <= limit) && (d == 1))) ! 516: goto out; /* Look no further */ ! 517: } ! 518: np++; ! 519: } ! 520: if (d > 1) { ! 521: /* If too wide, find best to look at. */ ! 522: if (count > width) { ! 523: qsort((char *)nextp, count, sizeof(MOVE), compnext); ! 524: count = width; ! 525: } ! 526: /* Find values of next moves recursively. */ ! 527: d--; /* Depth for next level */ ! 528: bestnp = np = nextp; ! 529: bestn = WIN; ! 530: for (i=0; i<count; i++) { ! 531: if (np->m_val != WIN) { ! 532: domove(np); ! 533: n = -findbest(NULL, d, -bestn); ! 534: #if DEBUG ! 535: printf("\tfrom=%d to=%d val=%d\n", np->m_from, np->m_to, n); ! 536: #endif ! 537: domove(NULL); /* And undo it */ ! 538: if (n < bestn) { ! 539: bestn = n; ! 540: bestnp = np; ! 541: if (n <= limit) ! 542: goto out; /* Look no further */ ! 543: } ! 544: } ! 545: np++; ! 546: } ! 547: } ! 548: out: ! 549: if (mp != NULL) ! 550: *mp = *bestnp; /* Structure assignment */ ! 551: #if DEBUG ! 552: printf("BEST: from=%d to=%d val=%d\n", bestnp->m_from, bestnp->m_to, bestnp->m_val); ! 553: #endif ! 554: return(bestn); ! 555: } ! 556: ! 557: /* Test for winning or losing position. */ ! 558: gameover() ! 559: { ! 560: value(); ! 561: if ((val[0] != 0) && (val[1] != 0)) ! 562: return(0); ! 563: printboard(); ! 564: if ((val[0] == 0) && (val[1] == 0)) ! 565: puts("Drawn game."); ! 566: else ! 567: printf("Player %c wins.\n", MAN(val[0])); ! 568: puts("Type i to play again or q to quit."); ! 569: return(1); ! 570: } ! 571: ! 572: /* Generate all legal moves from current position, return count. */ ! 573: genmoves(mp) MOVE *mp; ! 574: { ! 575: register int off; ! 576: register int *bp; ! 577: int i, j, k, first, last, ofirst, olast, pos, d, dir, toff, nmoves; ! 578: int *locp, *cip; ! 579: ! 580: first = firstman[plr]; ! 581: last = lastman[plr]; ! 582: ofirst = firstman[opp]; ! 583: olast = lastman[opp]; ! 584: nmoves = 0; /* Moves generated */ ! 585: locp = &loc[first]; /* loc pointer */ ! 586: for (i=first; i<=last; i++) { /* Player's man i */ ! 587: #if DEBUG ! 588: assert(locp==&loc[i]); ! 589: printf("Gen player=%d man=%d loc=%d\n", plr, i, *locp); ! 590: #endif ! 591: pos = *locp++; /* Position of i */ ! 592: cip = &cindex[pos][0]; ! 593: for (j=0; j<4; j++) { /* Direction of movement */ ! 594: d = count[*cip++]; /* Distance */ ! 595: off = offset[j]; /* Offset in given direction */ ! 596: toff = d * off; /* Total offset to target */ ! 597: dir = 0; ! 598: again: ! 599: #if DEBUG ! 600: printf("\tdir=%d dist=%d off=%d ", j+4*dir, d, off); ! 601: #endif ! 602: bp = &board[pos]; /* Ptr to pos */ ! 603: for (k=1; k<d; k++) { ! 604: bp += off; /* Next position */ ! 605: if ((*bp==EDGE) || ((*bp>=ofirst)&&(*bp<=olast))) ! 606: goto reject; /* Edge or occupied by opp */ ! 607: } ! 608: bp += off; /* Ptr to target position */ ! 609: if ((*bp==EDGE) || ((*bp>=first)&&(*bp<=last))) ! 610: goto reject; /* Edge or occupied by plr */ ! 611: /* Found legal move */ ! 612: nmoves++; ! 613: mp->m_from = pos; ! 614: mp->m_to = pos + toff; ! 615: mp->m_man = i; ! 616: mp->m_cap = *bp; ! 617: mp++; ! 618: #if DEBUG ! 619: printf("legal move to=%d cap=%d", pos+toff, *bp); ! 620: #endif ! 621: reject: ! 622: #if DEBUG ! 623: putchar('\n'); ! 624: #endif ! 625: if (dir == 0) { /* Try opposite direction */ ! 626: dir++; ! 627: off = -off; ! 628: toff = -toff; ! 629: goto again; ! 630: } ! 631: } ! 632: } ! 633: #if DEBUG ! 634: printf("genmoves returning %d moves\n", nmoves); ! 635: #endif ! 636: if (vflag) { ! 637: npos++; ! 638: ngen += ((long)nmoves); ! 639: if (nmoves > maxgen) ! 640: maxgen = nmoves; ! 641: } ! 642: return(nmoves); ! 643: } ! 644: ! 645: /* Initialize everything. */ ! 646: initialize() ! 647: { ! 648: register char *cp; ! 649: register int j; ! 650: int i, n; ! 651: int *ip; ! 652: ! 653: /* Globals. */ ! 654: ip = &board[0]; ! 655: for (i=0; i<100; i++) ! 656: *ip++ = ((i%10==0)||(i%10==9)||(i/10==0)||(i/10==9))?EDGE:0; ! 657: plr = nmove = 0; ! 658: opp = 1; ! 659: val[0] = val[1] = -1; ! 660: firstman[0] = 1; ! 661: lastman[0] = 12; ! 662: firstman[1] = 13; ! 663: lastman[1] = 24; ! 664: for (j=0; j<46; j++) ! 665: count[j] = 2; ! 666: count[0] = count[7] = count[8] = count[15] = 6; ! 667: count[16] = count[23] = count[30] = count[31] = count[38] = count[45] = 0; ! 668: ! 669: /* Initialize the printable display. */ ! 670: cp = &pboard[0][0]; ! 671: for (i=0; i<17; i++) { ! 672: for (j=0; j<33; j++) ! 673: *cp++ = ((i%2) ! 674: ? ((j%4)?SPACE:VERT) ! 675: : ! 676: ((j%4) ! 677: ? HORIZ ! 678: : ! 679: ((i==0) ! 680: ? ((j==0)?TOPL:((j==32)?TOPR:TOPM)) ! 681: : ! 682: ((i==16) ! 683: ? ((j==0)?BOTL:((j==32)?BOTR:BOTM)) ! 684: : ((j==0)?MIDL:((j==32)?MIDR:MIDM)) ! 685: )))); ! 686: *cp++ = SPACE; ! 687: *cp++ = ((i%2) ? '1' + i/2 : SPACE); ! 688: *cp++ = ((i%2) ? '0' : SPACE); ! 689: *cp++ = '\n'; ! 690: } ! 691: for (j=1; j<=8; j++) { ! 692: *cp++ = SPACE; ! 693: *cp++ = SPACE; ! 694: *cp++ = '0' + j; ! 695: *cp++ = SPACE; ! 696: } ! 697: *cp++ = '\0'; ! 698: ! 699: /* Initial positions. */ ! 700: n = 1; /* Man number */ ! 701: for (i=12; i<=17; i++) { ! 702: display (MAN0, i); ! 703: loc[n] = i; ! 704: board[i] = n++; ! 705: } ! 706: for (i=82; i<=87; i++) { ! 707: display (MAN0, i); ! 708: loc[n] = i; ! 709: board[i] = n++; ! 710: } ! 711: for (i=21; i<=71; i+=10) { ! 712: display (MAN1, i); ! 713: loc[n] = i; ! 714: board[i] = n++; ! 715: } ! 716: for (i=28; i<=78; i+=10) { ! 717: display (MAN1, i); ! 718: loc[n] = i; ! 719: board[i] = n++; ! 720: } ! 721: ! 722: printf("%c moves first.\n", MAN0); ! 723: printboard(); ! 724: } ! 725: ! 726: /* Test whether n is legal move and fill in *mp accordingly. */ ! 727: legalmove(n,mp) int n; MOVE *mp; ! 728: { ! 729: register int *bp; ! 730: register int i; ! 731: int from, to, fromx, fromy, tox, toy, dir, off, dist; ! 732: ! 733: mp->m_from = from = n/100; ! 734: mp->m_to = to = n%100; ! 735: mp->m_man = board[from]; ! 736: if ((board[from]<firstman[plr]) || (board[from]>lastman[plr])) ! 737: return(0); ! 738: mp->m_cap = board[to]; ! 739: fromx = from/10; ! 740: fromy = from%10; ! 741: tox = to/10; ! 742: toy = to%10; ! 743: if (fromx==tox) dir = 0; ! 744: else if (fromy==toy) dir = 1; ! 745: else if (fromx+fromy==tox+toy) dir = 2; ! 746: else if (fromx-fromy==tox-toy) dir = 3; ! 747: else return(0); ! 748: off = offset[dir]; ! 749: if (from>to) ! 750: off = -off; ! 751: dist = count[cindex[from][dir]]; ! 752: bp = &board[from]; ! 753: for (i=1; i<dist; i++) { ! 754: bp += off; ! 755: if ((*bp==EDGE)||((*bp>=firstman[opp])&&(*bp<=lastman[opp]))) ! 756: return(0); ! 757: } ! 758: bp += off; ! 759: if ((*bp==EDGE)||((*bp>=firstman[plr])&&(*bp<=lastman[plr]))||(bp!=&board[to])) ! 760: return(0); ! 761: return(1); ! 762: } ! 763: ! 764: /* List game. */ ! 765: listgame() ! 766: { ! 767: register MOVE *mp; ! 768: register int i; ! 769: char c; ! 770: FILE *fp = stdout; ! 771: char *filename = &command[1]; ! 772: ! 773: if (*filename) { ! 774: fp = fopen(filename, "w"); ! 775: if (fp == NULL) { ! 776: printf("Cannot open list file \"%s\"\n", filename); ! 777: return; ! 778: } ! 779: } ! 780: mp = &movelist[0]; ! 781: for (i=0; i<nmove; i++) { ! 782: if (i%2 == 0) ! 783: fprintf(fp, "\n%d. ", i/2+1); ! 784: c = (mp->m_cap) ? '*' : '-'; ! 785: fprintf(fp, "%d%c%d ", mp->m_from, c, mp->m_to); ! 786: mp++; ! 787: } ! 788: putc('\n', fp); ! 789: if ((fp != stdout) && (fclose(fp) == EOF)) ! 790: printf("Cannot close list file \"%s\"\n", filename); ! 791: } ! 792: ! 793: /* Print the board. */ ! 794: printboard() ! 795: { ! 796: puts(pboard); ! 797: } ! 798: ! 799: /* Set parameter (depth or width). */ ! 800: setparam(sp, s, max) int *sp; char *s; int max; ! 801: { ! 802: register int i; ! 803: ! 804: printf("Old search %s is %d.\n", s, *sp); ! 805: if (command[1]=='\0') ! 806: return; ! 807: i = atoi(&command[1]); ! 808: if (i < 1 || i > max) { ! 809: printf("%s arg must be between 1 and %d -- try again.\n", s, max); ! 810: return; ! 811: } ! 812: *sp = i; ! 813: printf("New search %s is %d.\n", s, *sp); ! 814: } ! 815: ! 816: /* Initialize readonly global data. */ ! 817: staticinit() ! 818: { ! 819: register int *ip; ! 820: register int j; ! 821: int i, ix, iy, dx, dy, n; ! 822: ! 823: offset[0] = 1; ! 824: offset[1] = 10; ! 825: offset[2] = 9; ! 826: offset[3] = 11; ! 827: ip = &boarddist[0][0]; ! 828: for (i=0; i<100; i++) { ! 829: ix = i/10; ! 830: iy = i%10; ! 831: for (j=0; j<100; j++) { ! 832: dx = ix - j/10; /* x distance i to j */ ! 833: dy = iy - j%10; /* y distance i to j */ ! 834: if (dx < 0) ! 835: dx = -dx; ! 836: if (dy < 0) ! 837: dy = -dy; ! 838: if (dx < dy) ! 839: dx = dy; ! 840: *ip++ = --dx; ! 841: } ! 842: } ! 843: for (i=0; i<8; i++) ! 844: for (j=0; j<8; j++) { ! 845: n = 10*(i+1) + j+1; ! 846: cindex[n][0] = i; ! 847: cindex[n][1] = 8+j; ! 848: cindex[n][2] = 16 + i + j; ! 849: cindex[n][3] = 38 + i - j; ! 850: } ! 851: } ! 852: ! 853: /* Return value of current position. */ ! 854: /* Reevaluate a position only if it has changed. */ ! 855: value() ! 856: { ! 857: register int pval, oval; ! 858: ! 859: neval++; ! 860: pval = val[plr]; ! 861: oval = val[opp]; ! 862: if (pval < 0) ! 863: pval = val[plr] = eval(plr); ! 864: if (oval < 0) ! 865: oval = val[opp] = eval(opp); ! 866: if (pval == 0) ! 867: return((oval) ? WIN : 0); ! 868: return((oval) ? oval-pval : LOSS); ! 869: } ! 870: ! 871: /* end of lines.c */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.