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