![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to move.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / games / backgammon|
Return to move.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / games / backgammon |
1.1 root 1: /*
2: * Copyright (c) 1980 Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted
6: * provided that the above copyright notice and this paragraph are
7: * duplicated in all such forms and that any documentation,
8: * advertising materials, and other materials related to such
9: * distribution and use acknowledge that the software was developed
10: * by the University of California, Berkeley. The name of the
11: * University may not be used to endorse or promote products derived
12: * from this software without specific prior written permission.
13: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
14: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
15: * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
16: */
17:
18: #ifndef lint
19: static char sccsid[] = "@(#)move.c 5.4 (Berkeley) 6/18/88";
20: #endif /* not lint */
21:
22: #include "back.h"
23:
24: #ifdef DEBUG
25: #include <stdio.h>
26: FILE *trace;
27: static char tests[20];
28: #endif
29:
30: struct BOARD { /* structure of game position */
31: int b_board[26]; /* board position */
32: int b_in[2]; /* men in */
33: int b_off[2]; /* men off */
34: int b_st[4], b_fn[4]; /* moves */
35:
36: struct BOARD *b_next; /* forward queue pointer */
37: };
38:
39: struct BOARD *freeq = 0;
40: struct BOARD *checkq = 0;
41: struct BOARD *bsave();
42: struct BOARD *nextfree();
43:
44: /* these variables are values for the
45: * candidate move */
46: static int ch; /* chance of being hit */
47: static int op; /* computer's open men */
48: static int pt; /* comp's protected points */
49: static int em; /* farthest man back */
50: static int frc; /* chance to free comp's men */
51: static int frp; /* chance to free pl's men */
52:
53: /* these values are the values for the
54: * move chosen (so far) */
55: static int chance; /* chance of being hit */
56: static int openmen; /* computer's open men */
57: static int points; /* comp's protected points */
58: static int endman; /* farthest man back */
59: static int barmen; /* men on bar */
60: static int menin; /* men in inner table */
61: static int menoff; /* men off board */
62: static int oldfrc; /* chance to free comp's men */
63: static int oldfrp; /* chance to free pl's men */
64:
65: static int cp[5]; /* candidate start position */
66: static int cg[5]; /* candidate finish position */
67:
68: static int race; /* game reduced to a race */
69:
70: move (okay)
71: int okay; /* zero if first move */
72: {
73: register int i; /* index */
74: register int l; /* last man */
75:
76: if (okay) {
77: /* see if comp should double */
78: if (gvalue < 64 && dlast != cturn && dblgood()) {
79: writel (*Colorptr);
80: dble(); /* double */
81: /* return if declined */
82: if (cturn != 1 && cturn != -1)
83: return;
84: }
85: roll();
86: }
87:
88: race = 0;
89: for (i = 0; i < 26; i++) {
90: if (board[i] < 0)
91: l = i;
92: }
93: for (i = 0; i < l; i++) {
94: if (board[i] > 0)
95: break;
96: }
97: if (i == l)
98: race = 1;
99:
100: /* print roll */
101: if (tflag)
102: curmove (cturn == -1? 18: 19,0);
103: writel (*Colorptr);
104: writel (" rolls ");
105: writec (D0+'0');
106: writec (' ');
107: writec (D1+'0');
108: /* make tty interruptable
109: * while thinking */
110: if (tflag)
111: cline();
112: fixtty (noech);
113:
114: /* find out how many moves */
115: mvlim = movallow();
116: if (mvlim == 0) {
117: writel (" but cannot use it.\n");
118: nexturn();
119: fixtty (raw);
120: return;
121: }
122:
123: /* initialize */
124: for (i = 0; i < 4; i++)
125: cp[i] = cg[i] = 0;
126:
127: /* strategize */
128: trymove (0,0);
129: pickmove();
130:
131: /* print move */
132: writel (" and moves ");
133: for (i = 0; i < mvlim; i++) {
134: if (i > 0)
135: writec (',');
136: wrint (p[i] = cp[i]);
137: writec ('-');
138: wrint (g[i] = cg[i]);
139: makmove (i);
140: }
141: writec ('.');
142:
143: /* print blots hit */
144: if (tflag)
145: curmove (20,0);
146: else
147: writec ('\n');
148: for (i = 0; i < mvlim; i++)
149: if (h[i])
150: wrhit(g[i]);
151: /* get ready for next move */
152: nexturn();
153: if (!okay) {
154: buflush();
155: sleep (3);
156: }
157: fixtty (raw); /* no more tty interrupt */
158: }
159:
160: trymove (mvnum,swapped)
161: register int mvnum; /* number of move (rel zero) */
162: int swapped; /* see if swapped also tested */
163:
164: {
165: register int pos; /* position on board */
166: register int rval; /* value of roll */
167:
168: /* if recursed through all dice
169: * values, compare move */
170: if (mvnum == mvlim) {
171: binsert (bsave());
172: return;
173: }
174:
175: /* make sure dice in always
176: * same order */
177: if (d0 == swapped)
178: swap;
179: /* choose value for this move */
180: rval = dice[mvnum != 0];
181:
182: /* find all legitimate moves */
183: for (pos = bar; pos != home; pos += cturn) {
184: /* fix order of dice */
185: if (d0 == swapped)
186: swap;
187: /* break if stuck on bar */
188: if (board[bar] != 0 && pos != bar)
189: break;
190: /* on to next if not occupied */
191: if (board[pos]*cturn <= 0)
192: continue;
193: /* set up arrays for move */
194: p[mvnum] = pos;
195: g[mvnum] = pos+rval*cturn;
196: if (g[mvnum]*cturn >= home) {
197: if (*offptr < 0)
198: break;
199: g[mvnum] = home;
200: }
201: /* try to move */
202: if (makmove (mvnum))
203: continue;
204: else
205: trymove (mvnum+1,2);
206: /* undo move to try another */
207: backone (mvnum);
208: }
209:
210: /* swap dice and try again */
211: if ((!swapped) && D0 != D1)
212: trymove (0,1);
213: }
214:
215: struct BOARD *
216: bsave () {
217: register int i; /* index */
218: struct BOARD *now; /* current position */
219:
220: now = nextfree (); /* get free BOARD */
221:
222: /* store position */
223: for (i = 0; i < 26; i++)
224: now->b_board[i] = board[i];
225: now->b_in[0] = in[0];
226: now->b_in[1] = in[1];
227: now->b_off[0] = off[0];
228: now->b_off[1] = off[1];
229: for (i = 0; i < mvlim; i++) {
230: now->b_st[i] = p[i];
231: now->b_fn[i] = g[i];
232: }
233: return (now);
234: }
235:
236: binsert (new)
237: struct BOARD *new; /* item to insert */
238: {
239: register struct BOARD *p = checkq; /* queue pointer */
240: register int result; /* comparison result */
241:
242: if (p == 0) { /* check if queue empty */
243: checkq = p = new;
244: p->b_next = 0;
245: return;
246: }
247:
248: result = bcomp (new,p); /* compare to first element */
249: if (result < 0) { /* insert in front */
250: new->b_next = p;
251: checkq = new;
252: return;
253: }
254: if (result == 0) { /* duplicate entry */
255: mvcheck (p,new);
256: makefree (new);
257: return;
258: }
259:
260: while (p->b_next != 0) { /* traverse queue */
261: result = bcomp (new,p->b_next);
262: if (result < 0) { /* found place */
263: new->b_next = p->b_next;
264: p->b_next = new;
265: return;
266: }
267: if (result == 0) { /* duplicate entry */
268: mvcheck (p->b_next,new);
269: makefree (new);
270: return;
271: }
272: p = p->b_next;
273: }
274: /* place at end of queue */
275: p->b_next = new;
276: new->b_next = 0;
277: }
278:
279: bcomp (a,b)
280: struct BOARD *a;
281: struct BOARD *b;
282: {
283: register int *aloc = a->b_board; /* pointer to board a */
284: register int *bloc = b->b_board; /* pointer to board b */
285: register int i; /* index */
286: int result; /* comparison result */
287:
288: for (i = 0; i < 26; i++) { /* compare boards */
289: result = cturn*(aloc[i]-bloc[i]);
290: if (result)
291: return (result); /* found inequality */
292: }
293: return (0); /* same position */
294: }
295:
296: mvcheck (incumbent,candidate)
297: register struct BOARD *incumbent;
298: register struct BOARD *candidate;
299: {
300: register int i;
301: register int result;
302:
303: for (i = 0; i < mvlim; i++) {
304: result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
305: if (result > 0)
306: return;
307: if (result < 0)
308: break;
309: }
310: if (i == mvlim)
311: return;
312: for (i = 0; i < mvlim; i++) {
313: incumbent->b_st[i] = candidate->b_st[i];
314: incumbent->b_fn[i] = candidate->b_fn[i];
315: }
316: }
317:
318: makefree (dead)
319: struct BOARD *dead; /* dead position */
320: {
321: dead->b_next = freeq; /* add to freeq */
322: freeq = dead;
323: }
324:
325: struct BOARD *
326: nextfree () {
327: struct BOARD *new;
328:
329: if (freeq == 0) {
330: new = (struct BOARD *)calloc (1,sizeof (struct BOARD));
331: if (new == 0) {
332: writel ("\nOut of memory\n");
333: getout();
334: }
335: new->b_next = 0;
336: return (new);
337: }
338:
339: new = freeq;
340: freeq = freeq->b_next;
341: }
342:
343: pickmove () {
344: /* current game position */
345: register struct BOARD *now = bsave();
346: register struct BOARD *next; /* next move */
347:
348: #ifdef DEBUG
349: if (trace == NULL)
350: trace = fopen ("bgtrace","w");
351: fprintf (trace,"\nRoll: %d %d%s\n",D0,D1,race? " (race)": "");
352: fflush (trace);
353: #endif
354: do { /* compare moves */
355: bcopy (checkq);
356: next = checkq->b_next;
357: makefree (checkq);
358: checkq = next;
359: movcmp();
360: } while (checkq != 0);
361:
362: bcopy (now);
363: }
364:
365: bcopy (s)
366: register struct BOARD *s; /* game situation */
367: {
368: register int i; /* index */
369:
370: for (i = 0; i < 26; i++)
371: board[i] = s->b_board[i];
372: for (i = 0; i < 2; i++) {
373: in[i] = s->b_in[i];
374: off[i] = s->b_off[i];
375: }
376: for (i = 0; i < mvlim; i++) {
377: p[i] = s->b_st[i];
378: g[i] = s->b_fn[i];
379: }
380: }
381:
382: movcmp () {
383: register int i;
384: register int c;
385:
386: #ifdef DEBUG
387: if (trace == NULL)
388: trace = fopen ("bgtrace","w");
389: #endif
390:
391: odds (0,0,0);
392: if (!race) {
393: ch = op = pt = 0;
394: for (i = 1; i < 25; i++) {
395: if (board[i] == cturn)
396: ch = canhit (i,1);
397: op += abs (bar-i);
398: }
399: for (i = bar+cturn; i != home; i += cturn)
400: if (board[i]*cturn > 1)
401: pt += abs(bar-i);
402: frc = freemen (bar)+trapped (bar,cturn);
403: frp = freemen (home)+trapped (home,-cturn);
404: }
405: for (em = bar; em != home; em += cturn)
406: if (board[em]*cturn > 0)
407: break;
408: em = abs(home-em);
409: #ifdef DEBUG
410: fputs ("Board: ",trace);
411: for (i = 0; i < 26; i++)
412: fprintf (trace, " %d",board[i]);
413: if (race)
414: fprintf (trace,"\n\tem = %d\n",em);
415: else
416: fprintf (trace,
417: "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
418: ch,pt,em,frc,frp);
419: fputs ("\tMove: ",trace);
420: for (i = 0; i < mvlim; i++)
421: fprintf (trace," %d-%d",p[i],g[i]);
422: fputs ("\n",trace);
423: fflush (trace);
424: strcpy (tests,"");
425: #endif
426: if ((cp[0] == 0 && cg[0] == 0) || movegood()) {
427: #ifdef DEBUG
428: fprintf (trace,"\t[%s] ... wins.\n",tests);
429: fflush (trace);
430: #endif
431: for (i = 0; i < mvlim; i++) {
432: cp[i] = p[i];
433: cg[i] = g[i];
434: }
435: if (!race) {
436: chance = ch;
437: openmen = op;
438: points = pt;
439: endman = em;
440: barmen = abs(board[home]);
441: oldfrc = frc;
442: oldfrp = frp;
443: }
444: menin = *inptr;
445: menoff = *offptr;
446: }
447: #ifdef DEBUG
448: else {
449: fprintf (trace,"\t[%s] ... loses.\n",tests);
450: fflush (trace);
451: }
452: #endif
453: }
454:
455: movegood () {
456: register int n;
457:
458: if (*offptr == 15)
459: return (1);
460: if (menoff == 15)
461: return (0);
462: if (race) {
463: #ifdef DEBUG
464: strcat (tests,"o");
465: #endif
466: if (*offptr-menoff)
467: return (*offptr > menoff);
468: #ifdef DEBUG
469: strcat (tests,"e");
470: #endif
471: if (endman-em)
472: return (endman > em);
473: #ifdef DEBUG
474: strcat (tests,"i");
475: #endif
476: if (menin == 15)
477: return (0);
478: if (*inptr == 15)
479: return (1);
480: #ifdef DEBUG
481: strcat (tests,"i");
482: #endif
483: if (*inptr-menin)
484: return (*inptr > menin);
485: return (rnum(2));
486: } else {
487: n = barmen-abs(board[home]);
488: #ifdef DEBUG
489: strcat (tests,"c");
490: #endif
491: if (abs(chance-ch)+25*n > rnum(150))
492: return (n? (n < 0): (ch < chance));
493: #ifdef DEBUG
494: strcat (tests,"o");
495: #endif
496: if (*offptr-menoff)
497: return (*offptr > menoff);
498: #ifdef DEBUG
499: strcat (tests,"o");
500: #endif
501: if (abs(openmen-op) > 7+rnum(12))
502: return (openmen > op);
503: #ifdef DEBUG
504: strcat (tests,"b");
505: #endif
506: if (n)
507: return (n < 0);
508: #ifdef DEBUG
509: strcat (tests,"e");
510: #endif
511: if (abs(endman-em) > rnum(2))
512: return (endman > em);
513: #ifdef DEBUG
514: strcat (tests,"f");
515: #endif
516: if (abs(frc-oldfrc) > rnum(2))
517: return (frc < oldfrc);
518: #ifdef DEBUG
519: strcat (tests,"p");
520: #endif
521: if (abs(n = pt-points) > rnum(4))
522: return (n > 0);
523: #ifdef DEBUG
524: strcat (tests,"i");
525: #endif
526: if (*inptr-menin)
527: return (*inptr > menin);
528: #ifdef DEBUG
529: strcat (tests,"f");
530: #endif
531: if (abs(frp-oldfrp) > rnum(2))
532: return (frp > oldfrp);
533: return (rnum(2));
534: }
535: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.