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