Research V7 development
[unix-history] / usr / src / games / backgammon.c
CommitLineData
1555795d
KT
1# include <stdio.h>
2
3#
4#define NIL (-1)
5#define MAXGMOV 10
6#define MAXIMOVES 1000
7 char level; /*'b'=beginner, 'i'=intermediate, 'e'=expert*/
8int die1;
9int die2;
10int i;
11int j;
12int l;
13int m;
14int count;
15int red[] {0,2,0,0,0,0,0,0,0,0,0,0,5,
16 0,0,0,0,3,0,5,0,0,0,0,0,
17 0,0,0,0,0,0};
18int white[] {0,2,0,0,0,0,0,0,0,0,0,0,5,
19 0,0,0,0,3,0,5,0,0,0,0,0,
20 0,0,0,0,0,0};
21int probability[]{0,11,12,13,14,15,16,
22 06,05,04,03,02,01};
23int imoves;
24int goodmoves[MAXGMOV] ;
25int probmoves[MAXGMOV] ;
26struct {int pos[4],mov[4];} moves[MAXIMOVES] ;
27
28main()
29{
30 int t,k,n,go[5];
31 char s[100];
32 go[5]=NIL;
33 srand();
34 printf( "Do you want instructions? Type 'y' for yes,\n");
35 printf( "anything else means no.?? ");
36 getstr(s);
37 if(*s=='y')instructions();
38 printf( "Choose the level of your oppponent.\n");
39 printf( "Type 'b' for beginner, or 'i' for intermediate.\n");
40 printf( "Anything else gets you an expert.?? ");
41 level='e';
42 getstr(s);
43 if(*s=='b')level='b';
44 else if(*s=='i')level='i';
45 printf( "You will play red. Do you wan't to move first?\n");
46 printf( "Type 'y' for yes, anything else means no.?? ");
47 getstr(s);
48 if(*s=='y')goto nowhmove;
49whitesmv:
50 roll();
51 printf( "white rolls %d,%d\n",die1,die2);
52 printf( "white's move is:");
53 if(nextmove(white,red)==NIL)goto nowhmove;
54 if(piececount(white,0,24)==0){
55 printf( "White wins\n");
56 printf( "Aren't you ashamed. You've been beaten by a computer.\n");
57 exit();
58 }
59nowhmove:
60 prtbrd();
61
62 roll();
63retry:
64 printf( "your roll is %d, %d\n",die1,die2);
65 printf( "your move, please?? ");
66 getstr(s);
67 if(*s==0){
68 printf( "red's move skipped\n");
69 goto whitesmv;
70 }
71 n=sscanf(s,"%d%d%d%d%d",&go[0],&go[1],&go[2],&go[3],&go[4]);
72 if((die1!=die2&&n>2)||n>4){
73 printf( "you've made too many moves\n");
74 goto retry;
75 }
76 go[n]=NIL;
77 if(*s=='-'){
78 go[0]= -go[0];
79 t=die1;
80 die1=die2;
81 die2=t;
82 }
83 for(k=0;k<n;k++){
84 if(0<=go[k] && go[k]<=24)continue;
85 else{
86 printf( "move %d is illegal\n",go[k]);
87 goto retry;
88 }
89 }
90 if(play(red,white,go))goto retry;
91 if(piececount(red,0,24)==0){
92 printf( "Red wins.\n");
93 printf( "Congratulations! You have just defeated a dumb machine.\n");
94 exit();
95 }
96 goto whitesmv;
97}
98
99getstr(s)
100char *s;
101{
102 while((*s=getchar())!='\n')s++;
103 *s=0;
104}
105
106play(player,playee,pos)
107int *player,*playee,pos[];
108{
109 int k,n,die,ipos;
110 for(k=0;k<player[0];k++){ /*blots on player[0] must be moved first*/
111 if(pos[k]==NIL)break;
112 if(pos[k]!=0){
113 printf( "piece on position 0 must be moved first\n");
114 return(-1);
115 }
116 }
117 for(k=0;(ipos=pos[k])!=NIL;k++){
118 die=k?die2:die1;
119 n=25-ipos-die;
120 if(player[ipos]==0)goto badmove;
121 if(n>0&&playee[n]>=2)goto badmove;
122 if(n<=0){
123 if(piececount(player,0,18)!=0)goto badmove;
124 if((ipos+die)!=25&&
125 piececount(player,19,24-die)!=0)goto badmove;
126 }
127 player[ipos]--;
128 player[ipos+die]++;
129 }
130 for(k=0;pos[k]!=NIL;k++){
131 die=k?die2:die1;
132 n=25-pos[k]-die;
133 if(n>0 && playee[n]==1){
134 playee[n]=0;
135 playee[0]++;
136 }
137 }
138 return(0);
139
140badmove:
141 printf( "Move %d is not legal.\n",ipos);
142 while(k--){
143 die=k?die2:die1;
144 player[pos[k]]++;
145 player[pos[k]+die]--;
146 }
147 return(-1);
148}
149nextmove(player,playee)
150int *player,*playee;
151{
152 int k;
153 imoves=0;
154 movegen(player,playee);
155 if(die1!=die2){
156 k=die1;
157 die1=die2;
158 die2=k;
159 movegen(player,playee);
160 }
161 if(imoves==0){
162 printf( "roll was %d,%d; no white move possible\n",die1,die2);
163 return(NIL);
164 }
165 k=strategy(player,playee); /*select kth possible move*/
166 prtmov(k);
167 update(player,playee,k);
168 return(0);
169}
170prtmov(k)
171int k;
172{
173 int n;
174 if(k==NIL)printf( "no move possible\n");
175 else for(n=0;n<4;n++){
176 if(moves[k].pos[n]==NIL)break;
177 printf( " %d, %d",25-moves[k].pos[n],moves[k].mov[n]);
178 }
179 printf( "\n");
180}
181update(player,playee,k)
182int *player,*playee,k;
183{
184 int n,t;
185 for(n=0;n<4;n++){
186 if(moves[k].pos[n]==NIL)break;
187 player[moves[k].pos[n]]--;
188 player[moves[k].pos[n]+moves[k].mov[n]]++;
189 t=25-moves[k].pos[n]-moves[k].mov[n];
190 if(t>0 && playee[t]==1){
191 playee[0]++;
192 playee[t]--;
193 }
194 }
195}
196piececount(player,startrow,endrow)
197int *player,startrow,endrow;
198{
199 int sum;
200 sum=0;
201 while(startrow<=endrow)
202 sum=+player[startrow++];
203 return(sum);
204}
205/*
206prtmovs()
207{
208 int i1,i2;
209 printf( "possible moves are\n");
210 for(i1=0;i1<imoves;i1++){
211 printf( "\n%d",i1);
212 for(i2=0;i2<4;i2++){
213 if(moves[i1].pos[i2]==NIL)break;
214 printf( "%d, %d",moves[i1].pos[i2],moves[i1].mov[i2]);
215 }
216 }
217 printf( "\n");
218}
219*/
220
221roll()
222{
223 extern int die1,die2;
224 die1=(rand()>>8)%6+1;
225 die2=(rand()>>8)%6+1;
226}
227
228movegen(mover,movee)
229int *mover,*movee;
230{
231 extern int i,j,l,m,count;
232 extern int die1,die2;
233 int k;
234 for(i=0;i<=24;i++){
235 count=0;
236 if(mover[i]==0)continue;
237 if((k=25-i-die1)>0&&movee[k]>=2)
238 if(mover[0]>0)break;
239 else continue;
240 if(k<=0){
241 if(piececount(mover,0,18)!=0)break;
242 if((i+die1)!=25&&
243 piececount(mover,19,24-die1)!=0)break;
244 }
245 mover[i]--;
246 mover[i+die1]++;
247 count=1;
248 for(j=0;j<=24;j++){
249 if(mover[j]==0)continue;
250 if((k=25-j-die2)>0&&movee[k]>=2)
251 if(mover[0]>0)break;
252 else continue;
253 if(k<=0){
254 if(piececount(mover,0,18)!=0)break;
255 if((j+die2)!=25&&
256 piececount(mover,19,24-die2)!=0)break;
257 }
258 mover[j]--;
259 mover[j+die2]++;
260 count=2;
261 if(die1!=die2){
262 moverecord(mover);
263 if(mover[0]>0)break;
264 else continue;
265 }
266 for(l=0;l<=24;l++){
267 if(mover[l]==0)continue;
268 if((k=25-l-die1)>0&&movee[k]>=2)
269 if(mover[0]>0)break;
270 else continue;
271 if(k<=0){
272 if(piececount(mover,0,18)!=0)break;
273 if((l+die2)!=25&&
274 piececount(mover,19,24-die1)!=0)break;
275 }
276 mover[l]--;
277 mover[l+die1]++;
278 count=3;
279 for(m=0;m<=24;m++){
280 if(mover[m]==0)continue;
281 if((k=25-m-die1)>=0&&movee[k]>=2)
282 if(mover[0]>0)break;
283 else continue;
284 if(k<=0){
285 if(piececount(mover,0,18)!=0)break;
286 if((m+die2)!=25&&
287 piececount(mover,19,24-die1)!=0)break;
288 }
289 count=4;
290 moverecord(mover);
291 if(mover[0]>0)break;
292 }
293 if(count==3)moverecord(mover);
294 else{
295 mover[l]++;
296 mover[l+die1]--;
297 }
298 if(mover[0]>0)break;
299 }
300 if(count==2)moverecord(mover);
301 else{
302 mover[j]++;
303 mover[j+die1]--;
304 }
305 if(mover[0]>0)break;
306 }
307 if(count==1)moverecord(mover);
308 else{
309 mover[i]++;
310 mover[i+die1]--;
311 }
312 if(mover[0]>0)break;
313 }
314}
315moverecord(mover)
316int *mover;
317{
318 extern int i,j,l,m,imoves,count;
319 int t;
320 if(imoves>=MAXIMOVES)goto undo;;
321 for(t=0;t<=3;t++)
322 moves[imoves].pos[t]= NIL;
323 switch(count){
324case 4:
325 moves[imoves].pos[3]=m;
326 moves[imoves].mov[3]=die1;
327case 3:
328 moves[imoves].pos[2]=l;
329 moves[imoves].mov[2]=die1;
330case 2:
331 moves[imoves].pos[1]=j;
332 moves[imoves].mov[1]=die2;
333case 1:
334 moves[imoves].pos[0]=i;
335 moves[imoves].mov[0]=die1;
336 imoves++;
337 }
338undo:
339 switch(count){
340case 4:
341 break;
342case 3:
343 mover[l]++;
344 mover[l+die1]--;
345 break;
346case 2:
347 mover[j]++;
348 mover[j+die2]--;
349 break;
350case 1:
351 mover[i]++;
352 mover[i+die1]--;
353 }
354}
355
356
357strategy(player,playee)
358int *player,*playee;
359{
360 extern char level;
361 int k,n,nn,bestval,moveval,prob;
362 n=0;
363 if(imoves==0)return(NIL);
364 goodmoves[0]=NIL;
365 bestval= -32000;
366 for(k=0;k<imoves;k++){
367 if((moveval=eval(player,playee,k,&prob))<bestval)continue;
368 if(moveval>bestval){
369 bestval=moveval;
370 n=0;
371 }
372 if(n<MAXGMOV){
373 goodmoves[n]=k;
374 probmoves[n++]=prob;
375 }
376 }
377 if(level=='e' && n>1){
378 nn=n;
379 n=0;
380 prob=32000;
381 for(k=0;k<nn;k++){
382 if((moveval=probmoves[k])>prob)continue;
383 if(moveval<prob){
384 prob=moveval;
385 n=0;
386 }
387 goodmoves[n]=goodmoves[k];
388 probmoves[n++]=probmoves[k];
389 }
390 }
391 return(goodmoves[(rand()>>4)%n]);
392}
393
394eval(player,playee,k,prob)
395int *player,*playee,k,*prob;
396{
397 extern char level;
398 int newtry[31],newother[31],*r,*q,*p,n,sum,first;
399 int ii,lastwhite,lastred;
400 *prob=sum=0;
401 r=player+25;
402 p=newtry;
403 q=newother;
404 while(player<r){
405 *p++= *player++;
406 *q++= *playee++;
407 }
408 q=newtry+31;
409 for(p=newtry+25;p<q;) *p++ = 0; /*zero out spaces for hit pieces*/
410 for(n=0;n<4;n++){
411 if(moves[k].pos[n]==NIL)break;
412 newtry[moves[k].pos[n]]--;
413 newtry[ii=moves[k].pos[n]+moves[k].mov[n]]++;
414 if(ii<25 && newother[25-ii]==1){
415 newother[25-ii]=0;
416 newother[0]++;
417 if(ii<=15 && level=='e')sum++; /*hit if near other's home*/
418 }
419 }
420 for(lastred=0;newother[lastred]==0;lastred++);
421 for(lastwhite=0;newtry[lastwhite]==0;lastwhite++);
422 lastwhite=25-lastwhite;
423 if(lastwhite<=6 && lastwhite<lastred)sum=1000;
424 if(lastwhite<lastred && level=='e'
425 && lastwhite>6){ /*expert's running game.
426 First priority to get all
427 pieces into white's home*/
428 for(sum=1000;lastwhite>6;lastwhite--)
429 sum=sum-lastwhite*newtry[25-lastwhite];
430 }
431 for(first=0;first<25;first++)
432 if(newother[first]!=0)break; /*find other's first piece*/
433 q=newtry+25;
434 for(p=newtry+1;p<q;)if(*p++ > 1)sum++; /*blocked points are good*/
435 if(first>5){ /*only stress removing pieces if homeboard
436 cannot be hit
437 */
438 q=newtry+31;
439 p=newtry+25;
440 for(n=6;p<q;n--)
441 sum=+ *p++ * n; /*remove pieces, but just barely*/
442 }
443 if(level!='b'){
444 r=newtry+25-first; /*singles past this point can't be hit*/
445 for(p=newtry+7;p<r;)
446 if(*p++ == 1)sum--; /*singles are bad after 1st 6 points
447 if they can be hit*/
448 q=newtry+3;
449 for(p=newtry;p<q;)sum=- *p++; /*bad to be on 1st three points*/
450 }
451
452 for(n=1;n<=4;n++)
453 *prob=+ n*getprob(newtry,newother,6*n-5,6*n);
454 return(sum);
455}
456instructions()
457{
458 printf( "To play backgammon, type the numbers of the points\n");
459 printf( "from which pieces are to be moved. Thus, if the\n");
460 printf( "roll is '3,5', typing '2 6' will move a piece\n");
461 printf( "from point 2 three spaces to point 5,\n");
462 printf( "and a piece from point 6 forward to\n");
463 printf( "point 11. If the moves must be made in the\n");
464 printf( "opposite order, the first character typed must\n");
465 printf( "be a minus ('-'). Thus, typing\n");
466 printf( "'-2 6' moves the piece on point 2\n");
467 printf( "by 5, and the piece on point 6 by 3.\n");
468 printf( "If you want to move a single piece several times,\n");
469 printf( "the sequence of points from which it is to be\n");
470 printf( "moved must be typed. Thus '14 17' will move\n");
471 printf( "a piece from point 14 to point 17 and thence to\n");
472 printf( "to point 22.\n");
473 printf( "If a double is rolled, you should type four numbers.\n");
474 printf( "Red pieces that have been removed from the board by\n");
475 printf( "being hit by white are on point 0 and\n");
476 printf( "must be brought in before any other move can be made.\n");
477 printf( "White pieces that are hit are removed to point 25.\n");
478 printf( "You will not be allowed to make an illegal move, or\n");
479 printf( "to make too many moves. However, if you make too\n");
480 printf( "few moves, the program does not care. In particular\n");
481 printf( "you may skip your turn by typing a 'new-line'\n");
482 printf( "all by itself.\n\n");
483}
484
485getprob(player,playee,start,finish)
486int *player,*playee,start,finish;
487{ /*returns the probability (times 102) that any
488 pieces belonging to 'player' and lying between
489 his points 'start' and 'finish' will be hit
490 by a piece belonging to playee
491 */
492 int k,n,sum;
493 sum=0;
494 for(;start<=finish;start++){
495 if(player[start]==1){
496 for(k=1;k<=12;k++){
497 if((n=25-start-k)<0)break;
498 if(playee[n]!=0)sum=+probability[k];
499 }
500 }
501 }
502 return(sum);
503}
504prtbrd()
505{
506 int k;
507 printf( "White's Home\n");
508 for(k=1;k<=6;k++)
509 printf( "%4d",k);
510 printf( " ");
511 for(k=7;k<=12;k++)printf( "%4d",k);
512 putchar('\r' );
513 for(k=1;k<=54;k++)putchar('_' );
514 putchar('\n' );
515 numline(red,white,1,6);
516 printf( " ");
517 numline(red,white,7,12);
518 putchar('\n' );
519 colorline(red,'R',white,'W',1,6);
520 printf( " ");
521 colorline(red,'R',white,'W',7,12);
522 putchar('\n' );
523 if(white[0]!=0)printf( "%28dW\n",white[0]);
524 else putchar('\n' );
525 if(red[0]!=0)printf( "%28dR\n",red[0]);
526 else putchar('\n' );
527 colorline(white,'W',red,'R',1,6);
528 printf( " ");
529 colorline(white,'W',red,'R',7,12);
530 putchar('\n' );
531 numline(white,red,1,6);
532 printf( " ");
533 numline(white,red,7,12);
534 putchar('\r' );
535 for(k=1;k<=54;k++)putchar('_' );
536 putchar('\n' );
537 for(k=24;k>=19;k--)printf( "%4d",k);
538 printf( " ");
539 for(k=18;k>=13;k--)printf( "%4d",k);
540 printf( "\nRed's Home\n\n\n\n\n");
541}
542numline(upcol,downcol,start,fin)
543int *upcol,*downcol,start,fin;
544{
545 int k,n;
546 for(k=start;k<=fin;k++){
547 if((n=upcol[k])!=0 || (n=downcol[25-k])!=0)printf( "%4d",n);
548 else printf( " ");
549 }
550}
551colorline(upcol,c1,downcol,c2,start,fin)
552int *upcol,*downcol,start,fin;
553char c1,c2;
554{
555 int k;
556 char c;
557 for(k=start;k<=fin;k++){
558 c=' ';
559 if(upcol[k]!=0)c=c1;
560 if(downcol[25-k]!=0)c=c2;
561 printf( " %c",c);
562 }
563}
564
565int rrno 0;
566
567srand(){
568 rrno = _look( 0x40000 );
569 _store( 0x40000, rrno+1 );
570 }
571
572rand(){
573 rrno =* 0106273;
574 rrno =+ 020202;
575 return( rrno & 077777 );
576 }
577
578_look(p) int *p; {
579 return( *p );
580 }
581
582_store( p, numb ) int *p; {
583 *p = numb;
584 }