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