1 /* UNIX V7 source code: see /COPYRIGHT or www.tuhs.org for details. */
2 /* ANSIfied and some PDP11isms and bugs fixed for FUZIX */
3 /* Borrowed from FUZIX project */
4
5 // zcc +cpm -vn -SO3 -clib=sdcc_iy --max-allocs-per-node200000 --opt-code-size backgammon.c -o backg -create-app
6 // zcc +zx -vn -SO3 -startup=4 -clib-sdcc_iy --max-allocs-per-node200000 --opt-code-size backgammon.c -o backg -create-app
7
8 #pragma printf = "%c %d"
9 #pragma scanf = "%d"
10
11 #ifdef __SPECTRUM
12
13 #pragma output CRT_ORG_CODE = 30000 // move ORG to 30000
14 #pragma output REGISTER_SP = -1 // indicate crt should not modify stack location
15 #pragma output CRT_ENABLE_EIDI = 0x01 // disable interrupts at start
16
17 #endif
18
19 #pragma output CRT_ENABLE_COMMANDLINE = 0 // no command line parsing
20 #pragma output CLIB_EXIT_STACK_SIZE = 0 // do not reserve space for registering atexit() functions
21 #pragma output CLIB_MALLOC_HEAP_SIZE = 0 // do not create malloc heap
22 #pragma output CLIB_STDIO_HEAP_SIZE = 0 // do not create stdio heap (cannot open files)
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <unistd.h>
27 #include <string.h>
28 #include <input.h>
29
30 #define NIL (-1)
31 #define MAXGMOV 10
32 #define MAXIMOVES 1000
33
34 char level; /*'b'=beginner, 'i'=intermediate, 'e'=expert */
35 int die1;
36 int die2;
37 int i;
38 int j;
39 int l;
40 int m;
41 int count;
42 int red[] = { 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
43 0, 0, 0, 0, 3, 0, 5, 0, 0, 0, 0, 0,
44 0, 0, 0, 0, 0, 0
45 };
46
47 int white[] = { 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[] = { 0, 11, 12, 13, 14, 15, 16,
53 06, 05, 04, 03, 02, 01
54 };
55
56 int imoves;
57 int goodmoves[MAXGMOV];
58 int probmoves[MAXGMOV];
59 struct {
60 int pos[4], mov[4];
61 } moves[MAXIMOVES];
62
63
getstr(char * s)64 void getstr(char *s)
65 {
66 while ((*s = getchar()) != '\n')
67 s++;
68 *s = 0;
69 }
70
piececount(int * player,int startrow,int endrow)71 int piececount(int *player, int startrow, int endrow)
72 {
73 int sum;
74 sum = 0;
75 while (startrow <= endrow)
76 sum += player[startrow++];
77 return (sum);
78 }
79
play(int * player,int * playee,int pos[])80 int play(int *player, int *playee, int pos[])
81 {
82 int k, n, die, ipos;
83 for (k = 0; k < player[0]; k++) { /*blots on player[0] must be moved first */
84 if (pos[k] == NIL)
85 break;
86 if (pos[k] != 0) {
87 printf
88 ("piece on position 0 must be moved first\n");
89 return (-1);
90 }
91 }
92 for (k = 0; (ipos = pos[k]) != NIL; k++) {
93 die = k ? die2 : die1;
94 n = 25 - ipos - die;
95 if (player[ipos] == 0)
96 goto badmove;
97 if (n > 0 && playee[n] >= 2)
98 goto badmove;
99 if (n <= 0) {
100 if (piececount(player, 0, 18) != 0)
101 goto badmove;
102 if ((ipos + die) != 25 &&
103 piececount(player, 19, 24 - die) != 0)
104 goto badmove;
105 }
106 player[ipos]--;
107 player[ipos + die]++;
108 }
109 for (k = 0; pos[k] != NIL; k++) {
110 die = k ? die2 : die1;
111 n = 25 - pos[k] - die;
112 if (n > 0 && playee[n] == 1) {
113 playee[n] = 0;
114 playee[0]++;
115 }
116 }
117 return (0);
118
119 badmove:
120 printf("Move %d is not legal.\n", ipos);
121 while (k--) {
122 die = k ? die2 : die1;
123 player[pos[k]]++;
124 player[pos[k] + die]--;
125 }
126 return (-1);
127 }
128
129
prtmov(int k)130 void prtmov(int k)
131 {
132 int n;
133 if (k == NIL)
134 printf("no move possible\n");
135 else
136 for (n = 0; n < 4; n++) {
137 if (moves[k].pos[n] == NIL)
138 break;
139 printf(" %d, %d", 25 - moves[k].pos[n],
140 moves[k].mov[n]);
141 }
142 printf("\n");
143 }
144
update(int * player,int * playee,int k)145 void update(int *player, int *playee, int k)
146 {
147 int n, t;
148 for (n = 0; n < 4; n++) {
149 if (moves[k].pos[n] == NIL)
150 break;
151 player[moves[k].pos[n]]--;
152 player[moves[k].pos[n] + moves[k].mov[n]]++;
153 t = 25 - moves[k].pos[n] - moves[k].mov[n];
154 if (t > 0 && playee[t] == 1) {
155 playee[0]++;
156 playee[t]--;
157 }
158 }
159 }
160
161 /*
162 void prtmovs(void)
163 {
164 int i1,i2;
165 printf( "possible moves are\n");
166 for(i1=0;i1<imoves;i1++){
167 printf( "\n%d",i1);
168 for(i2=0;i2<4;i2++){
169 if(moves[i1].pos[i2]==NIL)break;
170 printf( "%d, %d",moves[i1].pos[i2],moves[i1].mov[i2]);
171 }
172 }
173 printf( "\n");
174 }
175 */
176
roll(void)177 void roll(void)
178 {
179 extern int die1, die2;
180 die1 = (rand() >> 8) % 6 + 1;
181 die2 = (rand() >> 8) % 6 + 1;
182 }
183
moverecord(int * mover)184 void moverecord(int *mover)
185 {
186 extern int i, j, l, m, imoves, count;
187 int t;
188 if (imoves >= MAXIMOVES)
189 goto undo;;
190 for (t = 0; t <= 3; t++)
191 moves[imoves].pos[t] = NIL;
192 switch (count) {
193 case 4:
194 moves[imoves].pos[3] = m;
195 moves[imoves].mov[3] = die1;
196 case 3:
197 moves[imoves].pos[2] = l;
198 moves[imoves].mov[2] = die1;
199 case 2:
200 moves[imoves].pos[1] = j;
201 moves[imoves].mov[1] = die2;
202 case 1:
203 moves[imoves].pos[0] = i;
204 moves[imoves].mov[0] = die1;
205 imoves++;
206 }
207 undo:
208 switch (count) {
209 case 4:
210 break;
211 case 3:
212 mover[l]++;
213 mover[l + die1]--;
214 break;
215 case 2:
216 mover[j]++;
217 mover[j + die2]--;
218 break;
219 case 1:
220 mover[i]++;
221 mover[i + die1]--;
222 }
223 }
224
movegen(int * mover,int * movee)225 void movegen(int *mover, int *movee)
226 {
227 extern int i, j, l, m, count;
228 extern int die1, die2;
229 int k;
230 for (i = 0; i <= 24; i++) {
231 count = 0;
232 if (mover[i] == 0)
233 continue;
234 if ((k = 25 - i - die1) > 0 && movee[k] >= 2)
235 if (mover[0] > 0)
236 break;
237 else
238 continue;
239 if (k <= 0) {
240 if (piececount(mover, 0, 18) != 0)
241 break;
242 if ((i + die1) != 25 &&
243 piececount(mover, 19, 24 - die1) != 0)
244 break;
245 }
246 mover[i]--;
247 mover[i + die1]++;
248 count = 1;
249 for (j = 0; j <= 24; j++) {
250 if (mover[j] == 0)
251 continue;
252 if ((k = 25 - j - die2) > 0 && movee[k] >= 2)
253 if (mover[0] > 0)
254 break;
255 else
256 continue;
257 if (k <= 0) {
258 if (piececount(mover, 0, 18) != 0)
259 break;
260 if ((j + die2) != 25 &&
261 piececount(mover, 19, 24 - die2) != 0)
262 break;
263 }
264 mover[j]--;
265 mover[j + die2]++;
266 count = 2;
267 if (die1 != die2) {
268 moverecord(mover);
269 if (mover[0] > 0)
270 break;
271 else
272 continue;
273 }
274 for (l = 0; l <= 24; l++) {
275 if (mover[l] == 0)
276 continue;
277 if ((k = 25 - l - die1) > 0
278 && movee[k] >= 2)
279 if (mover[0] > 0)
280 break;
281 else
282 continue;
283 if (k <= 0) {
284 if (piececount(mover, 0, 18) != 0)
285 break;
286 if ((l + die2) != 25 &&
287 piececount(mover, 19,
288 24 - die1) != 0)
289 break;
290 }
291 mover[l]--;
292 mover[l + die1]++;
293 count = 3;
294 for (m = 0; m <= 24; m++) {
295 if (mover[m] == 0)
296 continue;
297 if ((k = 25 - m - die1) >= 0
298 && movee[k] >= 2)
299 if (mover[0] > 0)
300 break;
301 else
302 continue;
303 if (k <= 0) {
304 if (piececount
305 (mover, 0, 18) != 0)
306 break;
307 if ((m + die2) != 25 &&
308 piececount(mover, 19,
309 24 -
310 die1) != 0)
311 break;
312 }
313 count = 4;
314 moverecord(mover);
315 if (mover[0] > 0)
316 break;
317 }
318 if (count == 3)
319 moverecord(mover);
320 else {
321 mover[l]++;
322 mover[l + die1]--;
323 }
324 if (mover[0] > 0)
325 break;
326 }
327 if (count == 2)
328 moverecord(mover);
329 else {
330 mover[j]++;
331 mover[j + die1]--;
332 }
333 if (mover[0] > 0)
334 break;
335 }
336 if (count == 1)
337 moverecord(mover);
338 else {
339 mover[i]++;
340 mover[i + die1]--;
341 }
342 if (mover[0] > 0)
343 break;
344 }
345 }
346
getprob(int * player,int * playee,int start,int finish)347 int getprob(int *player, int *playee, int start, int finish)
348 { /*returns the probability (times 102) that any
349 pieces belonging to 'player' and lying between
350 his points 'start' and 'finish' will be hit
351 by a piece belonging to playee
352 */
353 int k, n, sum;
354 sum = 0;
355 for (; start <= finish; start++) {
356 if (player[start] == 1) {
357 for (k = 1; k <= 12; k++) {
358 if ((n = 25 - start - k) < 0)
359 break;
360 if (playee[n] != 0)
361 sum += probability[k];
362 }
363 }
364 }
365 return (sum);
366 }
367
eval(int * player,int * playee,int k,int * prob)368 int eval(int *player, int *playee, int k, int *prob)
369 {
370 extern char level;
371 int newtry[31], newother[31], *r, *q, *p, n, sum, first;
372 int ii, lastwhite, lastred;
373 *prob = sum = 0;
374 r = player + 25;
375 p = newtry;
376 q = newother;
377 while (player < r) {
378 *p++ = *player++;
379 *q++ = *playee++;
380 }
381 q = newtry + 31;
382 for (p = newtry + 25; p < q;)
383 *p++ = 0; /*zero out spaces for hit pieces */
384 for (n = 0; n < 4; n++) {
385 if (moves[k].pos[n] == NIL)
386 break;
387 newtry[moves[k].pos[n]]--;
388 newtry[ii = moves[k].pos[n] + moves[k].mov[n]]++;
389 if (ii < 25 && newother[25 - ii] == 1) {
390 newother[25 - ii] = 0;
391 newother[0]++;
392 if (ii <= 15 && level == 'e')
393 sum++; /*hit if near other's home */
394 }
395 }
396 for (lastred = 0; newother[lastred] == 0; lastred++);
397 for (lastwhite = 0; newtry[lastwhite] == 0; lastwhite++);
398 lastwhite = 25 - lastwhite;
399 if (lastwhite <= 6 && lastwhite < lastred)
400 sum = 1000;
401 if (lastwhite < lastred && level == 'e' && lastwhite > 6) { /*expert's running game.
402 First priority to get all
403 pieces into white's home */
404 for (sum = 1000; lastwhite > 6; lastwhite--)
405 sum = sum - lastwhite * newtry[25 - lastwhite];
406 }
407 for (first = 0; first < 25; first++)
408 if (newother[first] != 0)
409 break; /*find other's first piece */
410 q = newtry + 25;
411 for (p = newtry + 1; p < q;)
412 if (*p++ > 1)
413 sum++; /*blocked points are good */
414 if (first > 5) { /*only stress removing pieces if homeboard
415 cannot be hit
416 */
417 q = newtry + 31;
418 p = newtry + 25;
419 for (n = 6; p < q; n--)
420 sum += *p++ * n; /*remove pieces, but just barely */
421 }
422 if (level != 'b') {
423 r = newtry + 25 - first; /*singles past this point can't be hit */
424 for (p = newtry + 7; p < r;)
425 if (*p++ == 1)
426 sum--; /*singles are bad after 1st 6 points
427 if they can be hit */
428 q = newtry + 3;
429 for (p = newtry; p < q;)
430 sum -= *p++; /*bad to be on 1st three points */
431 }
432
433 for (n = 1; n <= 4; n++)
434 *prob += n * getprob(newtry, newother, 6 * n - 5, 6 * n);
435 return (sum);
436 }
437
strategy(int * player,int * playee)438 int strategy(int *player, int *playee)
439 {
440 extern char level;
441 int k, n, nn, bestval, moveval, prob;
442 n = 0;
443 if (imoves == 0)
444 return (NIL);
445 goodmoves[0] = NIL;
446 bestval = -32000;
447 for (k = 0; k < imoves; k++) {
448 if ((moveval = eval(player, playee, k, &prob)) < bestval)
449 continue;
450 if (moveval > bestval) {
451 bestval = moveval;
452 n = 0;
453 }
454 if (n < MAXGMOV) {
455 goodmoves[n] = k;
456 probmoves[n++] = prob;
457 }
458 }
459 if (level == 'e' && n > 1) {
460 nn = n;
461 n = 0;
462 prob = 32000;
463 for (k = 0; k < nn; k++) {
464 if ((moveval = probmoves[k]) > prob)
465 continue;
466 if (moveval < prob) {
467 prob = moveval;
468 n = 0;
469 }
470 goodmoves[n] = goodmoves[k];
471 probmoves[n++] = probmoves[k];
472 }
473 }
474 return (goodmoves[(rand() >> 4) % n]);
475 }
476
nextmove(int * player,int * playee)477 int nextmove(int *player, int *playee)
478 {
479 int k;
480 imoves = 0;
481 movegen(player, playee);
482 if (die1 != die2) {
483 k = die1;
484 die1 = die2;
485 die2 = k;
486 movegen(player, playee);
487 }
488 if (imoves == 0) {
489 printf("roll was %d,%d; no white move possible\n", die1,
490 die2);
491 return (NIL);
492 }
493 k = strategy(player, playee); /*select kth possible move */
494 prtmov(k);
495 update(player, playee, k);
496 return (0);
497 }
498
499
500
501
502
instructions(void)503 void instructions(void)
504 {
505 printf("To play backgammon, type the numbers of the points\n");
506 printf("from which pieces are to be moved. Thus, if the\n");
507 printf("roll is '3,5', typing '2 6' will move a piece\n");
508 printf("from point 2 three spaces to point 5,\n");
509 printf("and a piece from point 6 forward to\n");
510 printf("point 11. If the moves must be made in the\n");
511 printf("opposite order, the first character typed must\n");
512 printf("be a minus ('-'). Thus, typing\n");
513 printf("'-2 6' moves the piece on point 2\n");
514 printf("by 5, and the piece on point 6 by 3.\n");
515 printf("If you want to move a single piece several times,\n");
516 printf("the sequence of points from which it is to be\n");
517 printf("moved must be typed. Thus '14 17' will move\n");
518 printf("a piece from point 14 to point 17 and thence to\n");
519 printf("to point 22.\n");
520 printf("If a double is rolled, you should type four numbers.\n");
521 printf("Red pieces that have been removed from the board by\n");
522 printf("being hit by white are on point 0 and\n");
523 printf("must be brought in before any other move can be made.\n");
524 printf("White pieces that are hit are removed to point 25.\n");
525 printf("You will not be allowed to make an illegal move, or\n");
526 printf("to make too many moves. However, if you make too\n");
527 printf("few moves, the program does not care. In particular\n");
528 printf("you may skip your turn by typing a 'new-line'\n");
529 printf("all by itself.\n\n");
530 }
531
532
numline(int * upcol,int * downcol,int start,int fin)533 void numline(int *upcol, int *downcol, int start, int fin)
534 {
535 int k, n;
536 for (k = start; k <= fin; k++) {
537 if ((n = upcol[k]) != 0 || (n = downcol[25 - k]) != 0)
538 printf("%4d", n);
539 else
540 printf(" ");
541 }
542 }
543
colorline(int * upcol,char c1,int * downcol,char c2,int start,int fin)544 void colorline(int *upcol, char c1, int *downcol, char c2, int start,
545 int fin)
546 {
547 int k;
548 char c;
549 for (k = start; k <= fin; k++) {
550 c = ' ';
551 if (upcol[k] != 0)
552 c = c1;
553 if (downcol[25 - k] != 0)
554 c = c2;
555 printf(" %c", c);
556 }
557 }
558
559
prtbrd(void)560 void prtbrd(void)
561 {
562 int k;
563 printf("White's Home\n");
564 for (k = 1; k <= 6; k++)
565 printf("%4d", k);
566 printf(" ");
567 for (k = 7; k <= 12; k++)
568 printf("%4d", k);
569 putchar('\n');
570 for (k = 1; k <= 54; k++)
571 putchar('_');
572 putchar('\n');
573 numline(red, white, 1, 6);
574 printf(" ");
575 numline(red, white, 7, 12);
576 putchar('\n');
577 colorline(red, 'R', white, 'W', 1, 6);
578 printf(" ");
579 colorline(red, 'R', white, 'W', 7, 12);
580 putchar('\n');
581 if (white[0] != 0)
582 printf("%28dW\n", white[0]);
583 else
584 putchar('\n');
585 if (red[0] != 0)
586 printf("%28dR\n", red[0]);
587 else
588 putchar('\n');
589 colorline(white, 'W', red, 'R', 1, 6);
590 printf(" ");
591 colorline(white, 'W', red, 'R', 7, 12);
592 putchar('\n');
593 numline(white, red, 1, 6);
594 printf(" ");
595 numline(white, red, 7, 12);
596 putchar('\n');
597 for (k = 1; k <= 54; k++)
598 putchar('_');
599 putchar('\n');
600 for (k = 24; k >= 19; k--)
601 printf("%4d", k);
602 printf(" ");
603 for (k = 18; k >= 13; k--)
604 printf("%4d", k);
605 printf("\nRed's Home\n\n\n\n\n");
606 }
607
608
main(void)609 int main(void)
610 {
611 int t, k, n, go[6];
612 char s[75];
613
614 go[5] = NIL;
615 printf("Do you want instructions? Type 'y' for yes,\n");
616 printf("anything else means no.?? ");
617 getstr(s);
618 if (*s == 'y')
619 instructions();
620
621 /* Set the randomness depending upon the user keyboard time */
622
623 printf("\nAny key to continue...\n\n");
624 in_wait_nokey();
625 for (t=0; !in_test_key(); ++t) ;
626 in_wait_nokey();
627 srand(t);
628 // srand(((uint16_t) time(NULL)) ^ getpid());
629
630 printf("Choose the level of your oppponent.\n");
631 printf("Type 'b' for beginner, or 'i' for intermediate.\n");
632 printf("Anything else gets you an expert.?? ");
633 level = 'e';
634 getstr(s);
635 if (*s == 'b')
636 level = 'b';
637 else if (*s == 'i')
638 level = 'i';
639 printf("You will play red. Do you wan't to move first?\n");
640 printf("Type 'y' for yes, anything else means no.?? ");
641 getstr(s);
642 if (*s == 'y')
643 goto nowhmove;
644 whitesmv:
645 roll();
646 printf("white rolls %d,%d\n", die1, die2);
647 printf("white's move is:");
648 if (nextmove(white, red) == NIL)
649 goto nowhmove;
650 if (piececount(white, 0, 24) == 0) {
651 printf("White wins\n");
652 printf
653 ("Aren't you ashamed. You've been beaten by a computer.\n");
654 exit(0);
655 }
656 nowhmove:
657 prtbrd();
658
659 roll();
660 retry:
661 printf("your roll is %d, %d\n", die1, die2);
662 printf("your move, please?? ");
663 getstr(s);
664 if (*s == 0) {
665 printf("red's move skipped\n");
666 goto whitesmv;
667 }
668 n = sscanf(s, "%d%d%d%d%d", &go[0], &go[1], &go[2], &go[3],
669 &go[4]);
670 if ((die1 != die2 && n > 2) || n > 4) {
671 printf("you've made too many moves\n");
672 goto retry;
673 }
674 go[n] = NIL;
675 if (*s == '-') {
676 go[0] = -go[0];
677 t = die1;
678 die1 = die2;
679 die2 = t;
680 }
681 for (k = 0; k < n; k++) {
682 if (0 <= go[k] && go[k] <= 24)
683 continue;
684 else {
685 printf("move %d is illegal\n", go[k]);
686 goto retry;
687 }
688 }
689 if (play(red, white, go))
690 goto retry;
691 if (piececount(red, 0, 24) == 0) {
692 printf("Red wins.\n");
693 printf
694 ("Congratulations! You have just defeated a dumb machine.\n");
695 exit(0);
696 }
697 goto whitesmv;
698 }
699