2 * Copyright (c) 1980, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)move.c 8.1 (Berkeley) 5/31/93
30 * $FreeBSD: src/games/backgammon/backgammon/move.c,v 1.5 1999/11/30 03:48:23 billf Exp $
38 static char tests[20];
41 static void trymove(int, int);
42 static struct BOARD *bsave(void);
43 static void binsert(struct BOARD *);
44 static int bcomp(struct BOARD *, struct BOARD *);
45 static void mvcheck(struct BOARD *, struct BOARD *);
46 static void makefree(struct BOARD *);
47 static struct BOARD *nextfree(void);
48 static void pickmove(void);
49 static void boardcopy(struct BOARD *);
50 static void movcmp(void);
51 static int movegood(void);
53 struct BOARD { /* structure of game position */
54 int b_board[26]; /* board position */
55 int b_in[2]; /* men in */
56 int b_off[2]; /* men off */
57 int b_st[4], b_fn[4]; /* moves */
59 struct BOARD *b_next; /* forward queue pointer */
62 struct BOARD *freeq = NULL;
63 struct BOARD *checkq = NULL;
65 /* these variables are values for the candidate move */
66 static int ch; /* chance of being hit */
67 static int op; /* computer's open men */
68 static int pt; /* comp's protected points */
69 static int em; /* farthest man back */
70 static int frc; /* chance to free comp's men */
71 static int frp; /* chance to free pl's men */
73 /* these values are the values for the move chosen (so far) */
74 static int chance; /* chance of being hit */
75 static int openmen; /* computer's open men */
76 static int points; /* comp's protected points */
77 static int endman; /* farthest man back */
78 static int barmen; /* men on bar */
79 static int menin; /* men in inner table */
80 static int menoff; /* men off board */
81 static int oldfrc; /* chance to free comp's men */
82 static int oldfrp; /* chance to free pl's men */
84 static int cp[5]; /* candidate start position */
85 static int cg[5]; /* candidate finish position */
87 static int race; /* game reduced to a race */
89 /* zero if first move */
98 /* see if comp should double */
99 if (gvalue < 64 && dlast != cturn && dblgood()) {
102 /* return if declined */
103 if (cturn != 1 && cturn != -1)
110 for (i = 0; i < 26; i++) {
114 for (i = 0; i < l; i++) {
123 curmove(cturn == -1 ? 18 : 19, 0);
129 /* make tty interruptable while thinking */
134 /* find out how many moves */
137 writel(" but cannot use it.\n");
144 for (i = 0; i < 4; i++)
152 writel(" and moves ");
153 for (i = 0; i < mvlim; i++) {
163 /* print blots hit */
168 for (i = 0; i < mvlim; i++)
171 /* get ready for next move */
177 fixtty(raw); /* no more tty interrupt */
181 * mvnum is number of move (rel zero)
182 * see if swapped also tested
185 trymove(int mvnum, int swapped)
187 int pos; /* position on board */
188 int rval; /* value of roll */
190 /* if recursed through all dice values, compare move */
191 if (mvnum == mvlim) {
196 /* make sure dice in always same order */
199 /* choose value for this move */
200 rval = dice[mvnum != 0];
202 /* find all legitimate moves */
203 for (pos = bar; pos != home; pos += cturn) {
204 /* fix order of dice */
207 /* break if stuck on bar */
208 if (board[bar] != 0 && pos != bar)
210 /* on to next if not occupied */
211 if (board[pos] * cturn <= 0)
213 /* set up arrays for move */
215 g[mvnum] = pos + rval * cturn;
216 if (g[mvnum] * cturn >= home) {
225 trymove(mvnum + 1, 2);
226 /* undo move to try another */
230 /* swap dice and try again */
231 if ((!swapped) && D0 != D1)
235 static struct BOARD *
239 struct BOARD *now; /* current position */
241 now = nextfree(); /* get free BOARD */
244 for (i = 0; i < 26; i++)
245 now->b_board[i] = board[i];
246 now->b_in[0] = in[0];
247 now->b_in[1] = in[1];
248 now->b_off[0] = off[0];
249 now->b_off[1] = off[1];
250 for (i = 0; i < mvlim; i++) {
258 binsert(struct BOARD *new)
260 int result; /* comparison result */
261 struct BOARD *qp; /* queue pointer */
264 if (qp == NULL) { /* check if queue empty */
269 result = bcomp(new, qp); /* compare to first element */
270 if (result < 0) { /* insert in front */
275 if (result == 0) { /* duplicate entry */
280 while (qp->b_next != NULL) { /* traverse queue */
281 result = bcomp(new, qp->b_next);
282 if (result < 0) { /* found place */
283 new->b_next = qp->b_next;
287 if (result == 0) { /* duplicate entry */
288 mvcheck(qp->b_next, new);
294 /* place at end of queue */
300 bcomp(struct BOARD *a, struct BOARD *b)
302 int *aloc = a->b_board; /* pointer to board a */
303 int *bloc = b->b_board; /* pointer to board b */
305 int result; /* comparison result */
307 for (i = 0; i < 26; i++) { /* compare boards */
308 result = cturn * (aloc[i] - bloc[i]);
310 return (result); /* found inequality */
312 return (0); /* same position */
316 mvcheck(struct BOARD *incumbent, struct BOARD *candidate)
321 for (i = 0; i < mvlim; i++) {
322 result = cturn * (candidate->b_st[i] - incumbent->b_st[i]);
330 for (i = 0; i < mvlim; i++) {
331 incumbent->b_st[i] = candidate->b_st[i];
332 incumbent->b_fn[i] = candidate->b_fn[i];
337 makefree(struct BOARD *dead)
339 dead->b_next = freeq; /* add to freeq */
343 static struct BOARD *
349 new = calloc(1, sizeof(struct BOARD));
351 writel("\nOut of memory\n");
357 freeq = freeq->b_next;
365 /* current game position */
366 struct BOARD *now = bsave();
367 struct BOARD *next; /* next move */
371 trace = fopen("bgtrace", "w");
372 fprintf(trace, "\nRoll: %d %d%s\n", D0, D1, race ? " (race)" : "");
375 do { /* compare moves */
377 next = checkq->b_next;
381 } while (checkq != NULL);
387 boardcopy(struct BOARD *s)
391 for (i = 0; i < 26; i++)
392 board[i] = s->b_board[i];
393 for (i = 0; i < 2; i++) {
395 off[i] = s->b_off[i];
397 for (i = 0; i < mvlim; i++) {
410 trace = fopen("bgtrace", "w");
416 for (i = 1; i < 25; i++) {
417 if (board[i] == cturn)
421 for (i = bar + cturn; i != home; i += cturn)
422 if (board[i] * cturn > 1)
424 frc = freemen(bar) + trapped(bar, cturn);
425 frp = freemen(home) + trapped(home, -cturn);
427 for (em = bar; em != home; em += cturn)
428 if (board[em] * cturn > 0)
432 fputs("Board: ", trace);
433 for (i = 0; i < 26; i++)
434 fprintf(trace, " %d", board[i]);
436 fprintf(trace, "\n\tem = %d\n", em);
439 "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
440 ch, pt, em, frc, frp);
441 fputs("\tMove: ", trace);
442 for (i = 0; i < mvlim; i++)
443 fprintf(trace, " %d-%d", p[i], g[i]);
448 if ((cp[0] == 0 && cg[0] == 0) || movegood()) {
450 fprintf(trace, "\t[%s] ... wins.\n", tests);
453 for (i = 0; i < mvlim; i++) {
462 barmen = abs(board[home]);
471 fprintf(trace, "\t[%s] ... loses.\n", tests);
490 if (*offptr - menoff)
491 return (*offptr > menoff);
496 return (endman > em);
508 return (*inptr > menin);
511 n = barmen - abs(board[home]);
515 if (abs(chance - ch) + 25 * n > rnum(150))
516 return (n ? (n < 0) : (ch < chance));
520 if (*offptr - menoff)
521 return (*offptr > menoff);
525 if (abs(openmen - op) > 7 + rnum(12))
526 return (openmen > op);
535 if (abs(endman - em) > rnum(2))
536 return (endman > em);
540 if (abs(frc - oldfrc) > rnum(2))
541 return (frc < oldfrc);
545 if (abs(n = pt - points) > rnum(4))
551 return (*inptr > menin);
555 if (abs(frp - oldfrp) > rnum(2))
556 return (frp > oldfrp);