UNIX 7th Ed. - /usr/src/games/backgammon.c

   1: # include <stdio.h>
   2: 
   3: #
   4: #define NIL (-1)
   5: #define MAXGMOV 10
   6: #define MAXIMOVES 1000
   7:     char level;     /*'b'=beginner, 'i'=intermediate, 'e'=expert*/
   8: int die1;
   9: int die2;
  10: int i;
  11: int j;
  12: int l;
  13: int m;
  14: int count;
  15: int red[]     {0,2,0,0,0,0,0,0,0,0,0,0,5,
  16:          0,0,0,0,3,0,5,0,0,0,0,0,
  17:          0,0,0,0,0,0};
  18: int white[]   {0,2,0,0,0,0,0,0,0,0,0,0,5,
  19:          0,0,0,0,3,0,5,0,0,0,0,0,
  20:          0,0,0,0,0,0};
  21: int probability[]{0,11,12,13,14,15,16,
  22:             06,05,04,03,02,01};
  23: int imoves;
  24: int goodmoves[MAXGMOV] ;
  25: int probmoves[MAXGMOV] ;
  26: struct {int pos[4],mov[4];} moves[MAXIMOVES] ;
  27: 
  28: main()
  29: {
  30:     int t,k,n,go[5];
  31:     char s[100];
  32:     go[5]=NIL;
  33:     srand();
  34:     printf( "Do you want instructions? Type 'y' for yes,\n");
  35:     printf( "anything else means no.?? ");
  36:     getstr(s);
  37:     if(*s=='y')instructions();
  38:     printf( "Choose the level of your oppponent.\n");
  39:     printf( "Type 'b' for beginner, or 'i' for intermediate.\n");
  40:     printf( "Anything else gets you an expert.?? ");
  41:     level='e';
  42:     getstr(s);
  43:     if(*s=='b')level='b';
  44:     else if(*s=='i')level='i';
  45:     printf( "You will play red. Do you wan't to move first?\n");
  46:     printf( "Type 'y' for yes, anything else means no.?? ");
  47:     getstr(s);
  48:     if(*s=='y')goto nowhmove;
  49: whitesmv:
  50:     roll();
  51:     printf( "white rolls %d,%d\n",die1,die2);
  52:     printf( "white's move is:");
  53:     if(nextmove(white,red)==NIL)goto nowhmove;
  54:     if(piececount(white,0,24)==0){
  55:         printf( "White wins\n");
  56:         printf( "Aren't you ashamed. You've been beaten by a computer.\n");
  57:         exit();
  58:     }
  59: nowhmove:
  60:     prtbrd();
  61: 
  62:     roll();
  63: retry:
  64:     printf( "your roll is %d,  %d\n",die1,die2);
  65:     printf( "your move, please?? ");
  66:     getstr(s);
  67:     if(*s==0){
  68:         printf( "red's move skipped\n");
  69:         goto whitesmv;
  70:     }
  71:     n=sscanf(s,"%d%d%d%d%d",&go[0],&go[1],&go[2],&go[3],&go[4]);
  72:     if((die1!=die2&&n>2)||n>4){
  73:         printf( "you've made too many moves\n");
  74:         goto retry;
  75:     }
  76:     go[n]=NIL;
  77:     if(*s=='-'){
  78:         go[0]= -go[0];
  79:         t=die1;
  80:         die1=die2;
  81:         die2=t;
  82:     }
  83:     for(k=0;k<n;k++){
  84:         if(0<=go[k] && go[k]<=24)continue;
  85:         else{
  86:         printf( "move %d is illegal\n",go[k]);
  87:         goto retry;
  88:         }
  89:     }
  90:     if(play(red,white,go))goto retry;
  91:     if(piececount(red,0,24)==0){
  92:         printf( "Red wins.\n");
  93:         printf( "Congratulations! You have just defeated a dumb machine.\n");
  94:         exit();
  95:     }
  96:     goto whitesmv;
  97: }
  98: 
  99: getstr(s)
 100: char *s;
 101: {
 102:     while((*s=getchar())!='\n')s++;
 103:     *s=0;
 104: }
 105: 
 106: play(player,playee,pos)
 107: int *player,*playee,pos[];
 108: {
 109:     int k,n,die,ipos;
 110:     for(k=0;k<player[0];k++){  /*blots on player[0] must be moved first*/
 111:         if(pos[k]==NIL)break;
 112:         if(pos[k]!=0){
 113:         printf( "piece on position 0 must be moved first\n");
 114:         return(-1);
 115:         }
 116:     }
 117:     for(k=0;(ipos=pos[k])!=NIL;k++){
 118:         die=k?die2:die1;
 119:         n=25-ipos-die;
 120:         if(player[ipos]==0)goto badmove;
 121:         if(n>0&&playee[n]>=2)goto badmove;
 122:         if(n<=0){
 123:         if(piececount(player,0,18)!=0)goto badmove;
 124:         if((ipos+die)!=25&&
 125:             piececount(player,19,24-die)!=0)goto badmove;
 126:         }
 127:         player[ipos]--;
 128:         player[ipos+die]++;
 129:     }
 130:     for(k=0;pos[k]!=NIL;k++){
 131:         die=k?die2:die1;
 132:         n=25-pos[k]-die;
 133:         if(n>0 && playee[n]==1){
 134:         playee[n]=0;
 135:         playee[0]++;
 136:         }
 137:     }
 138:     return(0);
 139: 
 140: badmove:
 141:     printf( "Move %d is not legal.\n",ipos);
 142:     while(k--){
 143:         die=k?die2:die1;
 144:         player[pos[k]]++;
 145:         player[pos[k]+die]--;
 146:     }
 147:     return(-1);
 148: }
 149: nextmove(player,playee)
 150: int *player,*playee;
 151: {
 152:     int k;
 153:     imoves=0;
 154:     movegen(player,playee);
 155:     if(die1!=die2){
 156:     k=die1;
 157:     die1=die2;
 158:     die2=k;
 159:     movegen(player,playee);
 160:     }
 161:     if(imoves==0){
 162:         printf( "roll was %d,%d; no white move possible\n",die1,die2);
 163:         return(NIL);
 164:     }
 165:     k=strategy(player,playee);      /*select kth possible move*/
 166:     prtmov(k);
 167:     update(player,playee,k);
 168:     return(0);
 169: }
 170: prtmov(k)
 171: int k;
 172: {
 173:     int n;
 174:     if(k==NIL)printf( "no move possible\n");
 175:     else for(n=0;n<4;n++){
 176:         if(moves[k].pos[n]==NIL)break;
 177:         printf( "    %d, %d",25-moves[k].pos[n],moves[k].mov[n]);
 178:     }
 179:     printf( "\n");
 180: }
 181: update(player,playee,k)
 182: int *player,*playee,k;
 183: {
 184:     int n,t;
 185:     for(n=0;n<4;n++){
 186:         if(moves[k].pos[n]==NIL)break;
 187:         player[moves[k].pos[n]]--;
 188:         player[moves[k].pos[n]+moves[k].mov[n]]++;
 189:         t=25-moves[k].pos[n]-moves[k].mov[n];
 190:         if(t>0 && playee[t]==1){
 191:         playee[0]++;
 192:         playee[t]--;
 193:         }
 194:     }
 195: }
 196: piececount(player,startrow,endrow)
 197: int *player,startrow,endrow;
 198: {
 199:     int sum;
 200:     sum=0;
 201:     while(startrow<=endrow)
 202:     sum=+player[startrow++];
 203:     return(sum);
 204: }
 205: /*
 206: prtmovs()
 207: {
 208: 	int i1,i2;
 209: 	printf( "possible moves are\n");
 210: 	for(i1=0;i1<imoves;i1++){
 211: 		printf( "\n%d",i1);
 212: 		for(i2=0;i2<4;i2++){
 213: 			if(moves[i1].pos[i2]==NIL)break;
 214: 			printf( "%d, %d",moves[i1].pos[i2],moves[i1].mov[i2]);
 215: 		}
 216: 	}
 217: 	printf( "\n");
 218: }
 219: */
 220: 
 221: roll()
 222: {
 223:     extern int die1,die2;
 224:     die1=(rand()>>8)%6+1;
 225:     die2=(rand()>>8)%6+1;
 226: }
 227: 
 228: movegen(mover,movee)
 229: int *mover,*movee;
 230: {
 231:     extern int i,j,l,m,count;
 232:     extern int die1,die2;
 233:     int k;
 234:     for(i=0;i<=24;i++){
 235:         count=0;
 236:         if(mover[i]==0)continue;
 237:         if((k=25-i-die1)>0&&movee[k]>=2)
 238:             if(mover[0]>0)break;
 239:             else continue;
 240:         if(k<=0){
 241:             if(piececount(mover,0,18)!=0)break;
 242:             if((i+die1)!=25&&
 243:                 piececount(mover,19,24-die1)!=0)break;
 244:         }
 245:         mover[i]--;
 246:         mover[i+die1]++;
 247:         count=1;
 248:         for(j=0;j<=24;j++){
 249:             if(mover[j]==0)continue;
 250:             if((k=25-j-die2)>0&&movee[k]>=2)
 251:                 if(mover[0]>0)break;
 252:                 else continue;
 253:             if(k<=0){
 254:                 if(piececount(mover,0,18)!=0)break;
 255:                 if((j+die2)!=25&&
 256:                     piececount(mover,19,24-die2)!=0)break;
 257:             }
 258:             mover[j]--;
 259:             mover[j+die2]++;
 260:             count=2;
 261:             if(die1!=die2){
 262:                 moverecord(mover);
 263:                 if(mover[0]>0)break;
 264:                 else continue;
 265:             }
 266:             for(l=0;l<=24;l++){
 267:                 if(mover[l]==0)continue;
 268:                 if((k=25-l-die1)>0&&movee[k]>=2)
 269:                 if(mover[0]>0)break;
 270:                 else continue;
 271:                 if(k<=0){
 272:                 if(piececount(mover,0,18)!=0)break;
 273:                 if((l+die2)!=25&&
 274:                     piececount(mover,19,24-die1)!=0)break;
 275:                 }
 276:                 mover[l]--;
 277:                 mover[l+die1]++;
 278:                 count=3;
 279:                 for(m=0;m<=24;m++){
 280:                 if(mover[m]==0)continue;
 281:                 if((k=25-m-die1)>=0&&movee[k]>=2)
 282:                     if(mover[0]>0)break;
 283:                     else continue;
 284:                 if(k<=0){
 285:                     if(piececount(mover,0,18)!=0)break;
 286:                     if((m+die2)!=25&&
 287:                         piececount(mover,19,24-die1)!=0)break;
 288:                 }
 289:                 count=4;
 290:                 moverecord(mover);
 291:                 if(mover[0]>0)break;
 292:                 }
 293:                 if(count==3)moverecord(mover);
 294:                 else{
 295:                 mover[l]++;
 296:                 mover[l+die1]--;
 297:                 }
 298:                 if(mover[0]>0)break;
 299:             }
 300:             if(count==2)moverecord(mover);
 301:             else{
 302:                 mover[j]++;
 303:                 mover[j+die1]--;
 304:             }
 305:             if(mover[0]>0)break;
 306:         }
 307:         if(count==1)moverecord(mover);
 308:         else{
 309:             mover[i]++;
 310:             mover[i+die1]--;
 311:         }
 312:         if(mover[0]>0)break;
 313:     }
 314: }
 315: moverecord(mover)
 316: int *mover;
 317: {
 318:     extern int i,j,l,m,imoves,count;
 319:     int t;
 320:     if(imoves>=MAXIMOVES)goto undo;;
 321:     for(t=0;t<=3;t++)
 322:         moves[imoves].pos[t]= NIL;
 323:     switch(count){
 324: case 4:
 325:         moves[imoves].pos[3]=m;
 326:         moves[imoves].mov[3]=die1;
 327: case 3:
 328:         moves[imoves].pos[2]=l;
 329:         moves[imoves].mov[2]=die1;
 330: case 2:
 331:         moves[imoves].pos[1]=j;
 332:         moves[imoves].mov[1]=die2;
 333: case 1:
 334:         moves[imoves].pos[0]=i;
 335:         moves[imoves].mov[0]=die1;
 336:         imoves++;
 337:     }
 338: undo:
 339:     switch(count){
 340: case 4:
 341:         break;
 342: case 3:
 343:         mover[l]++;
 344:         mover[l+die1]--;
 345:         break;
 346: case 2:
 347:         mover[j]++;
 348:         mover[j+die2]--;
 349:         break;
 350: case 1:
 351:         mover[i]++;
 352:         mover[i+die1]--;
 353:     }
 354: }
 355: 
 356: 
 357: strategy(player,playee)
 358: int *player,*playee;
 359: {
 360:     extern char level;
 361:     int k,n,nn,bestval,moveval,prob;
 362:     n=0;
 363:     if(imoves==0)return(NIL);
 364:     goodmoves[0]=NIL;
 365:     bestval= -32000;
 366:     for(k=0;k<imoves;k++){
 367:         if((moveval=eval(player,playee,k,&prob))<bestval)continue;
 368:         if(moveval>bestval){
 369:         bestval=moveval;
 370:         n=0;
 371:         }
 372:         if(n<MAXGMOV){
 373:         goodmoves[n]=k;
 374:         probmoves[n++]=prob;
 375:         }
 376:     }
 377:     if(level=='e' && n>1){
 378:         nn=n;
 379:         n=0;
 380:         prob=32000;
 381:         for(k=0;k<nn;k++){
 382:         if((moveval=probmoves[k])>prob)continue;
 383:         if(moveval<prob){
 384:             prob=moveval;
 385:             n=0;
 386:         }
 387:         goodmoves[n]=goodmoves[k];
 388:         probmoves[n++]=probmoves[k];
 389:         }
 390:     }
 391:     return(goodmoves[(rand()>>4)%n]);
 392: }
 393: 
 394: eval(player,playee,k,prob)
 395: int *player,*playee,k,*prob;
 396: {
 397:     extern char level;
 398:     int newtry[31],newother[31],*r,*q,*p,n,sum,first;
 399:     int ii,lastwhite,lastred;
 400:     *prob=sum=0;
 401:     r=player+25;
 402:     p=newtry;
 403:     q=newother;
 404:     while(player<r){
 405:         *p++= *player++;
 406:         *q++= *playee++;
 407:     }
 408:     q=newtry+31;
 409:     for(p=newtry+25;p<q;) *p++ = 0; /*zero out spaces for hit pieces*/
 410:     for(n=0;n<4;n++){
 411:         if(moves[k].pos[n]==NIL)break;
 412:         newtry[moves[k].pos[n]]--;
 413:         newtry[ii=moves[k].pos[n]+moves[k].mov[n]]++;
 414:         if(ii<25 && newother[25-ii]==1){
 415:         newother[25-ii]=0;
 416:         newother[0]++;
 417:         if(ii<=15 && level=='e')sum++;  /*hit if near other's home*/
 418:         }
 419:     }
 420:     for(lastred=0;newother[lastred]==0;lastred++);
 421:     for(lastwhite=0;newtry[lastwhite]==0;lastwhite++);
 422:     lastwhite=25-lastwhite;
 423:     if(lastwhite<=6 && lastwhite<lastred)sum=1000;
 424:     if(lastwhite<lastred && level=='e'
 425:         && lastwhite>6){            /*expert's running game.
 426: 						  First priority to get all
 427: 						  pieces into white's home*/
 428:         for(sum=1000;lastwhite>6;lastwhite--)
 429:         sum=sum-lastwhite*newtry[25-lastwhite];
 430:     }
 431:     for(first=0;first<25;first++)
 432:         if(newother[first]!=0)break;    /*find other's first piece*/
 433:     q=newtry+25;
 434:     for(p=newtry+1;p<q;)if(*p++ > 1)sum++;  /*blocked points are good*/
 435:     if(first>5){    /*only stress removing pieces if homeboard
 436: 			  cannot be hit
 437: 			*/
 438:         q=newtry+31;
 439:         p=newtry+25;
 440:         for(n=6;p<q;n--)
 441:         sum=+ *p++ * n; /*remove pieces, but just barely*/
 442:     }
 443:     if(level!='b'){
 444:         r=newtry+25-first;  /*singles past this point can't be hit*/
 445:         for(p=newtry+7;p<r;)
 446:         if(*p++ == 1)sum--; /*singles are bad after 1st 6 points
 447: 					  if they can be hit*/
 448:         q=newtry+3;
 449:         for(p=newtry;p<q;)sum=- *p++;  /*bad to be on 1st three points*/
 450:     }
 451: 
 452:     for(n=1;n<=4;n++)
 453:         *prob=+ n*getprob(newtry,newother,6*n-5,6*n);
 454:     return(sum);
 455: }
 456: instructions()
 457: {
 458:     printf( "To play backgammon, type the numbers of the points\n");
 459:     printf( "from which pieces are to be moved. Thus, if the\n");
 460:     printf( "roll is '3,5', typing '2 6' will move a piece\n");
 461:     printf( "from point 2 three spaces to point 5,\n");
 462:     printf( "and a piece from point 6 forward to\n");
 463:     printf( "point 11.  If the moves must be made in the\n");
 464:     printf( "opposite order, the first character typed must\n");
 465:     printf( "be a minus ('-'). Thus, typing\n");
 466:     printf( "'-2 6' moves the piece on point 2\n");
 467:     printf( "by 5, and the piece on point 6 by 3.\n");
 468:     printf( "If you want to move a single piece several times,\n");
 469:     printf( "the sequence of points from which it is to be\n");
 470:     printf( "moved must be typed. Thus '14 17' will move\n");
 471:     printf( "a piece from point 14 to point 17 and thence to\n");
 472:     printf( "to point 22.\n");
 473:     printf( "If a double is rolled, you should type four numbers.\n");
 474:     printf( "Red pieces that have been removed from the board by\n");
 475:     printf( "being hit by white are on point 0 and\n");
 476:     printf( "must be brought in before any other move can be made.\n");
 477:     printf( "White pieces that are hit are removed to point 25.\n");
 478:     printf( "You will not be allowed to make an illegal move, or\n");
 479:     printf( "to make too many moves. However, if you make too\n");
 480:     printf( "few moves, the program does not care. In particular\n");
 481:     printf( "you may skip your turn by typing a 'new-line'\n");
 482:     printf( "all by itself.\n\n");
 483: }
 484: 
 485: getprob(player,playee,start,finish)
 486: int *player,*playee,start,finish;
 487: {           /*returns the probability (times 102) that any
 488: 			  pieces belonging to 'player' and lying between
 489: 			  his points 'start' and 'finish' will be hit
 490: 			  by a piece belonging to playee
 491: 			*/
 492:     int k,n,sum;
 493:     sum=0;
 494:     for(;start<=finish;start++){
 495:         if(player[start]==1){
 496:         for(k=1;k<=12;k++){
 497:             if((n=25-start-k)<0)break;
 498:             if(playee[n]!=0)sum=+probability[k];
 499:         }
 500:         }
 501:     }
 502:     return(sum);
 503: }
 504: prtbrd()
 505: {
 506:     int k;
 507:     printf( "White's Home\n");
 508:     for(k=1;k<=6;k++)
 509:         printf( "%4d",k);
 510:     printf( "    ");
 511:     for(k=7;k<=12;k++)printf( "%4d",k);
 512:     putchar('\r' );
 513:     for(k=1;k<=54;k++)putchar('_' );
 514:     putchar('\n' );
 515:     numline(red,white,1,6);
 516:     printf( "    ");
 517:     numline(red,white,7,12);
 518:     putchar('\n' );
 519:     colorline(red,'R',white,'W',1,6);
 520:     printf( "    ");
 521:     colorline(red,'R',white,'W',7,12);
 522:     putchar('\n' );
 523:     if(white[0]!=0)printf( "%28dW\n",white[0]);
 524:     else putchar('\n' );
 525:     if(red[0]!=0)printf( "%28dR\n",red[0]);
 526:     else putchar('\n' );
 527:     colorline(white,'W',red,'R',1,6);
 528:     printf( "    ");
 529:     colorline(white,'W',red,'R',7,12);
 530:     putchar('\n' );
 531:     numline(white,red,1,6);
 532:     printf( "    ");
 533:     numline(white,red,7,12);
 534:     putchar('\r' );
 535:     for(k=1;k<=54;k++)putchar('_' );
 536:     putchar('\n' );
 537:     for(k=24;k>=19;k--)printf( "%4d",k);
 538:     printf( "    ");
 539:     for(k=18;k>=13;k--)printf( "%4d",k);
 540:     printf( "\nRed's Home\n\n\n\n\n");
 541: }
 542: numline(upcol,downcol,start,fin)
 543: int *upcol,*downcol,start,fin;
 544: {
 545:     int k,n;
 546:     for(k=start;k<=fin;k++){
 547:         if((n=upcol[k])!=0 || (n=downcol[25-k])!=0)printf( "%4d",n);
 548:         else printf( "    ");
 549:     }
 550: }
 551: colorline(upcol,c1,downcol,c2,start,fin)
 552: int *upcol,*downcol,start,fin;
 553: char c1,c2;
 554: {
 555:     int k;
 556:     char c;
 557:     for(k=start;k<=fin;k++){
 558:         c=' ';
 559:         if(upcol[k]!=0)c=c1;
 560:         if(downcol[25-k]!=0)c=c2;
 561:     printf( "   %c",c);
 562:     }
 563: }
 564: 
 565: int rrno 0;
 566: 
 567: srand(){
 568:     rrno = _look( 0x40000 );
 569:     _store( 0x40000, rrno+1 );
 570:     }
 571: 
 572: rand(){
 573:     rrno =* 0106273;
 574:     rrno =+ 020202;
 575:     return( rrno & 077777 );
 576:     }
 577: 
 578: _look(p) int *p; {
 579:     return( *p );
 580:     }
 581: 
 582: _store( p, numb ) int *p; {
 583:     *p = numb;
 584:     }

Defined functions

Defined variables

Defined macros