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