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 } 718