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. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * @(#)move.c 8.1 (Berkeley) 5/31/93 30 * $FreeBSD: src/games/backgammon/backgammon/move.c,v 1.5 1999/11/30 03:48:23 billf Exp $ 31 */ 32 33 #include "back.h" 34 35 #ifdef DEBUG 36 #include <stdio.h> 37 FILE *trace; 38 static char tests[20]; 39 #endif 40 41 static void trymove(int, int); 42 static struct BOARD *bsave(void); 43 static void binsert(struct BOARD *); 44 static int bcomp(struct BOARD *, struct BOARD *); 45 static void mvcheck(struct BOARD *, struct BOARD *); 46 static void makefree(struct BOARD *); 47 static struct BOARD *nextfree(void); 48 static void pickmove(void); 49 static void boardcopy(struct BOARD *); 50 static void movcmp(void); 51 static int movegood(void); 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 = NULL; 63 struct BOARD *checkq = NULL; 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 /* zero if first move */ 90 void 91 move(int okay) 92 { 93 int i; /* index */ 94 int l; /* last man */ 95 96 l = 0; 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 while thinking */ 130 if (tflag) 131 cline(); 132 fixtty(noech); 133 134 /* find out how many moves */ 135 mvlim = movallow(); 136 if (mvlim == 0) { 137 writel(" but cannot use it.\n"); 138 nexturn(); 139 fixtty(raw); 140 return; 141 } 142 143 /* initialize */ 144 for (i = 0; i < 4; i++) 145 cp[i] = cg[i] = 0; 146 147 /* strategize */ 148 trymove(0, 0); 149 pickmove(); 150 151 /* print move */ 152 writel(" and moves "); 153 for (i = 0; i < mvlim; i++) { 154 if (i > 0) 155 writec(','); 156 wrint(p[i] = cp[i]); 157 writec('-'); 158 wrint(g[i] = cg[i]); 159 makmove(i); 160 } 161 writec('.'); 162 163 /* print blots hit */ 164 if (tflag) 165 curmove(20, 0); 166 else 167 writec('\n'); 168 for (i = 0; i < mvlim; i++) 169 if (h[i]) 170 wrhit(g[i]); 171 /* get ready for next move */ 172 nexturn(); 173 if (!okay) { 174 buflush(); 175 sleep(3); 176 } 177 fixtty(raw); /* no more tty interrupt */ 178 } 179 180 /* 181 * mvnum is number of move (rel zero) 182 * see if swapped also tested 183 */ 184 static void 185 trymove(int mvnum, int swapped) 186 { 187 int pos; /* position on board */ 188 int rval; /* value of roll */ 189 190 /* if recursed through all dice values, compare move */ 191 if (mvnum == mvlim) { 192 binsert(bsave()); 193 return; 194 } 195 196 /* make sure dice in always same order */ 197 if (d0 == swapped) 198 swap; 199 /* choose value for this move */ 200 rval = dice[mvnum != 0]; 201 202 /* find all legitimate moves */ 203 for (pos = bar; pos != home; pos += cturn) { 204 /* fix order of dice */ 205 if (d0 == swapped) 206 swap; 207 /* break if stuck on bar */ 208 if (board[bar] != 0 && pos != bar) 209 break; 210 /* on to next if not occupied */ 211 if (board[pos] * cturn <= 0) 212 continue; 213 /* set up arrays for move */ 214 p[mvnum] = pos; 215 g[mvnum] = pos + rval * cturn; 216 if (g[mvnum] * cturn >= home) { 217 if (*offptr < 0) 218 break; 219 g[mvnum] = home; 220 } 221 /* try to move */ 222 if (makmove(mvnum)) 223 continue; 224 else 225 trymove(mvnum + 1, 2); 226 /* undo move to try another */ 227 backone(mvnum); 228 } 229 230 /* swap dice and try again */ 231 if ((!swapped) && D0 != D1) 232 trymove(0, 1); 233 } 234 235 static struct BOARD * 236 bsave(void) 237 { 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 257 static void 258 binsert(struct BOARD *new) 259 { 260 int result; /* comparison result */ 261 struct BOARD *qp; /* queue pointer */ 262 263 qp = checkq; 264 if (qp == NULL) { /* check if queue empty */ 265 checkq = qp = new; 266 qp->b_next = NULL; 267 return; 268 } 269 result = bcomp(new, qp); /* compare to first element */ 270 if (result < 0) { /* insert in front */ 271 new->b_next = qp; 272 checkq = new; 273 return; 274 } 275 if (result == 0) { /* duplicate entry */ 276 mvcheck(qp, new); 277 makefree(new); 278 return; 279 } 280 while (qp->b_next != NULL) { /* traverse queue */ 281 result = bcomp(new, qp->b_next); 282 if (result < 0) { /* found place */ 283 new->b_next = qp->b_next; 284 qp->b_next = new; 285 return; 286 } 287 if (result == 0) { /* duplicate entry */ 288 mvcheck(qp->b_next, new); 289 makefree(new); 290 return; 291 } 292 qp = qp->b_next; 293 } 294 /* place at end of queue */ 295 qp->b_next = new; 296 new->b_next = NULL; 297 } 298 299 static int 300 bcomp(struct BOARD *a, struct BOARD *b) 301 { 302 int *aloc = a->b_board; /* pointer to board a */ 303 int *bloc = b->b_board; /* pointer to board b */ 304 int i; /* index */ 305 int result; /* comparison result */ 306 307 for (i = 0; i < 26; i++) { /* compare boards */ 308 result = cturn * (aloc[i] - bloc[i]); 309 if (result) 310 return (result); /* found inequality */ 311 } 312 return (0); /* same position */ 313 } 314 315 static void 316 mvcheck(struct BOARD *incumbent, struct BOARD *candidate) 317 { 318 int i; 319 int result; 320 321 for (i = 0; i < mvlim; i++) { 322 result = cturn * (candidate->b_st[i] - incumbent->b_st[i]); 323 if (result > 0) 324 return; 325 if (result < 0) 326 break; 327 } 328 if (i == mvlim) 329 return; 330 for (i = 0; i < mvlim; i++) { 331 incumbent->b_st[i] = candidate->b_st[i]; 332 incumbent->b_fn[i] = candidate->b_fn[i]; 333 } 334 } 335 336 static void 337 makefree(struct BOARD *dead) 338 { 339 dead->b_next = freeq; /* add to freeq */ 340 freeq = dead; 341 } 342 343 static struct BOARD * 344 nextfree(void) 345 { 346 struct BOARD *new; 347 348 if (freeq == NULL) { 349 new = calloc(1, sizeof(struct BOARD)); 350 if (new == NULL) { 351 writel("\nOut of memory\n"); 352 getout(0); 353 } 354 new->b_next = NULL; 355 } else { 356 new = freeq; 357 freeq = freeq->b_next; 358 } 359 return (new); 360 } 361 362 static void 363 pickmove(void) 364 { 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 != NULL); 382 383 boardcopy(now); 384 } 385 386 static void 387 boardcopy(struct BOARD *s) 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 403 static void 404 movcmp(void) 405 { 406 int i; 407 408 #ifdef DEBUG 409 if (trace == NULL) 410 trace = fopen("bgtrace", "w"); 411 #endif 412 413 odds(0, 0, 0); 414 if (!race) { 415 ch = op = pt = 0; 416 for (i = 1; i < 25; i++) { 417 if (board[i] == cturn) 418 ch = canhit(i, 1); 419 op += abs(bar - i); 420 } 421 for (i = bar + cturn; i != home; i += cturn) 422 if (board[i] * cturn > 1) 423 pt += abs(bar - i); 424 frc = freemen(bar) + trapped(bar, cturn); 425 frp = freemen(home) + trapped(home, -cturn); 426 } 427 for (em = bar; em != home; em += cturn) 428 if (board[em] * cturn > 0) 429 break; 430 em = abs(home - em); 431 #ifdef DEBUG 432 fputs("Board: ", trace); 433 for (i = 0; i < 26; i++) 434 fprintf(trace, " %d", board[i]); 435 if (race) 436 fprintf(trace, "\n\tem = %d\n", em); 437 else 438 fprintf(trace, 439 "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n", 440 ch, pt, em, frc, frp); 441 fputs("\tMove: ", trace); 442 for (i = 0; i < mvlim; i++) 443 fprintf(trace, " %d-%d", p[i], g[i]); 444 fputs("\n", trace); 445 fflush(trace); 446 strcpy(tests, ""); 447 #endif 448 if ((cp[0] == 0 && cg[0] == 0) || movegood()) { 449 #ifdef DEBUG 450 fprintf(trace, "\t[%s] ... wins.\n", tests); 451 fflush(trace); 452 #endif 453 for (i = 0; i < mvlim; i++) { 454 cp[i] = p[i]; 455 cg[i] = g[i]; 456 } 457 if (!race) { 458 chance = ch; 459 openmen = op; 460 points = pt; 461 endman = em; 462 barmen = abs(board[home]); 463 oldfrc = frc; 464 oldfrp = frp; 465 } 466 menin = *inptr; 467 menoff = *offptr; 468 } 469 #ifdef DEBUG 470 else { 471 fprintf(trace, "\t[%s] ... loses.\n", tests); 472 fflush(trace); 473 } 474 #endif 475 } 476 477 static int 478 movegood(void) 479 { 480 int n; 481 482 if (*offptr == 15) 483 return (1); 484 if (menoff == 15) 485 return (0); 486 if (race) { 487 #ifdef DEBUG 488 strcat(tests, "o"); 489 #endif 490 if (*offptr - menoff) 491 return (*offptr > menoff); 492 #ifdef DEBUG 493 strcat(tests, "e"); 494 #endif 495 if (endman - em) 496 return (endman > em); 497 #ifdef DEBUG 498 strcat(tests, "i"); 499 #endif 500 if (menin == 15) 501 return (0); 502 if (*inptr == 15) 503 return (1); 504 #ifdef DEBUG 505 strcat(tests, "i"); 506 #endif 507 if (*inptr - menin) 508 return (*inptr > menin); 509 return (rnum(2)); 510 } else { 511 n = barmen - abs(board[home]); 512 #ifdef DEBUG 513 strcat(tests, "c"); 514 #endif 515 if (abs(chance - ch) + 25 * n > rnum(150)) 516 return (n ? (n < 0) : (ch < chance)); 517 #ifdef DEBUG 518 strcat(tests, "o"); 519 #endif 520 if (*offptr - menoff) 521 return (*offptr > menoff); 522 #ifdef DEBUG 523 strcat(tests, "o"); 524 #endif 525 if (abs(openmen - op) > 7 + rnum(12)) 526 return (openmen > op); 527 #ifdef DEBUG 528 strcat(tests, "b"); 529 #endif 530 if (n) 531 return (n < 0); 532 #ifdef DEBUG 533 strcat(tests, "e"); 534 #endif 535 if (abs(endman - em) > rnum(2)) 536 return (endman > em); 537 #ifdef DEBUG 538 strcat(tests, "f"); 539 #endif 540 if (abs(frc - oldfrc) > rnum(2)) 541 return (frc < oldfrc); 542 #ifdef DEBUG 543 strcat(tests, "p"); 544 #endif 545 if (abs(n = pt - points) > rnum(4)) 546 return (n > 0); 547 #ifdef DEBUG 548 strcat(tests, "i"); 549 #endif 550 if (*inptr - menin) 551 return (*inptr > menin); 552 #ifdef DEBUG 553 strcat(tests, "f"); 554 #endif 555 if (abs(frp - oldfrp) > rnum(2)) 556 return (frp > oldfrp); 557 return (rnum(2)); 558 } 559 } 560