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