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