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