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