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