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