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