home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / games / backgammon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-25  |  12.9 KB  |  585 lines
  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.     }
  585.