1 /* $OpenBSD: move.c,v 1.13 2015/11/30 08:19:25 tb Exp $ */
2
3 /*
4 * Copyright (c) 1980, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32 #include "back.h"
33 #include "backlocal.h"
34
35 struct BOARD { /* structure of game position */
36 int b_board[26]; /* board position */
37 int b_in[2]; /* men in */
38 int b_off[2]; /* men off */
39 int b_st[4], b_fn[4]; /* moves */
40
41 struct BOARD *b_next; /* forward queue pointer */
42 };
43
44 struct BOARD *freeq = 0;
45 struct BOARD *checkq = 0;
46
47 static int cp[5]; /* candidate start position */
48 static int cg[5]; /* candidate finish position */
49
50 static int race; /* game reduced to a race */
51 static float bestmove;
52
53 static int bcomp(struct BOARD *, struct BOARD *);
54 static struct BOARD *bsave(void);
55 static void binsert(struct BOARD *);
56 static void boardcopy(struct BOARD *);
57 static void makefree(struct BOARD *);
58 static void movcmp(void);
59 static void mvcheck(struct BOARD *, struct BOARD *);
60 static struct BOARD *nextfree(void);
61 static void pickmove(void);
62
63
64 void
domove(int okay)65 domove(int okay)
66 {
67 int i; /* index */
68 int l = 0; /* last man */
69
70 bestmove = -9999999.;
71 if (okay) {
72 /* see if comp should double */
73 if (dflag && gvalue < 64 && dlast != cturn && dblgood()) {
74 addstr(*Colorptr);
75 dble(); /* double */
76 /* return if declined */
77 if (cturn != 1 && cturn != -1)
78 return;
79 }
80 roll();
81 }
82 race = 0;
83 for (i = 0; i < 26; i++) {
84 if (board[i] < 0)
85 l = i;
86 }
87 for (i = 0; i < l; i++) {
88 if (board[i] > 0)
89 break;
90 }
91 if (i == l)
92 race = 1;
93
94 /* print roll */
95 move(cturn == -1 ? 18 : 19, 0);
96 printw("%s rolls %d %d", *Colorptr, D0, D1);
97 clrtoeol();
98
99 /* find out how many moves */
100 mvlim = movallow();
101 if (mvlim == 0) {
102 addstr(" but cannot use it.\n");
103 nexturn();
104 return;
105 }
106
107 /* initialize */
108 for (i = 0; i < 4; i++)
109 cp[i] = cg[i] = 0;
110
111 /* strategize */
112 trymove(0, 0);
113 pickmove();
114
115 /* print move */
116 addstr(" and moves ");
117 for (i = 0; i < mvlim; i++) {
118 if (i > 0)
119 addch(',');
120 printw("%d-%d", p[i] = cp[i], g[i] = cg[i]);
121 makmove(i);
122 }
123 addch('.');
124
125 /* print blots hit */
126 move(20, 0);
127 for (i = 0; i < mvlim; i++)
128 if (h[i])
129 wrhit(g[i]);
130 /* get ready for next move */
131 nexturn();
132 if (!okay) {
133 refresh();
134 sleep(3);
135 }
136 }
137
138 void
trymove(int mvnum,int swapped)139 trymove(int mvnum, int swapped)
140 {
141 int pos; /* position on board */
142 int rval; /* value of roll */
143
144 /* if recursed through all dice values, compare move */
145 if (mvnum == mvlim) {
146 binsert(bsave());
147 return;
148 }
149 /* make sure dice in always same order */
150 if (d0 == swapped)
151 swap;
152 /* choose value for this move */
153 rval = dice[mvnum != 0];
154
155 /* find all legitimate moves */
156 for (pos = bar; pos != home; pos += cturn) {
157 /* fix order of dice */
158 if (d0 == swapped)
159 swap;
160 /* break if stuck on bar */
161 if (board[bar] != 0 && pos != bar)
162 break;
163 /* on to next if not occupied */
164 if (board[pos] * cturn <= 0)
165 continue;
166 /* set up arrays for move */
167 p[mvnum] = pos;
168 g[mvnum] = pos + rval * cturn;
169 if (g[mvnum] * cturn >= home) {
170 if (*offptr < 0)
171 break;
172 g[mvnum] = home;
173 }
174 /* try to move */
175 if (makmove(mvnum))
176 continue;
177 else
178 trymove(mvnum + 1, 2);
179 /* undo move to try another */
180 backone(mvnum);
181 }
182
183 /* swap dice and try again */
184 if ((!swapped) && D0 != D1)
185 trymove(0, 1);
186 }
187
188 static struct BOARD *
bsave(void)189 bsave(void)
190 {
191 int i; /* index */
192 struct BOARD *now; /* current position */
193
194 now = nextfree(); /* get free BOARD */
195
196 /* store position */
197 for (i = 0; i < 26; i++)
198 now->b_board[i] = board[i];
199 now->b_in[0] = in[0];
200 now->b_in[1] = in[1];
201 now->b_off[0] = off[0];
202 now->b_off[1] = off[1];
203 for (i = 0; i < mvlim; i++) {
204 now->b_st[i] = p[i];
205 now->b_fn[i] = g[i];
206 }
207 return(now);
208 }
209
210 static void
binsert(struct BOARD * new)211 binsert(struct BOARD *new)
212 {
213 struct BOARD *p = checkq; /* queue pointer */
214 int result; /* comparison result */
215
216 if (p == 0) { /* check if queue empty */
217 checkq = p = new;
218 p->b_next = 0;
219 return;
220 }
221 result = bcomp(new, p); /* compare to first element */
222 if (result < 0) { /* insert in front */
223 new->b_next = p;
224 checkq = new;
225 return;
226 }
227 if (result == 0) { /* duplicate entry */
228 mvcheck(p, new);
229 makefree(new);
230 return;
231 }
232 while (p->b_next != 0) {/* traverse queue */
233 result = bcomp(new, p->b_next);
234 if (result < 0) { /* found place */
235 new->b_next = p->b_next;
236 p->b_next = new;
237 return;
238 }
239 if (result == 0) { /* duplicate entry */
240 mvcheck(p->b_next, new);
241 makefree(new);
242 return;
243 }
244 p = p->b_next;
245 }
246 /* place at end of queue */
247 p->b_next = new;
248 new->b_next = 0;
249 }
250
251 static int
bcomp(struct BOARD * a,struct BOARD * b)252 bcomp(struct BOARD *a, struct BOARD *b)
253 {
254 int *aloc = a->b_board; /* pointer to board a */
255 int *bloc = b->b_board; /* pointer to board b */
256 int i; /* index */
257 int result; /* comparison result */
258
259 for (i = 0; i < 26; i++) { /* compare boards */
260 result = cturn * (aloc[i] - bloc[i]);
261 if (result)
262 return(result); /* found inequality */
263 }
264 return(0); /* same position */
265 }
266
267 static void
mvcheck(struct BOARD * incumbent,struct BOARD * candidate)268 mvcheck(struct BOARD *incumbent, struct BOARD *candidate)
269 {
270 int i, result;
271
272 for (i = 0; i < mvlim; i++) {
273 result = cturn * (candidate->b_st[i] - incumbent->b_st[i]);
274 if (result > 0)
275 return;
276 if (result < 0)
277 break;
278 }
279 if (i == mvlim)
280 return;
281 for (i = 0; i < mvlim; i++) {
282 incumbent->b_st[i] = candidate->b_st[i];
283 incumbent->b_fn[i] = candidate->b_fn[i];
284 }
285 }
286
287 static void
makefree(struct BOARD * dead)288 makefree(struct BOARD *dead)
289 {
290 dead->b_next = freeq; /* add to freeq */
291 freeq = dead;
292 }
293
294 static struct BOARD *
nextfree(void)295 nextfree(void)
296 {
297 struct BOARD *new;
298
299 if (freeq == 0) {
300 new = calloc (1, sizeof(struct BOARD));
301 if (new == 0) {
302 addstr("\nOut of memory\n");
303 getout(0);
304 }
305 } else {
306 new = freeq;
307 freeq = freeq->b_next;
308 }
309
310 new->b_next = 0;
311 return(new);
312 }
313
314 static void
pickmove(void)315 pickmove(void)
316 {
317 /* current game position */
318 struct BOARD *now = bsave();
319 struct BOARD *next; /* next move */
320
321 #ifdef DEBUG
322 if (ftrace == NULL)
323 ftrace = fopen("bgtrace", "w");
324 fprintf(ftrace, "\nRoll: %d %d%s\n", D0, D1, race ? " (race)" : "");
325 fflush(ftrace);
326 #endif
327 do { /* compare moves */
328 boardcopy(checkq);
329 next = checkq->b_next;
330 makefree(checkq);
331 checkq = next;
332 movcmp();
333 } while (checkq != 0);
334
335 boardcopy(now);
336 }
337
338 static void
boardcopy(struct BOARD * s)339 boardcopy(struct BOARD *s)
340 {
341 int i; /* index */
342
343 for (i = 0; i < 26; i++)
344 board[i] = s->b_board[i];
345 for (i = 0; i < 2; i++) {
346 in[i] = s->b_in[i];
347 off[i] = s->b_off[i];
348 }
349 for (i = 0; i < mvlim; i++) {
350 p[i] = s->b_st[i];
351 g[i] = s->b_fn[i];
352 }
353 }
354
355 static void
movcmp(void)356 movcmp(void)
357 {
358 int i;
359 float f;
360
361 setx();
362 f = pubeval(race);
363 if (f > bestmove) {
364 bestmove = f;
365 for (i = 0; i < mvlim; i++) {
366 cp[i] = p[i];
367 cg[i] = g[i];
368 }
369 }
370 }
371