# include <stdio.h>##define NIL (-1)#define MAXGMOV 10#define MAXIMOVES 1000	char level;		/*'b'=beginner, 'i'=intermediate, 'e'=expert*/int die1;int die2;int i;int j;int l;int m;int count;int red[]     {0,2,0,0,0,0,0,0,0,0,0,0,5,		 0,0,0,0,3,0,5,0,0,0,0,0,		 0,0,0,0,0,0};int white[]   {0,2,0,0,0,0,0,0,0,0,0,0,5,		 0,0,0,0,3,0,5,0,0,0,0,0,		 0,0,0,0,0,0};int probability[]{0,11,12,13,14,15,16,		    06,05,04,03,02,01};int imoves;int goodmoves[MAXGMOV] ;int probmoves[MAXGMOV] ;struct {int pos[4],mov[4];} moves[MAXIMOVES] ;main(){	int t,k,n,go[5];	char s[100];	go[5]=NIL;	srand();	printf( "Do you want instructions? Type 'y' for yes,\n");	printf( "anything else means no.?? ");	getstr(s);	if(*s=='y')instructions();	printf( "Choose the level of your oppponent.\n");	printf( "Type 'b' for beginner, or 'i' for intermediate.\n");	printf( "Anything else gets you an expert.?? ");	level='e';	getstr(s);	if(*s=='b')level='b';	else if(*s=='i')level='i';	printf( "You will play red. Do you wan't to move first?\n");	printf( "Type 'y' for yes, anything else means no.?? ");	getstr(s);	if(*s=='y')goto nowhmove;whitesmv:	roll();	printf( "white rolls %d,%d\n",die1,die2);	printf( "white's move is:");	if(nextmove(white,red)==NIL)goto nowhmove;	if(piececount(white,0,24)==0){	    printf( "White wins\n");	    printf( "Aren't you ashamed. You've been beaten by a computer.\n");	    exit();	}nowhmove:	prtbrd();	roll();retry:	printf( "your roll is %d,  %d\n",die1,die2);	printf( "your move, please?? ");	getstr(s);	if(*s==0){	    printf( "red's move skipped\n");	    goto whitesmv;	}	n=sscanf(s,"%d%d%d%d%d",&go[0],&go[1],&go[2],&go[3],&go[4]);	if((die1!=die2&&n>2)||n>4){	    printf( "you've made too many moves\n");	    goto retry;	}	go[n]=NIL;	if(*s=='-'){	    go[0]= -go[0];	    t=die1;	    die1=die2;	    die2=t;	}	for(k=0;k<n;k++){	    if(0<=go[k] && go[k]<=24)continue;	    else{		printf( "move %d is illegal\n",go[k]);		goto retry;	    }	}	if(play(red,white,go))goto retry;	if(piececount(red,0,24)==0){	    printf( "Red wins.\n");	    printf( "Congratulations! You have just defeated a dumb machine.\n");	    exit();	}	goto whitesmv;}getstr(s)char *s;{	while((*s=getchar())!='\n')s++;	*s=0;}play(player,playee,pos)int *player,*playee,pos[];{	int k,n,die,ipos;	for(k=0;k<player[0];k++){  /*blots on player[0] must be moved first*/	    if(pos[k]==NIL)break;	    if(pos[k]!=0){		printf( "piece on position 0 must be moved first\n");		return(-1);	    }	}	for(k=0;(ipos=pos[k])!=NIL;k++){	    die=k?die2:die1;	    n=25-ipos-die;	    if(player[ipos]==0)goto badmove;	    if(n>0&&playee[n]>=2)goto badmove;	    if(n<=0){		if(piececount(player,0,18)!=0)goto badmove;		if((ipos+die)!=25&&		    piececount(player,19,24-die)!=0)goto badmove;	    }	    player[ipos]--;	    player[ipos+die]++;	}	for(k=0;pos[k]!=NIL;k++){	    die=k?die2:die1;	    n=25-pos[k]-die;	    if(n>0 && playee[n]==1){		playee[n]=0;		playee[0]++;	    }	}	return(0);badmove:	printf( "Move %d is not legal.\n",ipos);	while(k--){	    die=k?die2:die1;	    player[pos[k]]++;	    player[pos[k]+die]--;	}	return(-1);}nextmove(player,playee)int *player,*playee;{	int k;	imoves=0;	movegen(player,playee);	if(die1!=die2){	k=die1;	die1=die2;	die2=k;	movegen(player,playee);	}	if(imoves==0){	    printf( "roll was %d,%d; no white move possible\n",die1,die2);	    return(NIL);	}	k=strategy(player,playee);		/*select kth possible move*/	prtmov(k);	update(player,playee,k);	return(0);}prtmov(k)int k;{	int n;	if(k==NIL)printf( "no move possible\n");	else for(n=0;n<4;n++){	    if(moves[k].pos[n]==NIL)break;	    printf( "    %d, %d",25-moves[k].pos[n],moves[k].mov[n]);	}	printf( "\n");}update(player,playee,k)int *player,*playee,k;{	int n,t;	for(n=0;n<4;n++){	    if(moves[k].pos[n]==NIL)break;	    player[moves[k].pos[n]]--;	    player[moves[k].pos[n]+moves[k].mov[n]]++;	    t=25-moves[k].pos[n]-moves[k].mov[n];	    if(t>0 && playee[t]==1){		playee[0]++;		playee[t]--;	    }	}}piececount(player,startrow,endrow)int *player,startrow,endrow;{	int sum;	sum=0;	while(startrow<=endrow)	sum=+player[startrow++];	return(sum);}/*prtmovs(){	int i1,i2;	printf( "possible moves are\n");	for(i1=0;i1<imoves;i1++){		printf( "\n%d",i1);		for(i2=0;i2<4;i2++){			if(moves[i1].pos[i2]==NIL)break;			printf( "%d, %d",moves[i1].pos[i2],moves[i1].mov[i2]);		}	}	printf( "\n");}*/roll(){	extern int die1,die2;	die1=(rand()>>8)%6+1;	die2=(rand()>>8)%6+1;}movegen(mover,movee)int *mover,*movee;{	extern int i,j,l,m,count;	extern int die1,die2;	int k;	for(i=0;i<=24;i++){		count=0;		if(mover[i]==0)continue;		if((k=25-i-die1)>0&&movee[k]>=2)		    if(mover[0]>0)break;		    else continue;		if(k<=0){		    if(piececount(mover,0,18)!=0)break;		    if((i+die1)!=25&&		        piececount(mover,19,24-die1)!=0)break;		}		mover[i]--;		mover[i+die1]++;		count=1;		for(j=0;j<=24;j++){			if(mover[j]==0)continue;			if((k=25-j-die2)>0&&movee[k]>=2)			    if(mover[0]>0)break;			    else continue;			if(k<=0){			    if(piececount(mover,0,18)!=0)break;			    if((j+die2)!=25&&			        piececount(mover,19,24-die2)!=0)break;			}			mover[j]--;			mover[j+die2]++;			count=2;			if(die1!=die2){			    moverecord(mover);			    if(mover[0]>0)break;			    else continue;			}			for(l=0;l<=24;l++){			    if(mover[l]==0)continue;			    if((k=25-l-die1)>0&&movee[k]>=2)				if(mover[0]>0)break;				else continue;			    if(k<=0){				if(piececount(mover,0,18)!=0)break;				if((l+die2)!=25&&				    piececount(mover,19,24-die1)!=0)break;			    }			    mover[l]--;			    mover[l+die1]++;			    count=3;			    for(m=0;m<=24;m++){				if(mover[m]==0)continue;				if((k=25-m-die1)>=0&&movee[k]>=2)				    if(mover[0]>0)break;				    else continue;				if(k<=0){				    if(piececount(mover,0,18)!=0)break;				    if((m+die2)!=25&&				        piececount(mover,19,24-die1)!=0)break;				}				count=4;				moverecord(mover);				if(mover[0]>0)break;			    }			    if(count==3)moverecord(mover);			    else{				mover[l]++;				mover[l+die1]--;			    }			    if(mover[0]>0)break;			}			if(count==2)moverecord(mover);			else{			    mover[j]++;			    mover[j+die1]--;			}			if(mover[0]>0)break;		}		if(count==1)moverecord(mover);		else{		    mover[i]++;		    mover[i+die1]--;		}		if(mover[0]>0)break;	}}moverecord(mover)int *mover;{	extern int i,j,l,m,imoves,count;	int t;	if(imoves>=MAXIMOVES)goto undo;;	for(t=0;t<=3;t++)	    moves[imoves].pos[t]= NIL;	switch(count){case 4:	    moves[imoves].pos[3]=m;	    moves[imoves].mov[3]=die1;case 3:	    moves[imoves].pos[2]=l;	    moves[imoves].mov[2]=die1;case 2:	    moves[imoves].pos[1]=j;	    moves[imoves].mov[1]=die2;case 1:	    moves[imoves].pos[0]=i;	    moves[imoves].mov[0]=die1;	    imoves++;	}undo:	switch(count){case 4:	    break;case 3:	    mover[l]++;	    mover[l+die1]--;	    break;case 2:	    mover[j]++;	    mover[j+die2]--;	    break;case 1:	    mover[i]++;	    mover[i+die1]--;	}}strategy(player,playee)int *player,*playee;{	extern char level;	int k,n,nn,bestval,moveval,prob;	n=0;	if(imoves==0)return(NIL);	goodmoves[0]=NIL;	bestval= -32000;	for(k=0;k<imoves;k++){	    if((moveval=eval(player,playee,k,&prob))<bestval)continue;	    if(moveval>bestval){		bestval=moveval;		n=0;	    }	    if(n<MAXGMOV){		goodmoves[n]=k;		probmoves[n++]=prob;	    }	}	if(level=='e' && n>1){	    nn=n;	    n=0;	    prob=32000;	    for(k=0;k<nn;k++){		if((moveval=probmoves[k])>prob)continue;		if(moveval<prob){		    prob=moveval;		    n=0;		}		goodmoves[n]=goodmoves[k];		probmoves[n++]=probmoves[k];	    }	}	return(goodmoves[(rand()>>4)%n]);}eval(player,playee,k,prob)int *player,*playee,k,*prob;{	extern char level;	int newtry[31],newother[31],*r,*q,*p,n,sum,first;	int ii,lastwhite,lastred;	*prob=sum=0;	r=player+25;	p=newtry;	q=newother;	while(player<r){	    *p++= *player++;	    *q++= *playee++;	}	q=newtry+31;	for(p=newtry+25;p<q;) *p++ = 0;	/*zero out spaces for hit pieces*/	for(n=0;n<4;n++){	    if(moves[k].pos[n]==NIL)break;	    newtry[moves[k].pos[n]]--;	    newtry[ii=moves[k].pos[n]+moves[k].mov[n]]++;	    if(ii<25 && newother[25-ii]==1){		newother[25-ii]=0;		newother[0]++;		if(ii<=15 && level=='e')sum++;	/*hit if near other's home*/	    }	}	for(lastred=0;newother[lastred]==0;lastred++);	for(lastwhite=0;newtry[lastwhite]==0;lastwhite++);	lastwhite=25-lastwhite;	if(lastwhite<=6 && lastwhite<lastred)sum=1000;	if(lastwhite<lastred && level=='e'	    && lastwhite>6){			/*expert's running game.						  First priority to get all						  pieces into white's home*/	    for(sum=1000;lastwhite>6;lastwhite--)		sum=sum-lastwhite*newtry[25-lastwhite];	}	for(first=0;first<25;first++)	    if(newother[first]!=0)break;	/*find other's first piece*/	q=newtry+25;	for(p=newtry+1;p<q;)if(*p++ > 1)sum++;	/*blocked points are good*/	if(first>5){	/*only stress removing pieces if homeboard			  cannot be hit			*/	    q=newtry+31;	    p=newtry+25;	    for(n=6;p<q;n--)		sum=+ *p++ * n;	/*remove pieces, but just barely*/	}	if(level!='b'){	    r=newtry+25-first;	/*singles past this point can't be hit*/	    for(p=newtry+7;p<r;)		if(*p++ == 1)sum--;	/*singles are bad after 1st 6 points					  if they can be hit*/	    q=newtry+3;	    for(p=newtry;p<q;)sum=- *p++;  /*bad to be on 1st three points*/	}	for(n=1;n<=4;n++)	    *prob=+ n*getprob(newtry,newother,6*n-5,6*n);	return(sum);}instructions(){	printf( "To play backgammon, type the numbers of the points\n");	printf( "from which pieces are to be moved. Thus, if the\n");	printf( "roll is '3,5', typing '2 6' will move a piece\n");	printf( "from point 2 three spaces to point 5,\n");	printf( "and a piece from point 6 forward to\n");	printf( "point 11.  If the moves must be made in the\n");	printf( "opposite order, the first character typed must\n");	printf( "be a minus ('-'). Thus, typing\n");	printf( "'-2 6' moves the piece on point 2\n");	printf( "by 5, and the piece on point 6 by 3.\n");	printf( "If you want to move a single piece several times,\n");	printf( "the sequence of points from which it is to be\n");	printf( "moved must be typed. Thus '14 17' will move\n");	printf( "a piece from point 14 to point 17 and thence to\n");	printf( "to point 22.\n");	printf( "If a double is rolled, you should type four numbers.\n");	printf( "Red pieces that have been removed from the board by\n");	printf( "being hit by white are on point 0 and\n");	printf( "must be brought in before any other move can be made.\n");	printf( "White pieces that are hit are removed to point 25.\n");	printf( "You will not be allowed to make an illegal move, or\n");	printf( "to make too many moves. However, if you make too\n");	printf( "few moves, the program does not care. In particular\n");	printf( "you may skip your turn by typing a 'new-line'\n");	printf( "all by itself.\n\n");}getprob(player,playee,start,finish)int *player,*playee,start,finish;{			/*returns the probability (times 102) that any			  pieces belonging to 'player' and lying between			  his points 'start' and 'finish' will be hit			  by a piece belonging to playee			*/	int k,n,sum;	sum=0;	for(;start<=finish;start++){	    if(player[start]==1){		for(k=1;k<=12;k++){		    if((n=25-start-k)<0)break;		    if(playee[n]!=0)sum=+probability[k];		}	    }	}	return(sum);}prtbrd(){	int k;	printf( "White's Home\n");	for(k=1;k<=6;k++)	    printf( "%4d",k);	printf( "    ");	for(k=7;k<=12;k++)printf( "%4d",k);	putchar('\r' );	for(k=1;k<=54;k++)putchar('_' );	putchar('\n' );	numline(red,white,1,6);	printf( "    ");	numline(red,white,7,12);	putchar('\n' );	colorline(red,'R',white,'W',1,6);	printf( "    ");	colorline(red,'R',white,'W',7,12);	putchar('\n' );	if(white[0]!=0)printf( "%28dW\n",white[0]);	else putchar('\n' );	if(red[0]!=0)printf( "%28dR\n",red[0]);	else putchar('\n' );	colorline(white,'W',red,'R',1,6);	printf( "    ");	colorline(white,'W',red,'R',7,12);	putchar('\n' );	numline(white,red,1,6);	printf( "    ");	numline(white,red,7,12);	putchar('\r' );	for(k=1;k<=54;k++)putchar('_' );	putchar('\n' );	for(k=24;k>=19;k--)printf( "%4d",k);	printf( "    ");	for(k=18;k>=13;k--)printf( "%4d",k);	printf( "\nRed's Home\n\n\n\n\n");}numline(upcol,downcol,start,fin)int *upcol,*downcol,start,fin;{	int k,n;	for(k=start;k<=fin;k++){	    if((n=upcol[k])!=0 || (n=downcol[25-k])!=0)printf( "%4d",n);	    else printf( "    ");	}}colorline(upcol,c1,downcol,c2,start,fin)int *upcol,*downcol,start,fin;char c1,c2;{	int k;	char c;	for(k=start;k<=fin;k++){	    c=' ';	    if(upcol[k]!=0)c=c1;	    if(downcol[25-k]!=0)c=c2;	printf( "   %c",c);	}}int rrno 0;srand(){	rrno = _look( 0x40000 );	_store( 0x40000, rrno+1 );	}rand(){	rrno =* 0106273;	rrno =+ 020202;	return( rrno & 077777 );	}_look(p) int *p; {	return( *p );	}_store( p, numb ) int *p; {	*p = numb;	}