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