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 $
31 * $DragonFly: src/games/backgammon/backgammon/move.c,v 1.3 2006/08/08 16:36:11 pavalos Exp $
39 static char tests
[20];
42 static void trymove(int, int);
43 static struct BOARD
*bsave(void);
44 static void binsert(struct BOARD
*);
45 static int bcomp(struct BOARD
*, struct BOARD
*);
46 static void mvcheck(struct BOARD
*, struct BOARD
*);
47 static void makefree(struct BOARD
*);
48 static struct BOARD
*nextfree(void);
49 static void pickmove(void);
50 static void boardcopy(struct BOARD
*);
51 static void movcmp(void);
52 static int movegood(void);
54 struct BOARD
{ /* structure of game position */
55 int b_board
[26]; /* board position */
56 int b_in
[2]; /* men in */
57 int b_off
[2]; /* men off */
58 int b_st
[4], b_fn
[4]; /* moves */
60 struct BOARD
*b_next
; /* forward queue pointer */
63 struct BOARD
*freeq
= 0;
64 struct BOARD
*checkq
= 0;
66 /* these variables are values for the candidate move */
67 static int ch
; /* chance of being hit */
68 static int op
; /* computer's open men */
69 static int pt
; /* comp's protected points */
70 static int em
; /* farthest man back */
71 static int frc
; /* chance to free comp's men */
72 static int frp
; /* chance to free pl's men */
74 /* these values are the values for the move chosen (so far) */
75 static int chance
; /* chance of being hit */
76 static int openmen
; /* computer's open men */
77 static int points
; /* comp's protected points */
78 static int endman
; /* farthest man back */
79 static int barmen
; /* men on bar */
80 static int menin
; /* men in inner table */
81 static int menoff
; /* men off board */
82 static int oldfrc
; /* chance to free comp's men */
83 static int oldfrp
; /* chance to free pl's men */
85 static int cp
[5]; /* candidate start position */
86 static int cg
[5]; /* candidate finish position */
88 static int race
; /* game reduced to a race */
90 /* zero if first move */
99 /* see if comp should double */
100 if (gvalue
< 64 && dlast
!= cturn
&& dblgood()) {
103 /* return if declined */
104 if (cturn
!= 1 && cturn
!= -1)
111 for (i
= 0; i
< 26; i
++) {
115 for (i
= 0; i
< l
; i
++) {
124 curmove(cturn
== -1 ? 18 : 19, 0);
130 /* make tty interruptable while thinking */
135 /* find out how many moves */
138 writel(" but cannot use it.\n");
145 for (i
= 0; i
< 4; i
++)
153 writel(" and moves ");
154 for (i
= 0; i
< mvlim
; i
++) {
164 /* print blots hit */
169 for (i
= 0; i
< mvlim
; i
++)
172 /* get ready for next move */
178 fixtty(raw
); /* no more tty interrupt */
182 * mvnum is number of move (rel zero)
183 * see if swapped also tested
186 trymove(int mvnum
, int swapped
)
188 int pos
; /* position on board */
189 int rval
; /* value of roll */
191 /* if recursed through all dice values, compare move */
192 if (mvnum
== mvlim
) {
197 /* make sure dice in always same order */
200 /* choose value for this move */
201 rval
= dice
[mvnum
!= 0];
203 /* find all legitimate moves */
204 for (pos
= bar
; pos
!= home
; pos
+= cturn
) {
205 /* fix order of dice */
208 /* break if stuck on bar */
209 if (board
[bar
] != 0 && pos
!= bar
)
211 /* on to next if not occupied */
212 if (board
[pos
] * cturn
<= 0)
214 /* set up arrays for move */
216 g
[mvnum
] = pos
+ rval
* cturn
;
217 if (g
[mvnum
] * cturn
>= home
) {
226 trymove(mvnum
+ 1, 2);
227 /* undo move to try another */
231 /* swap dice and try again */
232 if ((!swapped
) && D0
!= D1
)
236 static struct BOARD
*
240 struct BOARD
*now
; /* current position */
242 now
= nextfree(); /* get free BOARD */
245 for (i
= 0; i
< 26; i
++)
246 now
->b_board
[i
] = board
[i
];
247 now
->b_in
[0] = in
[0];
248 now
->b_in
[1] = in
[1];
249 now
->b_off
[0] = off
[0];
250 now
->b_off
[1] = off
[1];
251 for (i
= 0; i
< mvlim
; i
++) {
259 binsert(struct BOARD
*new)
261 int result
; /* comparison result */
262 struct BOARD
*qp
; /* queue pointer */
265 if (qp
== 0) { /* check if queue empty */
270 result
= bcomp(new, qp
); /* compare to first element */
271 if (result
< 0) { /* insert in front */
276 if (result
== 0) { /* duplicate entry */
281 while (qp
->b_next
!= 0) { /* traverse queue */
282 result
= bcomp(new, qp
->b_next
);
283 if (result
< 0) { /* found place */
284 new->b_next
= qp
->b_next
;
288 if (result
== 0) { /* duplicate entry */
289 mvcheck(qp
->b_next
, new);
295 /* place at end of queue */
301 bcomp(struct BOARD
*a
, struct BOARD
*b
)
303 int *aloc
= a
->b_board
; /* pointer to board a */
304 int *bloc
= b
->b_board
; /* pointer to board b */
306 int result
; /* comparison result */
308 for (i
= 0; i
< 26; i
++) { /* compare boards */
309 result
= cturn
* (aloc
[i
] - bloc
[i
]);
311 return (result
); /* found inequality */
313 return (0); /* same position */
317 mvcheck(struct BOARD
*incumbent
, struct BOARD
*candidate
)
322 for (i
= 0; i
< mvlim
; i
++) {
323 result
= cturn
* (candidate
->b_st
[i
] - incumbent
->b_st
[i
]);
331 for (i
= 0; i
< mvlim
; i
++) {
332 incumbent
->b_st
[i
] = candidate
->b_st
[i
];
333 incumbent
->b_fn
[i
] = candidate
->b_fn
[i
];
338 makefree(struct BOARD
*dead
)
340 dead
->b_next
= freeq
; /* add to freeq */
344 static struct BOARD
*
350 new = calloc(1, sizeof(struct BOARD
));
352 writel("\nOut of memory\n");
358 freeq
= freeq
->b_next
;
366 /* current game position */
367 struct BOARD
*now
= bsave();
368 struct BOARD
*next
; /* next move */
372 trace
= fopen("bgtrace", "w");
373 fprintf(trace
, "\nRoll: %d %d%s\n", D0
, D1
, race
? " (race)" : "");
376 do { /* compare moves */
378 next
= checkq
->b_next
;
382 } while (checkq
!= 0);
388 boardcopy(struct BOARD
*s
)
392 for (i
= 0; i
< 26; i
++)
393 board
[i
] = s
->b_board
[i
];
394 for (i
= 0; i
< 2; i
++) {
396 off
[i
] = s
->b_off
[i
];
398 for (i
= 0; i
< mvlim
; i
++) {
411 trace
= fopen("bgtrace", "w");
417 for (i
= 1; i
< 25; i
++) {
418 if (board
[i
] == cturn
)
422 for (i
= bar
+ cturn
; i
!= home
; i
+= cturn
)
423 if (board
[i
] * cturn
> 1)
425 frc
= freemen(bar
) + trapped(bar
, cturn
);
426 frp
= freemen(home
) + trapped(home
, -cturn
);
428 for (em
= bar
; em
!= home
; em
+= cturn
)
429 if (board
[em
] * cturn
> 0)
433 fputs("Board: ", trace
);
434 for (i
= 0; i
< 26; i
++)
435 fprintf(trace
, " %d", board
[i
]);
437 fprintf(trace
, "\n\tem = %d\n", em
);
440 "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
441 ch
, pt
, em
, frc
, frp
);
442 fputs("\tMove: ", trace
);
443 for (i
= 0; i
< mvlim
; i
++)
444 fprintf(trace
, " %d-%d", p
[i
], g
[i
]);
449 if ((cp
[0] == 0 && cg
[0] == 0) || movegood()) {
451 fprintf(trace
, "\t[%s] ... wins.\n", tests
);
454 for (i
= 0; i
< mvlim
; i
++) {
463 barmen
= abs(board
[home
]);
472 fprintf(trace
, "\t[%s] ... loses.\n", tests
);
491 if (*offptr
- menoff
)
492 return (*offptr
> menoff
);
497 return (endman
> em
);
509 return (*inptr
> menin
);
512 n
= barmen
- abs(board
[home
]);
516 if (abs(chance
- ch
) + 25 * n
> rnum(150))
517 return (n
? (n
< 0) : (ch
< chance
));
521 if (*offptr
- menoff
)
522 return (*offptr
> menoff
);
526 if (abs(openmen
- op
) > 7 + rnum(12))
527 return (openmen
> op
);
536 if (abs(endman
- em
) > rnum(2))
537 return (endman
> em
);
541 if (abs(frc
- oldfrc
) > rnum(2))
542 return (frc
< oldfrc
);
546 if (abs(n
= pt
- points
) > rnum(4))
552 return (*inptr
> menin
);
556 if (abs(frp
- oldfrp
) > rnum(2))
557 return (frp
> oldfrp
);