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