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