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