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