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