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