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