1: 2: static char sccsid[] = " backgammon.c 4.1 82/10/24 "; 3: 4: /* 5: ** The game of Backgammon 6: */ 7: 8: #include <stdio.h> 9: 10: #define WHITE 0 11: #define BROWN 1 12: #define NIL (-1) 13: #define MAXGMOV 10 14: #define MAXIMOVES 1000 15: #define RULES "/usr/games/lib/backrules" 16: 17: char level; /*'b'=beginner, 'i'=intermediate, 'e'=expert*/ 18: 19: int die1; 20: int die2; 21: int i; 22: int j; 23: int l; 24: int m; 25: int pflg = 1; 26: int nobroll = 0; 27: int count; 28: int imoves; 29: int goodmoves[MAXGMOV]; 30: int probmoves[MAXGMOV]; 31: 32: int brown[] = { /* brown position table */ 33: 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 34: 0, 0, 0, 0, 3, 0, 5, 0, 0, 0, 0, 0, 35: 0, 0, 0, 0, 0, 0 36: }; 37: 38: int white[] = { /* white position table */ 39: 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 40: 0, 0, 0, 0, 3, 0, 5, 0, 0, 0, 0, 0, 41: 0, 0, 0, 0, 0, 0 42: }; 43: 44: int probability[] = { 45: 0, 11, 12, 13, 14, 15, 16, 46: 06, 05, 04, 03, 02, 01 47: }; 48: 49: struct { 50: int pos[4]; 51: int mov[4]; 52: } moves[MAXIMOVES]; 53: 54: main() 55: { 56: int go[5], tvec[2]; 57: int k, n, pid, ret, rpid, t; 58: char s[100]; 59: 60: srand(time(0)); 61: go[5] = NIL; 62: fprintf(stdout, "Instructions? "); 63: gets(s); 64: if(*s == 'y') 65: instructions(); 66: putchar('\n'); 67: fprintf(stdout, "Opponent's level: b - beginner,\n"); 68: fprintf(stdout, "i - intermediate, e - expert? "); 69: level='e'; 70: gets(s); 71: if(*s == 'b') 72: level = 'b'; 73: else if(*s == 'i') 74: level = 'i'; 75: putchar('\n'); 76: fprintf(stdout, "You will play brown.\n\n"); 77: fprintf(stdout, "Would you like to roll your own dice? "); 78: gets(s); 79: putchar('\n'); 80: if(*s == 'y') 81: nobroll = 1; 82: fprintf(stdout, "Would you like to go first? "); 83: gets(s); 84: putchar('\n'); 85: if(*s == 'y') 86: goto nowhmove; 87: whitesmv: 88: roll(WHITE); 89: fprintf(stdout, "white rolls %d, %d\n", die1, die2); 90: fprintf(stdout, "white's move is:"); 91: if(nextmove(white, brown) == NIL) 92: goto nowhmove; 93: if(piececount(white, 0, 24) == 0){ 94: fprintf(stdout, "White wins"); 95: if(piececount(brown, 0, 6) != 0) 96: fprintf(stdout, " with a Backgammon!\n"); 97: else if (piececount(brown, 0, 24) == 24) 98: fprintf(stdout, " with a Gammon.\n"); 99: else 100: fprintf(stdout, ".\n"); 101: exit(0); 102: } 103: nowhmove: 104: if(pflg) 105: prtbrd(); 106: roll(BROWN); 107: retry: 108: fprintf(stdout, "\nYour roll is %d %d\n", die1, die2); 109: fprintf(stdout, "Move? "); 110: gets(s); 111: switch(*s) { 112: case '\0': /* empty line */ 113: fprintf(stdout, "Brown's move skipped.\n"); 114: goto whitesmv; 115: 116: case 'b': /* how many beared off? */ 117: fprintf(stdout, "Brown: %d\n", piececount(brown, 0, 24) - 15); 118: fprintf(stdout, "White: %d\n", piececount(white, 0, 24) - 15); 119: goto retry; 120: 121: case 'p': /* print board */ 122: prtbrd(); 123: goto retry; 124: 125: case 's': /* stop auto printing of board */ 126: pflg = 0; 127: goto retry; 128: 129: case 'r': /* resume auto printing */ 130: pflg = 1; 131: goto retry; 132: 133: case 'm': /* print possible moves */ 134: pmoves(); 135: goto retry; 136: 137: case 'q': /* i give up */ 138: exit(0); 139: 140: case '!': /* escape to Shell */ 141: if(s[1] != '\0') 142: system(s+1); 143: else if((pid = fork()) == 0) { 144: execl("/bin/sh", "sh", "-", 0); 145: fprintf(stderr, "back: cannot exec /bin/sh!\n"); 146: exit(2); 147: } 148: while((rpid = wait(&ret)) != pid && rpid != -1) 149: ; 150: goto retry; 151: 152: case '?': /* well, what can i do? */ 153: fprintf(stdout, "<newline> skip this move\n"); 154: fprintf(stdout, "b number beared off\n"); 155: fprintf(stdout, "p print board\n"); 156: fprintf(stdout, "q quit\n"); 157: fprintf(stdout, "r resume auto print of board\n"); 158: fprintf(stdout, "s stop auto print of board\n"); 159: fprintf(stdout, "! escape to Shell\n"); 160: goto retry; 161: } 162: n = sscanf(s,"%d%d%d%d%d",&go[0],&go[1],&go[2],&go[3],&go[4]); 163: if((die1 != die2 && n > 2) || n > 4){ 164: fprintf(stdout, "Too many moves.\n"); 165: goto retry; 166: } 167: go[n] = NIL; 168: if(*s=='-'){ 169: go[0]= -go[0]; 170: t=die1; 171: die1=die2; 172: die2=t; 173: } 174: for(k = 0; k < n; k++){ 175: if(0 <= go[k] && go[k] <= 24) 176: continue; 177: else{ 178: fprintf(stdout, "Move %d illegal.\n", go[k]); 179: goto retry; 180: } 181: } 182: if(play(brown, white, go)) 183: goto retry; 184: if(piececount(brown, 0, 24) == 0){ 185: fprintf(stdout, "Brown wins"); 186: if(piececount(white, 0, 6) != 0) 187: fprintf(stdout, " with a Backgammon.\n"); 188: else if(piececount(white, 0, 24) == 24) 189: fprintf(stdout, " with a gammon.\n"); 190: else 191: fprintf(stdout, ".\n"); 192: exit(0); 193: } 194: goto whitesmv; 195: } 196: 197: play(player,playee,pos) 198: int *player,*playee,pos[]; 199: { 200: int k, n, die, ipos; 201: 202: for(k=0; k < player[0]; k++){ /*blots on player[0] must be moved first*/ 203: if(pos[k] == NIL) 204: break; 205: if(pos[k] != 0){ 206: fprintf(stdout, "Stone on bar must be moved first.\n"); 207: return(NIL); 208: } 209: } 210: for(k = 0; (ipos=pos[k]) != NIL; k++){ 211: die = k?die2:die1; 212: n = 25-ipos-die; 213: if(player[ipos] == 0) 214: goto badmove; 215: if(n > 0 && playee[n] >= 2) 216: goto badmove; 217: if(n <= 0){ 218: if(piececount(player,0,18) != 0) 219: goto badmove; 220: if((ipos+die) != 25 && piececount(player,19,24-die)!=0) 221: goto badmove; 222: } 223: player[ipos]--; 224: player[ipos+die]++; 225: } 226: for(k = 0; pos[k] != NIL; k++){ 227: die = k?die2:die1; 228: n = 25-pos[k]-die; 229: if(n>0 && playee[n]==1){ 230: playee[n]=0; 231: playee[0]++; 232: } 233: } 234: return(0); 235: 236: badmove: 237: fprintf(stdout, "Move %d illegal.\n", ipos); 238: while(k--){ 239: die=k?die2:die1; 240: player[pos[k]]++; 241: player[pos[k]+die]--; 242: } 243: return(NIL); 244: } 245: nextmove(player,playee) 246: int *player,*playee; 247: { 248: int k; 249: 250: imoves=0; 251: movegen(player,playee); 252: if(die1!=die2){ 253: k=die1; 254: die1=die2; 255: die2=k; 256: movegen(player,playee); 257: } 258: if(imoves==0){ 259: fprintf(stdout, "no move possible.\n"); 260: return(NIL); 261: } 262: k=strategy(player,playee); /*select kth possible move*/ 263: prtmov(k); 264: update(player,playee,k); 265: return(0); 266: } 267: prtmov(k) 268: int k; 269: { 270: int n; 271: 272: if(k == NIL) 273: fprintf(stdout, "No move possible\n"); 274: else for(n = 0; n < 4; n++){ 275: if(moves[k].pos[n] == NIL) 276: break; 277: fprintf(stdout, " %d, %d",25-moves[k].pos[n],moves[k].mov[n]); 278: } 279: fprintf(stdout, "\n"); 280: } 281: update(player,playee,k) 282: int *player,*playee,k; 283: { 284: int n,t; 285: 286: for(n = 0; n < 4; n++){ 287: if(moves[k].pos[n] == NIL) 288: break; 289: player[moves[k].pos[n]]--; 290: player[moves[k].pos[n]+moves[k].mov[n]]++; 291: t=25-moves[k].pos[n]-moves[k].mov[n]; 292: if(t>0 && playee[t]==1){ 293: playee[0]++; 294: playee[t]--; 295: } 296: } 297: } 298: piececount(player,startrow,endrow) 299: int *player,startrow,endrow; 300: { 301: int sum; 302: 303: sum=0; 304: while(startrow <= endrow) 305: sum += player[startrow++]; 306: return(sum); 307: } 308: pmoves() 309: { 310: int i1, i2; 311: 312: fprintf(stdout, "Possible moves are:\n"); 313: for(i1 = 0; i1 < imoves; i1++){ 314: fprintf(stdout, "\n%d",i1); 315: for (i2 = 0; i2<4; i2++){ 316: if(moves[i1].pos[i2] == NIL) 317: break; 318: fprintf(stdout, "%d, %d",moves[i1].pos[i2],moves[i1].mov[i2]); 319: } 320: } 321: fprintf(stdout, "\n"); 322: } 323: 324: roll(who) 325: { 326: register n; 327: char s[10]; 328: 329: if(who == BROWN && nobroll) { 330: fprintf(stdout, "Roll? "); 331: gets(s); 332: n = sscanf(s, "%d%d", &die1, &die2); 333: if(n != 2 || die1 < 1 || die1 > 6 || die2 < 1 || die2 > 6) 334: fprintf(stdout, "Illegal - I'll do it!\n"); 335: else 336: return; 337: } 338: die1 = ((rand()>>8) % 6) + 1; 339: die2 = ((rand()>>8) % 6) + 1; 340: } 341: 342: movegen(mover,movee) 343: int *mover,*movee; 344: { 345: int k; 346: 347: for(i = 0; i <= 24; i++){ 348: count = 0; 349: if(mover[i] == 0) 350: continue; 351: if((k=25-i-die1) > 0 && movee[k] >= 2) 352: if(mover[0] > 0) 353: break; 354: else 355: continue; 356: if(k <= 0){ 357: if(piececount(mover, 0, 18) != 0) 358: break; 359: if((i+die1) != 25 && piececount(mover,19,i-1) != 0) 360: break; 361: } 362: mover[i]--; 363: mover[i+die1]++; 364: count = 1; 365: for(j = 0; j <= 24; j++){ 366: if(mover[j]==0) 367: continue; 368: if((k=25-j-die2) > 0 && movee[k] >= 2) 369: if(mover[0] > 0) 370: break; 371: else 372: continue; 373: if(k <= 0){ 374: if(piececount(mover,0,18) != 0) 375: break; 376: if((j+die2) != 25 && piececount(mover,19,j-1) != 0) 377: break; 378: } 379: mover[j]--; 380: mover[j+die2]++; 381: count = 2; 382: if(die1 != die2){ 383: moverecord(mover); 384: if(mover[0] > 0) 385: break; 386: else 387: continue; 388: } 389: for(l = 0; l <= 24; l++){ 390: if(mover[l] == 0) 391: continue; 392: if((k=25-l-die1) > 0 && movee[k] >= 2) 393: if(mover[0] > 0) 394: break; 395: else 396: continue; 397: if(k <= 0){ 398: if(piececount(mover, 0, 18) != 0) 399: break; 400: if((l+die2) != 25 && piececount(mover,19,l-1) != 0) 401: break; 402: } 403: mover[l]--; 404: mover[l+die1]++; 405: count=3; 406: for(m=0;m<=24;m++){ 407: if(mover[m]==0) 408: continue; 409: if((k=25-m-die1) >= 0 && movee[k] >= 2) 410: if(mover[0] > 0) 411: break; 412: else 413: continue; 414: if(k <= 0){ 415: if(piececount(mover,0,18) != 0) 416: break; 417: if((m+die2) != 25 && piececount(mover,19,m-1) != 0) 418: break; 419: } 420: count=4; 421: moverecord(mover); 422: if(mover[0] > 0) 423: break; 424: } 425: if(count == 3) 426: moverecord(mover); 427: else{ 428: mover[l]++; 429: mover[l+die1]--; 430: } 431: if(mover[0] > 0) 432: break; 433: } 434: if(count == 2) 435: moverecord(mover); 436: else{ 437: mover[j]++; 438: mover[j+die1]--; 439: } 440: if(mover[0] > 0) 441: break; 442: } 443: if(count == 1) 444: moverecord(mover); 445: else{ 446: mover[i]++; 447: mover[i+die1]--; 448: } 449: if(mover[0] > 0) 450: break; 451: } 452: } 453: moverecord(mover) 454: int *mover; 455: { 456: int t; 457: 458: if(imoves < MAXIMOVES) { 459: for(t = 0; t <= 3; t++) 460: moves[imoves].pos[t] = NIL; 461: switch(count) { 462: case 4: 463: moves[imoves].pos[3]=m; 464: moves[imoves].mov[3]=die1; 465: 466: case 3: 467: moves[imoves].pos[2]=l; 468: moves[imoves].mov[2]=die1; 469: 470: case 2: 471: moves[imoves].pos[1]=j; 472: moves[imoves].mov[1]=die2; 473: 474: case 1: 475: moves[imoves].pos[0]=i; 476: moves[imoves].mov[0]=die1; 477: imoves++; 478: } 479: } 480: switch(count) { 481: case 4: 482: break; 483: 484: case 3: 485: mover[l]++; 486: mover[l+die1]--; 487: break; 488: 489: case 2: 490: mover[j]++; 491: mover[j+die2]--; 492: break; 493: 494: case 1: 495: mover[i]++; 496: mover[i+die1]--; 497: } 498: } 499: 500: strategy(player,playee) 501: int *player,*playee; 502: { 503: int k, n, nn, bestval, moveval, prob; 504: 505: n = 0; 506: if(imoves == 0) 507: return(NIL); 508: goodmoves[0] = NIL; 509: bestval = -32000; 510: for(k = 0; k < imoves; k++){ 511: if((moveval=eval(player,playee,k,&prob)) < bestval) 512: continue; 513: if(moveval > bestval){ 514: bestval = moveval; 515: n = 0; 516: } 517: if(n<MAXGMOV){ 518: goodmoves[n]=k; 519: probmoves[n++]=prob; 520: } 521: } 522: if(level=='e' && n>1){ 523: nn=n; 524: n=0; 525: prob=32000; 526: for(k = 0; k < nn; k++){ 527: if((moveval=probmoves[k]) > prob) 528: continue; 529: if(moveval<prob){ 530: prob=moveval; 531: n=0; 532: } 533: goodmoves[n]=goodmoves[k]; 534: probmoves[n++]=probmoves[k]; 535: } 536: } 537: return(goodmoves[(rand()>>4)%n]); 538: } 539: 540: eval(player,playee,k,prob) 541: int *player,*playee,k,*prob; 542: { 543: int newtry[31], newother[31], *r, *q, *p, n, sum, first; 544: int ii, lastwhite, lastbrown; 545: 546: *prob = sum = 0; 547: r = player+25; 548: p = newtry; 549: q = newother; 550: while(player<r){ 551: *p++= *player++; 552: *q++= *playee++; 553: } 554: q=newtry+31; 555: for(p = newtry+25; p < q; p++) /* zero out spaces for hit pieces */ 556: *p = 0; 557: for(n = 0; n < 4; n++){ 558: if(moves[k].pos[n] == NIL) 559: break; 560: newtry[moves[k].pos[n]]--; 561: newtry[ii=moves[k].pos[n]+moves[k].mov[n]]++; 562: if(ii<25 && newother[25-ii]==1){ 563: newother[25-ii]=0; 564: newother[0]++; 565: if(ii<=15 && level=='e') /* hit if near other's home */ 566: sum++; 567: } 568: } 569: for(lastbrown = 0; newother[lastbrown] == 0; lastbrown++); 570: ; 571: for(lastwhite = 0; newtry[lastwhite] == 0; lastwhite++) 572: ; 573: lastwhite = 25-lastwhite; 574: if(lastwhite<=6 && lastwhite<lastbrown) 575: sum=1000; 576: /* experts running game. */ 577: /* first priority is to */ 578: /* get all pieces into */ 579: /* white's home */ 580: if(lastwhite<lastbrown && level=='e' && lastwhite>6) { 581: for(sum = 1000; lastwhite > 6; lastwhite--) 582: sum = sum-lastwhite*newtry[25-lastwhite]; 583: } 584: for(first = 0; first < 25; first++) 585: if(newother[first] != 0) /*find other's first piece*/ 586: break; 587: q = newtry+25; 588: for(p = newtry+1; p < q;) /* blocked points are good */ 589: if(*p++ > 1) 590: sum++; 591: if(first > 5) { /* only stress removing pieces if */ 592: /* homeboard cannot be hit */ 593: q = newtry+31; 594: p=newtry+25; 595: for(n = 6; p < q; n--) 596: sum += *p++ * n; /*remove pieces, but just barely*/ 597: } 598: if(level != 'b'){ 599: r = newtry+25-first; /*singles past this point can't be hit*/ 600: for(p = newtry+7; p < r; ) 601: if(*p++ == 1) /*singles are bad after 1st 6 points if they can be hit*/ 602: sum--; 603: q = newtry+3; 604: for(p = newtry; p < q; ) /*bad to be on 1st three points*/ 605: sum -= *p++; 606: } 607: 608: for(n = 1; n <= 4; n++) 609: *prob += n*getprob(newtry,newother,6*n-5,6*n); 610: return(sum); 611: } 612: instructions() 613: { 614: register fd, r; 615: char buf[BUFSIZ]; 616: 617: if((fd = open(RULES, 0)) < 0) { 618: fprintf(stderr, "back: cannot open %s\n", RULES); 619: return; 620: } 621: while(r = read(fd, buf, BUFSIZ)) 622: write(1, buf, r); 623: } 624: 625: getprob(player,playee,start,finish) 626: int *player,*playee,start,finish; 627: { /*returns the probability (times 102) that any 628: pieces belonging to 'player' and lying between 629: his points 'start' and 'finish' will be hit 630: by a piece belonging to playee 631: */ 632: int k, n, sum; 633: 634: sum = 0; 635: for(; start <= finish; start++){ 636: if(player[start] == 1){ 637: for(k = 1; k <= 12; k++){ 638: if((n=25-start-k) < 0) 639: break; 640: if(playee[n] != 0) 641: sum += probability[k]; 642: } 643: } 644: } 645: return(sum); 646: } 647: prtbrd() 648: { 649: int k; 650: static char undersc[]="______________________________________________________"; 651: 652: fprintf(stdout, "White's Home\n%s\r",undersc); 653: for(k = 1; k <= 6; k++) 654: fprintf(stdout, "%4d",k); 655: fprintf(stdout, " "); 656: for(k = 7; k <= 12; k++) 657: fprintf(stdout, "%4d",k); 658: putchar('\n'); 659: numline(brown, white, 1, 6); 660: fprintf(stdout, " "); 661: numline(brown, white, 7, 12); 662: putchar('\n'); 663: colorline(brown, 'B', white, 'W', 1, 6); 664: fprintf(stdout, " "); 665: colorline(brown, 'B', white, 'W', 7, 12); 666: putchar('\n'); 667: if(white[0] != 0) 668: fprintf(stdout, "%28dW\n",white[0]); 669: else 670: putchar('\n'); 671: if(brown[0] != 0) 672: fprintf(stdout, "%28dB\n", brown[0]); 673: else 674: putchar('\n'); 675: colorline(white, 'W', brown, 'B', 1, 6); 676: fprintf(stdout, " "); 677: colorline(white, 'W', brown, 'B', 7, 12); 678: fprintf(stdout, "\n%s\r",undersc); 679: numline(white, brown, 1, 6); 680: fprintf(stdout, " "); 681: numline(white, brown, 7, 12); 682: putchar('\n'); 683: for(k = 24; k >= 19; k--) 684: fprintf(stdout, "%4d",k); 685: fprintf(stdout, " "); 686: for(k = 18; k >= 13; k--) 687: fprintf(stdout, "%4d",k); 688: fprintf(stdout, "\nBrown's Home\n\n\n\n\n"); 689: } 690: numline(upcol,downcol,start,fin) 691: int *upcol,*downcol,start,fin; 692: { 693: int k, n; 694: 695: for(k = start; k <= fin; k++){ 696: if((n = upcol[k]) != 0 || (n = downcol[25-k]) != 0) 697: fprintf(stdout, "%4d", n); 698: else 699: fprintf(stdout, " "); 700: } 701: } 702: colorline(upcol,c1,downcol,c2,start,fin) 703: int *upcol,*downcol,start,fin; 704: char c1,c2; 705: { 706: int k; 707: char c; 708: 709: for(k = start; k <= fin; k++){ 710: c = ' '; 711: if(upcol[k] != 0) 712: c = c1; 713: if(downcol[25-k] != 0) 714: c = c2; 715: fprintf(stdout, " %c",c); 716: } 717: }