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. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * @(#)move.c 8.1 (Berkeley) 5/31/93
34 * $FreeBSD: src/games/backgammon/backgammon/move.c,v 1.5 1999/11/30 03:48:23 billf Exp $
35 * $DragonFly: src/games/backgammon/backgammon/move.c,v 1.3 2006/08/08 16:36:11 pavalos Exp $
43 static char tests[20];
46 static void trymove(int, int);
47 static struct BOARD *bsave(void);
48 static void binsert(struct BOARD *);
49 static int bcomp(struct BOARD *, struct BOARD *);
50 static void mvcheck(struct BOARD *, struct BOARD *);
51 static void makefree(struct BOARD *);
52 static struct BOARD *nextfree(void);
53 static void pickmove(void);
54 static void boardcopy(struct BOARD *);
55 static void movcmp(void);
56 static int movegood(void);
58 struct BOARD { /* structure of game position */
59 int b_board[26]; /* board position */
60 int b_in[2]; /* men in */
61 int b_off[2]; /* men off */
62 int b_st[4], b_fn[4]; /* moves */
64 struct BOARD *b_next; /* forward queue pointer */
67 struct BOARD *freeq = 0;
68 struct BOARD *checkq = 0;
70 /* these variables are values for the
72 static int ch; /* chance of being hit */
73 static int op; /* computer's open men */
74 static int pt; /* comp's protected points */
75 static int em; /* farthest man back */
76 static int frc; /* chance to free comp's men */
77 static int frp; /* chance to free pl's men */
79 /* these values are the values for the
80 * move chosen (so far) */
81 static int chance; /* chance of being hit */
82 static int openmen; /* computer's open men */
83 static int points; /* comp's protected points */
84 static int endman; /* farthest man back */
85 static int barmen; /* men on bar */
86 static int menin; /* men in inner table */
87 static int menoff; /* men off board */
88 static int oldfrc; /* chance to free comp's men */
89 static int oldfrp; /* chance to free pl's men */
91 static int cp[5]; /* candidate start position */
92 static int cg[5]; /* candidate finish position */
94 static int race; /* game reduced to a race */
100 int l = 0; /* last man */
104 /* see if comp should double */
105 if (gvalue < 64 && dlast != cturn && dblgood()) {
108 /* return if declined */
109 if (cturn != 1 && cturn != -1)
116 for (i = 0; i < 26; i++) {
120 for (i = 0; i < l; i++) {
129 curmove (cturn == -1? 18: 19,0);
135 /* make tty interruptable
141 /* find out how many moves */
144 writel (" but cannot use it.\n");
151 for (i = 0; i < 4; i++)
159 writel (" and moves ");
160 for (i = 0; i < mvlim; i++) {
163 wrint (p[i] = cp[i]);
165 wrint (g[i] = cg[i]);
170 /* print blots hit */
175 for (i = 0; i < mvlim; i++)
178 /* get ready for next move */
184 fixtty (raw); /* no more tty interrupt */
188 * mvnum is number of move (rel zero)
189 * see if swapped also tested
192 trymove(int mvnum, int swapped)
194 int pos; /* position on board */
195 int rval; /* value of roll */
197 /* if recursed through all dice
198 * values, compare move */
199 if (mvnum == mvlim) {
204 /* make sure dice in always
208 /* choose value for this move */
209 rval = dice[mvnum != 0];
211 /* find all legitimate moves */
212 for (pos = bar; pos != home; pos += cturn) {
213 /* fix order of dice */
216 /* break if stuck on bar */
217 if (board[bar] != 0 && pos != bar)
219 /* on to next if not occupied */
220 if (board[pos]*cturn <= 0)
222 /* set up arrays for move */
224 g[mvnum] = pos+rval*cturn;
225 if (g[mvnum]*cturn >= home) {
235 /* undo move to try another */
239 /* swap dice and try again */
240 if ((!swapped) && D0 != D1)
244 static struct BOARD *
248 struct BOARD *now; /* current position */
250 now = nextfree (); /* get free BOARD */
253 for (i = 0; i < 26; i++)
254 now->b_board[i] = board[i];
255 now->b_in[0] = in[0];
256 now->b_in[1] = in[1];
257 now->b_off[0] = off[0];
258 now->b_off[1] = off[1];
259 for (i = 0; i < mvlim; i++) {
267 binsert(struct BOARD *new)
269 struct BOARD *qp = checkq; /* queue pointer */
270 int result; /* comparison result */
272 if (qp == 0) { /* check if queue empty */
278 result = bcomp (new,qp); /* compare to first element */
279 if (result < 0) { /* insert in front */
284 if (result == 0) { /* duplicate entry */
290 while (qp->b_next != 0) { /* traverse queue */
291 result = bcomp (new,qp->b_next);
292 if (result < 0) { /* found place */
293 new->b_next = qp->b_next;
297 if (result == 0) { /* duplicate entry */
298 mvcheck (qp->b_next,new);
304 /* place at end of queue */
310 bcomp(struct BOARD *a, struct BOARD *b)
312 int *aloc = a->b_board; /* pointer to board a */
313 int *bloc = b->b_board; /* pointer to board b */
315 int result; /* comparison result */
317 for (i = 0; i < 26; i++) { /* compare boards */
318 result = cturn*(aloc[i]-bloc[i]);
320 return (result); /* found inequality */
322 return (0); /* same position */
326 mvcheck(struct BOARD *incumbent, struct BOARD *candidate)
331 for (i = 0; i < mvlim; i++) {
332 result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
340 for (i = 0; i < mvlim; i++) {
341 incumbent->b_st[i] = candidate->b_st[i];
342 incumbent->b_fn[i] = candidate->b_fn[i];
347 makefree(struct BOARD *dead)
349 dead->b_next = freeq; /* add to freeq */
353 static struct BOARD *
359 new = (struct BOARD *)calloc (1,sizeof (struct BOARD));
361 writel ("\nOut of memory\n");
367 freeq = freeq->b_next;
375 /* current game position */
376 struct BOARD *now = bsave();
377 struct BOARD *next; /* next move */
381 trace = fopen ("bgtrace","w");
382 fprintf (trace,"\nRoll: %d %d%s\n",D0,D1,race? " (race)": "");
385 do { /* compare moves */
387 next = checkq->b_next;
391 } while (checkq != 0);
397 boardcopy(struct BOARD *s)
401 for (i = 0; i < 26; i++)
402 board[i] = s->b_board[i];
403 for (i = 0; i < 2; i++) {
405 off[i] = s->b_off[i];
407 for (i = 0; i < mvlim; i++) {
420 trace = fopen ("bgtrace","w");
426 for (i = 1; i < 25; i++) {
427 if (board[i] == cturn)
431 for (i = bar+cturn; i != home; i += cturn)
432 if (board[i]*cturn > 1)
434 frc = freemen (bar)+trapped (bar,cturn);
435 frp = freemen (home)+trapped (home,-cturn);
437 for (em = bar; em != home; em += cturn)
438 if (board[em]*cturn > 0)
442 fputs ("Board: ",trace);
443 for (i = 0; i < 26; i++)
444 fprintf (trace, " %d",board[i]);
446 fprintf (trace,"\n\tem = %d\n",em);
449 "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
451 fputs ("\tMove: ",trace);
452 for (i = 0; i < mvlim; i++)
453 fprintf (trace," %d-%d",p[i],g[i]);
458 if ((cp[0] == 0 && cg[0] == 0) || movegood()) {
460 fprintf (trace,"\t[%s] ... wins.\n",tests);
463 for (i = 0; i < mvlim; i++) {
472 barmen = abs(board[home]);
481 fprintf (trace,"\t[%s] ... loses.\n",tests);
501 return (*offptr > menoff);
506 return (endman > em);
518 return (*inptr > menin);
521 n = barmen-abs(board[home]);
525 if (abs(chance-ch)+25*n > rnum(150))
526 return (n? (n < 0): (ch < chance));
531 return (*offptr > menoff);
535 if (abs(openmen-op) > 7+rnum(12))
536 return (openmen > op);
545 if (abs(endman-em) > rnum(2))
546 return (endman > em);
550 if (abs(frc-oldfrc) > rnum(2))
551 return (frc < oldfrc);
555 if (abs(n = pt-points) > rnum(4))
561 return (*inptr > menin);
565 if (abs(frp-oldfrp) > rnum(2))
566 return (frp > oldfrp);