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
);