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