Commit | Line | Data |
---|---|---|
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*/ | |
8 | int die1; | |
9 | int die2; | |
10 | int i; | |
11 | int j; | |
12 | int l; | |
13 | int m; | |
14 | int count; | |
15 | int 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}; | |
18 | int 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}; | |
21 | int probability[]{0,11,12,13,14,15,16, | |
22 | 06,05,04,03,02,01}; | |
23 | int imoves; | |
24 | int goodmoves[MAXGMOV] ; | |
25 | int probmoves[MAXGMOV] ; | |
26 | struct {int pos[4],mov[4];} moves[MAXIMOVES] ; | |
27 | ||
28 | main() | |
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; | |
49 | whitesmv: | |
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 | } | |
59 | nowhmove: | |
60 | prtbrd(); | |
61 | ||
62 | roll(); | |
63 | retry: | |
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 | ||
99 | getstr(s) | |
100 | char *s; | |
101 | { | |
102 | while((*s=getchar())!='\n')s++; | |
103 | *s=0; | |
104 | } | |
105 | ||
106 | play(player,playee,pos) | |
107 | int *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 | ||
140 | badmove: | |
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 | } | |
149 | nextmove(player,playee) | |
150 | int *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 | } | |
170 | prtmov(k) | |
171 | int 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 | } | |
181 | update(player,playee,k) | |
182 | int *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 | } | |
196 | piececount(player,startrow,endrow) | |
197 | int *player,startrow,endrow; | |
198 | { | |
199 | int sum; | |
200 | sum=0; | |
201 | while(startrow<=endrow) | |
202 | sum=+player[startrow++]; | |
203 | return(sum); | |
204 | } | |
205 | /* | |
206 | prtmovs() | |
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 | ||
221 | roll() | |
222 | { | |
223 | extern int die1,die2; | |
224 | die1=(rand()>>8)%6+1; | |
225 | die2=(rand()>>8)%6+1; | |
226 | } | |
227 | ||
228 | movegen(mover,movee) | |
229 | int *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 | } | |
315 | moverecord(mover) | |
316 | int *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){ | |
324 | case 4: | |
325 | moves[imoves].pos[3]=m; | |
326 | moves[imoves].mov[3]=die1; | |
327 | case 3: | |
328 | moves[imoves].pos[2]=l; | |
329 | moves[imoves].mov[2]=die1; | |
330 | case 2: | |
331 | moves[imoves].pos[1]=j; | |
332 | moves[imoves].mov[1]=die2; | |
333 | case 1: | |
334 | moves[imoves].pos[0]=i; | |
335 | moves[imoves].mov[0]=die1; | |
336 | imoves++; | |
337 | } | |
338 | undo: | |
339 | switch(count){ | |
340 | case 4: | |
341 | break; | |
342 | case 3: | |
343 | mover[l]++; | |
344 | mover[l+die1]--; | |
345 | break; | |
346 | case 2: | |
347 | mover[j]++; | |
348 | mover[j+die2]--; | |
349 | break; | |
350 | case 1: | |
351 | mover[i]++; | |
352 | mover[i+die1]--; | |
353 | } | |
354 | } | |
355 | ||
356 | ||
357 | strategy(player,playee) | |
358 | int *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 | ||
394 | eval(player,playee,k,prob) | |
395 | int *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 | } | |
456 | instructions() | |
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 | ||
485 | getprob(player,playee,start,finish) | |
486 | int *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 | } | |
504 | prtbrd() | |
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 | } | |
542 | numline(upcol,downcol,start,fin) | |
543 | int *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 | } | |
551 | colorline(upcol,c1,downcol,c2,start,fin) | |
552 | int *upcol,*downcol,start,fin; | |
553 | char 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 | ||
565 | int rrno 0; | |
566 | ||
567 | srand(){ | |
568 | rrno = _look( 0x40000 ); | |
569 | _store( 0x40000, rrno+1 ); | |
570 | } | |
571 | ||
572 | rand(){ | |
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 | } |